International Association
for Cryptologic Research

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.

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.

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.