International Association
for Cryptologic Research

Eurocrypt 2023 will take place in Lyon, France on April 23-27, 2023.

The registration site is now open. To avoid late fees please register before March 30th.
https://eurocrypt.iacr.org/2023/registration.php

The goal of this research is to raise technical doubts regarding the usefulness of the repeated attempts by governments to curb Cryptography (aka the ``Crypto Wars''), and argue that they, in fact, cause more damage than adding effective control. The notion of {\em Anamorphic Encryption} was presented in Eurocrypt'22 for a similar aim. There, despite the presence of a Dictator who possesses all keys and knows all messages, parties can arrange a hidden ``{\it anamorphic}'' message in an otherwise indistinguishable from regular ciphertexts (wrt the Dictator).

In this work, we postulate a stronger cryptographic control setting where encryption does not exist (or is neutralized) since all communication is passed through the Dictator in, essentially, cleartext mode (or otherwise, when secure channels to and from the Dictator are the only confidentiality mechanism). Messages are only authenticated to assure recipients of the identity of the sender. We ask whether security against the Dictator still exists, even under such a~strict regime which allows only authentication (i.e., authenticated/ signed messages) to pass end-to-end, and where received messages are determined by/ known to the Dictator, and the Dictator also eventually gets all keys to verify compliance of past signing. To frustrate the Dictator, this authenticated message setting gives rise to the possible notion of anamorphic channels inside signature and authentication schemes, where parties attempt to send undetectable secure messages (or other values) using signature tags which are indistinguishable from regular tags. We define and present implementation of schemes for anamorphic signature and authentication; these are applicable to existing and standardized signature and authentication schemes which were designed independently of the notion of anamorphic messages. Further, some cornerstone constructions of the foundations of signatures, in fact, introduce anamorphism.

MIBS is a 32-round lightweight block cipher following a Feistel structure with the block length of 64-bit and the key length of 64 or 80 bits. In this paper, the properties of the key scheduling algorithm are investigated and lots of repeated bits among the different round keys are found. Moreover, the optimal guessing order of the unknown key bits is obtained by using the greedy algorithm. At last, combined with the early abort technique, the differential cryptanalyses are improved to 15 rounds both of MIBS-64 and MIBS-80. For MIBS-64, the data complexity is $2^{59}$, and the time complexity is $2^{46.2}$ encryptions. For MIBS-80, the data complexity is $2^{59}$, and the time complexity is $2^{51.7}$ encryptions. The key scheduling algorithm of MIBS is similar to some other lightweight block ciphers, and we hope further similarities will help build better attacks for them as well.

GIFT-64 is a block cipher that has received a lot of attention from the community since its proposal in 2017. The attack on the highest number of rounds is a differential related-key attack on 26 rounds~\cite{DBLP:journals/tosc/SunWW21}. We studied this attack, in particular with respect to the generic framework for improving key recovery from~\cite{DBLP:conf/asiacrypt/BrollCFLN21}, and we realised that this framework, combined with an efficient parallel key guessing of interesting subsets of the key and a consequent list merging applied to the partial solutions, can improve the complexity of the attack. We propose two different trade-offs, as a result of the improved key-recovery. We believe that the techniques are quite generic and that it is possible to apply them to improve other differential attacks.

Over the years, a large number of attacks have been proposed against substitution boxes used in symmetric ciphers such as differential attacks, linear attacks, algebraic attacks, etc. In the Advanced Encryption Standard (AES) Block cipher, the substitution box is the only nonlinear component and thus it holds the weight of the cipher. This basically means that if an attacker is able to mount a successful attack on the substitution box of AES, the cipher is compromised. This research work aims to provide a solution for increasing cryptographic immunity of S-boxes against such attacks. A genetic algorithm based approach has been proposed to search for 8 × 8 balanced and bijective S-boxes that exhibit values of differential branch number, non-linearity, differential uniformity, count and length of cycles present and distance from strict avalanche criterion that are similar to or better than the AES S-box. An S-Box evaluation tool is also implemented to evaluate any S-boxes generated. S-box of AES is resistant to the crypt-analytic attacks. S-boxes constructed by the proposed algorithm have better cryptographic properties so they are also resistant to the crypt-analytic attacks. The strict avalanche criterion[11], which is based on completeness[22] and diffusion[5], is an essential property for any 8 × 8 S-box. Good diffusion means that a small change in the plaintext may influence the complete block after a small number of rounds. Therefore, a lower DSAC value is desirable to prevent vulnerabilities to attacks such as differential attacks. The DSAC is therefore used as the primary fitness criterion in this research work to search for S-boxes with better diffusion.

