International Association
for Cryptologic Research

In this paper, we optimize Bleichenbacher's statistical attack technique against (EC)DSA and other Schnorr-like signature schemes with biased or partially exposed nonces. Previous approaches to Bleichenbacher's attack suffered from very large memory consumption during the so-called "range reduction" phase. Using a carefully analyzed and highly parallelizable approach to this range reduction based on the Schroeppel-Shamir algorithm for knapsacks, we manage to overcome the memory barrier of previous work while maintaining a practical level of efficiency in terms of time complexity.

As a separate contribution, we present new fault attacks against the qDSA signature scheme of Renes and Smith (ASIACRYPT 2017) when instantiated over the Curve25519 Montgomery curve, and we validate some of them on the AVR microcontroller implementation of qDSA using actual fault experiments on the ChipWhisperer-Lite evaluation board. These fault attacks enable an adversary to generate signatures with 2 or 3 bits of the nonces known.

Combining our two contributions, we are able to achieve a full secret key recovery on qDSA by applying our version of Bleichenbacher's attack to these faulty signatures. Using a hybrid parallelization model relying on both shared and distributed memory, we achieve a very efficient implementation of our highly scalable range reduction algorithm. This allows us to complete Bleichenbacher's attack in the 252-bit prime order subgroup of Curve25519 within a reasonable time frame and using relatively modest computational resources both for 3-bit nonce exposure and for the much harder case of 2-bit nonce exposure. Both of these computations, and particularly the latter, set new records in the implementation of Bleichenbacher's attack.

Consider the following embedding problem. Alice has input $\mathbf{a} = (a_1,\dotsc,a_m)\in\mathbb{F}^m$ and Bob has input $\mathbf{b} = (b_1,\dotsc,b_m)\in\mathbb{F}^m$, where $\mathbb{F}$ is a finite field. The two parties want Bob to receive $\mathbf{c} = (c_1,\dotsc,c_m)$ such that $c_i=a_i\cdot b_i$, for all $i\in\{1,\dotsc,m\}$. Alice and Bob have access to an oracle that takes as input two elements $A,B\in \mathbb{K}$ from Alice and Bob, respectively, and outputs the product $C=A\cdot B\in\mathbb{K}$ to Bob, where $\mathbb{K}$ is a degree-$n$ extension of the finite field $\mathbb{F}$. Alice and Bob want to perform only one call to this oracle and enable Bob to compute $\mathbb{c}$ without any additional communication. Given $n$, how large can $m$ be?

More tersely: ``How many multiplications over the base field can we perform using only one multiplication over an extension field?''

Block, Maji, and Nguyen (CRYPTO--2017) proposed this problem and their combinatorial solution achieved $m=n^{1-o(1)}$. Our paper presents an explicit embedding that achieves the optimal asymptotic bound $m=\Theta(n)$, where the constant in the asymptotic notation depends on the size of the base field $|\mathbb{F}|$. The construction of our proposed embedding relies on the toolkit provided by algebraic function fields.

Although the study of this embedding problem is of independent theoretical interest, we present a few representative applications to secure computation. We construct a linear number of oblivious transfers based on the computational hardness assumptions like the pseudorandomness of noisy Reed Solomon codewords with a constant computational overhead. This result enables the efficient secure evaluation of arithmetic circuits that use arithmetic gates over extension fields of the same base field. Next, we construct the first correlation extractor with a linear production rate and $1/2$ resilience by composing our embedding with the correlation extractor of Block, Maji, and Nguyen (CRYPTO--2017).

The problem of Byzantine Agreement (BA) is of interest to both distributed computing and cryptography community. Following well-known results from the distributed computing literature, BA problem in the asynchronous network setting encounters inevitable non-termination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavours of termination guarantee -- with overwhelming probability and with probability one. The latter type termed as almost-surely terminating BAs are the focus of this paper. An eluding problem in the domain of almost-surely terminating BAs is achieving a constant expected running time. Our work makes progress in this direction.

In a setting with $n$ parties and an adversary with unbounded computing power controlling at most $t$ parties in Byzantine fashion, we present two almost-surely terminating BA protocols in the asynchronous setting:

1. With the optimal resilience of $t < \frac{n}{3}$, our first protocol runs for expected ${\cal O}(n)$ time. The existing protocols in the same setting either runs for expected ${\cal O}(n^2)$ time (Abraham et al, PODC 2008) or requires exponential computing power from the honest parties (Wang, CoRR 2015). In terms of communication complexity, our construction outperforms all the known constructions that offer almost-surely terminating feature.

