International Association
for Cryptologic Research

Competitions are widely viewed as the safest way to select cryptographic algorithms. This paper surveys procedures that have been used in cryptographic competitions, and analyzes the extent to which those procedures reduce security risks.

Cryptocurrencies and decentralized ledger technology has been widely adopted over the last decades. However, there isn’t yet a decentralized exchange that protects users’ privacy from end to end. In this paper, we construct the first ledger-based decentralized token exchange with strong privacy guarantees. We propose the first Decentralized Anonymous eXchange scheme (DAX scheme) based on automated market maker (AMM) and zkSNARK and present a formal definition of its security and privacy properties.

Homomorphic encryption (HE) is considered as one of the most important primitives for privacy-preserving applications. However, an efficient approach to evaluate both polynomial and non-polynomial functions on encrypted data is still absent, which hinders the deployment of HE to real-life applications. To address this issue, we propose a practical framework PEGASUS. PEGASUS can efficiently switch back and forth between a packed CKKS ciphertext and FHEW ciphertexts without decryption, allowing us to evaluate arithmetic functions efficiently on the CKKS side, and to evaluate look-up tables on FHEW ciphertexts. Our FHEW ! CKKS conversion algorithm is more practical than the existing methods. We improve the computational complexity from linear to sublinear. Moreover, the size of our conversion key is significantly smaller, e.g., reduced from 80 gigabytes to 12 megabytes. We present extensive benchmarks of PEGASUS, including sigmoid/ReLU/min/max/division, sorting and max-pooling. To further demonstrate the capability of PEGASUS, we developed two more applications. The first one is a private decision tree evaluation whose communication cost is about two orders of magnitude smaller than the previous HE-based approaches. The second one is a secure K-means clustering that is able to run on thousands of encrypted samples in minutes that outperforms the best existing system by 14  – 20. To the best of our knowledge, this is the first work that supports practical K-means clustering using HE in a single server setting.

$P_4$-free graphs-- also known as cographs, complement-reducible graphs, or hereditary Dacey graphs--have been well studied in graph theory. We introduce the graph properties of partitioning and covering the edges of a graph with the minimum number of $P_4$-free graphs, namely, the $P_4$-free partition and $P_4$-free cover numbers. We prove that computing these numbers is \npol-complete, even for bipartite graphs. We present bipartite graph constructions where these numbers are at least ${\epsilon N^{1-2\epsilon}}$, for $\epsilon\in\{1/3,1/4,1/5,\dotsc\}$, where $N$ is the number of vertices in each partite set. Finally, we upper bound these numbers for bipartite graphs encoding well-studied Boolean functions from circuit complexity, such as set intersection, set disjointness, and inequality.

Our work encodes joint probability distributions and Boolean functions as equivalent bipartite graphs and studies the $P_4$-free partition and cover numbers of these graphs. Leveraging this connection, we present representative applications of these graph properties and their estimates to information-theory and circuit complexity. For applications in information theory, we consider a system where a setup samples from a joint distribution and gives the participants, Alice and Bob, their portion from this joint sample. The objective of Alice and Bob is to non-interactively establish a shared key and extract the left-over entropy from their portion of the samples as independent private randomness. A genie, who observes the joint sample, provides an appropriate assistance to help Alice and Bob with their objective. Lower bounds to the minimum size of the genie's assistance translates into communication and cryptographic lower bounds. We show that (the $\log_2$ of) the $P_4$-free partition number of a graph encoding the joint distribution that the setup uses is equivalent to the size of the genie's assistance. Consequently, the joint distributions corresponding to the bipartite graphs constructed above with high $P_4$-free partition number correspond to joint distributions requiring more assistance from the genie.

