International Association
for Cryptologic Research

Withthiswork, weintendondemonstratingtheneedfor improvements to the currently standardized AES family of cryptosystems, and provide a solution that meets the requirements of long-term security in the rapidly evolving threat landscape. The solution proposed is flexible, dramatically increases the potential security of the cipher, and strongly mitigates many of the most serious attacks on the AES family of cryptosystems. Further, our solution can be easily integrated into existing AES cryptosystem deployments, with only a few small changes required, thus preserving the large investments in this cipher both in hardware and software.

Non-malleable codes are encoding schemes that provide protections against various classes of tampering attacks. Recently Faust et al. (CRYPTO 2017) initiated the study of space- bounded non-malleable codes that provide such protections against tampering within small- space devices. They put forward a construction based on any non-interactive proof-of-space (NIPoS). However, the scheme only protects against an a priori bounded number of tampering attacks.

We construct non-malleable codes that are resilient to an unbounded polynomial number of space-bounded tamperings. Towards that we introduce a stronger variant of NIPoS called proof-extractable NIPoS (PExt-NIPoS), and propose two approaches of constructing such a primitive. Using a new proof strategy we show that the generic encoding scheme of Faust et al. achieves unbounded tamper-resilience when instantiated with a PExt-NIPoS. We show two methods to construct PExt-NIPoS:

1. The first method uses a special family of “memory-hard” graphs, called challenge-hard graphs (CHG), a notion we introduce here. We instantiate such family of graphs based on an extension of stack of localized expanders (first used by Ren and Devadas in the context of proof-of-space). In addition, we show that the graph construction used as a building block for the proof-of-space by Dziembowski et al. (CRYPTO 2015) satisfies challenge-hardness as well. These two CHG-instantiations lead to continuous space-bounded NMC with different features in the random oracle model.

2. Our second instantiation relies on a new measurable property, called uniqueness of NIPoS. We show that standard extractability can be upgraded to proof-extractability if the NIPoS also has uniqueness. We propose a simple heuristic construction of NIPoS, that achieves (partial) uniqueness, based on a candidate memory-hard function in the standard model and a publicly verifiable computation with small-space verification. Instantiating the encoding scheme of Faust et al. with this NIPoS, we obtain a continuous space-bounded NMC that supports the “most practical” parameters, complementing the provably secure but “relatively impractical” CHG-based constructions. Additionally, we revisit the construction of Faust et al. and observe that due to the lack of uniqueness of their NIPoS, the resulting encoding schemes yield “highly impractical” parameters in the continuous setting.

We conclude the paper with a comparative study of all our non-malleable code constructions with an estimation of concrete parameters.

This paper is focused on an open question regarding the correlation and the power of the NIST statistical test suite. If we found some correlation between these statistical tests, then we can improve the testing strategy by executing only one of the tests that are correlated. Using the Galton-Pearson “product-moment correlation coefficient”, by simulation, we found a high correlation between five couples of this statistical tests: (frequency, cumulative sums forward), (frequency, cumulative sums reverse), (cumulative sums forward, cumulative sums reverse), (random excursions, random excursions variant), and (serial 1, serial 2).

This paper describes a new public coin, succinct interactive zero-knowledge argument for NP under standard cryptographic hardness assumptions—without requiring a trusted setup. In particular, our argument enables a prover to prove the satisfiability of arithmetic circuits over a large finite field (an NP-complete language for which there exist efficient reductions from high-level programs of practical interest) to a verifier. We construct this argument through a novel synthesis of techniques from prior work on short PCPs, MIPs, and doubly-efficient IPs. Specifically, our interactive argument is a succinct variant of the sum-check protocol where the protocol is run with a carefully-constructed low-degree polynomial that encodes a given circuit satisfiability instance. Since our interactive argument is public coin, we make it non-interactive in the random oracle model, thereby obtaining a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK), which we call Spartan.

