International Association
for Cryptologic Research

Collision-resistant hashing, a fundamental primitive in modern cryptography, ensures that there is no efficient way to find distinct inputs that produce the same hash value. This property underpins the security of various cryptographic applications, making it crucial to understand its complexity. The complexity of this problem is well-understood in the classical setting and $\Theta(N^{1/2})$ queries are needed to find a collision. However, the advent of quantum computing has introduced new challenges since quantum adversaries - equipped with the power of quantum queries - can find collisions much more efficiently. Brassard, Höyer and Tapp and Aaronson and Shi established that full-scale quantum adversaries require $\Theta(N^{1/3})$ queries to find a collision, prompting a need for longer hash outputs, which impacts efficiency in terms of the key lengths needed for security.

This paper explores the implications of quantum attacks in the Noisy-Intermediate Scale Quantum (NISQ) era. In this work, we investigate three different models for NISQ algorithms and achieve tight bounds for all of them: (1) A hybrid algorithm making adaptive quantum or classical queries but with a limited quantum query budget, or (2) A quantum algorithm with access to a noisy oracle, subject to a dephasing or depolarizing channel, or (3) A hybrid algorithm with an upper bound on its maximum quantum depth; i.e., a classical algorithm aided by low-depth quantum circuits.

In fact, our results handle all regimes between NISQ and full-scale quantum computers. Previously, only results for the pre-image search problem were known for these models by Sun and Zheng, Rosmanis, Chen, Cotler, Huang and Li while nothing was known about the collision finding problem.

Along with our main results, we develop an information-theoretic framework for recording query transcripts of quantum-classical algorithms. The main feature of this framework is that it allows us to record queries in two incompatible bases - classical queries in the standard basis and quantum queries in the Fourier basis - consistently. We call the framework the hybrid compressed oracle as it naturally interpolates between the classical way of recording queries and the compressed oracle framework of Zhandry for recording quantum queries.

Hudoba proposed a public key encryption (PKE) scheme and conjectured its security to be based on the Planted Clique problem. In this note, we show that this scheme is not secure. We do so by devising an efficient algorithm for the even neighbor independent set problem proposed by Hudoba. This leaves open the possibility of building PKE based on Planted Clique.

EdDSA, standardized by both IRTF and NIST, is a variant of the well-known Schnorr signature based on Edwards curves, and enjoys the benefit of statelessly and deterministically deriving nonces (i.e., it does not require reliable source of randomness or state continuity). Recently, NIST calls for multi-party threshold EdDSA signatures in one mode of deriving nonce statelessly and deterministically and verifying such derivation via zero-knowledge (ZK) proofs. Multi-party full-threshold EdDSA signatures in the dishonest-majority malicious setting have the advantage of strong security guarantee, and specially cover the two-party case. However, it is challenging to translate the stateless and deterministic benefit of EdDSA to the multi-party setting, as no fresh randomness is available for the protocol execution.

We present the notion of information-theoretic message authenticated codes (IT-MACs) over groups in the multi-verifier setting, and adopt the recent pseudorandom correlation function (PCF) to generate IT-MACs statelessly and deterministically. Furthermore, we generalize the two-party IT-MACs-based ZK protocol by Baum et al. (Crypto'21) into the multi-verifier setting, which may be of independent interest. Together with multi-verifier extended doubly-authenticated bits (mv-edabits) with errors, we design a multi-verifier zero-knowledge (MVZK) protocol to derive nonces statelessly and deterministically. Building upon the MVZK protocol, we propose a stateless deterministic multi-party EdDSA signature, tolerating all-but-one malicious corruptions. Compared to the state-of-the-art multi-party EdDSA signature by Garillot et al. (Crypto'21), we improve communication cost by a factor of $61\times$, at the cost of increasing computation cost by about $2.25\times$ and requiring three extra rounds.

