International Association
for Cryptologic Research

Leakage during the signing process, including partial key exposure and partial (or complete) randomness leakage, may be devastating for the security of digital signatures. In this work, we consider the security of lattice-based Fiat-Shamir signatures in the presence of randomness leakage. Based on a connection with the ILWE problem introduced by Bootle et al. at Asiacrypt 2018, we show that the key recovery attack with partial randomness leakage can be reduced to a variant of ILWE (We call it FS-ILWE in this work). The ILWE problem is the problem of recovering the secret vector ${\bf s}$ given polynomially many samples of the form $({\bf a}, \langle {\bf a}, {\bf s} \rangle + e)$ and is proven solvable if the error $e$ is not superpolynomially larger than the inner product $\langle {\bf a}, {\bf s} \rangle$, whereas in the FS-ILWE ${\bf a}$ is a sparse vector with a fixed number of non-zero elements, which is either $1$ or $-1$. With one nice probability property that the expectation and covariance of any two coefficients of ${\bf a}$ are zeros, we show that FS-ILWE can also be solved in polynomial time.

Consequently, many lattice-based Fiat-Shamir signatures can be totally broken with only one bit leakage of randomness per signature. Our attack has been validated by conducting a series of experiments on two efficient NIST PQC submissions, Dilithium and qTESLA. The results indicate that the secret key of Dilithium and qTESLA can be recovered within seconds by running our method on an ordinary PC desktop.

This paper gives a new generalized key-recovery model of related-key rectangle attacks on block ciphers with linear key schedules. The model is quite optimized and applicable to various block ciphers with linear key schedule. As a proof of work, we apply the new model to two very important block ciphers, i.e. SKINNY and GIFT, which are basic modules of many candidates of the Lightweight Cryptography (LWC) standardization project by NIST.

For SKINNY, we reduce the complexity of the best previous 27-round related-tweakey rectangle attack on SKINNY-128-384 from $2^{331}$ to $2^{251.25}$. In addition, the first 28-round related-tweakey rectangle attack on SKINNY-128-384 is given, which gains one more round than before. For the candidate LWC SKINNY AEAD M1, we conduct a 24-round related-tweakey rectangle attack with a time complexity of $2^{123}$ and a data complexity of $2^{123}$ chosen plaintexts. For the case of GIFT-64, we give the first 24-round related-key rectangle attack with a time complexity $2^{91.58}$, while the best previous attack on GIFT-64 only reaches 23 rounds at most.

Satoshi Nakamoto's Blockchain allows to build publicly verifiable and almost immutable ledgers, but sometimes privacy has to be factored in.

In this work an original protocol is presented that allows sensitive data to be stored on a ledger where its integrity may be publicly verified, but its privacy is preserved and owners can tightly manage the sharing of their information with efficient revocation.

Block cipher modes of operation provide a way to securely encrypt using a block cipher, and different modes of operation achieve different tradeoffs of security, performance and simplicity. In this paper, we present a new authenticated encryption scheme that is designed for the lightweight cryptography setting, but can be used in standard settings as well. Our mode of encryption is extremely simple, requiring only a single block cipher primitive (in forward direction) and minimal padding, and supports streaming (online encryption). In addition, our mode achieves very strong security bounds, and can even provide good security when the block size is just 64 bits. As such, it is highly suitable for lightweight settings, where the lifetime of the key and/or overall amount encrypted may be high. Our new scheme can be seen as an improved version of CCM that supports streaming, and provides much better bounds.

In this work, we present a fast parallel architecture to perform supersingular isogeny key encapsulation (SIKE). We propose and implement a fast isogeny accelerator architecture that uses fast and parallelized isogeny formulas. On top of our isogeny accelerator, we build a novel architecture for the SIKE primitive, which provides both quantum and IND-CCA security. Since SIKE can support static keys, we propose and implement additional differential power analysis countermeasures. We synthesized this architecture on the Xilinx Virtex-7 and Kintex UltraScale+ FPGA families. Over Virtex-7 FPGA's, our constant-time implementations are roughly 20% faster than the state-of-the-art with a better area-time product. At the NIST security level 5 on a Kintex UltraScale+ FPGA, we can execute the SIKE protocol in 15.6 ms. This work continues to improve the speed of isogeny-based computations and also features the first full implementation of SIKE, with results applicable to NIST's post-quantum standardization process.

