Succinctness and zero-knowledge are two fundamental properties in the study of cryptographic proof systems. Several recent works have formalized the connections between these two notions by showing how to realize non-interactive zero-knowledge (NIZK) arguments from succinct non-interactive arguments. Specifically, Champion and Wu (CRYPTO 2023) as well as Bitansky, Kamath, Paneth, Rothblum, and Vasudevan (ePrint 2023) recently showed how to construct a NIZK argument for \(\textsf{NP}\) from a (somewhere-sound) non-interactive batch argument (BARG) and a dual-mode commitment scheme (and in the case of the Champion-Wu construction, a local pseudorandom generator). The main open question is whether a BARG suffices for a NIZK (just assuming one-way functions). In this work, we first show that an adaptively-sound BARG for \(\textsf{NP}\) together with an one-way function imply a computational NIZK argument for \(\textsf{NP}\) . We then show that the weaker notion of somewhere soundness achieved by existing BARGs from standard algebraic assumptions are also adaptively sound if we assume sub-exponential security. This transformation may also be of independent interest. Taken together, we obtain a NIZK argument for \(\textsf{NP}\) from one-way functions and a sub-exponentially-secure somewhere-sound BARG for \(\textsf{NP}\) . If we instead assume plain public-key encryption, we show that a standard polynomially-secure somewhere-sound batch argument for \(\textsf{NP}\) suffices for the same implication. As a corollary, this means a somewhere-sound BARG can be used to generically upgrade any semantically-secure public-key encryption scheme into one secure against chosen-ciphertext attacks. More broadly, our results demonstrate that constructing non-interactive batch arguments for \(\textsf{NP}\) is essentially no easier than constructing NIZK arguments for \(\textsf{NP}\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Batch Arguments to NIZKs from One-Way Functions

  • Eli Bradley,
  • Brent Waters,
  • David J. Wu

摘要

Succinctness and zero-knowledge are two fundamental properties in the study of cryptographic proof systems. Several recent works have formalized the connections between these two notions by showing how to realize non-interactive zero-knowledge (NIZK) arguments from succinct non-interactive arguments. Specifically, Champion and Wu (CRYPTO 2023) as well as Bitansky, Kamath, Paneth, Rothblum, and Vasudevan (ePrint 2023) recently showed how to construct a NIZK argument for \(\textsf{NP}\) from a (somewhere-sound) non-interactive batch argument (BARG) and a dual-mode commitment scheme (and in the case of the Champion-Wu construction, a local pseudorandom generator). The main open question is whether a BARG suffices for a NIZK (just assuming one-way functions). In this work, we first show that an adaptively-sound BARG for \(\textsf{NP}\) together with an one-way function imply a computational NIZK argument for \(\textsf{NP}\) . We then show that the weaker notion of somewhere soundness achieved by existing BARGs from standard algebraic assumptions are also adaptively sound if we assume sub-exponential security. This transformation may also be of independent interest. Taken together, we obtain a NIZK argument for \(\textsf{NP}\) from one-way functions and a sub-exponentially-secure somewhere-sound BARG for \(\textsf{NP}\) . If we instead assume plain public-key encryption, we show that a standard polynomially-secure somewhere-sound batch argument for \(\textsf{NP}\) suffices for the same implication. As a corollary, this means a somewhere-sound BARG can be used to generically upgrade any semantically-secure public-key encryption scheme into one secure against chosen-ciphertext attacks. More broadly, our results demonstrate that constructing non-interactive batch arguments for \(\textsf{NP}\) is essentially no easier than constructing NIZK arguments for \(\textsf{NP}\) .