TL;DR
This paper introduces ParaDiSE, a novel threshold authenticated encryption (TAE) scheme designed for the fully malicious model. ParaDiSE offers stronger security guarantees than previous schemes, particularly in preventing key reconstruction and ensuring ciphertext integrity, while maintaining competitive performance.
What Problem Does This Paper Address?
In today's digital landscape, securing cryptographic keys is paramount. Threshold cryptography offers a robust solution by distributing keys among multiple parties, requiring a threshold number to compromise the system. While threshold public-key primitives have seen significant development, authenticated encryption (AE) – crucial for data confidentiality and integrity – has lagged behind in threshold implementations. Existing approaches using multi-party computation (MPC) are often communication-intensive. Prior work on threshold AE (TAE), like DiSE, focused on specific security models and had limitations in their formalization, analysis, and design, potentially leading to insecure schemes or insufficient understanding of parameter impacts. This paper addresses these shortcomings by proposing new, stronger security definitions and constructing efficient TAE schemes that meet these definitions in the fully malicious setting.
Methods
The authors introduce new security definitions for TAE, specifically IND-RCCA (Indistinguishable Authenticated Encryption - Replayable Chosen-Ciphertext Attack) and IND-CCA (Indistinguishable Authenticated Encryption - Chosen-Ciphertext Attack), which fix issues in prior work by preventing key reconstruction and offering distinct integrity guarantees. They then present two new TAE constructions:
- TAE1 (Random Injection-based): This scheme uses a symmetric-key primitive called "random injection" and an all-or-nothing transform. It achieves IND-RCCA security.
- TAE2 (DPRF & Threshold Signature-based): This construction builds upon a distributed pseudorandom function (DPRF) and a threshold signature scheme. It achieves IND-RCCA security.
- TAE3 (DVRF & Threshold Signature-based): This scheme is similar to TAE2 but replaces the DPRF with a verifiable distributed pseudorandom function (DVRF). This upgrade allows it to achieve the stronger IND-CCA security.
The paper also introduces new formalizations and analyses for DPRFs and DVRFs, including a novel Tensor-DDH assumption, which contribute to tighter security reductions.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Stronger Security Definitions are Crucial: The paper highlights critical flaws in previous TAE security models, particularly the inability to prevent key reconstruction and the loose notion of integrity. Their new IND-RCCA and IND-CCA definitions are a significant step towards more secure threshold AE.
- Random Injection as a Building Block: The novel use of "random injection" as a primitive for constructing secure TAE schemes is a key contribution, offering a new avenue for designing efficient and secure primitives.
- Modular Proof Techniques: The introduction of the Tensor-DDH assumption and modular proof techniques simplifies the analysis of DPRFs and DVRFs, making the security proofs more accessible and concrete.
- Trade-off Between Security and Performance: The paper demonstrates that achieving stronger security (IND-CCA) comes at a performance cost, as seen in the comparison between TAE2 (RCCA) and TAE3 (CCA).
Key Results
- ParaDiSE Schemes: The paper presents ParaDiSE, a family of TAE schemes (TAE1, TAE2, TAE3) that offer improved security in the fully malicious model.
- Performance: TAE1 achieves a throughput of over 777,000 encryptions per second (n=3, t=2), while TAE3 achieves 346 encryptions per second. These results are competitive with prior schemes like DiSE, offering stronger security guarantees for a slight performance overhead.
- Security Proofs: The paper provides concrete security analyses for its constructions, proving their security against the new IND-RCCA and IND-CCA definitions based on standard cryptographic assumptions.
Limitations and Future Work
- Adaptive Corruption: The current work focuses on static corruption. The authors suggest that extending their definitional framework to adaptive corruption and constructing secure schemes in that setting would be an interesting future direction.
- Homomorphic Generators: The paper notes that their construction of TAE3 (which replaces DPRF with DVRF) relies on a random oracle for the generator G. They leave it as future work to investigate if a weaker property on G, such as a homomorphic property, would be sufficient to prove security of DiSE in their modified model.
- Parameter Instantiation: While the paper provides performance results, further research into optimal parameter choices for specific applications could be beneficial.
Summary updated