We say a tuple of NP statements \((x_1, \ldots , x_k)\) satisfies a monotone policy \(P :\{0,1\}^k \rightarrow \{0,1\}\) if \(P(b_1,\ldots ,b_k)=1\) , where \(b_i = 1\) if and only if \(x_i\) is in the NP language. A monotone-policy batch argument (monotone-policy BARG) for NP is a natural extension of regular batch arguments (BARGs) that allows a prover to prove that \(x_1, \ldots , x_k\) satisfy a monotone policy P with a proof of size \(\textsf{poly}(\lambda , |\mathcal {R}|, \log k)\) , where \(|\mathcal {R}|\) is the size of the Boolean circuit computing the NP relation \(\mathcal {R}\) .    Previously, Brakerski, Brodsky, Kalai, Lombardi, and Paneth (CRYPTO 2023) and Nassar, Waters, and Wu (TCC 2024) showed how to construct monotone-policy BARGs from (somewhere-extractable) BARGs for NP together with a leveled homomorphic encryption scheme (Brakerski et al.) or an additively homomorphic encryption scheme over a sufficiently-large group (Nassar et al.). In this work, we improve upon both works by showing that BARGs together with additively homomorphic encryption over any group suffices (e.g., over \(\mathbb {Z}_2\) ). For instance, we can instantiate the additively homomorphic encryption with the classic Goldwasser-Micali encryption scheme based on the quadratic residuosity (QR) assumption. Then, by appealing to existing compilers, we also obtain a monotone-policy aggregate signature scheme from any BARG and the QR assumption.

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

Monotone-Policy BARGs and More from BARGs and Quadratic Residuosity

  • Shafik Nassar,
  • Brent Waters,
  • David J. Wu

摘要

We say a tuple of NP statements \((x_1, \ldots , x_k)\) satisfies a monotone policy \(P :\{0,1\}^k \rightarrow \{0,1\}\) if \(P(b_1,\ldots ,b_k)=1\) , where \(b_i = 1\) if and only if \(x_i\) is in the NP language. A monotone-policy batch argument (monotone-policy BARG) for NP is a natural extension of regular batch arguments (BARGs) that allows a prover to prove that \(x_1, \ldots , x_k\) satisfy a monotone policy P with a proof of size \(\textsf{poly}(\lambda , |\mathcal {R}|, \log k)\) , where \(|\mathcal {R}|\) is the size of the Boolean circuit computing the NP relation \(\mathcal {R}\) .    Previously, Brakerski, Brodsky, Kalai, Lombardi, and Paneth (CRYPTO 2023) and Nassar, Waters, and Wu (TCC 2024) showed how to construct monotone-policy BARGs from (somewhere-extractable) BARGs for NP together with a leveled homomorphic encryption scheme (Brakerski et al.) or an additively homomorphic encryption scheme over a sufficiently-large group (Nassar et al.). In this work, we improve upon both works by showing that BARGs together with additively homomorphic encryption over any group suffices (e.g., over \(\mathbb {Z}_2\) ). For instance, we can instantiate the additively homomorphic encryption with the classic Goldwasser-Micali encryption scheme based on the quadratic residuosity (QR) assumption. Then, by appealing to existing compilers, we also obtain a monotone-policy aggregate signature scheme from any BARG and the QR assumption.