International Association
for Cryptologic Research

OpenPubkey makes a client-side modification to OpenID Connect so that an ID Token issued by an OpenID Provider commits to a user held public key. This transforms an ID Token into a certificate that cryptographically binds an OpenID Connect identity to a public key. We call such an ID Token, a PK Token. The user can then sign messages with their signing key and these signatures can be authenticated and attributed to the user’s OpenID Connect identity. This allows OpenPubkey to upgrade OpenID Connect from Bearer Authentication to Proof-of-Possession, eliminating trust assumptions in OpenID Connect and defeating entire categories of attacks present in OpenID Connect. OpenPubkey was designed to satisfy a decade-long need for this functionality. Prior to OpenPubkey, OpenID Connect did not have a secure way for users to sign statements under their OpenID identities.

OpenPubkey is transparent to users and OpenID Providers. An OpenID Provider can not even determine that OpenPubkey is being used. This makes OpenPubkey fully compatible with existing OpenID Providers. In fact a variant of OpenPubkey is currently deployed and used to authenticate signed messages and identities for users with accounts on Google, Microsoft, Okta, and Onelogin. OpenPubkey does not add new trusted parties to OpenID Connect and reduces preexisting trust assumptions. If used in tandem with our MFA-cosigner, OpenPubkey can maintain security even against a malicious OpenID Provider (the most trusted party in OpenID Connect).

An Ideal Cipher (IC) is a cipher where each key defines a random permutation on the domain. Ideal Cipher on a group has many attractive applications, e.g., the Encrypted Key Exchange (EKE) protocol for Password Authenticated Key Exchange (PAKE) [10], or asymmetric PAKE (aPAKE) [40, 36]. However, known constructions for IC on a group domain all have drawbacks, including key leakage from timing information [15], requiring 4 hash-onto-group operations if IC is an 8-round Feistel [27], and limiting the domain to half the group [12] or using variable-time encoding [56, 48] if IC is implemented via (quasi-) bijections from groups to bitstrings [40].

We propose an IC relaxation called a (Randomized) Half-Ideal Cipher (HIC), and we show that HIC on a group can be realized by a modified 2-round Feistel (m2F), at a cost of 1 hash-onto-group operation, which beats existing IC constructions in versatility and computational cost. HIC weakens IC properties by letting part of the ciphertext be non-random, but we exemplify that it can be used as a drop-in replacement for IC by showing that EKE [10] and aPAKE of [40] realize respectively UC PAKE and UC aPAKE even if they use HIC instead of IC. The m2F construction can also serve as IC domain extension, because m2F constructs HIC on domain D from an RO-indiferrentiable hash onto D and an IC on 2κ-bit strings, for κ a security parameter. One application of such extender is a modular lattice-based UC PAKE using EKE instantiated with HIC and anonymous lattice-based KEM.

Whereas theoretical attacks on standardized crypto primitives rarely lead to actual practical attacks, the situation is different for side-channel attacks. Improvements in the performance of side-channel attacks are of utmost importance.

In this paper, we propose a framework to be used in key-recovery side-channel attacks on CCA-secure post-quantum encryption schemes. The basic idea is to construct chosen ciphertext queries to a plaintext checking oracle that collects information on a set of secret variables in a single query. Then a large number of such queries is considered, each related to a different set of secret variables, and they are modeled as a low-density parity-check code (LDPC code). Secret variables are finally determined through efficient iterative decoding methods, such as belief propagation, using soft information. The utilization of LDPC codes offers efficient decoding, source compression, and error correction benefits. It has been demonstrated that this approach provides significant improvements compared to previous work by reducing the required number of queries, such as the number of traces in a power attack.

The framework is demonstrated and implemented in two different cases. On one hand, we attack implementations of HQC in a timing attack, lowering the number of required traces considerably compared to attacks in previous work. On the other hand, we describe and implement a full attack on a masked implementation of Kyber using power analysis. Using the ChipWhisperer evaluation platform, our real-world attacks recover the long-term secret key of a first-order masked implementation of Kyber-768 with an average of only 12 power traces.

The historical domain of information hiding is alternatively used nowadays for communication security. Maybe the oldest and certainly one of the most studied field that falls in this category is steganography. Within the current paper, we focus on image steganography techniques in the case of the JPEG format. We propose a corrected and optimized version of the J3 stegosystem which, to the best of our knowledge and as shown throughout the paper, may be considered a very good choice in terms of security and efficiency as compared to current solutions. We reconstruct the entire J3 algorithm (pre-processing, message insertion and extraction) and detail all the modifications. We also present implementation optimizations and cover all practical cases while still using the maximum image insertion capacity.

We are seeking highly motivated PhDs and post-docs to join the team.

Post-doc positions:
Responsibilities:

Conduct implementation on cutting-edge blockchain technologies and applications.

Develop innovative solutions and proof-of-concepts.

Design blockchain systems.

Collaborate with other team members to ensure successful delivery.
Requirements:

PhD in Computer Science, Electrical Engineering, or related field.

Sufficient knowledge of cryptography and blockchain technology.

Experience with programming languages such as Python, Rust, C++, and Solidity.

