International Association
for Cryptologic Research

In this paper we investigate the impact of decryption failures on the chosen-ciphertext security of (Ring/Module)-Learning With Errors and (Ring/Module)-Learning with Rounding based primitives. Our analysis is split in three parts: First, we introduce a technique to increase the failure rate of these schemes called failure boosting. Based on this technique we investigate the minimal effort for an adversary to obtain a failure in 3 cases: when he has access to a quantum computer, when he mounts a multi-target attack or when he can only perform a limited number of oracle queries. Secondly, we examine the amount of information that an adversary can derive from failing ciphertexts. Finally, these techniques are combined in an attack on (Ring/Module)-Learning with Errors and (Ring/Module)-Learning with Rounding based schemes with decryption failures. We provide both a theoretical analysis as well as an implementation to calculate the security impact and show that an attacker can significantly reduce the security of several candidates of the NIST post-quantum standardization process if sufficient oracle queries can be performed.

This paper describes two FPGA implementations for the encryption and authentication of data, based on the AES algorithm running in Galois/Counter mode (AES-GCM). Both architectures are protected against side-channel analysis attacks through the use of a threshold implementation (TI). The first architecture is fully unrolled and optimized for throughput. The second architecture uses a round-based structure, fits on a relatively small FPGA board, and is evaluated for side-channel attack resistance. We perform a Test Vector Leakage Assessment (TVLA), which shows no first-order leakage in the power consumption of the FPGA. To the best of our knowledge, our work is (1) the first to describe a throughput-optimized FPGA architecture of AES-GCM, protected against first-order side-channel information leakage, and (2) the first to evaluate the side-channel attack resistance of a TI-protected AES-GCM implementation.

OCB2 is a widely standardized mode of operation of a blockcipher that aims at providing authenticated encryption. A recent report by Inoue and Minematsu (IACR EPRINT report 2018/1040) indicates that OCB2 does not meet this goal. Concretely, by describing simple forging attacks the authors evidence that the (sub)goal of authenticity is not reached. The report does not question the confidentiality offered by OCB2.

In this note we show how the attacks of Inoue and Minematsu can be extended to also break the confidentiality of OCB2. We do this by constructing an IND-CCA adversary that requires minimal resources and achieves an overwhelming distinguishing advantage.

We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have $t$ samples from, respectively, distributions $a$ and $b$ over $[n]$, and they need to test whether $a=b$ or $a,b$ are $\varepsilon$-far (in the $\ell_1$ distance) for some fixed $\varepsilon>0$. This is in contrast to the well-studied one-party case, where the tester has unrestricted access to samples of both distributions, for which optimal bounds are known for a number of variations. Despite being a natural constraint in applications, the two-party setting has evaded attention so far.

We address two fundamental aspects of the two-party setting: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each other's input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have $t$ samples from distributions $a$ and $b$ respectively, which may be correlated; the question is whether $a,b$ are independent of $\epsilon$-far from being independent. Our contribution is three-fold:

$\bullet$ Communication: we show how to gain communication efficiency as we have more samples, beyond the information-theoretic bound on $t$. Furthermore, the gain is polynomially better than what one may obtain by adapting one-party algorithms.

For the closeness testing, our protocol has communication $s = \tilde{\Theta}_{\varepsilon}\left(n^2/t^2\right)$ as long as $t$ is at least the information-theoretic minimum number of samples. For the independence testing over domain $[n] \times [m]$, where $n\ge m$, we obtain $s = \tilde{O}_{\varepsilon}(n^2 m/t^2 + n m/t + \sqrt{m})$.

$\bullet$ Lower bounds: we prove tightness of our trade-off for the closeness testing, as well as that the independence testing requires tight $\Omega(\sqrt{m})$ communication for unbounded number of samples. These lower bounds are of independent interest as, to the best of our knowledge, these are the first 2-party communication lower bounds for testing problems, where the inputs represent a set of i.i.d. samples.

$\bullet$ Security: we define the concept of secure distribution testing and argue that it must leak at least some minimal information when the promise is not satisfied. We then provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter.