The Extended Access Control (EAC) protocol for authenticated key agreement is mainly used to secure connections between machine-readable travel documents (MRTDs) and inspection terminals, but it can also be adopted as a universal solution for attribute-based access control with smart cards. The security of EAC is currently based on the Diffie-Hellman problem, which may not be hard when considering quantum computers.

In this work we present PQ-EAC, a quantum-resistant version of the EAC protocol. We show how to achieve post-quantum confidentiality and authentication without sacrificing real-world usability on smart cards. To ease adoption, we present two main versions of PQ-EAC: One that uses signatures for authentication and one where authentication is facilitated using long-term KEM keys. Both versions can be adapted to achieve forward secrecy and to reduce round complexity. To ensure backwards-compatibility, PQ-EAC can be implemented using only Application Protocol Data Units (APDUs) specified for EAC in standard BSI TR-03110. Merely the protocol messages needed to achieve forward secrecy require an additional APDU not specified in TR-03110. We prove security of all versions in the real-or-random model of Bellare and Rogaway.

To show real-world practicality of PQ-EAC we have implemented a version using signatures on an ARM SC300 security controller, which is typically deployed in MRTDs. We also implemented PQ-EAC on a VISOCORE terminal for border control. We then conducted several experiments to evaluate the performance of PQ-EAC executed between chip and terminal under various real-world conditions. Our results strongly suggest that PQ-EAC is efficient enough for use in border control.

Herein, we propose an anonymous broadcast authentication (ABA) scheme to simultaneously control $10^9$ devices practically. We find a barrier to construct an ABA working with a larger number of devices.In a nutshell, there is a trilemma between (i) security, (ii) ciphertext length, and (iii) freedom in the target devices selection. For practical use, we propose ABAs with a ciphertext size of $O(\log N)$ where $N$ is the number of target devices while we impose a certain restriction on (iii). We provide an ABA template and instantiate it into specific schemes from the discrete logarithm problem (DLP) or the learning with errors (LWE) problem.

Existing Oblivious RAM protocols do not support the storage of data items of variable size in a non-trivial way. While the study of ORAM for items of variable size is of interest in and of itself, it is also motivated by the need for more performant and more secure Searchable Symmetric Encryption (SSE) schemes.

In this article, we introduce the notion of weighted ORAM, which supports the storage of blocks of different sizes. In a standard ORAM scheme, each data block has a fixed size $B$. In weighted ORAM, the size (or weight) of a data block is an arbitrary integer $w_i \in [1,B]$. The parameters of the weighted ORAM are entirely determined by an upper bound $B$ on the block size, and an upper bound $N$ on the total weight $\sum w_i$ of all blocks\textemdash regardless of the distribution of individual weights $w_i$. During write queries, the client is allowed to arbitrarily change the size of the queried data block, as long as the previous upper bounds continue to hold.

We introduce a framework to build efficient weighted ORAM schemes, based on an underlying standard ORAM satisfying a certain suitability criterion. This criterion is fulfilled by various Tree ORAM schemes, including Simple ORAM and Path ORAM. We deduce several instantiations of weighted ORAM, with very little overhead compared to standard ORAM. As a direct application, we obtain efficient SSE constructions with attractive security properties.

Electronic Medical Records (EMRs) have been utilized in plentiful medical institutions due to their superior convenience and low storage overhead. Nevertheless, it is difficult for medical departments with disparate management regulations to share EMRs through secure communication channels since sensitive EMRs are prone to be tampered with. Therefore, the EMRs should be encrypted before being outsourced to the network servers. Public key Encryption with Keyword Search (PEKS) has the ability for doctors to search encrypted EMRs, but traditional PEKS algorithms are susceptible to quantum computing attacks and without considering access control. To address the aforementioned issues, we proposed AAQ-PEKS scheme, named an attribute-based anti-quantum public-key encryption scheme with keyword search. Initially, based on the LWE hardness, we first introduce the attribute-based PEKS that can resist quantum attacks in E-health scenarios. Secondly, we combine Attribute-Based Encryption (ABE) into AAQ-PEKS to realize access control for sensitive EMRs. Thirdly, the computational security analysis illustrates that our scheme achieves correctness, Indistinguishability against Chosen Plaintext Attack (IND-CPA) and Indistinguishability against Chosen Keyword Attack (IND-CKA). Lastly, comprehensive performance evaluation in practice elaborates that our AAQ-PEKS is more efficient compared with other existing top-tier schemes. To conclude, our scheme has the characteristics of resisting quantum attacks and fine-grained access control for E-health scenarios.

