International Association
for Cryptologic Research

Zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in cryptocurrencies and other applications. In many systems each client downloads and verifies every new proof, and so proofs must be small and cheap to verify. The most practical schemes require either a trusted setup, as in (pre-processing) zk-SNARKs, or verification complexity that scales linearly with the complexity of the relation, as in Bulletproofs. The structured reference strings required by most zk-SNARK schemes can be constructed with multi-party computation protocols, but the resulting parameters are specific to an individual relation. Groth et al. discovered a zk-SNARK protocol with a universal and updateable structured reference string, however the string scales quadratically in the size of the supported relations.

Here we describe a zero-knowledge SNARK, Sonic, which supports a universal and continually updateable structured reference string that scales linearly in size. Sonic proofs are constant size, and in the batch verification context the marginal cost of verification is comparable with the most efficient SNARKs in the literature. We also describe a generally useful technique in which untrusted ``helpers'' can compute advice which allows batches of proofs to be verified more efficiently.

In this work, we propose the first post-quantum UC-commitment scheme in the Global Random Oracle Model, where only one non-programmable random oracle is available. The security of our proposal is based on two well-established post-quantum hardness assumptions from coding theory: The Syndrome Decoding and the Goppa Distinguisher. We prove that our proposal is perfectly hiding and computationally binding. The scheme is secure against static malicious adversaries.

Division property is a new cryptanalysis method introduced by Todo at Eurocrypt'15 that proves to be very efficient on block ciphers and stream ciphers. It can be viewed as a generalization or a more precise version of integral cryptanalysis, that allows to take into account bit properties. However, it is very cumbersome to study the propagation of a given division property through the layers of a block cipher. Fortunately, computer-aided techniques can be used to this end and many new results have been found. Nonetheless, we claim that the previous techniques do not consider the full search space. Indeed, we show that even if the previous techniques fail to find a distinguisher based on the division property over a given function $E$, we can find a distinguisher over a linearly equivalent function, \ie over $L_{out} \circ E \circ L_{in}$ with $L_{out}$ and $L_{in}$ being linear mappings, and such distinguisher is still relevant. We first show that the representation of the block cipher heavily influences the propagation of the division property, and exploiting this, we give an algorithm to efficiently search for such linear mappings $L_{out}$ and $L_{in}$. As a result, we are able to exhibit a new distinguisher over 10 rounds of RECTANGLE, while the previous best known distinguisher was over 9 rounds. Our algorithm also allows us to rule out such distinguisher over strictly more than 9 rounds of PRESENT, which is the highest known number of rounds on which we can build an integral distinguisher. Finally, we also give some insight about the construction of an S-box to strengthen a block cipher against our technique. As such, we exhibit some variant of RECTANGLE and PRESENT, on which we improve the maximum number of rounds we can distinguish by two.

Ever since the first candidate white-box implementations by Chow et al. in 2002, producing a secure white-box implementation of AES has remained an enduring challenge. Following the footsteps of the original proposal by Chow et al., other constructions were later built around the same framework. In this framework, the round function of the cipher is "encoded" by composing it with non-linear and affine layers known as encodings. However, all such attempts were broken by a series of increasingly efficient attacks that are able to peel off these encodings, eventually uncovering the underlying round function, and with it the secret key.

These attacks, however, were generally ad-hoc and did not enjoy a wide applicability. As our main contribution, we propose a generic and efficient algorithm to recover affine encodings, for any Substitution-Permutation-Network (SPN) cipher, such as AES, and any form of affine encoding. For AES parameters, namely 128-bit blocks split into 16 parallel 8-bit S-boxes, affine encodings are recovered with a time complexity estimated at $2^{32}$ basic operations, independently of how the encodings are built.

This algorithm is directly applicable to a large class of schemes. We illustrate this on a recent proposal due to Baek, Cheon and Hong, which was not previously analyzed. While Baek et al. evaluate the security of their scheme to 110 bits, a direct application of our generic algorithm is able to break the scheme with an estimated time complexity of only $2^{35}$ basic operations.

As a second contribution, we show a different approach to cryptanalyzing the Baek et al. scheme, which reduces the analysis to a standalone combinatorial problem, ultimately achieving key recovery in time complexity $2^{31}$. We also provide an implementation of the attack, which is able to recover the secret key in about 12 seconds on a standard desktop computer.

