International Association
for Cryptologic Research

We are oferring a fully funded PhD scholarship for a student to join our group on reinforcement learning and decision making under uncertainty more generally, at the University of Neuchatel, Switzerland. We are particularly interested in candidates with a strong mathematical and research interest in the following fields e

1. Theory of differential privacy.
2. Algorithms for differentially private machine learning.
3. Algorithms for fairness in machine learning.
4. Interactions between machine learning and game theory.
5. Inference of human models of fairness or privacy.

Overall, our group works on reinforcement learning, decision making under uncertainty, fairness and differential privacy. The student will also have the opportunity to visit and work with other group members at the University of Oslo, Norway and Chalmers University of Technology, Sweden.

• Starting date 1 Februrary 2022 or soon afterwards.
• Application deadline 30 November 2021.

Closing date for applications:

Contact: Christos Dimitrakakis

More information: https://sites.google.com/site/christosdimitrakakis/positions

Authentication constitutes the foundation and vertebrae of all security properties. It is the procedure in which communicating parties prove their identities to each other, and generally establish and derive secret keys to enforce other services, such as confidentiality, data integrity, non-repudiation, and availability. PUFs (Physical Unclonable Functions) has been the subject of many subsequent publications on lightweight, lowcost, and secure-by-design authentication protocols. This has turned our attention to investigate the most recent PUF-based authentication protocols for IoT. In [1], we reviewed the security of some PUF-based authentication protocols that were proposed between 2016 and October 2020, and drew important security lessons to consider by future authentication protocol designers. In this paper, we extend our previous work by reviewing the security of fifteen PUF-based authentication protocols that were recently published during the past two years (2020 and 2021). We first provide the necessary background on PUFs and how they are used for authentication. Then, we analyze the security of these authentication protocols to identify and report common security issues and design flaws. We draw lessons and recommendations for future authentication protocol designers

Performance in hardware has typically played a significant role in differentiating among leading candidates in cryptographic standardization efforts. Winners of two past NIST cryptographic contests (Rijndael in case of AES and Keccak in case of SHA-3) were ranked consistently among the two fastest candidates when implemented using FPGAs and ASICs. Hardware implementations of cryptographic operations may quite easily outperform software implementations for at least a subset of major performance metrics, such as latency, number of operations per second, power consumption, and energy usage, as well as in terms of security against physical attacks, including side-channel analysis. Using hardware also permits much higher flexibility in trading one subset of these properties for another. This paper presents high-speed hardware architectures for four lattice-based CCA-secure Key Encapsulation Mechanisms (KEMs), representing three NIST PQC finalists: CRYSTALS-Kyber, NTRU (with two distinct variants, NTRU-HPS and NTRU-HRSS), and Saber. We rank these candidates among each other and compare them with all other Round 3 KEMs based on the data from the previously reported work.

Adversaries using quantum computers can employ new attacks on cryptography that are not possible with classical computers. Grover's search algorithm, a well-known quantum algorithm, can reduce the search complexity of $O(2^n)$ to $\sqrt{2^n}$ for symmetric key cryptography using an $n$-bit key. To apply the Grover search algorithm, the target encryption process must be implemented as a quantum circuit. In this paper, we present optimized quantum circuits for Korean block ciphers based on ARX architectures. We adopt the optimal quantum adder and design in parallel way with only a few trade-offs between quantum resources. As a result, we provide a performance improvement of 78\% in LEA, 85\% in HIGHT, and 70\% in CHAM in terms of circuit depth, respectively. Finally, we estimate the cost of the Grover key search for Korean block ciphers and evaluate the post-quantum security based on the criteria presented by NIST.

Hash-based signature schemes are a class of post-quantum algorithms usually built upon one-time signature (OTS) solutions via hash-trees. The benefits of such schemes include small key sizes, efficient processing and the fact that they are simple to implement using a regular hash algorithm. In addition, their security properties are quite well understood, since they rely basically on the pre-image or collision resistance of the underlying hash function. Among the existing OTS schemes, W-OTS+ is among the most popular. One reason for such popularity is that the OTS public key can be recovered from the signature itself, which facilitates the construction of a multi-time signature scheme using Merkle trees. On the other hand, signature generation and verification in W-OTS+ take roughly the same time, which is not ideal for applications where each signature is expected to be verified several times, as in software stores, PKI certificate validation, and secure boot. It is also inconvenient when the devices that verify signatures have lower computational power than the signers. In such scenarios, it is desirable to design signature schemes enabling faster verification, even if such speed-ups come at the expense of a slower signature generation procedure. With this goal in mind, we hereby present and evaluate a novel OTS scheme, called z-OTS. The main interest of z-OTS is that it preserves all benefits of W-OTS+, but provides faster signature verification at the cost of a (not much) slower signature generation procedure. For example, for signature sizes equivalent to W-OTS+ with Winternitz parameter w=4, our simulations show that verification can be 30.3% faster with z-OTS, while key and signature generation become, respectively, 53.7% and 137.5% slower. Larger w leads to even more expressive gains in the verification procedure, besides providing lower overheads when generating keys and signatures.

