TL;DR
This paper introduces a new, more efficient public-key cryptosystem by extending the classic Goldwasser-Micali (GM) scheme using the generalized e-th power residue symbol. They establish a crucial link between computing this symbol and the discrete logarithm problem, enabling provable security and significant performance improvements in bandwidth and decryption speed compared to prior extensions.
What Problem Does This Paper Address?
The Goldwasser-Micali (GM) cryptosystem, a foundational work in semantic security, suffers from significant bandwidth inefficiency, limiting its practical use. While various extensions have been proposed to improve this, they often introduce complexities in security proofs or still have limitations. This paper aims to revisit the e-th power residue symbol, a generalization of the quadratic residue symbol used in GM, to develop a more efficient and practical cryptosystem that retains semantic security. Specifically, they address the challenge of efficiently computing the e-th power residue symbol for a broader range of parameters and leveraging this for improved cryptographic primitives.
Methods
The core of this paper lies in establishing a theoretical equivalence: computing the e-th power residue symbol is proven to be equivalent to solving the discrete logarithm problem under specific conditions. This connection is crucial because efficient algorithms exist for solving the discrete logarithm problem when the group order has small prime factors. This allows them to develop an efficient algorithm for the e-th power residue symbol when 'e' is composed of small prime factors.
Building on this, they propose a natural extension of the Goldwasser-Micali cryptosystem. This new scheme uses the e-th power residue symbol with a composite 'e' composed of small prime factors. The paper also introduces a new hardness assumption, the (ep, eq)-th Power Residue (PR) assumption, which is a generalization of the assumption underlying the original GM scheme. This new assumption is used to prove the IND-CPA security of their proposed cryptosystem.
Furthermore, the paper demonstrates how their findings can be applied to construct other cryptographic primitives:
- Lossy Trapdoor Functions (LTDFs): They propose a generic construction of LTDFs that inherits the efficiency benefits of their cryptosystem.
- Circular and Leakage Resilient Public Key Encryption: By instantiating the subgroup indistinguishability (SG) assumption with their e-th power residue symbol, they achieve more efficient schemes in terms of bandwidth utilization compared to prior work.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions and cryptographic assumptions rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Equivalence to Discrete Logarithm Problem: The most significant insight is proving that computing the e-th power residue symbol is equivalent to solving the discrete logarithm problem under certain conditions. This is a powerful theoretical result that unlocks efficient computation for a broader class of parameters.
- Generalizing GM for Efficiency: By using the e-th power residue symbol with composite 'e' (composed of small prime factors), they achieve a more efficient GM-like cryptosystem. This directly addresses the bandwidth limitations of the original GM scheme.
- New Hardness Assumption: The introduction of the (ep, eq)-PR assumption provides a solid theoretical foundation for the security of their proposed cryptosystem and related primitives. This assumption is a natural extension of existing, well-studied assumptions.
- Broad Applicability: The paper demonstrates that the e-th power residue symbol is not just useful for a single cryptosystem but can be a versatile tool for constructing various advanced cryptographic primitives like LTDFs and leakage-resilient encryption, offering improved efficiency.
Key Results
- Efficient e-th Power Residue Symbol Computation: An efficient algorithm for computing the e-th power residue symbol is presented when 'e' has small prime factors, by leveraging the equivalence to the discrete logarithm problem.
- New GM Extension: A novel public-key encryption scheme is proposed, extending the Goldwasser-Micali cryptosystem. This scheme offers improved bandwidth utilization and decryption speed compared to previous extensions like the Joye-Libert (JL) scheme.
- Provable IND-CPA Security: The proposed cryptosystem is proven to be IND-CPA secure under the new (ep, eq)-PR assumption.
- Performance Gains: The new cryptosystem demonstrates significant performance improvements. For instance, decryption of a 128-bit message is approximately 3.5 times faster than the JL scheme when using specific parameter choices.
- Efficient LTDFs and Leakage-Resilient Encryption: The paper shows how to construct more efficient lossy trapdoor functions and circular/leakage resilient public-key encryptions using their techniques.
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 potentially lead to attacks (e.g., related to Coppersmith's attack on RSA factorization). Further research into optimal parameter selection and potential attacks is implied. - New Assumptions: The security of the proposed schemes relies on the newly introduced (ep, eq)-PR assumption. While it's a natural extension of existing assumptions, its long-term security and resistance to cryptanalysis will be subject to further scrutiny by the research community.
- Future Work: The paper suggests future work in applying their results to other cryptographic primitives and exploring further optimizations. The efficiency gains in bandwidth and decryption speed for various applications are highlighted as promising directions.
Summary updated