Differential attacks are one of the main ways to attack block ciphers. Hence, we need to evaluate the security of a given block cipher against these attacks. One way to do so is to determine the minimal number of active S-boxes, and use this number along with the maximal differential probability of the S-box to determine the minimal probability of any differential characteristic. Thus, if one wants to build a new block cipher, one should try to maximize the minimal number of active S-boxes. On the other hand, the related-key security model is now quite important, hence, we also need to study the security of block ciphers in this model.

In this work, we search how one could design a key schedule to maximize the number of active S-boxes in the related-key model. However, we also want this key schedule to be efficient, and therefore choose to only consider permutations. Our target is AES, and along with a few generic results about the best reachable bounds, we found a permutation to replace the original key schedule that reaches a minimal number of active S-boxes of 20 over 6 rounds, while no differential characteristic with a probability larger than $2^{-128}$ exists. We also describe an algorithm which helped us to show that there is no permutation that can reach 18 or more active S-boxes in 5 rounds. Finally, we give several pairs $(P_s, P_k)$, replacing respectively the ShiftRows operation and the key schedule of the AES, reaching a minimum of 21 active S-boxes over 6 rounds, while again, there is no differential characteristic with a probability larger than $2^{-128}$.

Alongside CHES 2018 the side channel contest 'Deep learning vs. classic profiling' was held. Our team won both AES challenges (masked AES implementation), working under the handle AGSJWS. Here we describe and analyse our attack.

We can solve the more difficult of the two challenges with $2$ to $5$ power traces, which is much less than was available in the contest.

Our attack combines techniques from machine learning with classical techniques. The attack was superior to all classical and deep learning based attacks which we have tried. Moreover, it provides some insights on the implementation.

In this article we discuss the modular pentavariate and hexavariate linear equations and its usefulness for asymmetric cryptography. Construction of our key encapsulation mechanism dwells on such modular linear equations whose unknown roots can be interpreted as long vectors within a lattice which surpasses the Gaussian heuristic; hence unable to be identified by the LLL lattice reduction algorithm. By utilizing our specially constructed public key when computing the modular hexavariate linear ciphertext equation, the decapsulation mechanism can correctly output the shared secret parameter. The scheme has short key length, no decapsulation failure issues, plaintext-to-ciphertext expansion of one-to-one as well as uses ``simple" mathematics in order to achieve maximum simplicity in design, such that even practitioners with limited mathematical background will be able to understand the arithmetic. Due to inexistence of efficient algorithms running upon a quantum computer to obtain the roots of our modular pentavariate and hexavariate linear equation and also to retrieve the private key from the public key, our key encapsulation mechanism can be a probable candidate for seamless post quantum drop-in replacement for current traditional asymmetric schemes.

Event date: 26 August to 29 August 2019
Submission deadline: 15 March 2019
Notification: 24 May 2019

Event date: 5 June to 7 June 2019
Submission deadline: 30 March 2019
Notification: 30 April 2019

Streebog and Kuznyechik are the latest symmetric cryptographic primitives standardized by the Russian GOST. They share the same S-Box, $\pi$, whose design process was not described by its authors. In previous works, Biryukov, Perrin and Udovenko recovered two completely different decompositions of this S-Box.

We revisit their results and identify a third decomposition of $\pi$. It is an instance of a fairly small family of permutations operating on $2m$ bits which we call TKlog and which is closely related to finite field logarithms. Its simplicity and the small number of components it uses lead us to claim that it has to be the structure intentionally used by the designers of Streebog and Kuznyechik.

The $2m$-bit permutations of this type have a very strong algebraic structure: they map multiplicative cosets of the subfield $\mathbb{F}_{2^{m}}^{*}$ to additive cosets of $\mathbb{F}_{2^{m}}^{*}$. Furthermore, the function relating each multiplicative coset to the corresponding additive coset is always essentially the same. To the best of our knowledge, we are the first to expose this very strong algebraic structure.

We also investigate other properties of the TKlog and show in particular that it can always be decomposed in a fashion similar to the first decomposition of Biryukov et al., thus explaining the relation between the two previous decompositions. It also means that it is always possible to implement a TKlog efficiently in hardware and that it always exhibits a visual pattern in its LAT similar to the one present in $\pi$.

While we could not find attacks based on these new results, we discuss the impact of our work on the security of Streebog and Kuznyechik. To this end, we provide a new simpler representation of the linear layer of Streebog as a matrix multiplication in the exact same field as the one used to define $\pi$. We deduce that this matrix interacts in a non-trivial way with the partitions preserved by $\pi$.

