TL;DR
This paper introduces a new, more efficient public-key encryption scheme by generalizing the Goldwasser-Micali (GM) cryptosystem using the e-th power residue symbol. They establish an equivalence between computing this symbol and solving the discrete logarithm problem, leading to provably secure and faster cryptosystems with better bandwidth utilization, and also enabling new constructions for lossy trapdoor functions and leakage-resilient encryption.
What Problem Does This Paper Address?
The Goldwasser-Micali (GM) cryptosystem, a foundational scheme for semantic security in public-key cryptography, suffers from significant bandwidth inefficiency. While extensions have been proposed to improve this, they often introduce complexity or limitations. This paper aims to address these limitations by revisiting the e-th power residue symbol, a generalization of the quadratic residue symbol used in the original GM scheme. The goal is to create a more efficient and secure cryptosystem that retains the desirable properties of GM while overcoming its practical drawbacks.
Methods
The core of this paper lies in establishing a novel connection between the computation of the e-th power residue symbol and the discrete logarithm problem (DLP). Specifically, they prove that computing the e-th power residue symbol is equivalent to solving the DLP under certain conditions related to the parameters involved. This equivalence is crucial because efficient algorithms exist for solving DLP when the order of the group is a product of small primes (e.g., using the Pohlig-Hellman algorithm).
Leveraging this equivalence, the authors propose:
- A New Algorithm for Computing the e-th Power Residue Symbol: By reducing the problem to DLP with smooth orders, they achieve an efficient algorithm for the e-th power residue symbol.
- A Natural Extension of the GM Scheme: They construct a new public-key encryption scheme based on this generalized symbol. This scheme is designed to be more efficient in terms of bandwidth and decryption speed compared to prior extensions like the Joye-Libert (JL) scheme.
- A New Hardness Assumption: They introduce the "(ep, eq)-th Power Residue (PR) assumption," which generalizes the quadratic residuosity assumption used in the original GM scheme. This new assumption is used to prove the security of their proposed cryptosystem.
- New Constructions for Cryptographic Primitives: The paper also shows how their techniques can be used to build efficient lossy trapdoor functions and circular and leakage-resilient public-key encryptions, often outperforming existing methods.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- DLP Equivalence: The most significant insight is the proof that computing the e-th power residue symbol is equivalent to solving the discrete logarithm problem under specific conditions. This is a powerful reduction that unlocks efficient computation when the order of the group is smooth.
- Generalizing GM: The paper demonstrates that the GM cryptosystem can be naturally extended beyond the quadratic residue case to the e-th power residue symbol, leading to practical improvements.
- New Security Foundation: The introduction of the (ep, eq)-PR assumption provides a new, well-defined basis for proving the security of advanced cryptographic schemes.
- Efficiency Gains: The proposed cryptosystem offers tangible improvements in bandwidth utilization and decryption speed, making it more practical for real-world applications.
Key Results
- Efficient e-th Power Residue Symbol Computation: An efficient algorithm for computing the e-th power residue symbol is presented, applicable when the relevant group order is smooth.
- New IND-CPA Secure Cryptosystem: A novel public-key encryption scheme is proposed, proven IND-CPA secure under the new (ep, eq)-PR assumption.
- Performance Improvements: The new cryptosystem offers significantly better bandwidth utilization and decryption speed compared to the JL scheme. For instance, decrypting a 128-bit message with a 2048-bit modulus is approximately 3.5 times faster than the JL scheme.
- Enhanced Cryptographic Primitives: The work provides efficient constructions for lossy trapdoor functions and circular/leakage-resilient public-key encryptions, leveraging the e-th power residue symbol for better performance.
Limitations and Future Work
- Parameter Selection: While the paper discusses parameter selection, it notes that the size of
log ep + log eqis bounded bylog N. It also cautions against choosingepandeqtoo large, as it could lead to vulnerabilities related to factoringNwhen combined with attacks like Coppersmith's. Future work could explore optimal parameter choices to balance security and efficiency. - New Assumptions: The security of the proposed schemes relies on the newly introduced (ep, eq)-PR assumption. Further cryptanalysis and investigation into the strength of this assumption would be valuable.
- Broader Applications: The paper hints at further applications of the e-th power residue symbol in cryptography. Exploring these and other potential uses could be a fruitful direction for future research.
Summary updated