As a representative application in communication complexity, we study communication complexity of non-deterministic protocols augmented by access to the equality oracle at the output. We show that (the $\log_2$ of) the $P_4$-free cover number of the bipartite graph encoding a Boolean function $f$ is equivalent to the minimum size of the non-deterministic input required by the parties (referred to as the communication complexity of $f$ in this model). Consequently, the functions corresponding to the bipartite graphs with high $P_4$-free cover number have high communication complexity. Furthermore, there are functions with communication complexity close to the \naive protocol where the non-deterministic input reveals the input of a party. Finally, the access to the equality oracle reduces the communication complexity of computing set intersection and disjointness by a constant factor in contrast to the model where parties do not have access to the equality oracle. In the case of computing the inequality function, we show an exponential reduction in the communication complexity.

Contemporary libraries and frameworks that make it possible to incorporate secure multi-party computation protocols and capabilities into production software systems and applications must sometimes deliver underlying capabilities (such as logical circuit synthesis) to new kinds of environments (such as web browsers or serverless cloud computing platforms). In order to illustrate some of the benefits of addressing this challenge by building a solution from the ground up that leverages the features of a contemporary and widely used programming language, we present an embedded domain-specific language that allows programmers to describe and synthesize logical circuits. Notably, this approach allows programmers to employ many of the language features and any of the programming paradigms supported by the host language. We illustrate this flexibility by considering two use cases: synthesizing circuits for relational operations and synthesizing circuits corresponding to the SHA-256 cryptographic hash function.

Delegation of signing rights can be useful to promote effective resource sharing and smooth cooperation among participants in distributed systems, and in many situations, we often need restricted delegation such as one-timeness and unlinkability rather than simple full delegation. Particularly, one-timesness cannot be achieved just by deploying cryptographic measures, and one needs to resort to some form of tamper-proofness or the assistance from external cloud servers for ``key-disabling''. In this work, we extend the latter such that a delegatee can sign a message without the delegator's involvement with the assumption that there exists at least one honest cloud server with secure erasure to achieve one-timeness. In this setting, if the delegator just shares their signing key between the delegatee and cloud servers, it may be problematic. It is because in the worst case, the delegator cannot know whether or not a signing key theft occurred because the signatures generated illegally are indistinguishable from the ones generated legally. To solve this, first we propose an efficient one-time delegation scheme of Okamoto-Schnorr signing. Further we combine the basic delegation scheme with anonymous credentials such that the delegator can detect the signing key theft even if one-time delegation is broken while also achieving unlinkability for both the delegator and cloud servers. Further we show its application to an e-cash scheme, which can prevent double-spending.

Polynomial multiplication is one of the most costly operations of ideal lattice-based cryptosystems. In this work, we study its optimization when one of the operand has coefficients close to 0. We focus on this structure since it is at the core of lattice-based Key Exchange Mechanisms submitted to the NIST call for post-quantum cryptography. In particular, we propose optimization of this operation for embedded devices by using a RSA/ECC coprocessor that provides efficient large-integer arithmetic. In this context, we compare Kronecker Substitution, already studied by Albrecht et al. in TCHES 2019, with two specific algorithms that we introduce: KSV, a variant of this substitution, and an adaptation of the schoolbook multiplication, denoted Shift&Add. All these algorithms rely on the transformation of polynomial multiplication to large-integer arithmetic. Then, thanks to these algorithms, existing coprocessors dedicated to large-integer can be re-purposed in order to speed-up post-quantum schemes. The efficiency of these algorithms depends on the component specifications and the cryptosystem parameters set. Thus, we establish a methodology to determine which algorithm to use, for a given component, by only implementing basic large-integer operations. Moreover, the three algorithms are assessed on a chip ensuring that the theoretical methodology matches with practical results. They are also compared to reference software implementations such as NTT or schoolbook multiplication.

