International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Universally Composable Non-Interactive Zero-Knowledge from Sigma Protocols via a New Straight-line Compiler

Authors:
Megan Chen , Boston University
Pousali Dey , Indian Statistical Institute
Chaya Ganesh , Indian Institute of Science
Pratyay Mukherjee , Supra Research
Pratik Sarkar , Supra Research
Swagata Sasmal , Indian Statistical Institute
Download:
Search ePrint
Search Google
Conference: PKC 2025
Abstract: Non-interactive zero-knowledge proofs (NIZK) are essential building blocks in threshold cryptosystems like multiparty signatures, distributed key generation, and verifiable secret sharing, allowing parties to prove correct behavior without revealing secrets. Furthermore, universally composable (UC) NIZKs enable seamless composition in the larger cryptosystems. A popular way to construct NIZKs is to compile interactive protocols using the Fiat-Shamir transform. Unfortunately, Fiat-Shamir transformed NIZK requires rewinding the adversary and is not *straight-line extractable*, making it at odds with UC. Using Fischlin's transform gives straight-line extractability, but at the expense of many repetitions of the underlying protocol leading to poor concrete efficiency and difficulty in setting parameters. In this work, we propose a simple new transform that compiles a Sigma protocol for an algebraic relation into a UC-NIZK protocol *without any overheads of repetition*. - Given a Sigma protocol for proving m algebraic statements over n witnesses, we construct a compiler to transform it into a *straight-line extractable* protocol using an additively homomorphic encryption scheme AHE. Our prover executes the Sigma protocol's prover once and computes 2n encryptions. The verification process involves running the Sigma protocol verifier once and then computing n encryptions, which are homomorphically verified against the prover generated encryptions. We apply the Fiat-Shamir transform to the above straight-line extractable Sigma protocol to obtain a UC-NIZK. We instantiate AHE using class group-based encryption where the public key of the encryption scheme is obliviously sampled using a suitable hash function. This yields a UC-NIZK protocol in the random oracle model.
BibTeX
@inproceedings{pkc-2025-35188,
  title={Universally Composable Non-Interactive Zero-Knowledge from Sigma Protocols via a New Straight-line Compiler},
  publisher={Springer-Verlag},
  author={Megan Chen and Pousali Dey and Chaya Ganesh and Pratyay Mukherjee and Pratik Sarkar and Swagata Sasmal},
  year=2025
}