Knowledge of distributed systems and peer-to-peer networks.

Strong analytical and problem-solving skills.

Excellent communication and teamwork skills.

PhD positions:
Responsibilities:

Conduct research on cutting-edge cryptography, or AI technologies.

Develop innovative solutions for real-world applications.

Collaborate with national and international academic partners.

Deliver research works to top-tier conferences and journals.
Requirements:

MSc in Computer Science, Math, or related field.

Strong knowledge of AI, or cryptography.

Some experience with programming languages.

Strong analytical and problem-solving skills.

Great communication and teamwork.

Please send your CV, PhD/MSc transcripts, PhD/MSc certificate, English test certificate and a publication list to kaitai.liang@tudelft.nl.
We provide our PhDs and Post-Docs: (1) International academic and industrial collaborations, e.g., working with other top ranking universities, renown companies. (2) Opportunities of participating into various domestic and international cybersecurity projects. (3) Being trained to deliver world-leading research works and publish them to top-tier venues. (4) Flexible and supportive working surroundings. (5) Competitive salary and benefits package, relocation supports, summer and end-year bonus, free academic trainings.

Closing date for applications:

Contact: K. Liang (kaitai.liang@tudelft.nl)

In this work, we present a novel generic construction for a Distributed Key Generation (DKG) scheme. Our generic construction relies on three modular cryptographic building blocks. The first is an aggregatable Verifiable Secret Sharing (AgVSS) scheme, the second is a Non-Interactive Key Exchange (NIKE) scheme, and the third is a secure hash function. We give formal definitions for the AgVSS and NIKE schemes, as well as concrete constructions. The utility of this generic construction is flexibility; i.e., any aggregatable VSS and NIKE scheme can be employed, and the construction will remain secure.

To prove the security of our generic construction, we introduce formalized game-based notions of security for DKGs, building upon existing notions in the literature. However, these prior security notions either were presented informally, omitted important requirements, or assumed certain algebraic structure of the underlying scheme. Our security notions make no such assumption of underlying algebraic structure, and explicitly consider details such as participant consistency, communication patterns, and key validity. Further, our security notions imply simulatability with respect to a target key generation scheme without rewinding. Hence, any construction that is proven secure using our security notions additionally achieves UC security.

We then present STORM, a concrete instantiation of our generic construction that is secure in the discrete logarithm setting in the random oracle model. STORM is more efficient than related DKG schemes in the literature. Because of its simple design and composability, it is a practical choice for real-world settings and standardization efforts.

The growing popularity of cloud storage has brought attention to critical need for preventing information leakage from cloud access patterns. To this end, recent efforts have extended Oblivious RAM (ORAM) to the cloud environment in the form of Oblivious Store. However, its impracticality due to the use of probability encryption with fake accesses to obfuscate the access pattern, as well as the security requirements of conventional obliviousness designs, which hinder cloud interests in improving storage utilization by removing redundant data among cross-users, limit its effectiveness. Thus, we propose a practical Oblivious Store, PEO-Store, which integrates the obliviousness property into the cloud while removing redundancy without compromising security. Unlike conventional schemes, PEO-Store randomly selects a delegate for each client to communicate with the cloud, breaking the mapping link between a valid access pattern sequence and a specific client. Each client encrypts their data and shares it with selected delegates, who act as intermediaries with the cloud provider. This design leverages non-interactive zero-knowledge-based redundancy detection, discrete logarithm problem-based key sharing, and secure time-based delivery proof to protect access pattern privacy and accurately identify and remove redundancy in the cloud. The theoretical proof demonstrates that the probability of identifying the valid access pattern with a specific user is negligible in our design. Experimental results show that PEO-Store outperforms state-of-the-art methods, achieving an average throughput of up to 3 times faster and saving 74% of storage space.

In this short note, we describe a few implementation techniques that allow performing key pair generation for the Falcon and Hawk lattice-based signature schemes, and for the BAT key encapsulation scheme, in a fully constant-time way and without any use of floating-point operations. Our new code is faster than previously published implementations, especially when running on small embedded systems, and uses less RAM.

A secret-sharing scheme enables a dealer, holding a secret string, to distribute shares to parties such that only pre-defined authorized subsets of parties can reconstruct the secret. The collection of authorized sets is called an access structure. There is a huge gap between the best known upper-bounds on the share size of a secret-sharing scheme realizing an arbitrary access structure and the best known lower-bounds on the size of these shares. For an arbitrary $n$-party access structure, the best known upper-bound on the share size is $2^{O(n)}$. On the other hand, the best known lower-bound on the total share size is much smaller, i.e., $\Omega(n^2/\log (n))$ [Csirmaz, \emph{Studia Sci. Math. Hungar.}]. This lower-bound was proved more than 25 years ago and no major progress was made since.