Homomorphic encryption (HE), especially the CKKS scheme, can be extremely challenging to use. The EVA language and compiler (Dathathri et al., PLDI 2020) was an attempt at addressing this challenge. EVA allows a developer to express their encrypted computation in a simple form with a Python-integrated language called PyEVA. It then compiles the program into an executable form by inserting operations such as relinearization and rescaling, applying optimizations, and choosing encryption parameters with the objective of minimizing execution time. Compiled programs can be executed with a parallelizing back-end against a library of HE primitives.

Our work improves upon the EVA toolchain in several ways: changes to the Python front-end make writing PyEVA programs more natural, while a rework of EVA's C++ APIs makes writing new passes easier. We also implement two new optimizations, common subexpression elimination and reduction balancing, which we show allow users to write simpler and more modular PyEVA programs.

We argue that the abstraction EVA provides is insufficient to resolve some common usability challenges. For example, managing vectors of arbitrary size is non-trivial. To resolve these problems, we demonstrate how building a library of commonly used data structures and functions is simple in PyEVA. EVA's automation allows writing very concise code, which gets fused and optimized together with the user program. We create the beginnings of an EVA Extension Library (EXL), that provides vector and matrix classes and a collection of common statistical functions, to demonstrate the power of this approach.

A Posteriori Openable Public Key Encryptions (APOPKE) allow any user to generate a constant-size key that decrypts the messages they have sent over a chosen period of time. As an important feature, the period can be dynamically chosen after the messages have been sent. This primitive was introduced in 2016 by Bultel and Lafourcade. They also defined the Chosen-Plaintext Attack (CPA) security for APOPKE, and designed a scheme called GAPO, which is CPA secure in the random oracle model. In this paper, we formalize the Chosen-Ciphertext Attack (CCA) security for APOPKE, then we design a scheme called CHAPO (for CHosen-ciphetext attack resistant A Posteriori Openable encryption), and we prove its CCA security in the standard model. CHAPO is approximately twice as efficient as GAPO and is more generic. We also give news applications, and discuss the practical impact of its CCA security.

In this work we consider the following question: What is the cost of security for multi-party protocols? Specifically, given an insecure protocol where parties exchange (in the worst case) $\Gamma$ bits in $N$ rounds, is it possible to design a secure protocol with communication complexity close to $\Gamma$ and $N$ rounds? We systematically study this problem in a variety of settings and we propose solutions based on the intractability of different cryptographic problems. For the case of two parties we design an interaction-preserving compiler where the number of bits exchanged in the secure protocol approaches $\Gamma$ and the number of rounds is exactly $N$, assuming the hardness of standard problems over lattices. For the more general multi-party case, we obtain the same result assuming either (i) an additional round of interaction or (ii) the existence of extractable witness encryption and succinct non-interactive arguments of knowledge. As a contribution of independent interest, we construct the first multi-key fully homomorphic encryption scheme with message-to-ciphertext ratio (i.e., rate) of $1 - o(1)$, assuming the hardness of the learning with errors (LWE) problem. We view our work as a support for the claim that, as far as interaction and communication are concerned, one does not need to pay a significant price for security in multi-party protocols.

Integral attacks belong to the classical attack vectors against any given block ciphers. However, providing arguments that a given cipher is resistant against those attacks is notoriously difficult. In this paper, based solely on the assumption of independent round keys, we develop significantly stronger arguments than what was possible before: our main result is that we show how to argue that the sum of ciphertexts over any possible subset of plaintext is key-dependent, i.e., the non existence of integral distinguishers.

This paper studies quantitative relationships between privacy, verifiability, accountability, and coercion-resistance of voting protocols. We adapt existing definitions to make them better comparable with each other and determine which bounds a certain requirement on one property poses on some other property. It turns out that, in terms of proposed definitions, verifiability and accountability do not necessarily put constraints on privacy and coercion-resistance. However, the relations between these notions become more interesting in the context of particular attacks. Depending on the assumptions and the attacker's goal, voter coercion may benefit from a too weak as well as too strong verifiability.

Erasure coding is a key tool to reduce the space and communication overhead in fault-tolerant distributed computing. State-of-the-art distributed primitives, such as asynchronous verifiable information dispersal (AVID), reliable broadcast (RBC), multi-valued Byzantine agreement (MVBA), and atomic broadcast, all use erasure coding.

