Paper 2023/364

Zero-Knowledge Arguments for Subverted RSA Groups

Dimitris Kolonelos, IMDEA Software Institute, Universidad Politécnica de Madrid
Mary Maller, Ethereum Foundation, PQShield
Mikhail Volkhov, The University of Edinburgh
Abstract

This work investigates zero-knowledge protocols in subverted RSA groups where the prover can choose the modulus and where the verifier does not know the group order. We introduce a novel technique for extracting the witness from a general homomorphism over a group of unknown order that does not require parallel repetitions. We present a NIZK range proof for general homomorphisms such as Paillier encryptions in the designated verifier model that works under a subverted setup. The key ingredient of our proof is a constant sized NIZK proof of knowledge for a plaintext. Security is proven in the ROM assuming an IND-CPA additively homomorphic encryption scheme. The verifier's public key is reusable, can be maliciously generated and is linear in the number of proofs to be verified.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2023
Keywords
Zero-knowledge proofsRSA groupsSubversion-resistant
Contact author(s)
dimitris kolonelos @ imdea org
mary maller @ ethereum org
mikhail volkhov @ ed ac uk
History
2023-03-16: approved
2023-03-13: received
See all versions
Short URL
https://ia.cr/2023/364
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/364,
      author = {Dimitris Kolonelos and Mary Maller and Mikhail Volkhov},
      title = {Zero-Knowledge Arguments for Subverted RSA Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2023/364},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/364}},
      url = {https://eprint.iacr.org/2023/364}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.