Spartan is the first zkSNARK without trusted setup (i.e., a “transparent” zkSNARK) where verifying a proof incurs sub-linear costs without requiring data parallelism (or other homogeneity) in the structure of an arithmetic circuit for which a proof is produced. To achieve this, Spartan introduces a notion of computation commitments—a primitive to create a short cryptographic commitment to a mathematical description of an arithmetic circuit. Finally, Spartan is asymptotically efficient with small constants: the prover performs $O(n)$ cryptographic operations to produce a proof of size $O(n^{1/c})$ that can be verified in $O(n^{1-1/c})$ time (after a one-time, public preprocessing of the circuit to create a computation commitment that takes $O(n)$ time), where $n$ denotes the size of an arithmetic circuit and $c \geq 2$ (Spartan can produce $O(\log{n})$-sized proofs, but the verifier incurs $O(n)$ costs).

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.

We show that solving the End-of-Metered-Line problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD.

Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).

Combining our construction with a hash family proposed by Canetti et al. [STOC 2019] gives rise to a distribution in the class CLS, which is provably hard under the assumption that any one of a class of fully homomorphic encryption (FHE) schemes has almost-optimal security against quasi-polynomial time adversaries, and under the additional worst-case assumption that there is no polynomial time algorithm for counting the number of satisfying assignments for formulas over a polylogarithmic number of variables.

Wave is a recent digital signature scheme. It is based on a family of trapdoor one-way Preimage Sampleable Functions and is proven EUF-CMA in the random oracle model under two code-based computational assumptions. One of its key properties is to produce signatures uniformly distributed of fixed Hamming weight. This property implies that, if properly implemented, Wave is immune to leakage attack. We describe here the key stages for the implementation of the Wave trapdoor inverse function to integrate all the features to achieve leakage-freeness. A proof of concept implementation was made in SageMath. It allowed us to check that properly generated Wave signatures are uniformly distributed. In particular, we show that the signatures produced by this implementation defeat the Barreto-Persichetti attack. We show which features of the Wave specification were improperly put aside and explain why the claim of breaking Wave is incorrect.

Anonymity is a primary ingredient for our digital life. Several tools have been designed to address it such as, for authentication, blind signatures, group signatures or anonymous credentials and, for confidentiality, randomizable encryption or mix-nets. When it comes to complex electronic voting schemes, random shuffling of ciphertexts with mix-nets is the only known tool. However, it requires huge and complex zero-knowledge proofs to guarantee the actual permutation of the initial ciphertexts.

In this paper, we propose a new approach for proving correct shuffling: the mix-servers can simply randomize individual ballots, which means the ciphertexts, the signatures, and the verification keys, with an additional global proof of constant size, and the output will be publicly verifiable. The computational complexity for the mix-servers is linear in the number of ciphertexts. Verification is also linear in the number of ciphertexts, independently of the number of rounds of mixing. This leads to the most efficient technique, that is highly scalable. Our constructions make use of linearly-homomorphic signatures, with new features, that are of independent interest.

Zero-Knowledge Proof-of-Identity from trusted public certificates (e.g., national identity cards and/or ePassports; eSIM) is introduced here to permissionless blockchains in order to remove the inefficiencies of Sybil-resistant mechanisms such as Proof-of-Work (i.e., high energy and environmental costs) and Proof-of-Stake (i.e., capital hoarding and lower transaction volume). The proposed solution effectively limits the number of mining nodes a single individual would be able to run while keeping membership open to everyone, circumventing the impossibility of full decentralization and the blockchain scalability trilemma when instantiated on a blockchain with a consensus protocol based on the cryptographic random selection of nodes. Resistance to collusion is also considered. Solving one of the most pressing problems in blockchains, a zk-PoI cryptocurrency is proved to have the following advantageous properties: - an incentive-compatible protocol for the issuing of cryptocurrency rewards based on a unique Nash equilibrium - strict domination of mining over all other PoW/PoS cryptocurrencies, thus the zk-PoI cryptocurrency becoming the preferred choice by miners is proved to be a Nash equilibrium and the Evolutionarily Stable Strategy - PoW/PoS cryptocurrencies are condemned to pay the Price of Crypto-Anarchy, redeemed by the optimal efficiency of zk-PoI as it implements the social optimum - the circulation of a zk-PoI cryptocurrency Pareto dominates other PoW/PoS cryptocurrencies - the network effects arising from the social networks inherent to national identity cards and ePassports dominate PoW/PoS cryptocurrencies - the lower costs of its infrastructure imply the existence of a unique equilibrium where it dominates other forms of payment