This paper introduces an erasure coding proof (ECP) system, which allows the encoder to prove succinctly and non-interactively that an erasure-coded fragment is consistent with a constant-sized commitment to the original data block. Each fragment can be verified independently of the other fragments.

Our proof system is based on polynomial commitments, with new batching techniques that may be of independent interest. To illustrate the benefits of our ECP system, we show how to build the first AVID protocol with optimal message complexity, word complexity, and communication complexity.

Mix-networks were first proposed by Chaum in the late 1970s -- early 1980s as a general tool for building anonymous communication systems. Classical mix-net implementations rely on standard public key primitives (e.g. ElGamal encryption) that will become vulnerable when a sufficiently powerful quantum computer will be built. Thus, there is a need to develop quantum-resistant mix-nets. This paper focuses on the application case of electronic voting where the number of votes to be mixed may reach hundreds of thousands or even millions. We propose an improved architecture for lattice-based post-quantum mix-nets featuring more efficient zero-knowledge proofs while maintaining established security assumptions. Our current implementation scales up to 100000 votes, still leaving a lot of room for future optimisation.

All-or-nothing transforms (AONTs) were originally defined by Rivest as bijections from $s$ input blocks to $s$ output blocks such that no information can be obtained about any input block in the absence of any output block. Numerous generalizations and extensions of all-or-nothing transforms have been discussed in recent years, many of which are motivated by diverse applications in cryptography, information security, secure distributed storage, etc. In particular, $t$-AONTs, in which no information can be obtained about any $t$ input blocks in the absence of any $t$ output blocks, have received considerable study. In this paper, we study three generalizations of AONTs that are motivated by applications due to Pham et al. and Oliveira et al. We term these generalizations rectangular, range, and restricted AONTs. Briefly, in a rectangular AONT, the number of outputs is greater than the number of inputs. A range AONT satisfies the $t$-AONT property for a range of consecutive values of $t$. Finally, in a restricted AONT, the unknown outputs are assumed to occur within a specified set of "secure" output blocks. We study existence and non-existence and provide examples and constructions for these generalizations. We also demonstrate interesting connections with combinatorial structures such as orthogonal arrays, split orthogonal arrays, MDS codes and difference matrices.

G-Merkle (GM) (PQCrypto 2018) is the first hash-based group signature scheme where it was stated that multi-tree approaches are not applicable, thus limiting the maximum number of supported signatures to $2^{20}$. DGM (ESORICS 2019) is a dynamic and revocable GM-based group signature scheme that utilizes a computationally expensive puncturable encryption for revocation and requires interaction between verfiers and the group manager for signature verification. In this paper, we propose GMMT, a hash-based group signature scheme that provides solutions to the aforementioned challenges of the two schemes. GMMT builds on GM and adopts a multi-tree construction that constructs new GM trees for new signing leaves assignment while keeping the group public key unchanged. Compared to a single GM instance which enables $2^{20}$ signature, GMMT allows growing the multi-tree structure adaptively to support $2^{64}$ signatures under the same public key. Moreover, GMMT has a revocation mechanism that attains linkable anonymity of revoked signatures and has a logarithmic verfication computational complexity compared to the linear complexity of DGM. The group manager in GMMT requires storage that is linear in the number of members while the corresponding storage in DGM is linear in the number of signatures supported by the system. Concretely, for a system that supports $2^{64}$ signatures with $2^{15}$ members and provides 256-bit security, the required storage of the group manager is 1 MB (resp. $10^{8.7}$ TB) in GMMT(resp. DGM).

Group Merkle (GM) (PQCrypto 2018) and Dynamic Group Merkle (DGM) (ESORICS 2019) are recent proposals for post-quantum hash-based group signature schemes. They are designed as generic constructions that employ any stateful Merkle hash-based signature scheme. XMSS-T (PKC 2016, RFC8391) is the latest stateful Merkle hash-based signature scheme where (almost) optimal parameters are provided. In this paper, we show that the setup phase of both GM and DGM does not enable drop-in instantiation by XMSS-T which limits both designs in employing earlier XMSS versions with sub-optimal parameters which negatively affects the performance of both schemes. Thus, we provide a tweak to the setup phase of GM and DGM to overcome this limitation and enable the adoption of XMSS-T. Moreover, we analyze the bit security of DGM when instantiated with XMSS-T and show that it is susceptible to multi-target attacks because of the parallel Signing Merkle Trees (SMT) approach. More precisely, when DGM is used to sign 264 messages, its bit security is 44 bits less than that of XMSS-T. Finally, we provide a DGM variant that mitigates multi-target attacks and show that it attains the same bit security as XMSS-T.

