Excalibur Key-Generation Protocols For DAG Hierarchic Decryption

Louis Goubin, Geraldine Monsalve, Juan L. Reutter, Francisco José Vial Prado

TL;DR

This paper introduces novel cryptographic protocols that enable secure, hierarchical management of decryption rights within a multi-party setting. By leveraging advanced homomorphic encryption techniques, these protocols allow for the creation of "Excalibur" keys that inherit decryption capabilities from multiple sources without compromising the underlying secret keys, addressing a critical need in secure data sharing and access control.

What Problem Does This Paper Address?

In many real-world applications, such as secure email systems or access control for sensitive data, it's crucial to manage decryption rights in a structured, hierarchical manner. For example, a manager might need to decrypt all emails sent to their subordinates, but not vice-versa. A naive approach of simply sharing secret keys is highly insecure, as it can lead to leaks or unauthorized distribution of these keys. Existing solutions like proxy re-encryption or hierarchical identity-based encryption often rely on trusted third parties or complex procedures. This paper tackles the challenge of securely generating decryption keys that reflect a hierarchy (specifically, a Directed Acyclic Graph or DAG structure) without any trusted intermediaries and without leaking any secret information, even from powerful participants.

Methods

The core of this work lies in extending existing two-party "Excalibur" key generation protocols, which are based on the Multikey Fully Homomorphic Encryption (FHE) NTRU scheme. The authors propose new multi-party computation (MPC) protocols that can securely generate these Excalibur keys for a group of k parties, where k can be greater than two. These protocols are designed to work with any DAG-like hierarchy.

Key techniques include:

  • Multikey FHE-NTRU: This forms the cryptographic foundation, allowing for operations on encrypted data from multiple users.
  • Multi-Party Computation (MPC): The protocols are built using MPC techniques to ensure that no single party learns more than they are supposed to. This involves secure protocols for multiplication and other operations within the ring $R_q = Z_q[X]/(X^n+1)$.
  • Simulation-based Security Proofs: The security of the protocols is rigorously proven using the simulation paradigm, which demonstrates that an adversary cannot gain any advantage over a simulated environment. This is done for the semi-honest adversarial model, where parties follow the protocol but may collude to learn secrets.
  • Special Factors and Special GCD Problems: The security of the protocols relies on the hardness of these newly defined problems, which are related to factoring polynomials in the ring $R_q$.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Extending Excalibur to k-Parties: The most significant contribution is generalizing the two-party Excalibur key generation to an arbitrary number of parties (k), enabling more complex hierarchical structures.
  • DAG Hierarchies: The protocols are designed to support any DAG-like hierarchy, offering flexibility beyond simple linear chains.
  • No Trusted Third Parties: The entire process is decentralized, eliminating the need for a trusted authority to manage keys or decryption rights.
  • Information Leakage Prevention: The protocols are designed to prevent leakage of secret keys, even from participants who hold powerful decryption rights. This is achieved by carefully masking intermediate values and relying on the hardness of specific cryptographic problems.
  • Formal Security Guarantees: The paper provides formal, simulation-based security proofs in the semi-honest adversarial model, offering strong assurances about the protocols' security.

Key Results

The paper presents new MPC protocols for generating Excalibur keys for k parties. The security of these protocols is proven against semi-honest adversaries. The authors analyze the computational complexity, showing that for k parties and security parameter $\lambda$, the cost is approximately $O((2m)^{k-1})$ products in $R_q$ and $O((2m)^{k-1})$ oblivious transfer protocols. For practical parameters (e.g., 4 parties, 128 bits of security), this translates to around $2^{24}$ OT protocols and $2^{24}$ multiplications, which is shown to be feasible within minutes on a regular laptop.

Limitations and Future Work

  • Semi-Honest Adversary Model: The current security proofs are for the semi-honest model. The authors acknowledge that achieving security in the malicious adversarial setting (where parties can deviate from the protocol) is a challenging problem for $k > 2$ parties and is left for future work.
  • Efficiency for Large k: While the protocols are feasible for a small number of parties, the complexity grows exponentially with k. Future work could focus on improving efficiency for larger groups.
  • Hardness Assumptions: The security relies on the conjectured hardness of the Special Factors and Special GCD problems. Further cryptanalysis of these problems would strengthen the confidence in the protocols.
  • Practical Applications: While the protocols are theoretically sound, their efficiency for very large hierarchies might limit immediate practical deployment. Further optimizations are suggested.

Summary updated

BibTeX
@article{goubin2018excalibur,
  author = {Louis Goubin and Geraldine Monsalve and Juan L. Reutter and Francisco José Vial Prado},
  title = {{Excalibur Key-Generation Protocols For DAG Hierarchic Decryption}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
}
Figure