In this paper, we study secret-sharing schemes for k-hypergraphs, i.e., for access structure where all minimal authorized sets are of size exactly $k$ (however, unauthorized sets can be larger). We consider the case where $k$ is small, i.e., constant or at most $\log (n)$. The trivial upper-bound for these access structures is $O(k\cdot \binom{n}{k})$ and this can be slightly improved. If there were efficient secret-sharing schemes for such $k$-hypergraphs (e.g., $2$-hypergraphs or $3$-hypergraphs), then we would be able to construct secret-sharing schemes for arbitrary access structure that are better than the best known schemes. Thus, understanding the share size required for $k$-hypergraphs is important. Prior to our work, the best known lower-bound for these access structures was $\Omega(n \log (n))$, which holds already for graphs (i.e., $2$-hypergraphs).

We improve this lower-bound, proving a lower-bound of $\Omega(n^{1-1/(k-1)}/k)$ for some explicit $k$-hypergraphs, where $3 \leq k \leq \log (n)$. For example, for $3$-hypergraphs we prove a lower-bound of $\Omega(n^{3/2})$. For $\log (n)$-hypergraphs, we prove a lower-bound of $\Omega(n^{2}/\log (n))$, i.e., we show that the lower-bound of Csirmaz holds already when all minimal authorized sets are of size $\log (n)$. Our proof is simple and shows that the lower-bound of Csirmaz holds for a simple variant of the access structure considered by Csirmaz.

A central problem in cryptanalysis is to find all the significant deviations from randomness in a given $n$-bit cryptographic primitive. When $n$ is small (e.g., an $8$-bit S-box), this is easy to do, but for large $n$, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems which are designed to have hidden trapdoors.

In this paper we consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box, and reduce the complexity of the best known techniques for finding all its significant differential and linear properties by a large factor of $2^{n/2}$. Our main new tool is the idea of using {\it surrogate differentiation}. In the context of finding differential properties, it enables us to simultaneously find information about all the differentials of the form $f(x) \oplus f(x \oplus \alpha)$ in all possible directions $\alpha$ by differentiating $f$ in a single arbitrarily chosen direction $\gamma$ (which is unrelated to the $\alpha$'s). In the context of finding linear properties, surrogate differentiation can be combined in a highly effective way with the Fast Fourier Transform. For $64$-bit cryptographic primitives, this technique makes it possible to automatically find in about $2^{64}$ time all their differentials with probability $p \geq 2^{-32}$ and all their linear approximations with bias $|p| \geq 2^{-16}$; previous algorithms for these problems required at least $2^{96}$ time. Similar techniques can be used to significantly improve the best known time complexities of finding related key differentials, second-order differentials, and boomerangs. In addition, we show how to run variants of these algorithms which require no memory, and how to detect such statistical properties even in trapdoored cryptosystems whose designers specifically try to evade our techniques.

Recent advancements in low-cost cryptography have converged upon the use of nanoscale level structural variances as sources of entropy that is unique to each device. Consequently, such delay-based Physically Unclonable Functions or (PUFs) have gained traction for several cryptographic applications. In light of recent machine learning (ML) attacks on delay-based PUFs, the common trend among PUF designers is to either introduce non-linearity using XORs or input transformations applied on the challenges in order to harden the security of delay-based PUFs. Such approaches make machine learning modelling attacks hard by destroying the linear relationship between challenge-response pairs of a PUF. However, we propose to perceive PUFs, which are fundamentally viewed as Boolean functional mapping, as a set of delay parameters drawn from normal distribution. Using this newfound perception, we propose an alternative attack strategy in this paper. We show that instead of trying to learn the exact functional relationship between challenge-response pairs from a PUF, one can search through the search space of all PUFs to find alternative PUF delay parameter set that exhibits similar behaviour as the target PUF. The core intuition behind this strategy is that one can consider a PUF as a set of stages wherein, depending on the corresponding input challenge bit, one of the several signals within a PUF's stage win a race condition. To utilize this idea, we develop a novel Particle Swarm Optimization based framework inspired by the biomimicry of amoebic reproduction. The proposed algorithm avoids the pitfalls of textbook Genetic Algorithms and demonstrates complete break of existing delay-based PUFs which are based on arbiter chains. More specifically, we are able to model higher-rder $k$-XOR PUF variants which are resistant to all-known ML modelling techniques, including $k=13, 15$ and $20$, without the knowledge of reliability values. In addition to that, we also model PUFs that incorporate input transformation, like variants of IPUF and LP-PUF. Furthermore, we take forward this idea across different search spaces in order to learn a higher order PUF using a lower order (and simpler) PUF architecture. This allows us to explore a novel class of attacks, including modelling a $k$-XOR PUF using a $(k-1)$-XOR PUF as well as bypassing input transformations based PUF designs.

In this paper, we present the DORCIS tool, which finds depth-optimized quantum circuit implementations for arbitrary 3- and 4-bit S-boxes. It follows up from the previous LIGHTER-R tool (which only works for 4-bit S-boxes) by extending it in multiple ways, on top of modifications that allow for depth optimization instead of gate cost optimization. LIGHTER-R only deals at the top-level (i.e., Toffoli gates), whereas DORCIS takes quantum decomposition (i.e., Clifford + T gates) into account. We match, if not surpass, other optimized quantum circuit implementations put forth in the other papers. Our tool is easy to use, and we also provide a simple interface to IBM's Qiskit.

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.