SPHINCS+ is a stateless hash-based digital signature scheme and an alternate candidate in round 3 of the NIST Post- Quantum Cryptography standardization competition. Although not considered as a finalist because of its performance, SPHINCS+ may be considered for standardization by NIST after another round of evaluations. In this paper, we propose a Verfiable Obtained Random Subsets (v-ORS) generation mechanism which with one extra hash computation binds the message with the signing FORS instance (the underlying few-time signature algorithm). This enables SPHINCS+ to offer more security against generic attacks because the proposed modication restricts the ORS generation to use a hash key from the utilized signing FORS instance. Consequently, such a modication enables the exploration of dierent parameter sets for FORS to achieve better performance at the same security level. For instance, when using v-ORS, one parameter set for SPHINCS+-256s provides 82.9% reduction in the computation cost of FORS which leads to around 27% reduction in the number of hash calls of the signing procedure. Given that NIST has identfied the performance of SPHINCS+ as its main drawback, these results are a step forward in the path to standardization.

All instances of the semidirect key exchange protocol, a generalisation of the famous Diffie-Hellman key exchange protocol, satisfy the so-called ``telescoping equality''; in some cases, this equality has been used to construct an attack. In this report we present computational evidence suggesting that an instance of the scheme called `MOBS (Matrices Over Bitstrings)' is an example of a scheme where the telescoping equality has too many solutions to be a practically viable means to conduct an attack.

The 2021 Election for Directors of the IACR Board is now open.

You may vote as often as you wish now through November 16th using the Helios https://heliosvoting.org cryptographically-verifiable election system, but only your last vote will be counted.

Please see for a brief overview of how the Helios system works and https://www.iacr.org/elections/eVoting/ for information on the IACR decision to adopt Helios.

2021 members of the IACR (generally people who attended an IACR event in 2020) should shortly receive, or have already received, voting credentials from system@heliosvoting.org sent to their email address of record with the IACR. Please check your spam folder first if you believe that you haven't received the mail. Questions about this election may be sent to elections@iacr.org.

Information about the candidates can be found below and also at https://iacr.org/elections/2021/candidates.php.

The symmetric cryptographic primitive of choice today is AES. Its security is well-studied and hardware acceleration is available on a variety of platforms. Following the success of AES and the 128-bit AES-NI instructions for it, Intel has extended the x86 instruction set with Vector AES instructions. For the first time, we evaluate the performance impact that these instructions have on complex AES processing beyond bulk encryption. In particular, we focus on the area of secure multi-party computation where AES calls are either independent, allowing easy use of VAES for full speed-up, or where the AES calls are dependent on the results of previous AES evaluations. For independent calls, we evaluate the performance impact using Microsoft CrypTFlow2 and the EMP-OT library, both of which primarily use AES in counter mode. For dependent calls, we evaluate the performance impact using the ABY framework and the EMP-AGMPC framework. To get optimal efficiency from the hardware, enough independent calls need to be combined for each batch of AES executions. We identify such batches using a deferred execution technique paired with early execution to reduce non-locality issues and more static techniques using circuit depth and explicit gate independence. We present a performance and a modularity-focused technique to compute the AES operations efficiently while also immediately using the results and preparing the inputs. Using these manually implemented techniques, we achieve a performance improvement via VAES of up to 244% for ABY and of up to 28% for EMP-AGMPC. With our additional, alternative garbling schemes, we achieve up to 171% better performance for ABY through the use of VAES. Additionally, our evaluations show overall performance benefits of up to 24% for EMP-OT.

Password-authenticated key exchange (PAKE) is a major area of cryptographic protocol research and practice. Many PAKE proposals have emerged in the 30 years following the original 1992 Encrypted Key Exchange (EKE), some accompanied by new theoretical models to support rigorous analysis. To reduce confusion and encourage practical development, major standards bodies including IEEE, ISO/IEC and the IETF have worked towards standardizing PAKE schemes, with mixed results. Challenges have included contrasts between heuristic protocols and schemes with security proofs, and subtleties in the assumptions of such proofs rendering some schemes unsuitable for practice. Despite initial difficulty identifying suitable use cases, the past decade has seen PAKE adoption in numerous large-scale applications such as Wi-Fi, Apple's iCloud, browser synchronization, e-passports, and the Thread network protocol for Internet of Things devices. Given this backdrop, we consolidate three decades of knowledge on PAKE protocols, integrating theory, practice, standardization and real-world experience. We provide a thorough and systematic review of the field, a summary of the state-of-the-art, a taxonomy to categorize existing protocols, and a comparative analysis of protocol performance using representative schemes from each taxonomy category. We also review real-world applications, summarize lessons learned, and highlight open research problems related to PAKE protocols.