2. With the resilience of $t < \frac{n}{3 + \epsilon}$ for any $\epsilon > 0$, our second protocol runs for expected ${\cal O}(\frac{1}{\epsilon})$ time. The expected running time of our protocol turns constant when $\epsilon$ is a constant fraction. The known constructions with constant expected running time either require $\epsilon$ to be at least $1$ (Feldman-Micali, STOC 1988), implying $t < n/4$, or calls for exponential computing power from the honest parties (Wang, CoRR 2015). We follow the traditional route of building BA via common coin protocol that in turn reduces to asynchronous verifiable secret-sharing (AVSS). Our constructions are built on a variant of AVSS that is termed as shunning. A shunning AVSS fails to offer the properties of AVSS when the corrupt parties strike, but allows the honest parties to locally detect and shun a set of corrupt parties for any future communication. Our shunning AVSS with $t < n/3$ and $t < \frac{n}{3 + \epsilon}$ guarantee $\Omega(n)$ and respectively $\Omega(\epsilon t^2)$ conflicts to be revealed when failure occurs. Turning this shunning AVSS to a common coin protocol efficiently constitutes yet another contribution of our paper.

In this paper, we analyze security properties of the WalnutDSA, a digital signature algorithm recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels,that has been accepted by the National Institute of Standards and Technology for evaluation as a standard for quantum-resistant public-key cryptography. At the core of the algorithm is an action, named E-multiplication, of a braid group on some finite set. The protocol assigns a pair of braids to the signer as a private key. A signature of a message $m$ is a specially constructed braid that is obtained as a product of private keys, the hash value of $m$ encoded as a braid, and three specially designed cloaking elements.

We present a heuristic algorithm that allows a passive eavesdropper to recover a substitute for the signer's private key by removing cloaking elements and then solving a system of conjugacy equations in braids. Our attack has $100\%$ success rate on randomly generated instances of the protocol. It works with braids only and its success rate is not affected by a choice of the base finite field. In particular, it has the same $100\%$ success rate for recently suggested parameters values (including a new way to generate cloaking elements, see NIST PQC forum https://groups.google.com/a/list.nist.gov/forum/#!forum/pqc-forum). Implementation of our attack in C++, as well as our implementation of the WalnutDSA protocol, is available on GitHub (https://github.com/stevens-crag/crag).

The introduction of the processor instructions AES-NI and VPCLMULQDQ, that are designed for speeding up encryption, and their continual performance improvements through processor generations, has significantly reduced the costs of encryption overheads. More and more applications and platforms encrypt all of their data and traffic. As an example, we note the world wide proliferation of the use of AES-GCM, with performance dropping down to 0.64 cycles per byte (from ~23 before the instructions), on the latest Intel processors. This is close to the theoretically achievable performance with the existing hardware support. Anticipating future applications and increasing demand for high performance encryption, Intel has recently announced that its future architecture (codename "Ice Lake") will introduce new encryption instructions. These will be able to vectorize the AES-NI and VPCLMULQDQ instructions, on wide registers that are available on the AVX512 architectures. In this paper, we explain how these new instructions can be used effectively, and how properly using them can lead to the anticipated theoretical encryption throughput of around 0.16 cycles per byte. The included examples demonstrate AES encryption in various modes of operation, AEAD such as AES-GCM, and the emerging nonce misuse resistant variant AES-GCM-SIV.

