International Association
for Cryptologic Research

<jats:title>Abstract</jats:title><jats:p>Non-malleable codes were introduced by Dziembowski et al. (in: Yao (ed) ICS2010, Tsinghua University Press, 2010), and its main application is the protection of cryptographic devices against tampering attacks on memory. In this work, we initiate a comprehensive study on non-malleable codes for the class of partial functions, that read/write on an arbitrary subset of codeword bits with specific cardinality. We present two constructions: the first one is in the CRS model and allows the adversary to selectively choose the subset of codeword bits, while the latter is in the standard model and adaptively secure. Our constructions are efficient in terms of information rate, while allowing the attacker to access asymptotically almost the entire codeword. In addition, they satisfy a notion which is stronger than non-malleability, that we call non-malleability with manipulation detection, guaranteeing that any modified codeword decodes to either the original message or to <jats:inline-formula><jats:alternatives><jats:tex-math>$$\bot $$</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>. We show that our primitive implies All-Or-Nothing Transforms (AONTs), and as a result our constructions yield efficient AONTs under standard assumptions (only one-way functions), which, to the best of our knowledge, was an open question until now. Furthermore, we construct a notion of continuous non-malleable codes (CNMC), namely CNMC with light updates, that avoids the full re-encoding process and only uses shuffling and refreshing operations. Finally, we present a number of additional applications of our primitive in tamper resilience.</jats:p>

<jats:title>Abstract</jats:title><jats:p>Bitcoin is one of the most prominent examples of a distributed cryptographic protocol that is extensively used in reality. Nonetheless, existing security proofs are property-based, and as such they do not support composition. In this work, we put forth a universally composable treatment of the Bitcoin protocol. We specify the goal that Bitcoin aims to achieve as an instance of a parameterizable ledger functionality and present a UC abstraction of the Bitcoin blockchain protocol. Our ideal functionality is weaker than the first proposed candidate by Kiayias, Zhou, and Zikas [EUROCRYPT’16], but unlike the latter suggestion, which is arguably not implementable by the UC Bitcoin protocol, we prove that the one proposed here is securely UC-realized by the protocol assuming access to a global clock, to model time-based executions, a random oracle, to model hash functions, and an idealized network, to model message dissemination. We further show how known property-based approaches can be cast as special instances of our treatment and how their underlying assumptions can be cast in UC as part of the setup functionalities and without restricting the environment or the adversary. </jats:p>

<jats:title>Abstract</jats:title><jats:p>Chameleon-hash functions, introduced by Krawczyk and Rabin (NDSS’00), are trapdoor collision-resistant hash functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash function can be found efficiently. Chameleon-hash functions have prominent applications in the design of cryptographic primitives, such as lifting non-adaptively secure signatures to adaptively secure ones. Recently, this primitive also received a lot of attention as a building block in more complex cryptographic applications, ranging from editable blockchains to advanced signature and encryption schemes. We observe that, in latter applications, various different notions of collision-resistance are used, and it is not always clear if the respective notion really covers what seems intuitively required by the application. Therefore, we revisit existing collision-resistance notions in the literature, study their relations, and by means of selected applications discuss which practical impact different notions of collision-resistance might have. Moreover, we provide a stronger, and arguably more desirable, notion of collision-resistance than what is known from the literature (which we call full collision-resistance). Finally, we present a surprisingly simple, and efficient, black-box construction of chameleon-hash functions achieving this strong notion of full collision-resistance. </jats:p>

