International Association
for Cryptologic Research

We observe that any key agreement protocol satisfying perfect completeness, regardless of its round complexity, can be used to construct a non-interactive commitment scheme.

This observation simplifies the cryptographic assumptions required for some protocols that utilize non-interactive commitments and removes the need for ad-hoc constructions of non-interactive commitments from specific assumptions such as Learning with Errors.

A fundamental problem in the theory of secure multi-party computation (MPC) is to characterize functions with more than 2 parties which admit MPC protocols with information-theoretic security against passive corruption. This question has seen little progress since the work of Chor and Ishai (1996), which demonstrated difficulties in resolving it. In this work, we make significant progress towards resolving this question in the important case of aggregating functionalities, in which m parties P1, . . . , Pm hold inputs x1, . . . , xm and an aggregating party P0 must learn f(x1,...,xm).

We uncover a rich class of algebraic structures that are closely related to secure computability, namely, “Commuting Permutations Systems” (CPS) and its variants. We present an extensive set of results relating these algebraic structures among themselves and to MPC, including new protocols, impossibility results and separations. Our results include a necessary algebraic condition and slightly stronger sufficient algebraic condition for a function to admit information-theoretically secure MPC protocols.

We also introduce and study new models of minimally interactive MPC (called UNIMPC and UNIMPC*), which not only help in understanding our positive and negative results better, but also open up new avenues for studying the cryptographic complexity landscape of multi-party functionalities. Our positive results include novel protocols in these models, which may be of independent practical interest.

Finally, we extend our results to a definition that requires UC security as well as semi-honest security (which we term strong security). In this model we are able to carry out the characterization of all computable functions, except for a gap in the case of aggregating functionalities.

At Eurocrypt'18, Cid, Huang, Peyrin, Sasaki, and Song introduced a new tool called Boomerang Connectivity Table (BCT) for measuring the resistance of a block cipher against the boomerang attack which is an important cryptanalysis technique introduced by Wagner in 1999 against block ciphers. Next, Boura and Canteaut introduced an important parameter related to the BCT for cryptographic Sboxes called boomerang uniformity.

The purpose of this paper is to present a brief state-of-the-art on the notion of boomerang uniformity of vectorial Boolean functions (or Sboxes) and provide new results. More specifically, we present a slightly different but more convenient formulation of the boomerang uniformity and prove some new identities. Moreover, we focus on quadratic permutations in even dimension and obtain general criteria by which they have optimal BCT. As a consequence of, two previously known results can be derived, and many new quadratic permutations with optimal BCT (optimal means that the maximal value in the Boomerang Connectivity Table equals the lowest known differential uniformity) can be found. In particular, we show that the boomerang uniformity of the binomial differentially $4$-uniform permutations presented by Bracken, Tan, and Tan equals $4$. Finally, we show a link between the boomerang uniformity and the nonlinearity for some special quadratic permutations.

We focus on securely computing the $k^\text{th}$-ranked integer in a sequence of integers distributed among $n$ parties, e.g., the largest or smallest integer or the median. Our specific objective is low interactivity between parties to support blockchains or other scenarios where multiple rounds are time-consuming. Hence, we dismiss powerful, yet highly-interactive MPC frameworks and propose SCIB, a special-purpose protocol for secure computation of the $k^\text{th}$-ranked integer. SCIB uses additively homomorphic encryption to implement core comparisons, but computes under distinct keys, chosen by each party to optimize the number of rounds. By carefully combining ECC Elgamal encryption, encrypted comparisons, ciphertext blinding, secret sharing, and shuffling, SCIB sets up a system of multi-scalar equations which we efficiently prove with Groth-Sahai ZK proofs. As a result, SCIB is secure in the malicious model and practical, requiring only 3 rounds (blockchain blocks). This number of rounds is constant in both bit length $\ell$ of integers and the number of parties $n$ which is optimal. Our implementation indicates that SCIB's main bottleneck, ZK proof computations, is small in practice: even for a large number of parties ($n=200$) and high-precision integers ($\ell=32$), computation time of all proofs is less than a single Bitcoin block interval.

Secure Multi-party Computation (MPC) is one of the most influential achievements of modern cryptography: it allows evaluation of an arbitrary function on private inputs from multiple parties without revealing the inputs. A crucial step of utilizing contemporary MPC protocols is to describe the function as a Boolean circuit. While efficient solutions have been proposed for special case of two-party secure computation, the general case of more than two-party is not addressed. This paper proposes MPCircuits, the first automated solution to devise the optimized Boolean circuit representation for any MPC function using hardware synthesis tools with new customized libraries that are scalable to multiple parties. MPCircuits creates a new end-to-end tool-chain to facilitate practical scalable MPC realization. To illustrate the practicality of MPCircuits, we design and implement a set of five circuits that represent real-world MPC problems. Our benchmarks inherently have different computational and communication complexities and are good candidates to evaluate MPC protocols. We also formalize the metrics by which a given protocol can be analyzed. We provide extensive experimental evaluations for these benchmarks; two of which are the first reported solutions in multi-party settings. As our experimental results indicate, MPCircuits reduces the computation time of MPC protocols by up to 4.2x.