We present a new public key broadcast encryption scheme where both the ciphertext and secret keys consist of a constant number of group elements. Our result improves upon the work of Boneh, Gentry, and Waters (Crypto '05) as well as several recent follow-ups (TCC '16-A, Asiacrypt '16) in two ways: (i) we achieve adaptive security instead of selective security, and (ii) our construction relies on the decisional $k$-Linear Assumption in prime-order groups (as opposed to $q$-type assumptions or subgroup decisional assumptions in composite-order groups); our improvements come at the cost of a larger public key. Finally, we show that our scheme achieves adaptive security in the multi-ciphertext setting with a security loss that is independent of the number of challenge ciphertexts.

At Asiacrypt 2014, Sun et al. proposed a MILP model to search differential trails for bit-oriented block ciphers. In this paper, we improve this model to search differential characteristics of GIFT, a new lightweight block cipher proposed at CHES 2017. GIFT has two versions, namely GIFT-64 and GIFT-128. For GIFT-64, we find the best 12-round differential characteristic with MILP-based model and give a key-recovery attack on 19-round GIFT-64. For GIFT-128, we find a 20-round differential characteristic and give the first attack on 25-round GIFT-128.

SSH is a security network protocol that uses public key cryptography for client authentication. SSH connections are designed to be run between a client and a server and therefore in enterprise networks there is no centralized monitoring of all SSH connections. An attractive method for enforcing such centralized control, audit or even revocation is to require all clients to access a centralized service in order to obtain their SSH keys. Doing this will introduce security and availability issues. The benefits of centralized control come with new challenges in security and availability.

In this paper we present ESKM - a \emph{distributed enterprise SSH key manager}. ESKM is a secure and fault-tolerant logically-centralized SSH key manager. ESKM leverages $k$-out-of-$n$ threshold security to provide a high level of security. SSH private keys are never stored \emph{at any single node}, not even when they are used for signing. On a technical level, the system uses $k$-out-of-$n$ threshold RSA signatures, which are enforced with new methods that refresh the shares in order to achieve proactive security and prevent many side-channel attacks. In addition, we support password-based user authentication with security against offline dictionary attacks, that is achieved using threshold oblivious pseudo-random evaluation.

ESKM does not require modification in the server side or of the SSH protocol. We implemented the ESKM system, and a patch for OpenSSL libcrypto for client side services. We show that the system is scalable and that the overhead in the client connection setup time is marginal.

The designers of Radio-Frequency IDentification (RFID) systems have a challenging task for proposing secure mutual authentication protocols for Internet of Things (IoT) applications. Recently, Fan et al. proposed a new lightweight RFID mutual authentication protocol in the journal of IEEE Transactions on Industrial Informatics. They claimed that their protocol meets necessary security properties for RFID systems and can be applied for IoT. In this paper, we analyze the security of this protocol and show that it is vulnerable against secret disclosure, reader impersonation and tag traceability attacks. Additionally, we show that in their protocol the anonymity of the tag does not held.

We propose secret-sharing-based bit-decomposition and modulus conversion protocols for a prime order ring $\mathbb{Z}_p$ with an honest majority: an adversary can corrupt $k-1$ parties of $n$ parties and $2k-1 \le n$. Our protocols are secure against passive and active adversaries depending on the components of our protocols. We assume a secret is an $\ell$-bit element and $2^{\ell+\lceil \log m \rceil} < p$, where $m= k$ in the passive security and $m= \binom{n}{k-1}$ in the active security. The outputs of our bit-decomposition and modulus-conversion protocols are $\ell$ tuple of shares in $\mathbb{Z}_2$ and a share in $\mathbb{Z}_{p'}$, respectively, where $p'$ is the modulus to be converted. If $k$ and $n$ are small, the communication complexity of our passively secure bit-decomposition and modulus-conversion protocols are $O(\ell)$ bits and $O(\lceil \log p' \rceil)$ bits, respectively. Our key observation is that a quotient of additive shares can be computed from the \emph{least} significant $\lceil \log m \rceil$ bits. If a secret $a$ is ``shifted'' and additively shared by $x_i$ in $\mathbb{Z}_p$ as $2^{\lceil \log m \rceil}a = \sum_{i=0}^{m-1} x_i = 2^{ \lceil \log m \rceil} a + qp$, the least significant $\lceil \log m \rceil$ bits of $\sum_{i=0}^{m-1} x_i$ determines $q$ since $p$ is an odd prime and the least significant $\lceil \log m \rceil$ bits of $2^{\lceil \log m \rceil} a$ are $0$s.

We study the problem of finding efficiently computable non-degenerate multilinear maps from $G_1^n$ to $G_2$, where $G_1$ and $G_2$ are groups of the same prime order, and where computing discrete logarithms in $G_1$ is hard. We present several applications to cryptography, explore directions for building such maps, and give some reasons to believe that finding examples with $n>2$ may be difficult.

Certificateless public key cryptography (CL-PKC) is designed to have succinct public key management without using certificates at the same time avoid the key-escrow attribute in the identity-based cryptography. Security mechanisms employing implicit certificates achieve same goals. In this work, we first unify the security notions of these two types of mechanisms with a modified CL-PKC formulation. We further present a general key-pair generation algorithm for CL-PKC schemes and uses it to construct certificateless public key signature (CL-PKS) schemes from standard algorithms. The technique, which we apply, helps defeat known-attacks against existing constructions, and the resulting schemes could be quickly deployed based on the existing standard algorithm implementations. The proposed schemes are particularly useful to provide security services such as authentication, data integrity and non-repudiation in the Internet of Things because of their high efficiency of computation cost, bandwidth consumption and storage requirement.

Constructing collision-resistant hash families (CRHFs) from one-way functions is a long-standing open problem and source of frustration in theoretical cryptography. In fact, there are strong negative results: black-box separations from one-way functions that are $2^{-(1-o(1))n}$-secure against polynomial time adversaries (Simon, EUROCRYPT '98) and even from indistinguishability obfuscation (Asharov and Segev, FOCS '15).

In this work, we formulate a mild strengthening of exponentially secure one-way functions, and we construct CRHFs from such functions. Specifically, our security notion requires that every polynomial time algorithm has at most $2^{-n - \omega(\log(n))}$ probability of inverting two independent challenges.

More generally, we consider the problem of simultaneously inverting $k$ functions $f_1,\ldots, f_k$, which we say constitute a ``one-way product function'' (OWPF). We show that sufficiently hard OWPFs yield hash families that are multi-input correlation intractable (Canetti, Goldreich, and Halevi, STOC '98) with respect to all sparse (bounded arity) output relations. Additionally assuming indistinguishability obfuscation, we construct hash families that achieve a broader notion of correlation intractability, extending the recent work of Kalai, Rothblum, and Rothblum (CRYPTO '17). In particular, these families are sufficient to instantiate the Fiat-Shamir heuristic in the plain model for a natural class of interactive proofs.

An interesting consequence of our results is a potential new avenue for bypassing black-box separations. In particular, proving (with necessarily non-black-box techniques) that parallel repetition amplifies the hardness of specific one-way functions -- for example, all one-way permutations -- suffices to directly bypass Simon's impossibility result.

Distance-bounding (DB) protocols are being adopted in different applications, e.g., contactless payments, keyless entries. For DB to be application-ready, "pick-and-choose" corruption models and clear-cut security definitions in DB are needed. Yet, this is virtually impossible using the four existing formalisms for distance-bounding (DB), whereby each considers around five different security properties, arguably intertwined and hard to compare amongst each other.

In particular, terrorist-fraud resistance has been notoriously problematic to formalise in DB. Also, achieving this property, often weakness a protocol's general security. We demonstrate that --in fact-- terrorist-fraud resistance cannot be achieved, under standard assumptions made for DB protocols. Our result wraps up terrorist-fraud resistance in provable-security in DB.

As a consequence of terrorist-fraud resistance being made irrelevant, and to address application-ready DB, we present a new, provable-security model for distance-bounding. It formalises fine-grained corruption-modes (i.e., white-box and black-box corrupted provers) and this allows for clearer security definitions driven by the separation in corruption-modes. Also, our model explicitly includes a security-property generalising key-leakage, which per se --before this-- was studied only implicitly or as a by-product of other DB-security properties.

In all, our formalism only requires three, clear-cut security definitions which can be "picked and chosen" based on the application-driven prover-corruption modes.

We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes-Rostovtsev-Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field ${\mathbb F_p}$, rather than to ordinary elliptic curves. The Diffie-Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at the AES-128 security level, matching NIST's post-quantum security category I.

In this paper, we present an identity-based encryption scheme from codes with efficient key revocation. Recently, in Crypto 2017, Gaborit et al. proposed a first identity-based encryption scheme from codes with rank metric, called RankIBE. To extract the decryption key from any public identity, they constructed a trapdoor function which relies on RankSign, a signature scheme proposed by Gaborit et al. in PQCrypto 2014. We adopt the same trapdoor function to add efficient key revocation functionality in the RankIBE scheme. Our revocable IBE scheme from codes with rank metric makes use of a binary tree data structure to reduce the amount of work in terms of key updates for the key authority. The total size of key updates requires logarithmic complexity in the maximum number of users and linear in the number of revoked users. We prove that our revocable IBE scheme is selective-ID secure in the random oracle model, under the hardness of three problems: the Rank Syndrome Decoding (RSD) problem, the Augmented Low-Rank Parity Check Code (LRPC+) problem, and the Rank Support Learning (RSL) problem.

Abstract. Recently, numerous physical attacks have been demonstrated against lattice- based schemes, often exploiting their unique properties such as the reliance on Gaussian distributions, rejection sampling and FFT-based polynomial multiplication. As the call for concrete implementations and deployment of postquantum cryptography becomes more pressing, protecting against those attacks is an important problem. However, few counter- measures have been proposed so far. In particular, masking has been applied to the decryp- tion procedure of some lattice-based encryption schemes, but the much more difficult case of signatures (which are highly non-linear and typically involve randomness) has not been considered until now. In this paper, we describe the first masked implementation of a lattice-based signature scheme. Since masking Gaussian sampling and other procedures involving contrived prob- ability distribution would be prohibitively inefficient, we focus on the GLP scheme of Gu &#776;neysu, Lyubashevsky and Po &#776;ppelmann (CHES 2012). We show how to provably mask it in the Ishai–Sahai–Wagner model (CRYPTO 2003) at any order in a relatively efficient man- ner, using extensions of the techniques of Coron et al. for converting between arithmetic and Boolean masking. Our proof relies on a mild generalization of probing security that supports the notion of public outputs. We also provide a proof-of-concept implementation to assess the efficiency of the proposed countermeasure.

There have been tremendous advances in reducing interaction, communication and verification time in zero-knowledge proofs but it remains an important challenge to make the prover efficient. We construct the first zero-knowledge proof of knowledge for the correct execution of a program on public and private inputs where the prover computation is nearly linear time. This saves a polylogarithmic factor in asymptotic performance compared to current state of the art proof systems.

We use the TinyRAM model to capture general purpose processor computation. An instance consists of a TinyRAM program and public inputs. The witness consists of additional private inputs to the program. The prover can use our proof system to convince the verifier that the program terminates with the intended answer within given time and memory bounds. Our proof system has perfect completeness, statistical special honest verifier zero-knowledge, and computational knowledge soundness assuming linear-time computable collision-resistant hash functions exist.

The main advantage of our new proof system is asymptotically efficient prover computation. The prover's running time is only a superconstant factor larger than the program's running time in an apples-to-apples comparison where the prover uses the same TinyRAM model. Our proof system is also efficient on the other performance parameters; the verifier's running time time and the communication are sublinear in the execution time of the program and we only use a log-logarithmic number of rounds.

In this paper, we construct a Lattice-based one-time Linkable Ring Signature (L2RS) scheme, which enables the public to verify if two or more signatures were generated by same signatory, whilst still preserving the anonymity of the signatory. The L2RS provides unconditional anonymity and security guarantees under the Ring Short Integer Solution (Ring-SIS) lattice hardness assumption. The proposed L2RS scheme is extended to be applied in a protocol that we called Lattice Ring Condential transaction (Lattice RingCT) RingCT v1.0, which forms the foundation of the privacy-preserving protocol in any post-quantum secure cryptocurrency such as Hcash.

Proof-of-stake-based (in short, PoS-based) blockchains aim to overcome scalability, effi- ciency, and composability limitations of the proof-of-work paradigm, which underlies the security of several mainstream cryptocurrencies including Bitcoin. Our work puts forth the first (global universally) composable (GUC) treatment of PoS-based blockchains in a setting that captures—for the first time in GUC—arbitrary numbers of parties that may not be fully operational, e.g., due to network problems, reboots, or updates of their OS that affect all or just some of their local resources including their network interface and clock. This setting, which we refer to as dynamic availability, naturally captures decentralized environments within which real-world deployed blockchain protocols are assumed to operate. We observe that none of the existing PoS-based blockchain protocols can realize the ledger functionality under dynamic availability in the same way that bitcoin does (using only the information available in the genesis block). To address this we propose a new PoS-based protocol, “Ouroboros Genesis”, that adapts one of the latest cryptographically-secure PoS-based blockchain protocols with a novel chain selection rule. The rule enables new or offline parties to safely (re-)join and bootstrap their blockchain from the genesis block without any trusted advice—such as checkpoints—or assumptions regarding past availability. We say that such a blockchain protocol can “bootstrap from genesis.” We prove the GUC security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake. Our model allows adversarial scheduling of messages in a network with delays and captures the dynamic availability of participants in the worst case. Importantly, our protocol is effectively independent of both the maximum network delay and the minimum level of availability— both of which are run-time parameters. Proving the security of our construction against an adaptive adversary requires a novel martingale technique that may be of independent interest in the analysis of blockchain protocols.