Ishai et al. [28, 29] introduced a powerful technique that provided a general transformation from secure multiparty computation (MPC) protocols to zero-knowledge (ZK) proofs in a black-box way, called “MPC-in-the-head”. A recent work [27] extends this technique and shows two ZK proof protocols from a secure two-party computation (2PC) protocol. The works [28, 27] both show a basic three-round ZK proof protocol which can be made negligibly sound by standard sequential repetition [19]. Under general black-box zero knowledge notion, neither ZK proofs nor arguments with negligible soundness error can be achieved in less than four rounds without additional assumptions [15]. In this paper, we address this problem under the notion of augmented black-box zero knowledge [26], which is defined with a new simulation method, called augmented black-box simulation. It is presented by permitting the simulator to have access to the verifier’s current private state (i.e. “random coins” used to compute the current message) in a special manner. We first show a three-round augmented black-box ZK proof for the language graph 3-colorability, denoted G3C. And then we generalize the construction to a three-round augmented black-box ZK proof for any NP relation R(x, w) without relying on expensive Karp reductions. The two constructions are based on a family of claw-free permutations and the general construction is additionally based on a black-box use of a secure 2PC for a related two-party functionality. Besides, we show our protocols can be made negligibly sound by directly parallel repetition.

Online registration for FSE 2019 is now available at https://secure.iacr.org/conferences/fse2019/register/.

The early registration deadline is February 26, 2019. After that date, registration prices will increase!

FSE 2019 will take place in Paris, France during March 25-28, 2019. For more information on the conference please visit https://fse.iacr.org/2019.

We present the ring-based configuration of the NIST submission Round5, a Ring Learning with Rounding (RLWR)- based IND-CPA secure public-key encryption scheme. It combines elements of the NIST candidates Round2 (use of RLWR as underlying problem, having $1+x+\ldots +x^n$ with $n+1$ prime as reduction polynomial, allowing for a large design space) and HILA5 (the constant-time error-correction code XEf). Round5 performs part of encryption, and decryption via multiplication in $\mathbb{Z}_{p}[x]/(x^{n+1}-1)$, and uses secret-key polynomials that have a factor $(x-1)$. This technique reduces the failure probability and makes correlation in the decryption error negligibly low. The latter allows the effective application of error correction through XEf to further reduce the failure rate and shrink parameters, improving both security and performance. We argue for the security of Round5, both formal and concrete. We further analyze the decryption error, and give analytical as well as experimental results arguing that the decryption failure rate is lower than in Round2, with negligible correlation in errors. IND-CCA secure parameters constructed using Round5 and offering more than 232 and 256 bits of quantum and classical security respectively, under the conservative core sieving model, require only 2144 B of bandwidth. For comparison, similar, competing proposals require over 30% more bandwidth. Furthermore, the high flexibility of Round5's design allows choosing finely tuned parameters fitting the needs of diverse applications -- ranging from the IoT to high-security levels.

We propose the General Sieve Kernel (G6K, pronounced /ʒe.si.ka/), an abstract stateful machine supporting a wide variety of lattice reduction strategies based on sieving algorithms. Using the basic instruction set of this abstract stateful machine, we first give concise formulations of previous sieving strategies from the literature and then propose new ones. We then also give a light variant of BKZ exploiting the features of our abstract stateful machine. This encapsulates several recent suggestions (Ducas at Eurocrypt 2018; Laarhoven and Mariano at PQCrypto 2018) to move beyond treating sieving as a blackbox SVP oracle and to utilise strong lattice reduction as preprocessing for sieving. Furthermore, we propose new tricks to minimise the sieving computation required for a given reduction quality with mechanisms such as recycling vectors between sieves, on-the-fly lifting and flexible insertions akin to Deep LLL and recent variants of Random Sampling Reduction.

Moreover, we provide a highly optimised, multi-threaded and tweakable implementation of this machine which we make open-source. We then illustrate the performance of this implementation of our sieving strategies by applying G6K to various lattice challenges. In particular, our approach allows us to solve previously unsolved instances of the Darmstadt SVP (151, 153, 155) and LWE (e.g. (75, 0.005)) challenges. Our solution for the SVP-151 challenge was found 400 times faster than the time reported for the SVP-150 challenge, the previous record. For exact SVP, we observe a performance crossover between G6K and FPLLL's state of the art implementation of enumeration at dimension 70.