Cryptographic hash functions map data of arbitrary size to a fixed size digest, and are one of the most commonly used cryptographic objects. As it is infeasible to design an individual hash function for every input size, variable-input length hash functions are built by designing and bootstrapping a single fixed-input length function that looks sufficiently random. To prevent trivial preprocessing attacks, applications often require not just a single hash function but rather a family of keyed hash functions.

The most well-known methods for designing variable-input length hash function families from a fixed idealized function are the Merkle-Damgård and Sponge designs. The former underlies the SHA-1 and SHA-2 constructions and the latter underlies SHA-3. Unfortunately, recent works (Coretti et al. EUROCRYPT 2018, Coretti et al. CRYPTO 2018) show non-trivial time-space tradeoff attacks for finding collisions for both. Thus, this forces a parameter blowup (i.e., efficiency loss) for reaching a certain desired level of security. We ask whether it is possible to build families of keyed hash functions which are provably resistant to any non-trivial time-space tradeoff attacks for finding collisions, without incurring significant efficiency costs.

We present several new constructions of keyed hash functions that are provably resistant to any non-trivial time-space tradeoff attacks for finding collisions. Our constructions provide various tradeoffs between their efficiency and the range of parameters where they achieve optimal security for collision resistance. Our main technical contribution is proving optimal security bounds for converting a hash function with a fixed-sized input to a keyed hash function with (potentially larger) fixed-size input. We then use this keyed function as the underlying primitive inside the standard MD and Merkle tree constructions. We strongly believe that this paradigm of using a keyed inner hash function in these constructions is the right one, for which non-uniform security has not been analyzed prior to this work.

A typical approach for scaling blockchains is to create bilateral, off-chain channels, known as payment/state channels, that can protect parties against cheating via on-chain collateralization. While such channels have been studied extensively, not much attention has been given to off-chain programmability, where the parties can agree to enforce arbitrary conditions over their payments without going on-chain. Such ability is especially important for scaling off-chain channels via the hub-and-spoke model, where each party establishes a channel with a highly available (but untrusted) hub without a priori knowledge about the type and conditions of its off-chain transactions.

We introduce the notion of a programmable payment channel (PPC) that allows two parties to agree on a smart contract off-chain specifying the conditions on which the transactions can happen. If either party violates any of the terms, the other party can later deploy the contract on-chain to receive a remedy as agreed upon in the contract. Specifically, our PPC supports programmable payments where only one party deposits to the agreed off-chain contract, enabling lightweight payments. We further show that any two-party contract (even ones with two party deposits) can be implemented with PPC, by a compiler and associated protocol, allowing the parties to use their pre-deposited on-chain collaterals for any off-chain interaction potentially not anticipated at the time of channel setup. We formalize and prove the security and correctness of our protocol under the UC framework. We implement our protocol on Ethereum using accumulators to achieve efficient concurrent programmable transactions and measure the gas overhead of a hash-time-lock PPC contract to be < 100K which can be amortized over many off-chain payments.

The Faculty of Science and the Leiden Institute of Advanced Computer Science (LIACS) are looking for a PhD Candidate in Privacy-Preserving Machine Learning to work with Assistant Professor Eleftheria Makri.

The successful applicant should be a motivated university graduate who is a top performer among his/her peers and has an excellent education and/or research track record proven by relevant experience, publications, etc. The applicant is expected to have:

MSc degree in Computer Science, Electrical Engineering, Cryptography, Applied Mathematics, or related field;

Solid background in Computer Science and Mathematics;

Good programming skills in e.g., Python, C, C++;

Experience with Machine Learning;

Excellent written and oral communication skills in English.

For more information about the position, please see: https://www.universiteitleiden.nl/vacatures/2023/kwartaal-1/23-124phd-candidate-privacy-preserving-machine-learning

Closing date for applications:

Contact: Eleftheria Makri: e.makri@liacs.leidenuniv.nl

More information: https://www.universiteitleiden.nl/vacatures/2023/kwartaal-1/23-124phd-candidate-privacy-preserving-machine-learning

