International Association
for Cryptologic Research

RIPEMD-160 and SHA-256 are two hash functions used to generate the bitcoin address. In particular, RIPEMD-160 is an ISO/IEC standard and SHA-256 has been widely used in the world. Due to their complex designs, the progress to find (semi-free-start) collisions for the two hash functions is slow. Recently at EUROCRYPT 2023, Liu et al. presented the first collision attack on 36 steps of RIPEMD-160 and the first MILP-based method to find collision-generating signed differential characteristics. We continue this line of research and implement the MILP-based method with a SAT/SMT-based method. Furthermore, we observe that the collision attack on RIPEMD-160 can be improved to 40 steps with different message differences. We have practically found a colliding message pair for 40-step RIPEMD-160 in 16 hours with 115 threads. Moreover, we also report the first semi-free-start (SFS) colliding message pair for 39-step SHA-256, which can be found in about 3 hours with 120 threads. These results update the best (SFS) collision attacks on RIPEMD-160 and SHA-256. Especially, we have made some progress on SHA-256 since the last update on (SFS) collision attacks on it at EUROCRYPT 2013, where the first practical SFS collision attack on 38-step SHA-256 was found.

Fuzzy extractors (FE) are cryptographic primitives that establish a shared secret between two parties who have similar samples of a random source, and can communicate over a public channel. An example for this is that Alice has a stored biometric at a server and wants to have authenticated communication using a new reading of her biometric on her device. Reusability and robustness of FE, respectively, guarantee that security holds when FE is used with multiple samples, and the communication channel is tamperable. Fuzzy extractors have been studied in information theoretic and computational setting. Contributions of this paper are two-fold. First, we define a strongly robust and reusable FE that combines the strongest security requirements of FEs, and give three constructions. Construction 1 has computational security, and Constructions 2 and 3 provide information theoretic (IT) security, in our proposed model. Construction 1 provides a solution to the open question of Canetti et al. (Eurocrypt 2014), by achieving robustness and reusability (post-quantum) security in standard model for their construction. Constructions 2 and 3 offer a new approach to the construction of IT-secure FE. Construction 3 is the first robust and reusable FE with IT-security without assuming random oracle. Our robust FEs use a new IT-secure MAC with security against key-shift attack which is of independent interest. Our constructions are for structured sources which for Construction 1, matches Canetti et al.’s source. We then use our Construction 1 for biometric authentication using iris data. We use a widely used iris data set to find the system parameters of the construction for the data set, and implement it. We compare our implementation with an implementation of Canetti et al.’s reusable FE on the same data set, showing the cost of post-quantum security without using random oracle, and robustness in standard model.

Transaction fee mechanism design is a new decentralized mechanism design problem where users bid for space on the blockchain. Several recent works showed that the transaction fee mechanism design fundamentally departs from classical mechanism design. They then systematically explored the mathematical landscape of this new decentralized mechanism design problem in two settings: in the plain setting where no cryptography is employed, and in a cryptography-assisted setting where the rules of the mechanism are enforced by a multi-party computation protocol. Unfortunately, in both settings, prior works showed that if we want the mechanism to incentivize honest behavior for both users as well as miners (possibly colluding with users), then the miner revenue has to be zero. Although adopting a relaxed, approximate notion of incentive compatibility gets around this zero miner-revenue limitation, the scaling of the miner revenue is nonetheless poor.

In this paper, we show that if we make a mildly stronger reasonable-world assumption than prior works, we can circumvent the known limitations on miner revenue, and design auctions that generate optimal miner revenue. We also systematically explore the mathematical landscape of transaction fee mechanism design under the new reasonable-world and demonstrate how such assumptions can alter the feasibility and infeasibility landscape.

We introduce the notion of a quantum trapdoor function. This is an efficiently computable unitary that takes as input a "public" quantum state and a classical string $x$, and outputs a quantum state. This map is such that (i) it is hard to invert, in the sense that it is hard to recover $x$ given the output state (and many copies of the public state), and (ii) there is a classical trapdoor that allows efficient inversion. We show that a quantum trapdoor function can be constructed from any quantum-secure one-way function. A direct consequence of this result is that, assuming just the existence of quantum-secure one-way functions, there exist: (i) a public-key encryption scheme with a quantum public key, and (ii) a two-message key-exchange protocol, assuming an appropriate notion of a quantum authenticated channel.