Second-layer or off-chain protocols increase the throughput of permissionless blockchains by enabling parties to lock funds into smart-contracts and perform payments through peer-to-peer communication, only resorting to the smart-contracts for protection against fraud. Current protocols have fixed time periods during which participants can dispute any fraud attempts. However, current blockchains have limited transaction processing capacity, so a fixed dispute period will not always be sufficient to deter all fraudulent behaviour in an off-chain protocol. In this work, we describe how to set adaptive dispute periods that accommodate the congestion and capacity of the underlying blockchain. Adaptive dispute periods ensure that users retain the opportunity to dispute fraudulent behaviours during blockchain congestion, while increasing second-layer protocol efficiency by reducing dispute period lengths when the number of disputes is low. We describe a non-interactive argument system for setting adaptive dispute periods under the current Ethereum Virtual Machine, and discuss how to efficiently integrate built-in support for adaptive dispute periods in any blockchain. We empirically demonstrate that an adaptive-dispute second-layer protocol can handle a larger number of disputes and prevent more fraud than its non-adaptive counterparts even when users are slow to issue disputes, due to denial of service or blockchain congestion.

Due to the constant increase and versatility of IoT devices that should keep sensitive information private, Side-Channel Analysis (SCA) attacks on embedded devices are gaining visibility in the industrial field. The integration and validation of countermeasures against SCA can be an expensive and cumbersome process, especially for the less experienced ones, and current certification procedures require to attack the devices under test using multiple SCA techniques and attack vectors, often implying a high degree of complexity.

The goal of this paper is to ease one of the most crucial and tedious steps of profiling attacks i.e. the points of interest (POI) selection and hence assist the SCA evaluation process. To this end, we introduce the usage of Estimation of Distribution Algorithms (EDAs) in the SCA field in order to automatically tune the point of interest selection. We showcase our approach on several experimental use cases, including attacks on unprotected and protected AES implementations over distinct copies of the same device, dismissing in this way the portability issue.

In this work we describe a token-based solution to Contact Tracing via Distributed Point Functions (DPF) and, more generally, Function Secret Sharing (FSS). The key idea behind the solution is that FSS natively supports secure keyword search on raw sets of keywords without a need for processing the keyword sets via a data structure for set membership. Furthermore, the FSS functionality enables adding up numerical payloads associated with multiple matches without additional interaction. These features make FSS an attractive tool for lightweight privacy-preserving searching on a database of tokens belonging to infected individuals.

WARP is proposed by S. Banik et al. in SAC 2020. It is a 128-bit lightweight block cipher with 128-bit key. WARP is based on 32-nibble type-2 Generalised Feistel Network (GFN). It uses permutation over nibbles designed to optimize the security and efficiency. Designers have provided a lower bound for the number of differentially active S-boxes but detailed differential characteristics are not provided. In this paper, we discuss MILP based search technique and present differential characteristics for 18-round and 19-round WARP with probability of $2^{-122}$ and $2^{-132}$ respectively. To the best of our knowledge, these detailed differential characteristics for WARP are presented for the first time.

The Advanced Encryption Standard (AES) is the most widely used symmetric encryption algorithm. Its security is mainly based on the structure of the S-box. In this paper, we present a new way to create S-boxes for AES and exhibit an S-box with improved cryptographic properties such as Bit Independence Criterion (BIC), periodicity, algebraic complexity, Strict Avalanche Criterion (SAC) and Distance to SAC.

Private Information Retrieval (PIR) hides access patterns when several clients query a database held by one or more servers. Prior PIR schemes have achieved sublinear communication and computation by leveraging computational assumptions, federating trust among many servers, relaxing security to permit differentially private leakage, refactoring effort into a pre-processing stage to reduce online costs, or amortizing costs over a large batch of queries.

In this work, we present an efficient PIR protocol that combines all of the above techniques to achieve constant amortized communication and computation complexity in the size of the database, and is the first to scale to more than $10^5$ queries per second deployed on an AWS micro instance. Our protocol also builds upon a new secret sharing scheme that is both incremental and non-malleable, which may be of interest to a wider audience. We leverage differentially private leakage in order to provide better trade-offs between privacy and efficiency. Our protocol provides security up to abort against malicious adversaries that can corrupt all but one party.