This paper presents the complete description of the best differentials and linear hulls in 2-round Kuznyechik. We proved that 2-round $\mathrm{MEDP}=2^{-86.66...}$, $\mathrm{MELP}=2^{-76.739...}$. A comparison is made with similar results for the AES cipher.

This paper studies a fundamental problem regarding the security of blockchain on how the existence of multiple misbehaving pools influences the profitability of selfish mining. Each selfish miner maintains a private chain and makes it public opportunistically for the purpose of acquiring more rewards incommensurate to his Hashrate. We establish a novel Markov chain model to characterize all the state transitions of public and private chains. The minimum requirement of Hashrate together with the minimum delay of being profitable is derived in close-form. The former reduces to 21.48% with the symmetric selfish miners, while their competition with asymmetric Hashrates puts forward a higher requirement of the profitable threshold. The profitable delay increases with the decrease of the Hashrate of selfish miners, making the mining pools more cautious on performing selfish mining.

Private information retrieval (PIR) is a fundamental tool for preserving query privacy when accessing outsourced data. All previous PIR constructions have significant costs preventing widespread use. In this work, we present private stateful information retrieval (PSIR), an extension of PIR, allowing clients to be stateful and maintain information between multiple queries. Our design of the PSIR primitive maintains three important properties of PIR: multiple clients may simultaneously query without complex concurrency primitives, query privacy should be maintained if the server colludes with other clients, and new clients should be able to enroll into the system by exclusively interacting with the server.

We present a PSIR framework that reduces an online query to performing one single-server PIR on a sub-linear number of database records. All other operations beyond the single-server PIR consist of cryptographic hashes or plaintext operations. In practice, the dominating costs of resources occur due to the public-key operations involved with PIR. By reducing the input database to PIR, we are able to limit expensive computation and avoid transmitting large ciphertexts. We show that various instantiations of PSIR reduce server CPU by up to 10x and online network costs by up to 10x over the previous best PIR construction.

Cube attacks are an important type of key recovery attacks against NFSR-based cryptosystems. The key step in cube attacks closely related to key recovery is recovering superpolies. However, in the previous well-known cube attacks including original, division property based, and correlation cube attacks, the algebraic normal forms of superpolies could hardly be proved to be exact, which involves a small failure probability or unpractical computations. In this paper, we propose a new variant of cube attacks called deterministic cube attacks, which aims at recovering the exact algebraic normal forms of superpolies efficiently and practically. These new attacks are developed based on degree evaluation method proposed by Liu in CRYPTO2017. We apply our new cube attacks to the round-reduced Trivium. As a result, we recover the exact algebraic normal forms of some superpolies for the 818-, 819-, 837-, and 838-round Trivium. By the way, it is proved that the best cube of size 37 given by Liu in CRYPTO2017 is not a zero-sum distinguisher but a zero-biased distinguisher by recovering its exact superpoly for the first time. To the best of our knowledge, it is the first time that superpolies of cubes with the sizes less than 40 could be practically recovered for Trivium up to 838 rounds. Hopefully, our new attacks would provide some new insights on cube attacks against NFSR-based ciphers.

We introduce a new type of cryptanalytic algorithm on the obfuscations based on the branching programs. Applying this algorithm to two recent general-purpose obfuscation schemes one by Chen et al. (CRYPTO 2018) and the other by Bartusek et al. (TCC 2018), we can show that they do not have the desired security. In other words, there exist two functionally equivalent branching programs whose obfuscated programs can be distinguished in polynomial time. Our strategy is to reduce the security problem of indistinguishability obfuscation into the distinguishing problem of two distributions where polynomially many samples are given. More precisely, we perform the obfuscating process ourselves with randomly chosen secret values to obtain identical and independent samples according to the distribution of evaluations of obfuscations. We then use the variance of samples as a new distinguisher of two functionally equivalent obfuscated programs. This statistical attack gives a new perspective on the security of the indistinguishability obfuscations: We should consider the shape of distributions of the evaluations of obfuscations to ensure the security. In other words, while most of the previous (weak) security proofs have been studied with respect to algebraic attack model or ideal model, our attack shows that this algebraic security is not enough to achieve indistinguishability obfuscation.

