New Assumptions and Efficient Cryptosystems from the e-th Power Residue Symbol

Xiaopeng Zhao, Zhenfu Cao, Xiaolei Dong, Jun Shao, Licheng Wang, Zhusen Liu

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 eq is bounded by log N. It also cautions against choosing ep and eq too large, as it could lead to vulnerabilities related to factoring N when 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

BibTeX
@article{zhao2020new,
  author = {Xiaopeng Zhao and Zhenfu Cao and Xiaolei Dong and Jun Shao and Licheng Wang and Zhusen Liu},
  title = {{New Assumptions and Efficient Cryptosystems from the e-th Power Residue Symbol}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2020},
  url = {https://openreview.net/forum?id=GNhkeImvmu},
}

Loading related content...

Figure