The security in the quantum setting of a series of message authentication codes (MACs) with provable beyond-birthday-bound (BBB) security is analyzed in this paper, including SUM-ECBC, PolyMAC, PMAC_Plus, 3kf9 and some variants (2K-ECBC_Plus, GCM-SIV2, 1k-PMAC_Plus, 2K-PMAC_Plus, PMAC_TBC3k and 2kf9). All these MACs have a security proof up to $2^{2n/3}$ (even $2^{3n/4}$) queries assuming the block size of the underlying (tweakable) block cipher is $n$ bits. Given that the adversary can make quantum queries, we consider secret state recovery and partial key recovery attacks against these MACs. Both attacks lead to successful forgeries. For the first one, we apply Grover-meet-Simon algorithm to recover some secret states of SUM-ECBC, PolyMAC, PMAC_Plus, 3kf9 and so on. Our research shows this forgery attack costs at most $O(2^{n/2}n)$ quantum queries using at most $O(n^{2})$ qubits. For the second one, we apply Grover's algorithm to recover partial keys of PMAC_Plus, 3kf9, PMAC_TBC3k and so on. Our research shows this forgery attack costs $O(2^{m/2})$ quantum queries and $O(m+n^2)$ qubits assuming the size of one key is $m$ bits. As far as we know, these are the first quantum attacks against BBB MACs. Our results show that in the quantum setting their securities go back to birthday bounds.

We implement bootstrapping of RNS-CKKS on SEAL, a homomorphic encryption library released by Microsoft. And we measure the accuracy of encrypted data after bootstrapping for various parameters, which allows us to do more than thousands of homomorphic operations.

In this work, we present the first post-quantum secure Updatable Public-Key Encryption (UPKE) construction. UPKE has been proposed in the literature as a mechanism to improve the forward-secrecy and post-compromise security of secure messaging protocols, but the hardness of all existing constructions to date rely on discrete logarithm assumptions. We focus our assessment on isogeny-based cryptosystems due to their suitability for performing a potentially unbounded number of update operations, a practical requirement for secure messaging where user conversations can occur over months, if not years.

We begin by formalizing two UPKE variants presented in the literature as Symmetric and Asymmetric UPKE. At a fundamental level, these variants differ in how encryption and decryption keys are updated, and consequently impact the design and security model for quantum-safe constructions.

We demonstrate that Asymmetric UPKE cannot be instantiated using existing isogeny-based constructions. We then describe a SIDH-based Symmetric UPKE construction that is possible in theory but requires improving existing mathematical limitations before a practical implementation is possible. Finally, we present a CSIDH-based Symmetric UPKE construction that can be instantiated using a parameter set in which the class group structure is fully known to ensure efficient uniform sampling and canonical representation to prevent leakage of secret keys. We discuss several open problems which are applicable to any cryptosystem with similar requirements for continuous operations over elements in the secret domain.

Imagine that one or more non-colluding servers each holds a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrieval (PIR) schemes achieve polylogarithmic bandwidth per query, but require the server to perform linear computation per query, which is a deal breaker with respect to practical adoption.

Several recent works have shown, however, that by introducing a one-time, per-client, off-line preprocessing phase, an \emph{unbounded} number of client queries can be subsequently served with sublinear on-line computation time per query (and the cost of the preprocessing can be amortized over the unboundedly many queries). Unfortunately, existing preprocessing PIRs make undesirable tradeoffs to achieve sublinear online computation: they either require $\sqrt{n}$ or more bandwidth per query, which is asymptotically worse than classical PIR schemes, or they require the servers to store a linear amount state per client (or even per query), or require polylogarithmically many non-colluding servers.