We propose Path Oblivious Heap, an extremely simple, practical, and optimal oblivious priority queue. Path Oblivious Heap is only a small constant factor slower than the standard insecure binary heap. Our construction also implies a practical and optimal oblivious sorting algorithm.

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn a secret linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn a linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of long instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.

In this paper we analyze for the first time the post-quantum security of AES. AES is the most popular and widely used block cipher, established as the encryption standard by the NIST in 2001. We consider the secret key setting and, in particular, AES-256, the recommended primitive and one of the few existing ones that aims at providing a post-quantum security of 128 bits. In order to determine the new security margin, i.e., the lowest number of non-attacked rounds in time less than $2^{128}$ encryptions, we first provide generalized and quantized versions of the best known cryptanalysis on reduced-round AES, as well as a discussion on attacks that don't seem to benefit from a significant quantum speed-up.

We propose a new framework for structured search that encompasses both the classical and quantum attacks we present, and allows to efficiently compute their complexity. We believe this framework will be useful for future analysis.

Our best attack is a quantum Demirci-Selçuk meet-in-the-middle attack. Unexpectedly, using the ideas underlying its design principle also enables us to obtain new, counter-intuitive classical TMD trade-offs. In particular, we can reduce the memory in some attacks against AES-256 and AES-128.

One of the building blocks of our attacks is solving efficiently the AES S-Box differential equation, with respect to the quantum cost of a reversible S-Box. We believe that this generic quantum tool will be useful for future quantum differential attacks.

Judging by the results obtained so far, AES seems a resistant primitive in the post-quantum world as well as in the classical one, with a bigger security margin with respect to quantum generic attacks.

In this paper, we present a simple attack on LWE and Ring LWE encryption schemes used directly as Key Encapsulation Mechanisms (KEMs). This attack could work due to the fact that a key mismatch in a KEM is accessible to an adversary. Our method clearly indicates that any LWE or RLWE (or any similar type of construction) encryption directly used as KEM can be broken by modifying our attack method according to the respective cases.

Synchronous solutions for building Byzantine Fault Tolerance (BFT) replication can be safe when < 1/2 of the replicas fail. Assuming $\Delta$ is an upper bound on the time for messages to arrive, these solutions must incur at least $\Delta$ latency for consensus on a single value. In this work, we show a consensus protocol named Sync HotStuff designed to achieve consensus on a sequence of values with a latency of $2\Delta$ in the common mode when less than half of the replicas are Byzantine. Thus, in the common mode, Sync HotStuff is within a factor of 2 of the optimal latency. Moreover, Sync HotStuff has responsiveness, i.e., it advances at network speed, when < 1/4 of the replicas are not responding, a small sacrifice in availability compared with optimal asynchronous solutions. Borrowing from practical BFT solutions in the asynchronous arena, Sync HotStuff has an extremely simple, two-phase leader-based structure, that easily fits in one frame of pseudo-code.

The availability of a new carry-less multiplication instruction in the latest Intel desktop processors significantly accelerates multiplication in binary fields and hence presents the opportunity for reevaluating algorithms for binary field arithmetic and scalar multiplication over elliptic curves. We describe how to best employ this instruction in field multiplication and the effect on performance of doubling and halving operations. Alternate strategies for implementing inversion and half-trace are examined to restore most of their competitiveness relative to the new multiplier. These improvements in field arithmetic are complemented by a study on serial and parallel approaches for Koblitz and random curves, where parallelization strategies are implemented and compared. The contributions are illustrated with experimental results improving the state-of-the-art performance of halving and doubling-based scalar multiplication on NIST curves at the 112- and 192-bit security levels, and a new speed record for side-channel resistant scalar multiplication in a random curve at the 128-bit security level.

Event date: 20 June to 21 June 2019

We present a pairing-based signature scheme for use in blockchains that achieves substantial savings in bandwidth and storage requirements while providing strong security guarantees. Our signature scheme supports aggregation on the same message, which allows us to compress multiple signatures on the same block during consensus, and achieves forward security, which prevents adaptive attacks on the blockchain. Our signature scheme can be applied to all blockchains that rely on multi-party consensus protocols to agree on blocks of transactions (such as proof-of-stake or permissioned blockchains).

With increasing autonomous features of vehicles, key issues of robotic- and automotive engineering converge toward each other. Closing existing security gaps of device communication networks will be an enabling feature for connecting autonomously interacting systems in a more secure way. We introduce a novel approach for deriving a secret key using a lightweight cipher in the firmware of a low-end control unit. In this approach, we propose to use a non-standardized lightweight algorithm with unique hardware based parameters to prevent duplicate key generation. The randomness of the selected cipher was assessed by applying the NIST statistical test suite to produced key values. By evaluating the method on a typical low-end automotive platform, we could demonstrate the realistic applicability of the solution. The proposed method counteracts a known security issue in device communication between control units not only present in automotive solutions but also in the robotics domain. The security of the implemented solution has been compared to current automotive guidelines and recommendations for the security of resource constrained devices, also present in robotics. This approach allows low-end communication systems to be enhanced by message- and device authentication.

