International Association
for Cryptologic Research

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.

We consider the problem of garbling arithmetic circuits and present a garbling scheme for inner-product predicates over exponentially large fields. Our construction stems from a generic transformation from predicate encryption which makes only blackbox calls to the underlying primitive. The resulting garbling scheme has practical efficiency and can be used as a garbling gadget to securely compute common arithmetic subroutines. We also show that inner-product predicates are complete by generically bootstrapping our construction to arithmetic garbling for polynomial-size circuits, albeit with a loss of concrete efficiency. In the process of instantiating our construction we propose two new predicate encryption schemes, which might be of independent interest. More specifically, we construct (i) the first pairing-free (weakly) attribute-hiding non-zero inner-product predicate encryption scheme, and (ii) a key-homomorphic encryption scheme for linear functions from bilinear maps. Both schemes feature constant-size keys and practical efficiency.

Group signatures allow creating signatures on behalf of a group, while remaining anonymous. To prevent misuse, there exists a designated entity, named the opener, which can revoke anonymity by generating a proof which links a signature to its creator. Still, many intermediate cases have been discussed in the literature, where not the full power of the opener is required, or the users themselves require the power to claim (or deny) authorship of a signature and (un-)link signatures in a controlled way. However, these concepts were only considered in isolation. We unify these approaches, supporting all these possibilities simultaneously, providing fine-granular openings, even by members. Namely, a member can prove itself whether it has created a given signature (or not), and can create a proof which makes two created signatures linkable (or unlinkable resp.) in a controlled way. Likewise, the opener can show that a signature was not created by a specific member and can prove whether two signatures stem from the same signer (or not) without revealing anything else. Combined, these possibilities can make full openings irrelevant in many use-cases. This has the additional benefit that the requirements on the reachability of the opener are lessened. Moreover, even in the case of an involved opener, our framework is less privacy-invasive, as the opener no longer requires access to the signed message. Our provably secure black-box CCA-anonymous construction with dynamic joins requires only standard building blocks. We prove its practicality by providing a performance evaluation of a concrete instantiation, and show that our non-optimized implementation is competitive compared to other, less feature-rich, notions.

Secure multiparty computation allows a set of mutually distrusting parties to securely compute a function of their private inputs, revealing only the output, even if some of the parties are corrupt. Recent years have seen an enormous amount of work that drastically improved the concrete efficiency of secure multiparty computation protocols. Many secure multiparty protocols work in an ``offline-online" model. In this model, the computation is split into two main phases: a relatively slow ``offline phase", which the parties execute before they know their input, and a fast ``online phase", which the parties execute after receiving their input.

One of the most popular and efficient protocols for secure multiparty computation working in this model is the SPDZ protocol (Damgaard et al., CRYPTO 2012). The SPDZ offline phase is function independent, i.e., does not requires knowledge of the computed function at the offline phase. Thus, a natural question is: can the efficiency of the SPDZ protocol be improved if the function is known at the offline phase?

In this work, we answer the above question affirmatively. We show that by using a function dependent preprocessing protocol, the online communication of the SPDZ protocol can be brought down significantly, almost by a factor of 2, and the online computation is often also significantly reduced. In scenarios where communication is the bottleneck, such as strong computers on low bandwidth networks, this could potentially almost double the online throughput of the SPDZ protocol, when securely computing the same circuit many times in parallel (on different inputs).

We present two versions of our protocol: Our first version uses the SPDZ offline phase protocol as a black-box, which achieves the improved online communication at the cost of slightly increasing the offline communication. Our second version works by modifying the state-of-the-art SPDZ preprocessing protocol, Overdrive (Keller et al., Eurocrypt 2018). This version improves the overall communication over the state-of-the-art SPDZ when the function is known at the offline phase.

In EUROCRYPT 2018, Cid et al. introduced a new concept on the cryptographic property of S-boxes: Boomerang Connectivity Table (BCT for short) for evaluating the subtleties of boomerang-style attacks. Very recently, BCT and the boomerang uniformity, the maximum value in BCT, were further studied by Boura and Canteaut. Aiming at providing new insights, we show some new results about BCT and the boomerang uniformity of permutations in terms of theory and experiment in this paper. Firstly, we present an equivalent technique to compute BCT and the boomerang uniformity, which seems to be much simpler than the original definition. Secondly, thanks to Carlet's idea, we give a characterization of functions $f$ from $\mathbb{F}_{2}^n$ to itself with boomerang uniformity $\delta_{f}$ by means of the Walsh transform. Thirdly, by our method, we consider boomerang uniformities of some specific permutations, mainly the ones with low differential uniformity. Finally, we obtain another class of $4$-uniform BCT permutation polynomials over $\mathbb{F}_{2^n}$, which is the first binomial.

