International Association
for Cryptologic Research

We present BitGC, a garbling scheme for Boolean circuits with 1 bit per gate communication based on either ring learning with errors (RLWE) or NTRU assumption, with key-dependent message security. The garbling consists of 1) a homomorphically encrypted seed that can be expanded to encryption of many pseudo-random bits and 2) one-bit stitching information per gate to reconstruct garbled tables from the expanded ciphertexts. By using low-complexity PRGs, both the garbling and evaluation of each gate require only O(1) homomorphic addition/multiplication operations without bootstrapping.

EdDSA is a standardized signing algorithm, by both the IRTF and NIST, that is widely used in blockchain, e.g., Hyperledger, Cardano, Zcash, etc. It is a variant of the well-known Schnorr signature scheme that leverages Edwards curves. It features stateless and deterministic nonce generation, meaning it does not rely on a reliable source of randomness or state continuity. Recently, NIST issued a call for multi-party threshold EdDSA signatures, with one approach verifying nonce generation through zero-knowledge (ZK) proofs. In this paper, we propose a new stateless and deterministic multi-party EdDSA protocol in the full-threshold setting, capable of tolerating all-but-one malicious corruption. Compared to the state-of-the-art multi-party EdDSA protocol by Garillot et al. (Crypto’21), our protocol reduces communication cost by a factor of 56x while maintaining the same three-round structure, albeit with a roughly 2.25x increase in computational cost. We utilize information-theoretic message authentication codes (IT-MACs) in a multi-verifier setting to authenticate values and transform them from the Boolean domain to the arithmetic domain by refining multi-verifier extended doubly-authenticated bits (mv-edabits). Additionally, we employ pseudorandom correlation functions (PCF) to generate IT-MACs in a stateless and deterministic manner. Combining these elements, we design a multi-verifier zero-knowledge (MVZK) protocol for stateless and deterministic nonce generation. Our protocol can be used to build secure blockchain wallets and custody solutions, enhancing key protection.

We present ReSolveD, a new candidate post-quantum signature scheme under the regular syndrome decoding (RSD) assumption for random linear codes, which is a well-established variant of the well-known syndrome decoding (SD) assumption. Our signature scheme is obtained by designing a new zero-knowledge proof for proving knowledge of a solution to the RSD problem in the recent VOLE-in-the-head framework using a sketching scheme to verify that a vector has weight exactly one. We achieve a signature size of 3.99 KB with a signing time of 27.3 ms and a verification time of 23.1 ms on a single core of a standard desktop for a 128-bit security level. Compared to the state-of-the-art code-based signature schemes, our signature scheme achieves 1.5X ~ 2X improvement in terms of the common “signature size + public-key size” metric, while keeping the computational efficiency competitive.

Learning parity with noise (LPN) has been widely studied and used in cryptography. It was recently brought to new prosperity since Boyle et al. (CCS'18), putting LPN to a central role in designing secure multi-party computation, zero-knowledge proofs, private set intersection, and many other protocols. In this paper, we thoroughly studied security of LPN problems in this particular context. We found that some important aspects are long ignored and many conclusions from classical LPN cryptanalysis do not apply to this new setting, due to the low noise rates, extremely high dimensions, various types (in addition to $\FF_2$) and noise distributions. For LPN over a field, we give a parameterized reduction from exact-noise LPN to regular-noise LPN. Compared to the recent result by Feneuil, Joux and Rivain (Crypto'22), we significantly reduce the security loss by paying only a small additive price in dimension and number of samples. We analyze the security of LPN over a ring $\ZZ_{2^\lambda}$. Existing protocols based on LPN over integer rings use parameters as if they are over fields, but we found an attack that effectively reduces the weight of a noise by half compared to LPN over fields. Consequently, prior works that use LPN over $\ZZ_{2^\lambda}$ overestimate up to 40 bits of security. We provide a complete picture of the hardness of LPN over integer rings by showing: 1) the equivalence between its search and decisional versions; 2) an efficient reduction from LPN over $\FF_{2}$ to LPN over $\ZZ_{2^\lambda}$; and 3) generalization of our results to any integer ring. Finally, we provide an all-in-one estimator tool for the bit security of LPN parameters in the context of PCG, incorporating the recent advanced attacks.

