Paper 1998/008

An Efficient Non-Interactive Statistical Zero-Knowledge Proof System for Quasi-Safe Prime Products

Rosario Gennaro, Daniele Micciancio, and Tal Rabin

Abstract

We present efficient zero-knowledge proof systems for quasi-safe prime products and other related languages. Quasi-safe primes are a relaxation of safe primes, a class of prime numbers useful in many cryptographic applications. Our proof systems achieve higher security and better efficiency than all previously known ones. In particular, all our proof systems are perfect or statistical zero-knowledge, meaning that even a computationally unbounded adversary cannot extract any information from the proofs. Moreover, our proof systems are extremely efficient because they do not use general reductions to NP-complete problems, can be easily parallelized preserving zero-knowledge, and are non-interactive for computationally unbounded provers. The prover can also be efficiently implemented given some trapdoor information and using very little interaction. We demonstrate the applicability of quasi-safe primes by showing how they can be effectively used in the context of RSA based undeniable signatures to enforce the use of ``good'' public keys, i.e., keys such that if a signer can convince a recipient of the validity of a signature, then he won't be able to subsequently deny the same signature in case of a dispute.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords
RSA compositessafe primeszero-knowledgenon-interactive proofs
Contact author(s)
talr @ watson ibm com
History
1998-03-10: received
Short URL
https://ia.cr/1998/008
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1998/008,
      author = {Rosario Gennaro and Daniele Micciancio and Tal Rabin},
      title = {An Efficient Non-Interactive Statistical Zero-Knowledge Proof System for Quasi-Safe Prime Products},
      howpublished = {Cryptology ePrint Archive, Paper 1998/008},
      year = {1998},
      note = {\url{https://eprint.iacr.org/1998/008}},
      url = {https://eprint.iacr.org/1998/008}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.