International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Zero-Knowledge Arguments for Subverted RSA Groups

Dimitris Kolonelos , IMDEA Software Institute & Universidad Polit├ęcnica de Madrid
Mary Maller , Ethereum Foundation
Mikhail Volkhov , The University of Edinburgh
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
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 then present a NIZK range proof for general homomorphisms 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 can be maliciously generated and is reusable and linear in the number of proofs to be verified.
  title={Zero-Knowledge Arguments for Subverted RSA Groups},
  author={Dimitris Kolonelos and Mary Maller and Mikhail Volkhov},