This paper presents a correct-by-construction method of designing an FHE model based on the automated program verifier Dafny. We model FHE operations from the ground up, including fundamentals like GCD, coprimality, Montgomery multiplications, and polynomial operations, etc., and higher level optimizations such as Residue Number System (RNS) and Number Theoretic Transform (NTT). The fully formally verified FHE model serves as a reference design for both software stack development and hardware design, and verification efforts. Open-sourcing our FHE Dafny model with modular arithmetic libraries to GitHub is in progress.

The implemented consensus protocol of Ethereum, Gasper, has an hybrid design: it combines a protocol that allows dynamic participation among validators, called LMD-GHOST, and a finality gadget on top, called Casper. This design has been motivated and formalized by Neu, Tas, and Tse (S&P 2021) through the introduction of the ebb-and-flow class of protocols, which are protocols with two confirmation rules that output two ledgers, one that provides liveness under dynamic participation (and synchrony), LMD-GHOST, and one that provides safety even under network partitions, Casper.

Currently, Gasper takes between 64 and 95 slots to finalize blocks. Because of that, a significant portion of the chain is susceptible to reorgs. The possibility to capture MEV (Maximum Extractable Value) through such reorgs can then disincentivize honestly following the protocol, breaking the desired correspondence of honest and rational behavior. Moreover, the relatively long time to finality forces users to choose between economic security and faster transaction confirmation. This motivates the study of the so-called single slot finality protocols: consensus protocols that finalize a block in each slot and, more importantly, that finalize the block proposed at a given slot within such slot.

In this work we propose a simple, non-blackbox protocol that combines a synchronous dynamically available protocol with a finality gadget, resulting in a secure ebb-and-flow protocol that can finalize one block per slot, paving the way to single slot finality within Ethereum. Importantly, the protocol we present can finalize the block proposed in a slot, within such slot.

Dynamic participation has recently become a key requirement to devise permissionless consensus protocols, as it adds a degree of robustness to events that include portions of participants going offline, preserving safety and liveness of such dynamically available protocols. This notion, formalized by Pass and Shi (ASIACRYPT 2017) with the sleepy model, has been implicitly adopted to model several blockchain protocols such as, for example, the Ethereum's consensus protocol, Gasper.

Neu, Tas, and Tse (S&P 2021) show that LMD-GHOST, the dynamic availability component of Gasper, is actually not secure even in a context of full-participation, i.e., with all the validators online. Mitigations have shortly after been developed to cope with its problems, but the resulting protocol still falls short of achieving dynamic availability, motivating the research of more secure dynamically available protocols.

In this work we present RLMD-GHOST, a synchronous dynamically available protocol that does not lose safety during bounded periods of asynchrony. This protocol results appealing especially for practical systems, where strict synchrony assumptions might not always hold, contrary to what is generally assumed with standard synchronous protocols. Moreover, we introduce the generalized sleepy model, in which our results will be proved. This model takes up from the original sleepy model presented by Pass and Shi and extends it with more generalized and stronger constraints in the corruption and sleepiness power of the adversary. This allows us to explore a broad space of dynamic participation regimes which falls between complete dynamic participation and no dynamic participation, i.e., with every participant online, offering a foundation for the analysis of dynamic available protocols.

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:

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

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