We propose a novel 2-server preprocessing PIR scheme that achieves $\widetilde{O}(\sqrt{n})$ online computation per query, while preserving the polylogarithmic online bandwidth of classical PIR schemes. In our construction, each server stores only the original database and nothing extra, and each online query is served within a single round trip. Our construction relies on the standard LWE assumption. As an important stepping stone, we propose new, more generalized definitions for a cryptographic object called a Privately Puncturable Pseudorandom Set, and give novel constructions that depart significantly from prior approaches.

Suppose that $n$ players want to elect a random leader and they communicate by posting messages to a common broadcast channel. This problem is called leader election, and it is fundamental to the distributed systems and cryptography literature. Recently, it has attracted renewed interests due to its promised applications in decentralized environments.

In a game theoretically fair leader election protocol, roughly speaking, we want that even majority coalitions cannot increase its own chance of getting elected, nor hurt the chance of any honest individual. The folklore tournament-tree protocol, which completes in logarithmically many rounds, can easily be shown to satisfy game theoretic security. To the best of our knowledge, no sub-logarithmic round protocol was known in the setting that we consider.

We show that by adopting an appropriate notion of approximate game-theoretic fairness, and under standard cryptographic assumption, we can achieve $(1-1/2^{\Theta(r)})$-fairness in $r$ rounds for $\Theta(\log \log n) \leq r \leq \Theta(\log n)$, where $n$ denotes the number of players. In particular, this means that we can approximately match the fairness of the tournament tree protocol using as few as $O(\log \log n)$ rounds. We also prove a lower bound showing that logarithmically many rounds is necessary if we restrict ourselves to ``perfect'' game-theoretic fairness and protocols that are ``very similar in structure'' to the tournament-tree protocol.

Although leader election is a well-studied problem in other contexts in distributed computing, our work is the first exploration of the round complexity of {\it game-theoretically fair} leader election in the presence of a possibly majority coalition. As a by-product of our exploration, we suggest a new, approximate game-theoretic fairness notion, called ``approximate sequential fairness'', which provides a more desirable solution concept than some previously studied approximate fairness notions.

Looking for a top PhD program in English that you can start after BSc or MSc?

CS@max planck is a highly selective doctoral program that grants admitted students full financial support to pursue research in the broad area of computer and information science, with faculty at Max Planck Institutes and some of the best German universities. The faculty at the Max Planck Institute for Security and Privacy (MPI-SP) is also part of this program.

To qualify for the program, students must hold a Bachelor’s or Master’s degree in computer science (or a related field) and have an outstanding academic record. We especially encourage applications from students who wish to explore research across the CS spectrum before committing to a topic and advisor.

For more information about CS@max planck, see here: https://www.cis.mpg.de/graduate-programs/cs-max-planck

The next upcoming application deadline is 31 December 2020.

Closing date for applications:

Contact: csmaxplanck@cis.mpg.de

More information: https://www.cis.mpg.de/graduate-programs/cs-max-planck

This Ph.D. position is funded for EU and UK students, and the application deadline is on the 24th of January 2021.

In recent years, the use of solvers (SAT, MILP, CP...) to solve cryptanalysis problems has become prominent. The aim of this Ph.D. is to develop a fully automated framework based on these solvers for the cryptanalysis of block ciphers, starting with differential cryptanalysis. In particular, non-trivial modeling strategies are sometimes necessary to improve the resolution and scale up[1]. An important part of the task will be to derive efficient ways to model different types of ciphers, and compare which method (among MILP, CP, SAT) works best for each types of building blocks.

This position is fully funded, with a stipend of 16 000 GBP per year, and successful applicants are expected to start in April 2021.

[1] David Gerault, Pascal Lafourcade, Marine Minier, Christine Solnon: Computing AES related-key differential characteristics with constraint programming. Artificial Intelligence 278 (2020)

Closing date for applications:

Contact: David Gerault (david.gerault@surrey.ac.uk)

More information: https://www.surrey.ac.uk/fees-and-funding/studentships/phd-studentships-computer-science