<jats:title>Abstract</jats:title><jats:p>Collision-resistant hash functions (<jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{CRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>CRH</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{CRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>CRH</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> called <jats:italic>t</jats:italic><jats:italic>-way multi-collision-resistant hash functions</jats:italic> (<jats:inline-formula><jats:alternatives><jats:tex-math>$$t\text {-}\textsf{MCRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mtext>-</mml:mtext> <mml:mi>MCRH</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>). These are families of functions for which it is computationally hard to find a <jats:italic>t</jats:italic>-way collision, even though such collisions are abundant (and even <jats:inline-formula><jats:alternatives><jats:tex-math>$$(t-1)$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>-way collisions may be easy to find). The case of <jats:inline-formula><jats:alternatives><jats:tex-math>$$t=2$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> corresponds to standard <jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{CRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>CRH</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>, but it is natural to study <jats:italic>t</jats:italic>-<jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{MCRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>MCRH</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> for larger values of <jats:italic>t</jats:italic>. Multi-collision resistance seems to be a qualitatively weaker property than standard collision resistance. Nevertheless, in this work we show a <jats:italic>non-blackbox</jats:italic> transformation of any moderately shrinking <jats:italic>t</jats:italic>-<jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{MCRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>MCRH</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>, for <jats:inline-formula><jats:alternatives><jats:tex-math>$$t \in \{3,4\}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>{</mml:mo> <mml:mn>3</mml:mn> <mml:mo>,</mml:mo> <mml:mn>4</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, into an (infinitely often secure) <jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{CRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>CRH</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>. This transformation is non-constructive—we can prove the existence of a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{CRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>CRH</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> but cannot explicitly point out a construction. Our result partially extends to larger values of <jats:italic>t</jats:italic>. In particular, we show that for suitable values of <jats:inline-formula><jats:alternatives><jats:tex-math>$$t&gt;t'$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>&gt;</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mo>′</mml:mo> </mml:msup> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, we can transform a <jats:italic>t</jats:italic>-<jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{MCRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>MCRH</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> into a <jats:inline-formula><jats:alternatives><jats:tex-math>$$t'$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>t</mml:mi> <mml:mo>′</mml:mo> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula>-<jats:inline-formula><jats:alternatives><jats:tex-math>$$\textsf{MCRH}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>MCRH</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>, at the cost of reducing the shrinkage of the resulting hash function family and settling for infinitely often security. This result utilizes the list-decodability properties of Reed–Solomon codes.</jats:p>

The present article provides a novel hash function $${\mathcal {H}}$$ H to any elliptic curve of j -invariant $$\ne 0, 1728$$ ≠ 0 , 1728 over a finite field $${\mathbb {F}}_{\!q}$$ F q of large characteristic. The unique bottleneck of $${\mathcal {H}}$$ H consists of extracting a square root in $${\mathbb {F}}_{\!q}$$ F q as well as for most hash functions. However, $${\mathcal {H}}$$ H is designed in such a way that the root can be found by (Cipolla–Lehmer–)Müller’s algorithm in constant time. Violation of this security condition is known to be the only obstacle to applying the given algorithm in the cryptographic context. When the field $${\mathbb {F}}_{\!q}$$ F q is highly 2-adic and $$q \equiv 1 \ (\textrm{mod} \ 3)$$ q ≡ 1 ( mod 3 ) , the new batching technique is the state-of-the-art hashing solution except for some sporadic curves. Indeed, Müller’s algorithm costs $$\approx 2\log _2(q)$$ ≈ 2 log 2 ( q ) multiplications in $${\mathbb {F}}_{\!q}$$ F q . In turn, original Tonelli–Shanks’s square root algorithm and all of its subsequent modifications have the algebraic complexity $$\varTheta (\log (q) + g(\nu ))$$ Θ ( log ( q ) + g ( ν ) ) , where $$\nu $$ ν is the 2-adicity of $${\mathbb {F}}_{\!q}$$ F q and a function $$g(\nu ) \ne O(\nu )$$ g ( ν ) ≠ O ( ν ) . As an example, it is shown that Müller’s algorithm actually needs several times fewer multiplications in the field $${\mathbb {F}}_{\!q}$$ F q (whose $$\nu = 96$$ ν = 96 ) of the standardized curve NIST P-224.

<jats:title>Abstract</jats:title><jats:p>We construct an identity-based encryption (IBE) scheme that is tightly secure in a very strong sense. Specifically, we consider a setting with many instances of the scheme and many encryptions per instance. In this setting, we reduce the security of our scheme to a variant of a simple assumption used for a similar purpose by Chen and Wee (CRYPTO 2013, Springer, 2013). The security loss of our reduction is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\textbf{O} (k)$$</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>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> (where <jats:inline-formula><jats:alternatives><jats:tex-math>$$k $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> is the security parameter). Our scheme is the first IBE scheme to achieve this strong flavor of tightness under a simple assumption. Technically, our scheme is a variation of the IBE scheme by Chen and Wee. However, in order to “lift” their results to the multi-instance, multi-ciphertext case, we need to develop new ideas. In particular, while we build on (and extend) their high-level proof strategy, we deviate significantly in the low-level proof steps.</jats:p>

<jats:title>Abstract</jats:title><jats:p>Polynomial commitments schemes are a powerful tool that enables one party to commit to a polynomial <jats:italic>p</jats:italic> of degree <jats:italic>d</jats:italic>, and prove that the committed function evaluates to a certain value <jats:italic>z</jats:italic> at a specified point <jats:italic>u</jats:italic>, i.e. <jats:inline-formula><jats:alternatives><jats:tex-math>$$p(u) = z$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>(</mml:mo> <mml:mi>u</mml:mi> <mml:mo>)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>z</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, without revealing any additional information about the polynomial. Recently, polynomial commitments have been extensively used as a cryptographic building block to transform polynomial interactive oracle proofs (PIOPs) into efficient succinct arguments. In this paper, we propose a lattice-based polynomial commitment that achieves succinct proof size and verification time in the degree <jats:italic>d</jats:italic> of the polynomial. Extractability of our scheme holds in the random oracle model under a natural ring version of the BASIS assumption introduced by Wee and Wu (EUROCRYPT 2023). Unlike recent constructions of polynomial commitments by Albrecht et al. (CRYPTO 2022), and by Wee and Wu, we do not require any expensive preprocessing steps, which makes our scheme particularly attractive as an ingredient of a PIOP compiler for succinct arguments. We further instantiate our polynomial commitment, together with the PIOP (EUROCRYPT 2020), to obtain a publicly-verifiable trusted-setup succinct argument for Rank-1 Constraint System (R1CS). Performance-wise, we achieve <jats:inline-formula><jats:alternatives><jats:tex-math>$$17$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>17</mml:mn> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>MB proof size for <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{20}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>20</mml:mn> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula> constraints, which is <jats:inline-formula><jats:alternatives><jats:tex-math>$$15$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>15</mml:mn> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>X smaller than currently the only publicly-verifiable lattice-based SNARK proposed by Albrecht et al.</jats:p>

<jats:title>Abstract</jats:title><jats:p>We present new protocols for <jats:italic>Asynchronous Verifiable Secret Sharing</jats:italic> for Shamir (i.e., threshold <jats:inline-formula><jats:alternatives><jats:tex-math>$$t&lt;n$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>) sharing of secrets. Our protocols:<jats:list list-type="bullet"> <jats:list-item> <jats:p>Use only “lightweight” cryptographic primitives, such as hash functions;</jats:p> </jats:list-item> <jats:list-item> <jats:p>Can share secrets over rings such as <jats:inline-formula><jats:alternatives><jats:tex-math>$${\mathbb {Z}}/(p^k)$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Z</mml:mi> <mml:mo>/</mml:mo> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>p</mml:mi> <mml:mi>k</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> as well as finite fields <jats:inline-formula><jats:alternatives><jats:tex-math>$$\mathbb {F}_q$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:math></jats:alternatives></jats:inline-formula>;</jats:p> </jats:list-item> <jats:list-item> <jats:p>Provide <jats:italic>optimal resilience</jats:italic>, in the sense that they tolerate up to <jats:inline-formula><jats:alternatives><jats:tex-math>$$t &lt; n/3$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> corruptions, where <jats:italic>n</jats:italic> is the total number of parties;</jats:p> </jats:list-item> <jats:list-item> <jats:p>Are <jats:italic>complete</jats:italic>, in the sense that they guarantee that if any honest party receives their share then all honest parties receive their shares;</jats:p> </jats:list-item> <jats:list-item> <jats:p>Employ <jats:italic>batching</jats:italic> techniques, whereby a dealer shares many secrets in parallel and achieves an amortized communication complexity that is linear in <jats:italic>n</jats:italic>, at least on the “happy path”, where no party <jats:italic>provably</jats:italic> misbehaves. </jats:p> </jats:list-item> </jats:list></jats:p>

<jats:title>Abstract</jats:title><jats:p>We put forward two natural generalizations of predicate encryption (PE), dubbed <jats:italic>multi-key</jats:italic> and <jats:italic>multi-input</jats:italic> PE. More in details, our contributions are threefold.<jats:list list-type="bullet"> <jats:list-item> <jats:p><jats:bold>Definitions.</jats:bold> We formalize security of multi-key PE and multi-input PE following the standard indistinguishability paradigm, and modeling security both against malicious senders (i.e., corruption of encryption keys) and malicious receivers (i.e., collusions).</jats:p> </jats:list-item> <jats:list-item> <jats:p><jats:bold>Constructions.</jats:bold> We construct adaptively secure multi-key and multi-input PE supporting the conjunction of poly-many arbitrary single-input predicates, assuming the sub-exponential hardness of the learning with errors (LWE) problem.</jats:p> </jats:list-item> <jats:list-item> <jats:p><jats:bold>Applications.</jats:bold> We show that multi-key and multi-input PE for expressive enough predicates suffices for interesting cryptographic applications, including non-interactive multi-party computation (NI-MPC) and matchmaking encryption (ME).</jats:p> </jats:list-item> </jats:list> In particular, plugging in our constructions of multi-key and multi-input PE, under the sub-exponential LWE assumption, we obtain the first ME supporting <jats:italic>arbitrary policies</jats:italic> with unbounded collusions, as well as robust (resp. non-robust) NI-MPC for so-called <jats:italic>all-or-nothing</jats:italic> functions satisfying a non-trivial notion of reusability and supporting a constant (resp. polynomial) number of parties. Prior to our work, both of these applications required much heavier tools such as indistinguishability obfuscation or compact functional encryption.</jats:p>

The common approach in secure communication channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example, is the case with TLS or SSH. However, protocols like QUIC or DTLS which run over a non-reliable transport such as UDP, do not—and in fact cannot—close the connection if packets are lost or arrive in a different order. Those protocols instead have to carefully catch effects arising naturally in unreliable networks, usually by using a sliding-window technique where ciphertexts can be decrypted correctly as long as they are not misplaced too far. In order to be able to capture QUIC and the newest DTLS version 1.3, we introduce a generalized notion of robustness of cryptographic channels. This property can capture unreliable network behavior and guarantees that adversarial tampering cannot hinder ciphertexts that can be decrypted correctly from being accepted. We show that robustness is orthogonal to the common notion of integrity for channels, but together with integrity and chosen-plaintext security it provides a robust analog of chosen-ciphertext security of channels. In contrast to prior work, robustness allows us to study packet encryption in the record layer protocols of QUIC and of DTLS 1.3 and the novel sliding-window techniques both protocols employ. We show that both protocols achieve robust chosen-ciphertext security based on certain properties of their sliding-window techniques and the underlying AEAD schemes. Notably, the robustness needed in handling unreliable network messages requires both record layer protocols to tolerate repeated adversarial forgery attempts. This means we can only establish non-tight security bounds (in terms of AEAD integrity), a security degradation that was missed in earlier protocol drafts. Our bounds led the responsible IETF working groups to introduce concrete forgery limits for both protocols and the IRTF CFRG to consider AEAD usage limits more broadly.

<jats:title>Abstract</jats:title><jats:p>Two of the most useful cryptographic primitives that can be constructed from one-way functions are <jats:italic>pseudorandom generators</jats:italic> (PRGs) and <jats:italic>universal one-way hash functions</jats:italic> (UOWHFs). In order to implement them in practice, the efficiency of such constructions must be considered. The three major efficiency measures are: the <jats:italic>seed length</jats:italic>, the <jats:italic>call complexity</jats:italic> to the one-way function, and the <jats:italic>adaptivity</jats:italic> of these calls. Still, the optimal efficiency of these constructions is not yet fully understood: there exist gaps between the known upper bound and the known lower bound for black-box constructions. A special class of one-way functions called <jats:italic>unknown-regular</jats:italic> one-way functions is much better understood. Haitner, Harnik and Reingold (CRYPTO 2006) presented a PRG construction with semi-linear seed length and linear number of calls based on a method called <jats:italic>randomized iterate</jats:italic>. Ames, Gennaro and Venkitasubramaniam (ASIACRYPT 2012) then gave a construction of UOWHF with similar parameters and using similar ideas. On the other hand, Holenstein and Sinha (FOCS 2012) and Barhum and Holenstein (TCC 2013) showed an almost linear call-complexity lower bound for black-box constructions of PRGs and UOWHFs from one-way functions. Hence, Haitner et al. and Ames et al. reached <jats:italic>tight</jats:italic> constructions (in terms of seed length and the number of calls) of PRGs and UOWHFs from regular one-way functions. These constructions, however, are adaptive. In this work, we present non-adaptive constructions for both primitives which match the optimal call complexity given by Holenstein and Sinha and Barhum and Holenstein. Our constructions, besides being simple and non-adaptive, are robust also for <jats:italic>almost-regular</jats:italic> one-way functions.</jats:p>

<jats:title>Abstract</jats:title><jats:p>We construct the first actively-secure Multi-Party Computation (MPC) protocols with an <jats:italic>arbitrary</jats:italic> number of parties in the dishonest majority setting, for an <jats:italic>arbitrary</jats:italic> field <jats:inline-formula><jats:alternatives><jats:tex-math>$${\mathbb {F}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> with <jats:italic>constant communication overhead</jats:italic> over the “passive-GMW” protocol (Goldreich, Micali and Wigderson, STOC ‘87). Our protocols rely on passive implementations of Oblivious Transfer (OT) in the Boolean setting and Oblivious Linear function Evaluation (OLE) in the arithmetic setting. Previously, such protocols were only known over sufficiently large fields (Genkin et al. STOC ‘14) or a constant number of parties (Ishai et al. CRYPTO ‘08). Conceptually, our protocols are obtained via a new compiler from a passively-secure protocol for a distributed multiplication functionality <jats:inline-formula><jats:alternatives><jats:tex-math>$${{{\mathcal {F}}}}_{\scriptscriptstyle \textrm{MULT}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mstyle> <mml:mtext>MULT</mml:mtext> </mml:mstyle> </mml:msub> </mml:math></jats:alternatives></jats:inline-formula>, to an actively-secure protocol for general functionalities. Roughly, <jats:inline-formula><jats:alternatives><jats:tex-math>$${{{\mathcal {F}}}}_{\scriptscriptstyle \textrm{MULT}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mstyle> <mml:mtext>MULT</mml:mtext> </mml:mstyle> </mml:msub> </mml:math></jats:alternatives></jats:inline-formula> is parameterized by a linear-secret sharing scheme <jats:inline-formula><jats:alternatives><jats:tex-math>$${{{\mathcal {S}}}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>S</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>, where it takes <jats:inline-formula><jats:alternatives><jats:tex-math>$${{{\mathcal {S}}}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>S</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>-shares of two secrets and returns <jats:inline-formula><jats:alternatives><jats:tex-math>$${{{\mathcal {S}}}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>S</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>-shares of their product. We show that our compilation is concretely efficient for sufficiently large fields, resulting in an overhead of 2 when securely computing natural circuits. Our compiler has two additional benefits: (1) It can rely on <jats:italic>any</jats:italic> passive implementation of <jats:inline-formula><jats:alternatives><jats:tex-math>$${{{\mathcal {F}}}}_{\scriptscriptstyle \textrm{MULT}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mstyle> <mml:mtext>MULT</mml:mtext> </mml:mstyle> </mml:msub> </mml:math></jats:alternatives></jats:inline-formula>, which, besides the standard implementation based on OT (for Boolean) and OLE (for arithmetic), allows us to rely on implementations based on threshold cryptosystems (Cramer et al. Eurocrypt ‘01), and (2) it can rely on weaker-than-passive (i.e., imperfect/leaky) implementations, which in some parameter regimes yield actively-secure protocols with overhead less than 2. Instantiating this compiler with an “honest-majority” implementation of <jats:inline-formula><jats:alternatives><jats:tex-math>$${{{\mathcal {F}}}}_{\scriptscriptstyle \textrm{MULT}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mstyle> <mml:mtext>MULT</mml:mtext> </mml:mstyle> </mml:msub> </mml:math></jats:alternatives></jats:inline-formula>, we obtain the first honest-majority protocol (with up to one-third corruptions) for Boolean circuits with constant communication overhead over the best passive protocol (Damgård and Nielsen, CRYPTO ‘07). </jats:p>

<jats:title>Abstract</jats:title><jats:p>Boomerang attacks are extensions of differential attacks that make it possible to combine two unrelated differential properties of the first and second part of a cryptosystem with probabilities <jats:italic>p</jats:italic> and <jats:italic>q</jats:italic> into a new differential-like property of the whole cryptosystem with probability <jats:inline-formula><jats:alternatives><jats:tex-math>$$p^2q^2$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>p</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> (since each one of the properties has to be satisfied twice). In this paper, we describe a new version of boomerang attacks which uses the counterintuitive idea of throwing out most of the data in order to force equalities between certain values on the ciphertext side. In certain cases, this creates a correlation between the four probabilistic events, which increases the probability of the combined property to <jats:inline-formula><jats:alternatives><jats:tex-math>$$p^2q$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>p</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>q</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> and increases the signal-to-noise ratio of the resultant distinguisher. We call this variant a <jats:italic>retracing boomerang attack</jats:italic> since we make sure that the boomerang we throw follows the same path on its forward and backward directions. To demonstrate the power of the new technique, we apply it to the case of 5-round AES. This version of AES was repeatedly attacked by a large variety of techniques, but for twenty years its complexity had remained stuck at <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{32}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>32</mml:mn> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula>. At Crypto’18, it was finally reduced to <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{24}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>24</mml:mn> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula> (for full key recovery), and with our new technique, we can further reduce the complexity of full key recovery to the surprisingly low value of <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{16.5}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>16.5</mml:mn> </mml:mrow> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula> (i.e., only 90, 000 encryption/decryption operations are required for a full key recovery). In addition to improving previous attacks, our new technique unveils a hidden relationship between boomerang attacks and two other cryptanalytic techniques, the yoyo game and the recently introduced mixture differentials.</jats:p>

We revisit the problem of finding B -block-long collisions in Merkle–Damgård Hash Functions in the auxiliary-input random oracle model, in which an attacker gets a piece of S -bit advice about the random oracle and makes T oracle queries. Akshima, Cash, Drucker and Wee (CRYPTO 2020), based on the work of Coretti, Dodis, Guo and Steinberger (EUROCRYPT 2018), showed a simple attack for $$2\le B\le T$$ 2 ≤ B ≤ T (with respect to a random salt). The attack achieves advantage $$\widetilde{\Omega }(STB/2^n+T^2/2^n)$$ Ω ~ ( S T B / 2 n + T 2 / 2 n ) where n is the output length of the random oracle. They conjectured that this attack is optimal. However, this so-called STB conjecture was only proved for $$B\approx T$$ B ≈ T and $$B=2$$ B = 2 . Very recently, Ghoshal and Komargodski (CRYPTO 2022) confirmed the STB conjecture for all constant values of B and provided an $$\widetilde{O}(S^4TB^2/2^n+T^2/2^n)$$ O ~ ( S 4 T B 2 / 2 n + T 2 / 2 n ) bound for all choices of B . In this work, we prove an $$\widetilde{O}((STB/2^n)\cdot \max \{1,ST^2/2^n\}+ T^2/2^n)$$ O ~ ( ( S T B / 2 n ) · max { 1 , S T 2 / 2 n } + T 2 / 2 n ) bound for every $$2< B < T$$ 2 < B < T . Our bound confirms the STB conjecture for $$ST^2\le 2^n$$ S T 2 ≤ 2 n and is optimal up to a factor of S for $$ST^2>2^n$$ S T 2 > 2 n (note as $$T^2$$ T 2 is always at most $$2^n$$ 2 n , otherwise finding a collision is trivial by the birthday attack). Our result subsumes all previous upper bounds for all ranges of parameters except for $$B=\widetilde{O}(1)$$ B = O ~ ( 1 ) and $$ST^2>2^n$$ S T 2 > 2 n . We obtain our results by adopting and refining the technique of Chung, Guo, Liu and Qian (FOCS 2020). Our approach yields more modular proofs and sheds light on how to bypass the limitations of prior techniques. Along the way, we obtain a considerably simpler and illuminating proof for $$B=2$$ B = 2 , recovering the main result of Akshima, Cash, Drucker and Wee.