International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Black-Box Non-Interactive Zero Knowledge from Vector Trapdoor Hash

Authors:
Pedro Branco , Bocconi University
Arka Rai Choudhuri , Nexus
Nico Döttling , CISPA Helmholtz Center for Information Security
Abhishek Jain , NTT Research and JHU
Giulio Malavolta , Bocconi University
Akshayaram Srinivasan , University of Toronto
Download:
Search ePrint
Search Google
Conference: EUROCRYPT 2025
Abstract: We present a new approach for constructing non-interactive zero-knowledge (NIZK) proof systems from {\em vector trapdoor hashing} (VTDH) -- a generalization of trapdoor hashing [D\"ottling et al., Crypto'19]. Unlike prior applications of trapdoor hash to NIZKs, we use VTDH to realize the hidden bits model [Feige-Lapidot-Shamir, FOCS'90] leading to {\em black-box} constructions of NIZKs. This approach gives us the following new results: \begin{itemize} \item A {\em statistically-sound} NIZK proof system based on the hardness of decisional Diffie-Hellman (DDH) and learning parity with noise (LPN) over finite fields with inverse polynomial noise rate. This gives the first statistically sound NIZK proof system that is not based on either LWE, or bilinear maps, or factoring. \item A dual-mode NIZK satisfying statistical zero-knowledge in the common random string mode and statistical soundness in the common reference string mode assuming the hardness of learning with errors (LWE) with {\em polynomial} modulus-to-noise ratio. This gives the first {\it black-box} construction of such a dual-mode NIZK under LWE. This improves the recent work of Waters (STOC'24) which relied on LWE with super-polynomial modulus-to-noise ratio and required a setup phase with private coins. \end{itemize} The above constructions are black-box and satisfy single-theorem zero-knowledge property. Building on the works of Feige et al.(FOCS'90) and Fischlin and Rohrback (PKC'21), we upgrade these constructions (under the same assumptions) to satisfy multi-theorem zero-knowledge property at the expense of making non-black-box use of cryptography.
BibTeX
@inproceedings{eurocrypt-2025-34988,
  title={Black-Box Non-Interactive Zero Knowledge from Vector Trapdoor Hash},
  publisher={Springer-Verlag},
  author={Pedro Branco and Arka Rai Choudhuri and Nico Döttling and Abhishek Jain and Giulio Malavolta and Akshayaram Srinivasan},
  year=2025
}