In addition to its conceptual simplicity, a main advantage of this new technique over previous ones is that it avoids the Cook-Levin theorem, which tends to be rather inefficient. Indeed, our technique allows for very efficient instantiation based on the security of some efficient signature schemes and standard number-theoretic assumptions. For instance, one instantiation of our technique yields a universally composable zero-knowledge protocol under the Strong RSA assumption, incurring an overhead of a small constant number of exponentiations, plus the generation of two signatures.
Category / Keywords: cryptographic protocols / zero knowledge, digital signatures Publication Info: Extended abstract in Eurocrypt 2003 Date: received 27 Feb 2003, last revised 15 Aug 2003 Contact author: philmac at lucent com Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: This version contains minor revisions and corrections. Version: 20030815:163543 (All versions of this report) Short URL: ia.cr/2003/037 Discussion forum: Show discussion | Start new discussion