International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Black-Box Extensions of Non-interactive Zero-Knowledge Arguments, and Signatures Directly from Simulation Soundness

Authors:
Masayuki Abe
Miguel Ambrona
Miyako Ohkubo
Download:
DOI: 10.1007/978-3-030-45374-9_19
Search ePrint
Search Google
Abstract: Highly efficient non-interactive zero-knowledge arguments (NIZK) are often constructed for limited languages and it is not known how to extend them to cover wider classes of languages in general. In this work we initiate a study on black-box language extensions for conjunctive and disjunctive relations, that is, building a NIZK system for mathcalLdiamondhatmathcalL (with diamondinwedge,vee ) based on NIZK systems for languages mathcalL and hatmathcalL . While the conjunctive extension of NIZKs is straightforward by simply executing the given NIZKs in parallel, it is not known how disjunctive extensions could be achieved in a black-box manner. Besides, observe that the simple conjunctive extension does not work in the case of simulation-sound NIZKs (SS-NIZKs), as pointed out by Sahai (Sahai, FOCS 1999). Our main contribution is an impossibility result that negates the existence of the above extensions and implies other non-trivial separations among NIZKs, SS-NIZKs, and labelled SS-NIZKs. Motivated by the difficulty of such transformations, we additionally present an efficient construction of signature schemes based on unbounded simulation-sound NIZKs (USS-NIZKs) for any language without language extensions.
Video from PKC 2020
BibTeX
@article{pkc-2020-30299,
  title={On Black-Box Extensions of Non-interactive Zero-Knowledge Arguments, and Signatures Directly from Simulation Soundness},
  booktitle={Public-Key Cryptography – PKC 2020},
  series={Public-Key Cryptography – PKC 2020},
  publisher={Springer},
  volume={12110},
  pages={558-589},
  doi={10.1007/978-3-030-45374-9_19},
  author={Masayuki Abe and Miguel Ambrona and Miyako Ohkubo},
  year=2020
}