The hash function RIPEMD-160 is an ISO/IEC standard and is being used to generate the bitcoin address together with SHA-256. Despite the fact that many hash functions in the MD-SHA hash family have been broken, RIPEMD-160 remains secure and the best collision attack could only reach up to 34 out of 80 rounds, which was published at CRYPTO 2019. In this paper, we propose a new collision attack on RIPEMD-160 that can reach up to 36 rounds with time complexity $2^{64.5}$. This new attack is facilitated by a new strategy to choose the message differences and new techniques to simultaneously handle the differential conditions on both branches. Moreover, different from all the previous work on RIPEMD-160, we utilize a MILP-based method to search for differential characteristics, where we construct a model to accurately describe the signed difference transitions through its round function. As far as we know, this is the first model targeting the signed difference transitions for the MD-SHA hash family. Indeed, we are more motivated to design this model by the fact that many automatic tools to search for such differential characteristics are not publicly available and implementing them from scratch is too time-consuming and difficult. Hence, we expect that this can be an alternative easy tool for future research, which only requires to write down some simple linear inequalities.

This paper gives new constructions of two-round multi-signatures and threshold signatures for which security relies solely on either the hardness of the (plain) discrete logarithm problem or the hardness of RSA, in addition to assuming random oracles. Their signing protocol is partially non-interactive, i.e., the first round of the signing protocol is independent of the message being signed.

We obtain our constructions by generalizing the most efficient discrete- logarithm based schemes, MuSig2 (Nick, Ruffing, and Seurin, CRYPTO ’21) and FROST (Komlo and Goldberg, SAC ’20), to work with suitably defined linear hash functions. While the original schemes rely on the stronger and more controversial one-more discrete logarithm assumption, we show that suitable instantiations of the hash functions enable security to be based on either the plain discrete logarithm assumption or on RSA. The signatures produced by our schemes are equivalent to those obtained from Okamoto’s identification schemes (CRYPTO ’92).

More abstractly, our results suggest a general framework to transform schemes secure under OMDL into ones secure under the plain DL assumption and, with some restrictions, under RSA.

BBS signatures were implicitly proposed by Boneh, Boyen, and Shacham (CRYPTO ’04) as part of their group signature scheme, and explicitly cast as stand-alone signatures by Camenisch and Lysyanskaya (CRYPTO ’04). A provably secure version, called BBS+, was then devised by Au, Susilo, and Mu (SCN ’06), and is currently the object of a standardization effort which has led to a recent RFC draft. BBS+ signatures are suitable for use within anonymous credential and DAA systems, as their algebraic structure enables efficient proofs of knowledge of message-signature pairs that support partial disclosure.

BBS+ signatures consist of one group element and two scalars. As our first contribution, we prove that a variant of BBS+ producing shorter signatures, consisting only of one group element and one scalar, is also secure. The resulting scheme is essentially the original BBS proposal, which was lacking a proof of security. Here we show it satisfies, under the q-SDH assumption, the same provable security guarantees as BBS+. We also provide a complementary tight analysis in the algebraic group model, which heuristically justifies instantiations with potentially shorter signatures. Furthermore, we devise simplified and shorter zero-knowledge proofs of knowledge of a BBS message-signature pair that support partial disclosure of the message. Over the BLS12-381 curve, our proofs are 896 bits shorter than the prior proposal by Camenisch, Drijvers, and Lehmann (TRUST ’16), which is also adopted by the RFC draft.

Finally, we show that BBS satisfies one-more unforgeability in the algebraic group model in a scenario, arising in the context of credentials, where the signer can be asked to sign arbitrary group elements, meant to be commitments, without seeing their openings.

