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

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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2023
Zero-knowledge proofsRSA groupsSubversion-resistant
Contact author(s)
dimitris kolonelos @ imdea org
mary maller @ ethereum org
mikhail volkhov @ ed ac uk
2023-03-16: approved
2023-03-13: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.