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.

Note: Update August 2023: Samuel Ranellucci reported a serious security issue with the sigma protocol in Figure 2. Please see Section 1.2 for more details.

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-08-30: revised
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.