<jats:title>Abstract</jats:title> <jats:p>Actively secure two-party computation (2PC) is one of the canonical building blocks in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols. In this paper, we make significant progress in closing this gap by proposing two new actively secure constant-round 2PC protocols, one with one-way communication of <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2\kappa +5$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> bits per AND gate (for <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\kappa $$</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>-bit computational security and any statistical security) and one with total communication of <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2\kappa +\rho +5$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mi>ρ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> bits per AND gate (for <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\rho $$</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>-bit statistical security). In particular, our first protocol essentially matches the one-way communication of semi-honest half-gates protocol. Our optimization is achieved by three new techniques: <jats:list list-type="order"> <jats:list-item> <jats:p>The recent compression technique by Dittmer et al. (Crypto 13510:57–87, 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$5\rho +1$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>5</mml:mn> <mml:mi>ρ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> bits to 2 bits per AND gate for <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\rho $$</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>-bit statistical security.</jats:p> </jats:list-item> <jats:list-item> <jats:p>Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2\kappa +3\rho $$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>3</mml:mn> <mml:mi>ρ</mml:mi> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> bits per AND gate. We designed a new authenticated garbling that does not use information-theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit. This allows us to use a more compact half-gates based authenticated garbled circuit of size <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2\kappa +1$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2\kappa +5$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> bits per AND gate.</jats:p> </jats:list-item> <jats:list-item> <jats:p>In terms of total communication, we notice that the communication overhead of the consistency checking method by Dittmer et al. (Crypto 13510:57–87, 2022) can be optimized by adding one-round of interaction and utilizing the Free-XOR property. This reduces the online communication from <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2\kappa +3\rho $$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>3</mml:mn> <mml:mi>ρ</mml:mi> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> bits down to <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2\kappa +\rho +1$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mi>ρ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> bits per AND gate. Combined with our first contribution, this yields total amortized communication of <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2\kappa +\rho +5$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mi>ρ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> bits.</jats:p> </jats:list-item> </jats:list> </jats:p>

<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>

GGM tree is widely used in designing correlated oblivious transfer (COT), subfield vector oblivious linear evaluation (sVOLE), distributed point function (DPF), and distributed comparison function (DCF). Often, the computation and communication cost associated with GGM tree is the major cost in these protocols. In this paper, we propose a suite of optimizations that can reduce this cost by half. - Halving the cost of COT and sVOLE. Our basic protocol introduces extra correlation in each level of a GGM tree used by the state-of-the-art COT protocol. As a result, it reduces the number of AES calls and the communication by half. Extending the idea to sVOLE, we are able to achieve similar improvement with either halved computation or halved communication. - Halving the cost of DPF and DCF. We propose improved two-party protocols for distributed generation of DPF/DCF keys. Our tree structures behind these protocols lead to more efficient full-domain evaluation and halve the communication and the round complexity of the state-of-the-art DPF/DCF protocols. All protocols are provably secure in the random-permutation model and can be accelerated based on fixed-key AES-NI. We also improve the state-of-the-art schemes of puncturable pseudorandom function (PPRF), DPF, and DCF, which are of independent interest in dealer-available scenarios.

Actively secure two-party computation (2PC) is one of the canonical building blocks in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols. In this paper, we propose a new actively secure constant-round 2PC protocol with one-way communication of $2\kappa+5$ bits per AND gate (for $\kappa$-bit computational security and any statistical security), essentially matching the one-way communication of semi-honest half-gates protocol. This is achieved by two new techniques: - The recent compression technique by Dittmer et al. (Crypto 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from $5\rho+1$ bits to $2$ bits per AND gate for $\rho$-bit statistical security. - Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size $2\kappa+3\rho$ bits per AND gate. We designed a new authenticated garbling that does not use information theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit. This allows us to use a more compact half-gates based authenticated garbled circuit of size $2\kappa+1$ bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of $2\kappa+5$ bits per AND gate. Our technique of yielding authenticated AND triples can also be used to optimize the two-way communication (i.e., the total communication) by combining it with the authenticated garbled circuits by Dittmer et al., which results in an actively secure 2PC protocol with two-way communication of $2\kappa+3\rho+4$ bits per AND gate.

In this paper, we study zero-knowledge (ZK) proofs for circuit satisfiability that can prove to $n$ verifiers at a time efficiently. The proofs are secure against the collusion of a prover and a subset of $t$ verifiers. We refer to such ZK proofs as multi-verifier zero-knowledge (MVZK) proofs and focus on the case that a majority of verifiers are honest (i.e., $t<n/2$). We construct efficient MVZK protocols in the random oracle model where the prover sends one message to each verifier, while the verifiers only exchange one round of messages. When the threshold of corrupted verifiers $t<n/2$, the prover sends $1/2+o(1)$ field elements per multiplication gate to every verifier; when $t<n(1/2-\epsilon)$ for some constant $0<\epsilon<1/2$, we can further reduce the communication to $O(1/n)$ field elements per multiplication gate per verifier. Our MVZK protocols demonstrate particularly high scalability: the proofs are streamable and only require a memory proportional to what is needed to evaluate the circuit in the clear.

Currently, lattice-based cryptosystems are less efficient than their number-theoretic counterparts (based on RSA, discrete logarithm, etc.) in terms of key and ciphertext (signature) sizes. For adequate security the former typically needs thousands of bytes while in contrast the latter only requires at most hundreds of bytes. This significant difference has become one of the main concerns in replacing currently deployed public-key cryptosystems with lattice-based ones. Observing the inherent asymmetries in existing lattice-based cryptosystems, we propose asymmetric variants of the (module-)LWE and (module-)SIS assumptions, which yield further size-optimized KEM and signature schemes than those from standard counterparts. Following the framework of Lindner and Peikert (CT-RSA 2011) and the Crystals-Kyber proposal (EuroS&P 2018), we propose an IND-CCA secure KEM scheme from the hardness of the asymmetric module-LWE (AMLWE), whose asymmetry is fully exploited to obtain shorter public keys and ciphertexts. To target at a 128-bit quantum security, the public key (resp., ciphertext) of our KEM only has 896 bytes (resp., 992 bytes). Our signature scheme bears most resemblance to and improves upon the Crystals-Dilithium scheme (ToCHES 2018). By making full use of the underlying asymmetric module-LWE and module-SIS assumptions and carefully selecting the parameters, we construct an SUF-CMA secure signature scheme with shorter public keys and signatures. For a 128-bit quantum security, the public key (resp., signature) of our signature scheme only has 1312 bytes (resp., 2445 bytes). We adapt the best known attacks and their variants to our AMLWE and AMSIS problems and conduct a comprehensive and thorough analysis of several parameter choices (aiming at different security strengths) and their impacts on the sizes, security and error probability of lattice-based cryptosystems. Our analysis demonstrates that AMLWE and AMSIS problems admit more flexible and size-efficient choices of parameters than the respective standard versions.