We are looking for a Research Associate to contribute, in the frame of an EU funded project, to the research and the development of solutions in the area of security and privacy, with a special focus on distributed systems and blockchain security.

Required Skills and Experience

• Strong experience in system security and distributed systems
• Experience in blockchain technologies.
• Experience in cryptography
• Experience in software development with programming languages such as Python, Golang, Java, or C/C++
• Excellent interpersonal and communication skills in English

Our work ranges from foundational research and IPR creation to prototype development for NEC products and services.

The Security group (SEC) is considered one of the pioneers in Europe in the area of security and privacy R&D with its top researchers in the fields of cloud security, blockchain security, system security, and applied cryptography.

At NEC Laboratories Europe, we provide a collaborative, team-working environment that supports your career aspirations. Our working language is English. The position is initially limited to two years.

NEC Laboratories Europe is located in the beautiful city of Heidelberg, Germany. Home office schemes within the country may be offered. Heidelberg is an international and lively city with a large number of exciting cultural, entertainment, and outdoor activities.

Application deadline: March 27, 2023

For further detail and how to apply, see:

https://jobs.neclab.eu/jobs/openings/staff/NEC-NLE-2301-461-SEC-1-Research_Associate_%5b2301_461_SEC%5d.pdf

Closing date for applications:

Contact: Giorgia Marson

More information: https://jobs.neclab.eu/jobs/openings/staff/NEC-NLE-2301-461-SEC-1-Research_Associate_%5b2301_461_SEC%5d.pdf

Event date: 21 June to 22 June 2023
Submission deadline: 1 May 2023
Notification: 19 March 2023

Due to the completeness, reliability and zero-knowledge nature, the zero-knowledge proof is widely used to designed various protocols, including zero-knowledge authentication protocols. However, the existing zero-knowledge proof scheme cannot realize bidirectional authentication. In this paper, we design a series of bidirectional zero-knowledge protocols based on two new flavors of operations applicable to multiplicative cyclic group. The two notions are formally defined in this paper. We also provide some formal definitions and properties for the two notions. According to our definitions, any bounded polynomial function defined on multiplicative cyclic group has duality and mirror. Based on the two operations, we introduce and formally define dual commitment scheme and mirror commitment scheme. Besides, we provide two efficient constructions for dual commitment and mirror commitment respectively based on CDH assumption and RSA assumption, and named DCCDH, DCRSA, MCCDH and MCRSA respectively. We also provide the extended version supporting multiple messages in the appendix. Then, we design some efficient non-interactive as well as interactive zero-knowledge authentication protocols based on these commitments. The protocols allow two participants to submit commitments to each other so that they can achieve mutual zero-knowledge authentication only a communication initialization needed. Moreovere , similar to other commitment schemes, our schemes also can be widely used to construction of other schemes for cryptography, such as, verifiable secret sharing, zero-knowledge sets, credentials and content extraction signatures.

It is an important question to find constructions of quantum cryptographic protocols which rely on weaker computational assumptions than classical protocols. Recently, it has been shown that oblivious transfer and multi-party computation can be constructed from one-way functions, whereas this is impossible in the classical setting in a black-box way. In this work, we study the question of building quantum public-key encryption schemes from one-way functions and even weaker assumptions. Firstly, we revisit the definition of IND-CPA security to this setting. Then, we propose three schemes for quantum public-key encryption from one-way functions, pseudorandom function-like states with proof of deletion and pseudorandom function-like states, respectively.

The learning with errors (LWE) problem is one of the fundamental problems in cryptography and it has many applications in post-quantum cryptography. There are two variants of the problem, the decisional-LWE problem, and the search-LWE problem. LWE search-to-decision reduction shows that the hardness of the search-LWE problem can be reduced to the hardness of the decisional-LWE problem. We initiate a study of quantum search-to-decision reduction for the LWE problem and propose a reduction that satisfies sample-preserving. In sample-preserving reduction, it preserves all parameters even the number of instances. Especially, our quantum reduction invokes the distinguisher only $2$ times to solve the search-LWE problem, while classical reductions require a polynomial number of invocations. Furthermore, we give a way to amplify the success probability of the reduction algorithm. Our amplified reduction works with fewer LWE samples compared to the classical reduction that has a high success probability. Our reduction algorithm supports a wide class of error distributions and also provides a search-to-decision reduction for the learning parity with noise problem. In the process of constructing the search-to-decision reduction, we give a quantum Goldreich-Levin theorem over $\mathbb{Z}_q$ where $q$ is prime. In short, this theorem states that, if a hardcore predicate $a\cdot s \pmod q$ can be predicted with probability distinctly greater than $1/q$ with respect to a uniformly random $a\in\mathbb{Z}_q^n$, then it is possible to determine $s\in\mathbb{Z}_q^n$.

