Paper 2020/1399

A New Generalisation of the Goldwasser-Micali Cryptosystem Based on the Gap $2^k$-Residuosity Assumption

Diana Maimut and George Teseleanu


We present a novel public key encryption scheme that enables users to exchange many bits messages by means of \emph{at least} two large prime numbers in a Goldwasser-Micali manner. Our cryptosystem is in fact a generalization of the Joye-Libert scheme (being itself an abstraction of the first probabilistic encryption scheme). We prove the security of the proposed cryptosystem in the standard model (based on the gap $2^k$-residuosity assumption) and report complexity related facts. We also describe an application of our scheme to biometric authentication and discuss the security of our suggested protocol. Last but not least, we indicate several promising research directions.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.SECITC 2020
public key encryptionquadratic residuositysquared Jacobi symbolgap $2^k$-residuosityprovable securitybiometric authentication protocol
Contact author(s)
george teseleanu @ yahoo com
maimut diana @ gmail com
2022-03-15: last of 3 revisions
2020-11-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Diana Maimut and George Teseleanu},
      title = {A New Generalisation of the Goldwasser-Micali Cryptosystem Based on the Gap $2^k$-Residuosity Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1399},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.