Right from its introduction by Boneh et al., fault attacks (FA) have been established to be one of the most practical threats to both public key and symmetric key based cryptosystems. Statistical Ineffective Fault Analysis (SIFA) is a recently proposed class of fault attacks introduced at CHES 2018. The fascinating feature of this attack is that it exploits the correct ciphertexts obtained during a fault injection campaign, instead of the faulty ciphertexts. The SIFA has been shown to bypass almost all of the existing fault attack countermeasures even when they are combined with provably secure masking schemes for side-channel resistance. The goal of this work is to propose a countermeasure for SIFA. It has been observed that a randomized domain transformation of the intermediate computation combined with bit-level error correction can throttle SIFA. The randomized domain transformation can be achieved by standard masking schemes. In fact, we prove that if biased faults are injected at the state register of a block cipher at a target round, then masking is sufficient to protect against SIFA, until all the shares for a specific bit are corrupted. However, masking alone cannot prevent SIFA if the faults are injected at certain specific locations inside the S-Boxes. To address this issue, we incorporate a bit-level error-correction mechanism. The strongest advantage of the proposed countermeasure, called AntiSIFA, is that it provides provable and quantifiable security guarantees. Proof-of-concept evaluations were performed on software implementations of the block cipher PRESENT, which correlates with the theoretical results.

Code-based cryptographic schemes recently raised to prominence as quantum-safe alternatives to the currently employed number-theoretic constructions, which do not resist quantum attacks. In this article, we discuss the Courtois-Finiasz-Sendrier signature scheme and derive code-based signature schemes using the Fiat-Shamir transformation from code-based zero-knowledge identification schemes, namely the Stern scheme, the Jain-Krenn-Pietrzak-Tentes scheme, and the Cayrel-Veron-El Yousfi scheme. We analyze the security of these code-based signature schemes and derive the security parameters to achieve the 80-bit and 128-bit level of classical security. To derive the secure parameters, we have studied the hardness of Syndrome Decoding Problem. Furthermore, we implement the signature schemes, based on the Fiat-Shamir transform, which were mentioned above, and compare their performance on a PC.

We introduce the notion of Ticket-Mediated Password Strengthening (TMPS), a technique for allowing users to derive keys from passwords while imposing a strict limit on the number of guesses of their password any attacker can make, and strongly protecting the users' privacy. We describe the security requirements of TMPS, and then a set of efficient and practical protocols to implement a TMPS scheme, requiring only hash functions, CCA2-secure encryption, and blind signatures. We provide several variant protocols, including an offline symmetric-only protocol that uses a local trusted computing environment, and online variants that use group signatures or stronger trust assumptions instead of blind signatures. We formalize the security of our scheme by defining an ideal functionality in the Universal Composability (UC) framework, and by providing game-based definitions of security. We prove that our protocol realizes the ideal functionality in the random oracle model (ROM) under adaptive corruptions with erasures, and prove that security with respect to the ideal/real definition implies security with respect to the game-based definitions.

After suffering decades of high-profile attacks, the need for formal verification of security-critical software has never been clearer. Verification-oriented programming languages like F* are now being used to build high-assurance cryptographic libraries and implementations of standard protocols like TLS. In this paper, we seek to apply these verification techniques to modern Web applications, like WhatsApp, that embed sophisticated custom cryptographic components. The problem is that these components are often implemented in JavaScript, a language that is both hostile to cryptographic code and hard to reason about. So we instead target WebAssebmy, a new instruction set that is supported by all major JavaScript runtimes.

We present a new toolchain that compiles Low*, a low-level subset of the F* programming language, into WebAssembly. Unlike other WebAssembly compilers like Emscripten, our compilation pipeline is focused on compactness and auditability: we formalize the full translation rules in the paper and implement it in a few thousand lines of OCaml. Using this toolchain, we present two case studies. First, we build WHACL*, a WebAssembly version of the existing, verified HACL* cryptographic library. Then, we present LibSignal*, a brand new, verified implementation of the Signal protocol in WebAssembly, that can be readily used by messaging applications like WhatsApp, Skype, and Signal.