A \emph{witness map} deterministically maps a witness $w$ of some NP statement $x$ into computationally sound proof that $x$ is true, with respect to a public common reference string (CRS). In other words, it is a deterministic, non-interactive, computationally sound proof system in the CRS model. A \emph{unique witness map} (UWM) ensures that for any fixed statement $x$, the witness map should output the same \emph{unique} proof for $x$, no matter what witness $w$ it is applied to. More generally a \emph{compact witness map} (CWM) can only output one of at most $2^\alpha$ proofs for any given statement $x$, where $\alpha$ is some compactness parameter. Such compact/unique witness maps were proposed recently by Chakraborty, Prabhakaran and Wichs (PKC '20) as a tool for building tamper-resilient signatures, who showed how to construct UWMs from indistinguishability obfuscation (iO). In this work, we study CWMs and UWMs as primitives of independent interest and present a number of interesting connections to various notions in cryptography. \begin{itemize} \item First, we show that UWMs lie somewhere between witness PRFs (Zhandry; TCC '16) and iO -- they imply the former and are implied by the latter. In particular, we show that a relaxation of UWMs to the ``designated verifier (dv-UWM)'' setting is \emph{equivalent} to witness PRFs. Moreover, we consider two flavors of such dv-UWMs, which correspond to two flavors of witness PRFs previously considered in the literature, and show that they are all in fact equivalent to each other in terms of feasibility. \item Next, we consider CWMs that are extremely compact, with $\alpha = O(\log \kappa)$, where $\kappa$ is the security parameter. We show that such CWMs imply \emph{pseudo-UWMs} where the witness map is allowed to be \emph{pseudo-deterministic} -- i.e., for every true statement $x$, there is a unique proof such that, on any witness $w$, the witness map outputs this proof with $1-1/p(\lambda)$ probability, for a polynomial $p$ that we can set arbitrarily large. \item Lastly, we consider CWMs that are mildly compact, with $\alpha = p(\lambda)$ for some a-priori fixed polynomial $p$, independent of the length of the statement $x$ or witness $w$. Such CWMs are implied by succinct non-interactive arguments (SNARGs). We show that such CWMs imply NIZKs, and therefore lie somewhere between NIZKs and SNARGs. \end{itemize}

In a recent presentation, we promoted the use of 12-round instances of Keccak, collectively called “TurboSHAKE”, in post-quantum cryptographic schemes, but without defining them further. The goal of this note is to fill this gap: The definition of the TurboSHAKE family simply consists in exposing and generalizing the primitive already defined inside KangarooTwelve.

Zero-knowledge proof (ZKP) mixers are one of the most widely used blockchain privacy solutions, operating on top of smart contract-enabled blockchains. We find that ZKP mixers are tightly intertwined with the growing number of Decentralized Finance (DeFi) attacks and Blockchain Extractable Value (BEV) extractions. Through coin flow tracing, we discover that 205 blockchain attackers and 2,595 BEV extractors leverage mixers as their source of funds, while depositing a total attack revenue of 412.87M USD. Moreover, the US OFAC sanctions against the largest ZKP mixer, Tornado.Cash, have reduced the mixer’s daily deposits by more than 80%.

Further, ZKP mixers advertise their level of privacy through a so-called anonymity set size, which similarly to $k$-anonymity allows a user to hide among a set of $k$ other users. Through empirical measurements, we, however, find that these anonymity set claims are mostly inaccurate. For the most popular mixers on Ethereum (ETH) and Binance Smart Chain (BSC), we show how to reduce the anonymity set size on average by 27.34% and 46.02% respectively. Our empirical evidence is also the first to suggest a differing privacy-predilection of users on ETH and BSC.

State-of-the-art ZKP mixers are moreover interwoven with the DeFi ecosystem by offering anonymity mining (AM) incentives, i.e., users receive monetary rewards for mixing coins. However, contrary to the claims of related work, we find that AM does not necessarily improve the quality of a mixer’s anonymity set. Our findings indicate that AM attracts privacy-ignorant users, who then do not contribute to improving the privacy of other mixer users.