International Association
for Cryptologic Research

<jats:title>Abstract</jats:title> <jats:p>We propose a generic compiler that can convert any zero-knowledge (ZK) proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art.<jats:list list-type="bullet"> <jats:list-item> <jats:p>By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for general circuits from <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathcal {O}(C^{3/4})$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> to <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathcal {O}(C^{1/2})$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula>. Our implementation shows that for a circuit of size <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2^{27}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>27</mml:mn> </mml:msup> </mml:math> </jats:alternatives> </jats:inline-formula>, it achieves up to <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$83.6\times $$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>83.6</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$70\%$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>70</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> faster in a 10Mbps network.</jats:p> </jats:list-item> <jats:list-item> <jats:p>Using the recent results on compressed <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\varSigma $$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math> </jats:alternatives> </jats:inline-formula>-protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathcal {O}(C^{1/2})$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation.</jats:p> </jats:list-item> <jats:list-item> <jats:p>We improve the communication of a designated <jats:italic>n</jats:italic>-verifier zero-knowledge proof from <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathcal {O}(nC/B+n^2B^2)$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>C</mml:mi> <mml:mo>/</mml:mo> <mml:mi>B</mml:mi> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mi>B</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> to <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathcal {O}(nC/B+n^2)$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>C</mml:mi> <mml:mo>/</mml:mo> <mml:mi>B</mml:mi> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula>.</jats:p> </jats:list-item> </jats:list> To demonstrate the scalability of our compilers, we were able to extract a commit-and-prove SIMD ZK from Ligero and cast it in our framework. We also give one instantiation derived from LegoSNARK, demonstrating that the idea of CP-SNARK also fits in our methodology.</jats:p>