Oblivious RAM (ORAM) allows a client to outsource storage to a remote server while hiding the data access pattern from the server. Many ORAM designs have been proposed to reduce the computational overhead and bandwidth blowup for the client. A recent work, Onion Ring ORAM (CCS'19), is able to achieve $O(1)$ bandwidth blowup in the online phase using fully homomorphic encryption (FHE) techniques. However, it requires a computationally expensive client-side offline phase to do so. Furthermore, it is a stateful construction, which means that the client has to maintain a state of the database locally. We present Panacea: a novel design of ORAM based on FHE techniques, that is non-interactive and stateless, achieves $O(1)$ bandwidth blowup, and does not require an expensive offline phase for the client to perform; in that sense, our design is the first of its kind among other ORAM designs. To provide the client with such performance benefits, our design pushes all of expensive computations to the resourceful server. We additionally show how to boost the server performance significantly using probabilistic batch codes at the cost of only 1.5x in additional bandwidth blowup and 3x expansion in server storage. Our experimental results show that our design, with the employment of this batching technique, is practical in terms of server computation overhead as well. Specifically, for a database size of $2^{19}$, it takes only $1.16$ seconds of amortized computation time for a server to respond to a query. As a result of our client's statelessness, low computational overhead and practical computational overhead with the server, our design is ideal to be deployed as a cloud-based privacy-preserving storage outsourcing solution.

A privacy pool enables clients to deposit units of a cryptocurrency into a shared pool where ownership of deposited currency is tracked via a system of cryptographically hidden records. Clients may later withdraw from the pool without linkage to previous deposits. Some privacy pools also support hidden transfer of currency ownership within the pool. In August 2022, the U.S. Department of Treasury sanctioned Tornado Cash, the largest Ethereum privacy pool, on the premise that it enables illicit actors to hide the origin of funds, citing its usage by the DPRK-sponsored Lazarus Group to launder over \$455 million dollars worth of stolen cryptocurrency. This ruling effectively made it illegal for U.S. persons/institutions to use or accept funds that went through Tornado Cash, sparking a global debate among privacy rights activists and lawmakers. Against this backdrop, we present Derecho, a system that institutions could use to request cryptographic attestations of fund origins rather than naively rejecting all funds coming from privacy pools. Derecho is a novel application of proof-carrying data, which allows users to propagate allowlist membership proofs through a privacy pool's transaction graph. Derecho is backwards-compatible with existing Ethereum privacy pool designs, adds no significant overhead in gas costs, and costs users only a few seconds to produce attestations.

The NIST, in its recent competition on quantum-resilient confidentiality primitives, requested the submission of exclusively KEMs. The task of KEMs is to establish secure session keys that can drive, amongst others, public key encryption and TLS-like secure channels. In this work we test the KEM abstraction in the context of constructing cryptographic schemes that are not subsumed in the PKE and secure channels categories. We find that, when used to construct a key transport scheme or when used within a secure combiner, the KEM abstraction imposes certain inconvenient limits, the settling of which requires the addition of auxiliary symmetric primitives.

We hence investigate generalizations of the KEM abstraction that allow a considerably simplified construction of the above primitives. In particular, we study VKEMs and KDFEMs, which augment classic KEMs by label inputs, encapsulation handle outputs, and key derivation features, and we demonstrate that they can be transformed into KEM combiners and key transport schemes without requiring auxiliary components. We finally show that all four finalist KEMs of the NIST competition are effectively KDFEMs. Our conclusion is that only very mild adjustments are necessary to significantly increase their versatility.

The advent of quantum computers has generated a wave of interest for post-quantum cryptographic schemes, as a replacement for currently used cryptographic primitives. In this context, lattice-based cryptography has emerged as the leading paradigm to build post-quantum cryptography. However, all viable replacements of the classical Diffie-Hellman key exchange require additional rounds of interactions, thus failing to achieve all the benefits of this protocol. Although earlier work has shown that lattice-based Non-Interactive Key Exchange (NIKE) is theoretically possible, it has been considered too inefficient for real-life applications.

In this work, we provide the first evidence against this folklore belief. We construct a practical lattice-based NIKE whose security is based on the standard module learning with errors (M-LWE) problem in the quantum random oracle model. Our scheme is obtained in two steps: (i) A passively-secure construction that achieves a strong notion of correctness, coupled with (ii) a generic compiler that turns any such scheme into an actively secure one. To substantiate our efficiency claim, we present an optimised implementation of our construction in Rust and Jasmin, demonstrating its applicability to real-world scenarios. For this we obtain public keys of approximately 220 KBs and the computation of shared keys takes than 12 million cycles on an Intel Skylake CPU at a post-quantum security level of more than 120 bits.

Event date: 23 March 2023
Submission deadline: 25 March 2023
Notification: 25 April 2023

Event date: 2 July to 8 July 2023
Submission deadline: 5 March 2023
Notification: 23 April 2023

As part of an experienced team in security and software, you will contribute to the development of security features for future generation of sustainable IoT applications leveraging distributed architectures, edge AI capabilities and advanced cryptography (e.g. post quantum, threshold cryptography). You will be working closely with a diverse team of engineers and researchers, and you will take a leading role in transforming a vision into tangible IPs.

Your responsibilities

• Implement cryptography and security primitives for embedded devices.
• Develop Proof of concepts based on advanced cryptography topics.
• Harden the security modules against side channel attacks, software attacks and other relevant threats.
• Adopt a holistic approach to design robust (end to end) security features.
• Propose innovative security IPs and challenge them against state of the art and review them with peers.
• Build demonstrators and share results/knowledge with your colleagues.
• Continuously keep aware of the state of the art.
• Contribute to the supervision of interns.

Your profile
You are a PhD graduate or an MSc graduate with >=2 years experience. You have background in applied cryptography or embedded security and experience in embedded development. You are motivated to progress within applied cryptography and embedded security. Programming languages: C, Python. ML frameworks, VHDL would be an advantage.

Closing date for applications:

Contact: To apply, please follow the link to the job description by clicking on the job title above. (If not working, paste https://www.csem.ch/en/jobs/cryptography-engineer to your browser.)

More information: https://www.csem.ch/en/jobs/cryptography-engineer

We study the complexity of two-party secure arithmetic computation where the goal is to evaluate an arithmetic circuit over a finite field $F$ in the presence of an active (aka malicious) adversary. In the passive setting, Applebaum et al. (Crypto 2017) constructed a protocol that only makes a *constant* (amortized) number of field operations per gate. This protocol uses the underlying field $F$ as a black box, makes black-box use of (standard) oblivious transfer, and its security is based on arithmetic analogs of well-studied cryptographic assumptions. We present an actively-secure variant of this protocol that achieves, for the first time, all the above features. The protocol relies on the same assumptions and adds only a minor overhead in computation and communication.

Along the way, we construct a highly-efficient Vector Oblivious Linear Evaluation (VOLE) protocol and present several practical and theoretical optimizations, as well as a prototype implementation. Our most efficient variant can achieve an asymptotic rate of $1/4$ (i.e., for vectors of length $w$ we send roughly $4w$ elements of $F$), which is only slightly worse than the passively-secure protocol whose rate is $1/3$. The protocol seems to be practically competitive over fast networks, even for relatively small fields $F$ and relatively short vectors. Specifically, our VOLE protocol has 3 rounds, and even for 10K-long vectors, it has an amortized cost per entry of less than 4 OT's and less than 300 arithmetic operations. Most of these operations (about 200) can be pre-processed locally in an offline non-interactive phase. (Better constants can be obtained for longer vectors.) Some of our optimizations rely on a novel intractability assumption regarding the non-malleability of noisy linear codes that may be of independent interest.

Our technical approach employs two new ingredients. First, we present a new information-theoretic construction of Conditional Disclosure of Secrets (CDS) and show how to use it in order to immunize the VOLE protocol of Applebaum et al. against active adversaries. Second, by using elementary properties of low-degree polynomials, we show that, for some simple arithmetic functionalities, one can easily upgrade Yao's garbled-circuit protocol to the active setting with a minor overhead while preserving the round complexity.

In this work we apply the Type-Safe (TS) generic group model, recently introduced by Zhandry (2022), to the more general setting of group actions and extend it to the universal composability (UC) framework of Canetti (2000). We then relax this resulting model, that we call UC-TS, to define an algebraic action framework (UC-AA), where the adversaries can behave algebraically, similarly to the algebraic group model (AGM), but for group actions. Finally, we instantiate UC-AA with isogeny-based assumptions, obtaining the Explicit-Isogeny model, UC-EI, and show that, under certain assumptions, UC-EI is less restricting that UC-AGM. We demonstrate the utility of our definitions by proving UC-EI security for the passive-secure protocol described by Lai et al. (2021), hence providing the first concretely efficient two-round isogeny-based OT protocol in the random oracle model against malicious adversaries.