The iMessage PQ3 protocol is an end-to-end encrypted messaging protocol designed for exchanging data in long-lived sessions between two devices. It aims to provide classical and post-quantum confidentiality for forward secrecy and post-compromise secrecy, as well as classical authentication. Its initial authenticated key exchange is constructed from digital signatures plus elliptic curve Diffie–Hellman and post-quantum key exchanges; to derive per-message keys on an ongoing basis, it employs an adaptation of the Signal double ratchet that includes a post-quantum key encapsulation mechanism. This paper presents the cryptographic details of the PQ3 protocol and gives a reductionist security analysis by adapting the multi-stage key exchange security analysis of Signal by Cohn-Gordon et al. (J. Cryptology, 2020). The analysis shows that PQ3 provides confidentiality with forward secrecy and post-compromise security against both classical and quantum adversaries, in both the initial key exchange as well as the continuous rekeying phase of the protocol.

Recent work has introduced the "Quantum-Computation Classical-Communication" (QCCC) (Chung et. al.) setting for cryptography. There has been some evidence that One Way Puzzles (OWPuzz) are the natural central cryptographic primitive for this setting (Khurana and Tomer). For a primitive to be considered central it should have several characteristics. It should be well behaved (which for this paper we will think of as having amplification, combiners, and universal constructions); it should be implied by a wide variety of other primitives; and it should be equivalent to some class of useful primitives. We present combiners, correctness and security amplifica- tion, and a universal construction for OWPuzz. Our proof of security amplification uses a new and cleaner version construction of EFI from OWPuzz (in comparison to the result of Khurana and Tomer) that generalizes to weak OWPuzz and is the most technically involved section of the paper. It was previously known that OWPuzz are implied by other primitives of interest including commitments, symmetric key encryp- tion, one way state generators (OWSG), and therefore pseudorandom states (PRS). However we are able to rule out OWPuzz’s equivalence to many of these primitives by showing a black box separation between general OWPuzz and a restricted class of OWPuzz (those with efficient verification, which we call EV − OWPuzz). We then show that EV − OWPuzz are also implied by most of these primitives, which separates them from OWPuzz as well. This separation also separates extending PRS from highly compressing PRS answering an open question of Ananth et. al.

This paper introduces the first adaptively secure streaming functional encryption (sFE) scheme for P/Poly. sFE stands as an evolved variant of traditional functional encryption (FE), catering specifically to contexts with vast and/or dynamically evolving data sets. sFE is designed for applications where data arrives in a streaming fashion and is computed on in an iterative manner as the stream arrives. Unlike standard FE, in sFE: (1) encryption is possible without knowledge of the full data set, (2) partial decryption is possible given only a prefix of the input. Guan, Korb, and Sahai introduced this concept in their recent publication [CRYPTO 2023], where they constructed an sFE scheme for P/Poly using a compact standard FE scheme for the same. However, their sFE scheme only achieved semi-adaptive-function-selective security, which constrains the adversary to obtain all functional keys prior to seeing any ciphertext for the challenge stream. This limitation severely limits the scenarios where sFE can be applied, and therefore fails to provide a suitable theoretical basis for sFE. In contrast, the adaptive security model empowers the adversary to arbitrarily interleave requests for functional keys with ciphertexts related to the challenge stream. Guan, Korb, and Sahai identified achieving adaptive security for sFE as the key question left open by their work. We resolve this open question positively by constructing an adaptively secure sFE construction from indistinguishability obfuscation for P/Poly and injective PRGs. By combining our work with that of Jain, Lin, and Sahai [STOC 2021, EUROCRYPT 2022], we obtain the first adaptively secure sFE scheme for P/Poly based on sub-exponential hardness of well-studied computational problems

Inspired by range-check trick from recent Latticefold paper we construct elliptic-curve based IVC capable of simulating non-native arithmetic efficiently.

We explain the general principle (which can be applied to both Protostar and Hypernova), and describe the Wrongfield ARithmetic for Protostar folding in details.

Our construction supports circuits over mutilple non-native fields simultaneously and allows interfacing between them using range-checked elements.

WARPfold can be used to warp between different proof systems and construct folding schemes over curves not admitting a dual partner (such as BLS12-381).

