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 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 eq is bounded by log N. It also cautions against choosing ep and eq too 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

Abstract

The e-th power residue symbol \(\left( \frac{\alpha }{\mathfrak {p}}\right) _e\) is a useful mathematical tool in cryptography, where \(\alpha \) is an integer, \(\mathfrak {p}\) is a prime ideal in the prime factorization of \(p\mathbb {Z}[\zeta _e]\) with a large prime p satisfying \(e | p-1\), and \(\zeta _e\) is an e-th primitive root of unity. One famous case of the e-th power symbol is the first semantic secure public key cryptosystem due to Goldwasser and Micali (at STOC 1982). In this paper, we revisit the e-th power residue symbol and its applications. In particular, we prove that computing the e-th power residue symbol is equivalent to solving the discrete logarithm problem. By this result, we give a natural extension of the Goldwasser-Micali cryptosystem, where e is an integer only containing small prime factors. Compared to another extension of the Goldwasser-Micali cryptosystem due to Joye and Libert (at EUROCRYPT 2013), our proposal is more efficient in terms of bandwidth utilization and decryption cost. With a new hardness assumption naturally extended from the one used in the Goldwasser-Micali cryptosystem, our proposal is provable IND-CPA secure. Furthermore, we show that our results on the e-th power residue symbol can also be used to construct lossy trapdoor functions and circular and leakage resilient public key encryptions with more efficiency and better bandwidth utilization.
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