We present a protocol for a cryptoeconomic fair exchange of data previously owned by the purchaser for tokens that functions even when both parties are anonymous. This enables peer-to-peer data storage without identity verification. We use a smart contract on a decentralized ledger as a trusted third party. Actual data transfer can take place with any standard anonymous exchange channel. Due to the anonymity of the parties, the smart contract cannot punish either party's off-ledger reputation. Furthermore, the contract has limited power to arbitrate fault in off-ledger disputes. Thus, an important feature of our protocol is a collateral mechanism that collectively punishes both Alice and Bob if either of them abandons the protocol or cheats. However, we prove that parameters can be chosen such that the collateral can be made, subject to data size, arbitrarily low and still result in an expected financial loss if either Alice or Bob cheats. We are able to achieve this due to our non-standard use of error-correcting codes. In addition, the protocol allows those storing the data to exchange it without the client's participation.

I am making this work from August 1998 available for historical reasons. It has been cited as an ``unpublished manuscript'' more than two dozen times over the years -- even though it has not been publicly available anywhere for almost 20 years. The short memo describes a simple non-intrusive reverse engineering technique against Russian GOST chips. The technique is based on a slide attack. This may be historically interesting since slide attacks had not been ``invented yet'', at least in formal sense.

The brief original abstract: We show that a simple ``black box'' chosen-key attack against GOST can recover secret S-boxes with approximately $2^{32}$ encryptions.

In this draft, the internal keyed permutation of FlexAEAD has been analysed. In our analysis, we have first reported an iterated truncated differential for one round which holds with a probability of $2^{-7}$ and can penetrate same number of rounds as claimed by the designers with much less complexity which can be easily converted to a key-recovery attack. We have also reported a Super-Sbox construction in the internal permutation, which has been exploited using the Yoyo game to devise a 6-round deterministic distinguisher and a 7-round key recovery attack for 128-bit internal permutation. Similar attacks can be mounted for 64-bit and 256-bit internal permutation.

It has been 70 years since the publication of the seminal outstanding work of Claude Elwood Shannon, in which he first gave a mathematical definition of the cryptosystem and introduced the concept of perfect ciphers. He also examined the conditions in which such a ciphers exist. Shannon's results in one form or another are presented in almost all books on cryptography. One of his result deals with so-called endomorphic ciphers in which the cardinalities of the message space $\mathcal{M}$ and the ciphertexts $\mathcal{C}$ are the same. The Vernam cipher (one-time pad) is the most famous representative of such ciphers. Moreover, it's the only one known to be perfect.

Surprisingly, we have found a mistake in the Shannon's result. Namely, Shannon stated that an endomorphic cipher, in which the keyspace $\mathcal{K}$ has the same cardinality as message space, is perfect if and only if two conditions are satisfied. The first suggests that for any pair plaintext - ciphertext there exists only one key that translates this plaintext into this ciphertext. The second argues that the key distribution must be uniform. We show, that these two conditions are not really enough. We prove in three different ways that the plaintexts must also be equally probable. Moreover, we study the general endomorphic cipher and get the same result. It follows, that in practice perfect endomorphic ciphers do not exist.

The Feistel construction is one of the most studied ways of building block ciphers. Several generalizations were then proposed in the literature, leading to the Generalized Feistel Network, where the round function first applies a classical Feistel operation in parallel on an even number of blocks, and then a permutation is applied to this set of blocks. In 2010 at FSE, Suzaki and Minematsu studied the diffusion of such construction, raising the question of how many rounds are required so that each block of the ciphertext depends on all blocks of the plaintext. They thus gave some optimal permutations, with respect to this diffusion criteria, for a Generalized Feistel Network consisting of 2 to 16 blocks, as well as giving a good candidate for 32 blocks. Later at FSE'19, Cauchois et al. went further and were able to propose optimal even-odd permutations for up to 26 blocks.