FuLeeca is a signature scheme submitted to the recent NIST call for additional signatures. It is an efficient hash-and-sign scheme based on quasi-cyclic codes in the Lee metric and resembles the lattice-based signature Falcon. FuLeeca proposes a so-called concentration step within the signing procedure to avoid leakage of secret-key information from the signatures. However, FuLeeca is still vulnerable to learning attacks, which were first observed for lattice-based schemes. We present three full key-recovery attacks by exploiting the proximity of the code-based FuLeeca scheme to lattice-based primitives. More precisely, we use a few signatures to extract an $n/2$-dimensional circulant sublattice of the given length-$n$ code, that still contains the exceptionally short secret-key vector. This significantly reduces the classical attack cost and, in addition, leads to a full key recovery in quantum-polynomial time. Furthermore, we exploit a bias in the concentration procedure to classically recover the full key for any security level with at most 175,000 signatures in less than an hour.

The Nostradamus attack was originally proposed as a security vulnerability for a hash function by Kelsey and Kohno at EUROCRYPT 2006. It requires the attacker to commit to a hash value y of an iterated hash function H. Subsequently, upon being provided with a message prefix P, the adversary’s task is to identify a suffix S such that H(P||S) equals y. Kelsey and Kohno demonstrated a herding attack requiring $O(\sqrt{n}\cdot 2^{2n/3})$ evaluations of the compression function of H, where n represents the output and state size of the hash, placing this attack between preimage attacks and collision searches in terms of complexity. At ASIACRYPT 2022, Benedikt et al. transform Kelsey and Kohno’s attack into a quantum variant, decreasing the time complexity from $O(\sqrt{n}\cdot 2^{2n/3})$ to $O(\sqrt[3]{n}\cdot 2^{3n/7})$. At ToSC 2023, Zhang et al. proposed the first dedicated Nostradamus attack on AES-like hashing in both classical and quantum settings. In this paper, we have made revisions to the multi-target technique incorporated into the meet-in-the-middle automatic search framework. This modification leads to a decrease in time complexity during the online linking phase, effectively reducing the overall attack time complexity in both classical and quantum scenarios. Specifically, we can achieve more rounds in the classical setting and reduce the time complexity for the same round in the quantum setting.

In this paper, we extend the applicability of differential meet- in-the-middle attacks, proposed at Crypto 2023, to truncated differen- tials, and in addition, we introduce three new ideas to improve this type of attack: we show how to add longer structures than the original pa- per, we show how to improve the key recovery steps by introducing some probability in them, and we combine this type of attacks with the state- test technique, that was introduced in the context of impossible differ- ential attacks. Furthermore, we have developed a MILP-based tool to automate the search for a truncated differential-MITM attack with op- timized overall complexity, incorporating some of the proposed improve- ments. Thanks to this, we can build the best known attacks on the cipher CRAFT, reaching 23 rounds against 21 previously; we provide a new at- tack on 23-round SKINNY-64-192, and we improve the best attacks on SKINNY-128-384.

The Institute of Software Chinese Academy of Sciences (ISCAS) is looking for two postdoctoral researchers in post-quantum cryptography under Prof. Zhenfeng Zhang's team. The roles involve designing, analyzing, and implementing post-quantum cryptographic algorithms and protocols.

Candidates should have a Ph.D. in a related field and proven expertise in areas like lattice-based, multivariable polynomial-based, hash-based, code-based, or isogeny-based cryptography. A strong publication record and the ability to work collaboratively are essential. Excellent programming skills and knowledge of provable security theories are preferred.

Responsibilities include conducting high-level research, publishing findings, collaborating with team members, and participating in academic and industry events. The positions offer an annual pre-tax salary of 500,000 to 700,000 CNY (approx. 80,000 to 100,000 USD) and are based in Beijing. English proficiency is required; Chinese is not.

Applicants should send a CV with publications, a research statement, and at least two recommendation letters. Apply by July 30, 2024, for full consideration. This opportunity allows you to contribute to the advancement of cryptography at a leading Chinese research institution.