The Trusted Platform Module (TPM) version 2.0, which has been demonstrated as a key element of Industry 4.0, presents a two-phase key exchange primitive for secure communications between Industry 4.0 components. The key exchange primitive of TPM 2.0 can be used to implement three widely-standardized authenticated key exchange protocols: the Full Unified Model, the Full MQV, and the SM2 key exchange protocols. However, vulnerabilities have been found in all of these protocols. Fortunately, it seems that the protections offered by TPM chips can mitigate these vulnerabilities. In this paper, we present a security model which captures TPM's protections on keys and protocols' computation environments and in which multiple protocols can be analyzed in a unified way. Based on the unified security model, we give the first formal security analysis of the key exchange primitive of TPM 2.0, and the analysis results show that, with the help of hardware protections of TPM chips, the key exchange primitive indeed satisfies the well-defined security property of our security model, but unfortunately under some impractical limiting conditions, which would prevent the application of the key exchange primitive in real-world networks. To make TPM 2.0 applicable to real-world networks, we present a revision of the key exchange primitive of TPM 2.0, which can keep secure without the limiting conditions. We give a rigorous analysis of our revision, and the results show that our revision achieves not only the basic security property of modern AKE security models but also some further security properties.

One of the main goals of securing data transmission is focused on the security of cloud data storage. In this paper, we describe several cryptographic techniques which can be used to address the relevant threats and security goals for analyzing cloud computing security. Private semi-trusted clouds, allow researchers to design private clouds by using cryptographic techniques, to protect the semi-trusted ones. Finally, we elaborate on semi-trusted clouds which are related to real-world deployments of cloud resources, and how optimizing cryptographic protocols, would indeed lead to the usage of this certain cloud and therefore practical ways of securing this type of data.

A special metric of interest about Boolean functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a Boolean circuit over the basis {XOR, AND, NOT}. In this paper we study the MC of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. in 2000 and by Boyar and Peralta in 2008. We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions $\Sigma^n_k$ and counting functions $E^n_k$ with up to n = 25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric $\Sigma^8_4$ and the counting $E^8_4$ functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric Boolean functions, for each n up to 132.

Since the seminal result of Kilian, Oblivious Transfer has proven to be a fundamental primitive in cryptography. In such a scheme, a user is able to gain access to an element owned by a server, without learning more than this single element, and without the server learning which element the user has accessed. This primitive has received a lot of study in the literature, among which very few schemes are based on lattices. The recent NIST call for post-quantum encryption and signature schemes has revived the interest for cryptographic protocols based on post-quantum assumptions and the need for a secure post-quantum oblivious transfer scheme. In this paper, we show how to construct an oblivious transfer scheme based on lattices, from a collision-resistant chameleon hash scheme (CH) and a CCA encryption scheme accepting a smooth projective hash function (SPHF). Note that our scheme does not rely on random oracles and provides UC security against adaptive corruptions assuming reliable erasures.

Oblivious Transfer has played a crucial role in the design of secure multi party computation. Nevertheless, there are not many practical solutions that achieve simulation based security and at the same time instantiable based on different assumptions.

In this work, we show how to construct highly efficient oblivious transfer in the random oracle model that achieves simulation based security under a wide range of assumptions, among them DDH, CDH, LWE and coding based assumptions. We revise classical security notions and propose a new security notion that we call endemic security. We construct an endemically secure oblivious transfer based on DDH that takes only a single communication round which allows significant performance gains over previously known solutions. We also instantiate our oblivious transfer with the Crystals.Kyber key agreement. Our implementation shows that both instantiations can be computed in under one millisecond.

Further, our new security notion also allows us to revisit, correct and improve existing oblivious transfer extension techniques. We provide an implementation of an oblivious transfer extension protocol in the ideal cipher model that is actively secure, processing up to 23 million OTs per second and up to 10 times faster than previous secure implementations. We also show that our framework can compute endemically secure OT extension and the base OTs in just two rounds.