In this paper, we complete the literature by building optimal even-odd permutations for 28, 30, 32, 36 blocks which to the best of our knowledge were unknown until now. The main idea behind our constructions and impossibility proof is a new characterization of the total diffusion of a permutation after a given number of rounds. In fact, we propose an efficient algorithm based on this new characterization which constructs all optimal even-odd permutations for the 28, 30, 32, 36 blocks cases and proves a better lower bound for the 34, 38, 40 and 42 blocks cases. In particular, we improve the 32 blocks case by exhibiting optimal even-odd permutations with diffusion round of 9. The existence of such a permutation was an open problem for almost 10 years and the best known permutation in the literature had a diffusion round of 10. Moreover, our characterization can be implemented very efficiently and allows us to easily re-find all optimal even-odd permutations for up to 26 blocks with a basic exhaustive search.

At ASIACRYPT 2018 it was shown that Statistical Ineffective Fault Attacks (SIFA) pose a threat for many practical implementations of symmetric cryptography. In particular, countermeasures against both power analysis and fault attacks typically do not prevent straightforward SIFA attacks that require very limited knowledge about the concrete attacked implementation. Consequently, the exploration of countermeasures against SIFA that do not rely on protocols or physical protection mechanisms is of particular interest. In this paper, we explore different countermeasure strategies against SIFA. First, we thoroughly analyze the conditions for an attack to be successful. We then show that by building the implementation from invertible building blocks rather than binary gates we can create circuits where a single fault in the computation does not cancel out. This property, when combined with a typical redundancy-based countermeasure, then results in a single-fault SIFA-secure implementation. This approach can be implemented efficiently and we show how it can be applied to 3-bit, 4-bit, and 5-bit S-boxes. Additionally, we also present an alternative countermeasure strategy based on fine-grained detection. Although this approach may lead to a higher implementation cost, it can be used to protect arbitrary circuits and can be generalized to cover multi-fault SIFA.

We present the first practical software implementation of Supersingular Isogeny Key Encapsulation (SIKE) round 2, targeting NIST’s 1, 2, and 5 security levels on 32-bit ARM Cortex-M4 microcontrollers. The proposed library introduces a new speed record of SIKE protocol on the target platform. We achieved this record by adopting several state-of-the-art engineering techniques as well as highly-optimized hand-crafted assembly implementation of finite field arithmetic. In particular, we carefully redesign the previous optimized implementations of filed arithmetic on 32-bit ARM Cortex-M4 platform and propose a set of novel techniques which are explicitly suitable for SIKE/SIDH primes. Moreover, the proposed arithmetic implementations are fully scalable to larger bit-length integers and can be adopted over different security levels. The benchmark result on STM32F4 Discovery board equipped with 32-bit ARM Cortex-M4 microcontrollers shows that the entire key encapsulation over p434 takes about 326 million clock cycles (i.e. 1.94 seconds @168MHz). In contrast to the previous optimized implementation of the isogeny-based key exchange on low-power 32-bit ARM Cortex-M4, our performance evaluation shows feasibility of using SIKE mechanism on the target platform. In comparison to the most of the post-quantum candidates, SIKE requires an excessive number of arithmetic operations, resulting in significantly slower timings. However, its small key size makes this scheme as a promising candidate on low-end microcontrollers in the quantum era by ensuring the lower energy consumption for key transmission than other schemes.

The era of PUFs has been characterized by the efforts put into research and the development of PUFs that are robust against attacks, in particular, machine learning (ML) attacks. In the lack of systematic and provable methods for this purpose, we have witnessed the ever-continuing competition between PUF designers/ manufacturers, cryptanalysts, and of course, adversaries that maliciously break the security of PUFs. This is despite a series of acknowledged principles developed in cryptography and complexity theory, under the umbrella term ``hardness amplification." The goal of studies on the hardness amplification is to build a strongly secure construction out of considerably weaker primitives. This paper aims at narrowing the gap between these studies and hardware security, specifically for applications in the domain of PUFs. To this end, we first review an example of practical efforts made to construct more secure PUFs, namely the concept of rolling PUFs. Based on what can be learned from this and central insights provided by the ML and complexity theory, we propose a new PUF-based scheme built around the idea of using a new function, namely, the Tribes function, which combines the outputs of a set of PUFs to generate the final response. Our theoretical findings are discussed in an exhaustive manner and supported by the results of experiments, conducted extensively on real-world PUFs.