Continuous Key Agreement (CKA) is a two-party procedure used by Double Ratchet protocols (e. g., Signal). This is a continuous and synchronous protocol that generates a fresh key for every sent/received message. It guarantees forward secrecy and Post-Compromise Security (PCS). PCS allows for reestablishing the security within a few rounds after the state of one of the parties has been compromised. Alwen et al. have recently proposed a new KEM-based CKA construction where every message contains a ciphertext and a fresh public key. This can be made quantum-safe by deploying a quantum-safe KEM. They mention that the bandwidth can be reduced when using an ElGamal KEM (which is not quantum-safe). In this paper, we generalized their approach by defining a new primitive, namely Merged KEM (MKEM). This primitive merges the key generation and the encapsulation steps of a KEM. This is not possible for every KEM and we discuss cases where a KEM can be converted to an MKEM. One example is the quantum-safe proposal BIKE1, where the BIKE-MKEM saves 50% of the communication bandwidth, compared to the original construction. In addition, we offer the notion and two constructions for hybrid CKA.

Link Prediction is an important and well-studied problem for social networks. Given a snapshot of a graph, the link prediction problem predicts which new interactions between members are most likely to occur in the near future. As networks grow in size, data owners are forced to store the data in remote cloud servers which reveals sensitive information about the network. The graphs are therefore stored in encrypted form.

We study the link prediction problem on encrypted graphs. To the best of our knowledge, this secure link prediction problem has not been studied before. We use the number of common neighbors for prediction. We present three algorithms for the secure link prediction problem. We design prototypes of the schemes and formally prove their security. We execute our algorithms in real-life datasets.

Constant blinding is an efficient countermeasure against just-in-time (JIT) spraying attacks. Unfortunately, this mitigation mechanism is not always implemented correctly. One such example is the constant blinding mechanism found in the Adobe Flash Player. Instead of choosing a strong mainstream pseudo-random number generator (PRNG), the Flash Player designers chose to implement a proprietary one. This led to the discovery of a vulnerability that can be exploited to recover the initial seed used by the PRNG and thus, to bypass the constant blinding mechanism. Using this vulnerability as a starting point, we show that no matter the parameters used by the previously mentioned PRNG it still remains a weak construction. A consequence of this study is an improvement of the seed recovering mechanism from previously known complexity of $\mathcal O(2^{21})$ to one of $\mathcal O(2^{11})$.

We present qTESLA, a family of post-quantum digital signature schemes based on the ring learning with errors (R-LWE) problem that exhibits several attractive features such as simplicity, high-performance, strong security guarantees against quantum adversaries, and built-in protection against certain side-channel and fault attacks. qTESLA, selected for the first round of NIST's post-quantum cryptography standardization project, consolidates a series of recent proposals of R-LWE-based signature schemes originating in works by Lyubashevsky, and Bai and Galbraith, leading to the best performance among lattice-based signature schemes instantiated against state-of-the-art quantum attacks and implemented with protection against timing and cache side-channels. We provide full-fledged, constant-time reference and AVX2-optimized implementations that showcase the high-speed and simplicity of our scheme. As part of our implementations, we present an efficient and portable Gaussian sampler that gets by without using floating-point operations and is easily implementable in constant-time. While the Gaussian sampling is solely used in qTESLA's key generation, variants of it are used in most lattice-based primitives and, hence, our approach is of independent interest for other lattice-based implementations.

Relative cryptographic semantic security for encrypted words of user data at runtime holds in the emerging field of encrypted computing, in conjunction with an appropriate instruction set and compiler. An information obfuscation calculus for program compilation in that context is introduced here that quantifies the security exactly, improving markedly on the result.

In ASIACCS 2015, Nuñez, Agudo, and Lopez proposed a proxy re-encryption scheme, NTRUReEncrypt, based on NTRU, which allows a proxy to translate ciphertext under the delegator's public key into a re-encrypted ciphertext that can be decrypted correctly by delegatee's private key. In addition to its potential resistance to quantum algorithm, the scheme was also considered to be efficient. However, in this paper we point out that the re-encryption process will increase the decryption error, and the increased decryption error will lead to a reaction attack that enables the proxy to recover the private key of the delegator and the delegatee. Moreover, we also propose a second attack which enables the delegatee to recover the private key of the delegator when he collects enough re-encrypted ciphertexts from a same message. We reevaluate the security of NTRUReEncrypt, and also give suggestions and discussions on potential mitigation methods.