Closing date for applications:

Contact: Dr. Long Chen (Email:chenlong@iscas.ac.cn)

More information: https://people.ucas.ac.cn/~zfzhang

We are looking for a self-motivated post-doc in Homomorphic Encryption supported under ARC Discovery project. The project is planned to start in July 2024 and for three years. The candidate is required to have a PhD qualification in relevant research fields in cryptography, mathematics or related fields. Please send your updated CV and related documents to the contact below.

Closing date for applications:

Contact: Steven Duong

In view of its ongoing development, the CRYPTO group of the University of Versailles St-Quentin-en-Yvelines (France) invites applications for the following full-time position.

A tenured Professor faculty position (“Professeur des universités”) is open to highly qualified candidates who are committed to a career in research and teaching. Preference will be given to candidates with very strong research achievements in one or several of the areas related to the general fields of cryptology and information security.

Responsibilities include research leadership and dissemination, supervision of doctoral students, development of national or international research projects, and strong commitment to teaching at undergraduate or graduate level.

IMPORTANT NOTE: Except for candidates who are currently “Maître de conférences” in France and hold an HDR diploma (“Habilitation à diriger des recherches”), a “Qualification aux fonctions de professeur des universités” certificate from the french “Conseil National des Universités” is usually required to apply. However candidates who already hold a tenured professor (or equivalent) position may in some cases be exempted from this certificate.

Closing date for applications:

Contact: Louis Goubin, Full Professor, head of the "Cryptology and Information Security" group

e-mail: louis.goubin (at) uvsq.fr

More information: https://www.galaxie.enseignementsup-recherche.gouv.fr/ensup/ListesPostesPublies/ANTEE/2024_1/0781944P/FOPC_0781944P_4338.pdf

The Cryptography and Privacy Engineering Group (ENCRYPTO) @CS Department @Technical University of Darmstadt offers a fully funded position as Doctoral Researcher (Research Assistant/PhD Student) in Cryptography and Privacy Engineering to be filled as soon as possible and initially for 3 years with the possibility of extension.

Job description:

You'll work in the collaborative research center CROSSING funded by the German Research Foundation (DFG). In our project E4 Compiler for Privacy-Preserving Protocols, we build compilers to automatically generate optimized MPC protocols for privacy-preserving applications. See https://encrypto.de/CROSSING for details. As PhD@ENCRYPTO, you primarily focus on your research aiming to publish&present the results at top venues.

We offer:

We demonstrate that privacy is efficiently protectable in real-world applications via cryptographic protocols. Our open and international working environment facilitates excellent research in a sociable team. TU Darmstadt is a top research university for IT security, cryptography and CS in Europe. Darmstadt is a very international, livable and well-connected city in the Rhine-Main area around Frankfurt.

Your profile:

• Completed Master's degree (or equivalent) at a top university with excellent grades in IT security, computer science, or a similar area.
• Extensive knowledge in applied cryptography/IT security and very good software development skills. Knowledge in cryptographic protocols (ideally MPC) is a plus.
• Experience and interest to engage in teaching.
• Self-motivated, reliable, creative, can work independently, and striving to do excellent research.
• Our working language is English: Able to discuss/write/present scientific results in English. German is beneficial but not required.

Application deadline:Apr 8, 2024. Later applications are considered.

Closing date for applications:

Contact: Thomas Schneider (application@encrypto.cs.tu-darmstadt.de)

More information: https://encrypto.de/2024-CROSSING

We are looking for a strong candidate that wants to pursue a PhD on privacy-preserving machine learning at Monash University (a world top 50 university) in the vibrant city of Melbourne, Australia (frequently ranked among the top 10 cities to live in the world).

Closing date for applications:

Contact: Rafael Dowsley (rafael.dowsley@monash.edu)

The Journal of Cryptology will have a Topical Collection on “Modern Zero-Knowledge Protocols”.

The submission deadline has been extended to July 1st 2024 and the CFP is available at the URL: https://iacr.org/jofc/TopicalCollection-mzkp.html