We revisit the framework of Commodity-based Cryptography presented by Beaver (STOC'97) with a focus on updating the framework to fit with modern multiparty computation (MPC) protocols. We study the possibility of replacing the well-known preprocessing model with a commodity-based setting, where a set of independent servers (some of which may be corrupt) provide clients with correlated randomness. From this, the clients then distill correct and secure correlated randomness that they can use during the online phase of the MPC protocol. Beaver showed how to do OT with semi-honest security in the commodity setting. We improve on Beaver's result as follows: In a model where one of two clients and a constant fraction of the servers may be maliciously corrupted, we obtain unconditionally secure multiplication triples and oblivious linear evaluations (OLEs) such that the amortized communication cost of one triple/OLE is a constant number of field elements (when the field is sufficiently large). We also report on results from an implementation of the OLE protocol. Finally, we suggest an approach to practical realization of a commodity based system where servers need no memory and can be accessed asynchronously by clients, but still a maliciously corrupt client cannot get data he should not have access to.

This work presents Arcula, a new design for hierarchical deterministic wallets that significantly improves the state of the art. Arcula is built on top of provably secure cryptographic primitives. It generates all its cryptographic secrets from a user-provided seed and enables the derivation of new signing public keys without requiring any secret information. Unlike other wallets, it achieves all these properties while being secure against privilege escalation. We prove that an attacker compromising an arbitrary number of users within an Arcula wallet cannot escalate his privileges and compromise users higher in the access hierarchy. Our design works out-of-the-box with any blockchain that enables the verification of signatures on arbitrary messages. We evaluate its usage in a real-world scenario on the Bitcoin Cash network.

Event date: 4 May to 7 May 2020
Submission deadline: 2 November 2019
Notification: 18 January 2020

An established ingredient in the security evaluation of cryptographic devices is leakage detection, whereby physically observable characteristics such as the power consumption are measured during operation and statistically analysed in search of sensitive data dependencies. However, depending on its precise execution, this approach potentially suffers several drawbacks: a risk of false positives, a difficulty interpreting negative outcomes, and the infeasibility of covering every possible eventuality. Moreover, efforts to mitigate for these drawbacks can be costly with respect to the data complexity of the testing procedures. In this work, we clarify the (varying) goals of leakage detection and assess how well-geared current practice is towards meeting each of those goals. We introduce some new innovations on existing methodologies and make recommendations for best practice. Ultimately, though, we find that many of the obstacles cannot be fully overcome according to existing statistical procedures, so that it remains to be highly cautious and to clearly state the limitations of the methods used when reporting outcomes.

Plantlet is a lightweight stream cipher designed by Mikhalev, Armknecht and M\"{u}ller in IACR ToSC 2017. It has a Grain-like structure with two state registers of size 40 and 61 bits. In spite of this, the cipher does not seem to lose in security against generic Time-Memory-Data Tradeoff attacks due to the novelty of its design. The cipher uses a 80-bit secret key and a 90-bit IV. In this paper, we present a key recovery attack on Plantlet that requires around $2^{76.26}$ Plantlet encryptions. The attack leverages the fact that two internal states of Plantlet that differ in the 43rd LFSR location are guaranteed to produce keystream that are either equal or unequal in 45 locations with probability 1. Thus an attacker can with some probability guess that when 2 segments of keystream blocks possess the 45 bit difference just mentioned, they have been produced by two internal states that differ only in the 43rd LFSR location. Thereafter by solving a system of polynomial equations representing the keystream bits, the attacker can find the secret key if his guess was indeed correct, or reach some kind of contradiction if his guess was incorrect. In the latter event, he would repeat the procedure for other keystream blocks with the given difference. We show that the process when repeated a finite number of times, does indeed yield the value of the secret key.

We propose a decentralized multi-authority anonymous authentication scheme in which a prover and a verifier are non-interactive. We give two security definitions; resistance against collusion attacks that cause misauthentication, and anonymity for privacy protection. Then we give a construction under a principle of ``commit-to-ID''. We employ two building blocks; the structure-preserving signature scheme and the Groth-Sahai non-interactive proof system, the both of which are based on bilinear groups. We give security proofs in the standard model, which reduce to the security of the building blocks.

Lightweight cryptography in computationally constrained devices is actively studied. In contrast to advances of lightweight blockcipher in the last decade, lightweight mode of operation is seemingly not so mature, yet it has large impact in performance. Therefore, there is a great demand for lightweight mode of operation, especially that for authenticated encryption with associated data (AEAD). Among many known properties of conventional modes of operation, the following four properties are essential for constrained devices:

1. Minimum State Size: the state size equals to a block size of a blockcipher.

2. Inverse Free: no need for a blockcipher decryption.

3. XOR Only: only XOR is needed in addition to a blockcipher encryption.

4. Online: a data block is processed only once.

The properties 1 and 4 contribute to small memory usage, and the properties 2 and 3 contribute to small program/circuit footprint. On top of the above properties, the fifth property regarding associated data (AD) is also important for performance:

5. Efficient Handling of Static AD: static AD can be precomputed.

We design a lightweight blockcipher-based AEAD mode of operation called SAEB: the first mode of operation that satisfies all the five properties to the best of our knowledge. Performance of SAEB is evaluated in various software and hardware platforms. The evaluation results show that SAEB outperforms conventional blockcipher-based AEAD modes of operation in various performance metrics for lightweight cryptography.

Applying the Fiat-Shamir transform on identification schemes is one of the main ways of constructing signature schemes. While the classical security of this transformation is well understood, it is only very recently that generic results for the quantum case has been proposed [DFMS19,LZ19]. In this paper, we show that if we start from a commit-and-open identification scheme, where the prover first commits to several strings and then as a second message opens a subset of them depending on the verifier's message, then the Fiat-Shamir transform is quantum secure, for a suitable choice of commitment scheme. Unlike previous generic results, our transformation doesn't require to reprogram the random function H used in the Fiat-Shamir transform and we actually only require a quantum one-wayness property.

Our techniques can in some cases lead to a much tighter security reduction. To illustrate this, we apply our techniques to identifications schemes at the core of the MQDSS signature scheme, the Picnic scheme (both present in the round 2 of the post quantum NIST competition) and the Stern signature scheme. For all these schemes, we show that our technique can be applied with essentially tight results.

In cryptocurrencies such as Bitcoin or Ethereum users control funds via secret keys. To transfer funds from one user to another, the owner of the money signs a new transaction that transfers the funds to the new recipient. This makes secret keys a highly attractive target for attacks, and has lead to prominent examples where millions of dollars worth in cryptocurrency have been stolen. To protect against these attacks, a widely used approach are so-called hot/cold wallets. In a hot/cold wallet system, the hot wallet is permanently connected to the network, while the cold wallet stores the secret key and is kept without network connection. In this work, we propose the first comprehensive security model for hot/cold wallets and develop wallet schemes that are provable secure within these models. At the technical level our main contribution is to provide a new provably secure ECDSA-based hot/cold wallet scheme that can be integrated into legacy cryptocurrencies such as Bitcoin. Our scheme makes several subtle changes to the BIP32 proposal and requires a technically involved security analysis.

Assuring security of the Internet of Things (IoT) is much more challenging than assuring security of centralized environments, like the cloud. A reason for this is that IoT devices are often deployed in domains that are remotely managed and monitored. Thus, their physical security cannot be guaranteed as reliably as physical security of data centers. Some believe that physical security becomes less important if all data processed and stored within a device is encrypted. However, an attacker with a physical access to a device implementing an encryption algorithm may be able to extract the encryption key and decrypt data. As a demonstration, in this paper we attack ACORN stream cipher, a finalist of CESAR competition for authenticated encryption. By injecting a single stuck-at-0 fault into ACORN's implementation, we reduce its non-linear feedback function to a linear one. Since this obviously makes ACORN weaker, many known attacks can be applied to break it. We apply an algebraic attack which recovers the key from $2^{15.34}$ keystream bits using $2^{35.46}$ operations.