Paper 2013/569

More Efficient Cryptosystems From $k^{th}$-Power Residues

Zhenfu Cao, Xiaolei Dong, Licheng Wang, and Jun Shao

Abstract

At Eurocrypt 2013, Joye and Libert proposed a method for constructing public key cryptosystems (PKCs) and lossy trapdoor functions (LTDFs) from $(2^\alpha)^{th}$-power residue symbols. Their work can be viewed as non-trivial extensions of the well-known PKC scheme due to Goldwasser and Micali, and the LTDF scheme due to Freeman et al., respectively. In this paper, we will demonstrate that this kind of work can be extended \emph{more generally}: all related constructions can work for any $k^{th}$-power residues if $k$ only contains small prime factors, instead of $(2^\alpha)^{th}$-power residues only. The resultant PKCs and LTDFs are more efficient than that from Joye-Libert method in terms of decryption speed with the same message length.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Goldwasser-Micali cryptosystem$k^{th}$-power residuosity$k$-residue discrete logarithmadditive homomorphismlossy trapdoor function
Contact author(s)
zfcao @ cs sjtu edu cn
History
2013-09-24: revised
2013-09-09: received
See all versions
Short URL
https://ia.cr/2013/569
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/569,
      author = {Zhenfu Cao and Xiaolei Dong and Licheng Wang and Jun Shao},
      title = {More Efficient Cryptosystems From $k^{th}$-Power Residues},
      howpublished = {Cryptology ePrint Archive, Paper 2013/569},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/569}},
      url = {https://eprint.iacr.org/2013/569}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.