Parallel cryptographic implementations are generally considered to be more advantageous than their non-parallel counterparts in mitigating side-channel attacks because of their higher noise-level. So far as we know, the side-channel security of GPU-based cryptographic implementations have been studied in recent years, and those implementations then turn out to be susceptible to some side-channel attacks. Unfortunately, the target parallel implementations in their work do not achieve strict parallelism because of the occurrence of cached memory accesses or the use of conditional branches, so how strict parallelism affects the side-channel security of cryptographic implementations is still an open problem. In this work, we make a case study of the side-channel security of a GPU-based bitsliced AES implementation in terms of bit-level parallelism and thread-level parallelism in order to show the way that works to reduce the side-channel security of strict parallel implementations. We present GPU-based bitsliced AES implementation as the study case because (1) it achieves strict parallelism so as to be resistant to cache-based attacks and timing attacks; and (2) it achieves both bit-level parallelism and thread-level parallelism (a.k.a. task-level parallelism), which enables us to research from multiple perspectives. More specifically, we first set up our testbed and collect electro-magnetic (EM) traces with some special techniques. Then, the measured traces are analyzed in two granularity. In bit-level parallelism, we give a non-profiled leakage detection test before mounting attacks with our proposed bit-level fusion techniques like multi-bits feature-level fusion attacks (MBFFA) and multi-bits decision-level fusion attacks (MBDFA). In thread-level parallelism, a profiled leakage detection test is employed to extract some special information from multi-threads leakages, and with the help of those information our proposed multi-threads hybrid fusion attack (MTHFA) method takes effect. Last, we propose a simple metric to quantify the side-channel security of parallel cryptographic implementations. Our research shows that the secret key of our target implementation can be recovered with less cost than expected, which suggests that the side-channel security of parallel cryptographic implementations should be reevaluated before application.

Most classical consensus protocols rely on a leader to coordinate nodes’ voting efforts. One novel idea that stems from blockchain-style consensus is to rely, instead, on a “longest-chain” idea for such coordination. Such a longest-chain idea was initially considered in randomized protocols, where in each round, a node has some probability of being elected a leader who can propose the next block. Recently, well-known systems have started implementing the deterministic counterpart of such longest-chain protocols — the deterministic counterpart is especially attractive since it is even simpler to implement than their randomized cousins. A notable instantiation is the Aura protocol which is shipped with Parity’s open-source Ethereum implementation. Interestingly, mathematical analyses of deterministic, longest-chain protocols are lacking even though there exist several analyses of randomized versions. In this paper, we provide the first formal analysis of deterministic, longest-chain-style consensus. We show that a variant of the Aura protocol can defend against a Byzantine adversary that controls fewer than 1/3 fraction of the nodes, and this resilience parameter is tight by some technical interpretation. Based on insights gained through our mathematical treatment, we point out that Aura’s concrete instantiation actually fails to achieve the resiliene level they claim. Finally, while our tight proof for the longest-chain protocol is rather involved and non-trivial; we show that a variant of the “longest-chain” idea which we call “largest-set” enables a textbook construction that admits a simple proof (albeit with slower confirmation).

We provide the first constructions of two round information-theoretic (IT) secure multiparty computation (MPC) protocols in the plain model that tolerate any $t<n/2$ malicious corruptions. Our protocols satisfy the strongest achievable standard notions of security in two rounds in different communication models.

Previously, IT-MPC protocols in the plain model either required a larger number of rounds, or a smaller minority of corruptions.