A cryptographic function with a fixed-length output, such as a block cipher, hash function, or message authentication code (MAC), should behave as a random mapping. The mapping's randomness can be evaluated with statistical tests. Statistical test suites typically used to evaluate cryptographic functions, such as the NIST test suite, are not well-suited for testing fixed-output-length cryptographic functions. Also, these test suites employ a frequentist approach, making it difficult to obtain an overall evaluation of the mapping's randomness. This paper describes CryptoStat, a test suite that overcomes the aforementioned deficiencies. CryptoStat is specifically designed to test the mappings of fixed-output-length cryptographic functions, and CryptoStat employs a Bayesian approach that quite naturally yields an overall evaluation of the mappings' randomness. Results of applying CryptoStat to reduced-round and full-round versions of the AES block ciphers and the SHA-1 and SHA-2 hash functions are reported; the results are analyzed to determine the algorithms' randomness margins.

Pairing-based cryptography is now a mature science. However implementation of a pairing-based protocol can be challenging, as the efficient computation of a pairing is difficult, and the existing literature on implementation might not match with the requirements of a particular application. Furthermore developments in our understanding of the true security of pairings render much of the existing literature redundant. Here we take a fresh look and develop a simpler three-stage algorithm for calculating pairings, as they arise in real applications.

White-box cryptography is the last security barrier for a cryptographic software implementation deployed in an untrusted environment. The principle of internal encodings is a commonly used white-box technique to protect block cipher implementations. It consists in representing an implementation as a network of look-up tables which are then encoded using randomly generated bijections (the internal encodings). When this approach is implemented based on nibble (i.e. 4-bit wide) encodings, the protected implementation has been shown to be vulnerable to differential computation analysis (DCA). The latter is essentially an adaptation of differential power analysis techniques to computation traces consisting of runtime information, e.g., memory accesses, of the target software. In order to thwart DCA, it has then been suggested to use wider encodings, and in particular byte encodings, at least to protect the outer rounds of the block cipher which are the prime targets of DCA.

In this work, we provide an in-depth analysis of when and why DCA works. We pinpoint the properties of the target variables and the encodings that make the attack (in)feasible. In particular, we show that DCA can break encodings wider than 4-bit, such as byte encodings. Additionally, we propose new DCA-like attacks inspired from side-channel analysis techniques. Specifically, we describe a collision attack particularly effective against the internal encoding countermeasure. We also investigate mutual information analysis (MIA) which naturally applies in this context. Compared to the original DCA, these attacks are also passive and they require very limited knowledge of the attacked implementation, but they achieve significant improvements in terms of trace complexity. All the analyses of our work are experimentally backed up with various attack simulation results. We also verified the practicability of our analyses and attack techniques against a publicly available white-box AES implementation protected with byte encodings --which DCA has failed to break before-- and against a ``masked'' white-box AES implementation --which intends to resist DCA.

Event date: 9 July to 11 July 2019
Submission deadline: 10 March 2019
Notification: 15 April 2019

The Security and Cryptography Group at Microsoft Research, led by Brian LaMacchia, is looking for research interns.

The researchers and engineers in the MSR Security and Cryptography team pursue both theoretical and applied research in our field that will have impact for Microsoft, Microsoft’s customers, and the industry at large. Our current projects include the design and development of quantum-resistant public-key cryptographic algorithms and protocols, high-performance post-quantum cryptographic libraries, quantum cryptanalysis, and end-to-end verifiable election technology.

We are interested in applicants with expertise in one or more of the following: isogeny-based cryptography, lattice-based cryptography, classical and quantum cryptanalysis, and the design of key exchange and digital signature primitives with post-quantum security.

Closing date for applications: 30 June 2019

Contact: Dr. Brian LaMacchia, CryptoIntern (at) microsoft.com

More information: https://careers.microsoft.com/us/en/job/573172/Research-Intern-MSR-Security-and-Cryptography