As an ISO/IEC standard, the hash function RIPEMD-160 has been used to generate the Bitcoin address with SHA-256. However, due to the complex double-branch structure of RIPEMD-160, the best collision attack only reaches 36 out of 80 steps of RIPEMD-160, and the best semi-free-start (SFS) collision attack only reaches 40 steps. To improve the 36-step collision attack proposed at EUROCRYPT 2023, we explored the possibility of using different message differences to increase the number of attacked steps, and we finally identified one choice allowing a 40-step collision attack. To find the corresponding 40-step differential characteristic, we re-implement the MILP-based method to search for signed differential characteristics with SAT/SMT. As a result, we can find a colliding message pair for 40-step RIPEMD-160 in practical time, which significantly improves the best collision attack on RIPEMD-160. For the best SFS collision attack published at ToSC 2019, we observe that the bottleneck is the probability of the right-branch differential characteristics as they are fully uncontrolled in the message modification. To address this issue, we utilize our SAT/SMT-based tool to search for high-probability differential characteristics for the right branch. Consequently, we can mount successful SFS collision attacks on 41, 42 and 43 steps of RIPEMD-160, thus significantly improving the SFS collision attacks. In addition, we also searched for a 44-step differential characteristic, but the differential probability is too low to allow a meaningful SFS collision attack.

The SHA-2 family including SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 and SHA512/256 is a U.S. federal standard pub- lished by NIST. Especially, there is no doubt that SHA-256 is one of the most important hash functions used in real-world applications. Due to its complex design compared with SHA-1, there is almost no progress in collision attacks on SHA-2 after ASIACRYPT 2015. In this work, we retake this challenge and aim to significantly improve collision attacks on the SHA-2 family. First, we observe from many existing attacks on SHA-2 that the current advanced tool to search for SHA-2 characteristics has reached the bottleneck. Specifically, longer differential characteristics could not be found, and this causes that the collision attack could not reach more steps. To address this issue, we adopt Liu et al.’s MILP-based method and implement it with SAT/SMT for SHA-2, where we also add more techniques to detect contradictions in SHA-2 characteristics. This answers an open problem left in Liu et al.’s paper to apply the technique to SHA-2. With this SAT/SMT-based tool, we search for SHA-2 charac- teristics by controlling its sparsity in a dedicated way. As a result, we successfully find the first practical semi-free-start (SFS) colliding message pair for 39-step SHA-256, improving the best 38-step SFS collision attack published at EUROCRYPT 2013. In addition, we also report the first practical free-start (FS) collision attack on 40-step SHA-224, while the previously best theoretic 40-step attack has time complexity 2110. More- over, for the first time, we can mount practical and theoretic collision attacks on 28-step and 31-step SHA-512, respectively, which improve the best collision attack only reaching 27 steps of SHA-512 at ASIACRYPT 2015. In a word, with new techniques to find SHA-2 characteristics, we have made some notable progress in the analysis of SHA-2 after the major achievements made at EUROCRYPT 2013 and ASIACRYPT 2015.

Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a ``nice" sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.

In this paper, we present a new type of algebraic attack that applies to many recent arithmetization-oriented families of permutations, such as those used in Griffin, Anemoi, ArionHash, and XHash8, whose security relies on the hardness of the constrained-input constrained-output (CICO) problem. We introduce the FreeLunch approach: the monomial ordering is chosen so that the natural polynomial system encoding the CICO problem already is a Gröbner basis. In addition, we present a new dedicated resolution algorithm for FreeLunch systems of complexity lower than applicable state-of-the-art FGLM algorithms. We show that the FreeLunch approach challenges the security of fullround instances of Anemoi, Arion and Griffin. We confirm these theoretical results with experimental results on those three permutations. In particular, using the FreeLunch attack combined with a new technique to bypass 3 rounds of Griffin, we recover a CICO solution for 7 out of 10 rounds of Griffin in less than four hours on one core of AMD EPYC 7352 (2.3GHz).