We develop new constructions of lattice-based PRFs using keyed pseudorandom synthesizers. We generalize all of the known `basic' parallel lattice-based PRFs--those of [BPR12], [BLMR13], and [BP14]--to build highly parallel lattice-based PRFs with smaller modulus (and thus better reductions from worst-case lattice problems) while still maintaining computational efficiency asymptotically equal to the fastest known lattice-based PRFs at only the cost of larger key sizes.

In particular, we build several parallel (in $NC^{2}$) lattice-based PRFs with modulus independent of the number of PRF input bits based on both standard LWE and ring LWE. Our modulus for these PRFs is just $O \left(m^{ f \left(m \right)} \right)$ for lattice dimension $m$ and any function $f \left(m \right) \in \omega \left(1 \right)$. The only known parallel construction of a lattice-based PRF with such a small modulus is a construction from Banerjee's thesis, and some of our parallel PRFs with equivalently small modulus have smaller key sizes and are very slightly faster (when using FFT multiplication). These PRFs also asymptotically match the computational efficiency of the most efficient PRFs built from any LWE- or ring LWE-based assumptions known (potentially excluding some concurrent work), respectively, and concretely require less computation per output than any known parallel lattice-based PRFs (again when using FFT multiplication).

We additionally use our techniques to build other efficient PRFs with very low circuit complexity (but higher modulus) which improve known results on highly parallel lattice PRFs. For instance, for input length $\lambda$, we show that there exists a ring LWE-based PRF in $NC^{1}$ with modulus proportional to $m^{\lambda^{c}}$ for any $c \in \left(0, 1 \right)$. Constructions from lattices with this circuit depth were only previously known from larger moduli.

Coin toss has been extensively studied in the cryptography literature, and the well-accepted notion of fairness (henceforth called strong fairness) requires that a corrupt coalition cannot cause non-negligible bias. It is well-understood that two-party coin toss is impossible if one of the parties can prematurely abort; further, this impossibility generalizes to multiple parties with a corrupt majority (even if the adversary is computationally bounded and fail-stop only).

Interestingly, the original proposal of (two-party) coin toss protocols by Blum in fact considered a weaker notion of fairness: imagine that the (randomized) transcript of the coin toss protocol defines a winner among the two parties. Now Blum's notion requires that a corrupt party cannot bias the outcome in its favor (but self-sacrificing bias is allowed). Blum showed that this weak notion is indeed attainable for two parties assuming the existence of one-way functions.

In this paper, we ask a very natural question which, surprisingly, has been overlooked by the cryptography literature: can we achieve Blum's weak fairness notion in multi-party coin toss? What is particularly interesting is whether this relaxation allows us to circumvent the corrupt majority impossibility that pertains to strong fairness. Even more surprisingly, in answering this question, we realize that it is not even understood how to define weak fairness for multi-party coin toss. We propose several natural notions drawing inspirations from game theory, all of which equate to Blum's notion for the special case of two parties. We show, however, that for multiple parties, these notions vary in strength and lead to different feasibility and infeasibility results.

The rapid distribution of lightweight devices raised the demand for efficient encryption and authenticated encryption schemes for small messages. For this purpose, Andreeva et al. recently proposed forkciphers, which fork the middle state within a cipher and encrypt it twice further under two smaller independent permutations. So, forkciphers can produce two output blocks which can allow to authenticate and encrypt small messages more efficiently. As instance of particular interest, Andreeva et al. proposed ForkAES, a tweakable forkcipher based on the AES-128 round function, which forks the state after five out of ten rounds. While their authenticated encrypted schemes were accompanied by proofs, the security discussion for ForkAES could not be covered in their work, and founded on existing results on the AES and KIASU-BC; so, the study of advanced differential attacks remained to be filled by the community. This work tries to foster the understanding of the security of ForkAES. It outlines a rectangle and an impossible-differential attack on nine rounds in the single-key related-tweak model; moreover, it describes a rectangle attack on ten rounds for a fraction of approximately $2^{32}$ keys. We emphasize that our results do not break ForkAES in the single-key setting, but shed more light on its security margin.

It is well known that Canright’s tower field construction leads to a very small, unprotected AES S-box circuit by recursively embedding Galois Field operations into smaller fields. The current size record for the AES S-box by Boyar, Matthews and Peralta improves the original design with optimal subcomponents, while maintaining the overall tower-field structure. Similarly, all small state-of-the-art first-order SCA-secure AES S-box constructions are based on a tower field structure. We demonstrate that a smaller first-order secure AES S-box is achievable by representing the field inversion as a multiplication chain of length 4. Based on this representation, we showcase a very compact S-box circuit with only one GF($2^8$)-multiplier instance. Thereby, we introduce a new high-level representation of the AES S-box and set a new record for the smallest first-order secure implementation

In this work, we propose a faster homomorphic linear transform algorithm for structured matrices such as the discrete Fourier transform (DFT) and linear transformations in bootstrapping.

First, we proposed new method to evaluate the DFT homomorphically for a given packed ciphertext from the Cooley-Tukey fast Fourier transform algorithm. While the previous method requires $O(\sqrt n)$ rotations and $O(n)$ constant vector multiplications, our method only needs $O(\log n)$ rotations/multiplications by consuming $O(\log n)$ depth for the length of input vector $n$.

Second, we apply the same method to the linear transform of bootstrapping for $\textsf{HEAAN}$. To achieve this, we construct a recursive relation of matrices in those linear transformations. Accordingly, we can highly accelerate the linear transformation part of bootstrapping: the number of homomorphic operations becomes logarithmic to the number of slots, as in homomorphic DFT.

We also implement both algorithms. Our homomorphic DFT with length $2^{14}$ only takes about 8 seconds which is about 150 times faster result than previous one. The bootstrapping for $\textsf{HEAAN}$ with our linear transform algorithm takes about 2 minutes for $\mathbb{C}^{32768}$ plaintext space with 8 bit precision, which takes 26 hours using the previous method.

This paper investigates the construction of lightweight MDS matrices with generalized Feistel structures (GFS). The approach developed by this paper consists in deriving MDS matrices from the product of several sparser ones. This can be seen as a generalization to several matrices of the recursive construction which derives MDS matrices as the powers of a single companion matrix. The first part of this paper gives some theoretical results on the iteration of GFS and the second part gives concrete instantiations. The results match the best known lightweight $4\times 4$ MDS matrix and improve the best known $6\times 6$ and $8\times 8$ MDS matrices. Based on GFS structure, we propose some types of sparse matrices that are called EGFS matrices. Then, by applying binary linear functions to several round of EGFS matrices, we propose lightweight $4\times 4$, $6\times 6$ and $8\times 8$ MDS matrices which are implemented with 67, 158 and 272 XOR for 8-bit input, respectively. The major work of this paper is the design of an $8\times 8$ MDS matrix with 272 XOR for 8-bit input, since the best known result is 392 XOR.

In conventional PKI, CAs are assumed to be fully trusted. However, in practice, CAs' absolute responsibility for providing trustworthiness caused major security and privacy issues. To prevent such issues, Google introduced the concept of Certificate Transparency (CT) in 2013. Later, several new PKI models (e.g., AKI, ARPKI, and DTKI) are proposed to reduce the level of trust to the CAs. However, all of these proposals are still vulnerable to split-world attacks if the adversary is capable of showing different views of the log to the targeted victims. In this paper, we propose a new PKI architecture with certificate transparency based on blockchain, what we called CertLedger, to eliminate the split-world attacks and to provide an ideal certificate/revocation transparency. All TLS certificates, their revocation status, entire revocation process, and trusted CA management are conducted in the CertLedger. CertLedger provides a unique, efficient, and trustworthy certificate validation process eliminating the conventional inadequate and incompatible certificate validation processes implemented by different software vendors. TLS clients in the CertLedger also do not require to make certificate validation and store the trusted CA certificates anymore. We analyze the security and performance of the CertLedger and provide a comparison with the previous proposals.

The FHE (fully homomorphic encryption) schemes [7, 13] based on the modified AGCD problem (noise-free AGCD problem) are vulnerable to quantum attacks, because its security relies partly on the hardness of factoring, and some FHE schemes based on the decisional AGCD without the noise-free assumption, for example [1], has a drawback that its ciphertexts are very large. In this paper, we construct a new batch FHE scheme based on the decisional AGCD problem to overcome these weaknesses and prove its security.