CryptoDB

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

Authors: Masayuki Abe Miguel Ambrona Miyako Ohkubo DOI: 10.1007/978-3-030-45374-9_19 Search ePrint Search Google 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 ${mathcal L}diamond hat{{mathcal L}}$ (with $diamond in {wedge , vee }$ ) based on NIZK systems for languages ${mathcal L}$ and $hat{{mathcal L}}$ . 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.
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
}