Sampling from discrete Gaussian distribution has applications in lattice-based post-quantum cryptography. Several efficient solutions have been proposed in recent years. However, making a Gaussian sampler secure against timing attacks turned out to be a challenging research problem. In this work, we observed an important property of the input random bit strings that generate samples in Knuth-Yao sampling. We delineate a generic step-by-step method to instantiate a discrete Gaussian sampler of arbitrary standard deviation and precision by efficiently minimizing the Boolean expressions by exploiting this prop- erty. Discrete Gaussian samplers generated in this method can be up to 37% faster than the state of the art method. Finally, we show that the signing algorithm of post-quantum signature scheme Falcon using our constant-time sampler is at most 33% slower than the fastest non-constant time sampler.

This paper introduces streamlined constant-time variants of Euclid's algorithm, both for polynomial inputs and for integer inputs. As concrete applications, this paper saves time in (1) modular inversion for Curve25519, which was previously believed to be handled much more efficiently by Fermat's method, and (2) key generation for the ntruhrss701 and sntrup4591761 lattice-based cryptosystems.

Financial exchanges are typically built out of two trusted components: a trade matching and a trade settlement system. With the advent of decentralized ledgers, that perform transactions without a trusted intermediary, so called decentralized exchanges (DEX) emerged. Some DEXs propose to off-load trade order matching to a centralized system outside the blockchain to scale, but settle each trade trustlessly as an expensive on-chain transaction. While DEX are non-custodial, their order books remains trusted, a malicious exchange operator or miner could front-run trades --- i.e. alter trade order execution for financial gain. The scalability limitations of the settlement layer (e.g. Proof of Work (PoW) blockchains) moreover hinders the practical growth of such DEX architectures.

We propose TEX, a front-running resilient, non-custodial centralized exchange. Our matching system enforces the trade order sequence provided by traders, i.e. is resilient against trade sequence alteration by the exchange operator. As such the matching system can operate in conjunction with a blockchain based settlement layer (as proposed in the following), or make custodian exchanges provably accountable for their matching process. Our layer-two settlement system executes a trade without holding the assets, and allows to reach similar scales as traditional exchanges (trading volume in USD, number of trades/second), despite a slow underlying ledger. TEX might become a point of availability-failure, but we show how the settlement system's security properties would not compromise the trader's assets, even if the centralized operator is compromised and/or colludes with all other traders. We provide an evaluation on a PoW blockchain.

We introduce KL-hardness, a new notion of hardness for search problems which on the one hand is satisfied by all one-way functions and on the other hand implies both next-block pseudoentropy and inaccessible-entropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively. Thus, KL-hardness unifies the latter two notions of computational entropy and sheds light on the apparent "duality" between them. Additionally, it yields a more modular and illuminating proof that one-way functions imply next-block inaccessible entropy, similar in structure to the proof that one-way functions imply next-block pseudoentropy (Vadhan and Zheng, STOC '12).

Cryptocurrencies have provided a promising infrastructure for pseudonymous online payments. However, low throughput has significantly hindered the scalability and usability of cryptocurrency systems for increasing numbers of users and transactions. Another obstacle to achieving scalability is the requirement for every node to duplicate the communication, storage, and state representation of the entire network.

In this paper, we introduce the Asynchronous Consensus Zones, which scales blockchain system linearly without compromising decentralization or security. We achieve this by running multiple independent and parallel instances of single-chain consensus systems termed as zones. The consensus happens independently within each zone with minimized communication, which partitions the workload of the entire network and ensures a moderate burden for each individual node as the network grows. We propose eventual atomicity to ensure transaction atomicity across zones, which achieves the efficient completion of transactions without the overhead of a two-phase commit protocol. Additionally, we propose Chu-ko-nu mining to ensure the effective mining power in each zone to be at the same level of the entire network, making an attack on any individual zone as hard as that on the full network. Our experimental results show the effectiveness of our work: on a testbed including 1,200 virtual machines worldwide to support 48,000 nodes, our system delivers 1,000x throughput and 2,000x capacity over the Bitcoin and Ethereum networks.

The Fiat-Shamir transformation is a useful approach to building non-interactive arguments (of knowledge) in the random oracle model. Unfortunately, existing proof techniques are incapable of proving the security of Fiat-Shamir in the quantum setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the inability of current techniques to adaptively program random oracles in the quantum setting.

In this work, we show how to overcome the limitations above in many settings. In particular, we give mild conditions under which Fiat-Shamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications.