International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

21:17 [Forum] [2014 Reports] 2015/313: Quantum attacks against the short PIP problem are not polynomial time by biasse

  The authors of 2015/313 claim that their result implies a quantum polynomial time key-recovery attack against cryptographic constructions relying on the hardness of finding a short generator of a principal ideal in a cyclotomic field (ex: multilinear maps or Smart-Vercauteren scheme). This statement is not true, and it should be amended. It is based on two references to justify the existence of a quantum polynomial time algorithm to solve the Principal Ideal Problem (PIP). First, an online draft from Campbel, Grove and Shepherd [CGS14]. This work in progress has been publicly released as it was when the corresponding research program at CESG was interrupted. According to its authors, the polynomial run time of the attack is an overstatement that cannot be supported (This has been stated at the Heilbronn Quantum Algorithms Meeting 2015 and at the ICERM workshop on lattices and cybersecurity 2015). Moreover, it is unclear that the approach chosen in [CGS14] could ever lead to a polynomial run time for at least two fundamental reasons explained in this forum post :!topic/cryptanalytic-algorithms/GdVfp5Kbdb8 Then, the authors of 2015/313 refer to ongoing research by Fang Song and myself. This work in progress (which adopts a totally different approach than that of [CGS14]) has never been shared with the authors and has never been publicly released. We have no timeline for its submission, and although it is promissing, it is clearly too soon to refer to it with the level of confidence chosen by the authors of this preprint ("known algorithm for the PIP"). We have already shared our concerns about this citation with the authors of 2015/313, but no change has been made so far. It is clearly "work in progress", and Fang Song and myself do not refer to it as an actual result. From: 2015-07-05 20:21:15 (UTC)

21:17 [Pub][ePrint] A Note on the Unsoundness of vnTinyRAM\'s SNARK, by Bryan Parno

  Gennaro, Gentry, Parno, and Raykova (GGPR) introduced Quadratic Arithmetic Programs (QAPs) as a way of representing arithmetic circuits in a form amendable to highly efficient cryptographic protocols (EUROCRYPT 2013), particularly for verifiable computation and succinct non-interactive arguments. Subsequently, Parno, Gentry, Howell, and Raykova introduced an improved cryptographic protocol (and implementation), which they dubbed Pinocchio (IEEE S&P 2013).

Ben-Sasson et al. then introduced a lightly modified version of the Pinocchio protocol and implemented it as part of their libsnark distribution. Later work by the same authors employed this protocol, as did a few works by others. Many of these works cite the version of the paper which was published at USENIX Security. However, the protocol does not appear in that peer-reviewed paper; instead, it appears only in a technical report, where it is justified via a lemma that lacks a proof. Unfortunately, the lemma is incorrect, and the modified protocol is unsound. With probability one, an adversary can submit false statements and proofs that the verifier will accept. We demonstrate this theoretically, as well as with concrete examples in which the protocol\'s implementation in libsnark accepts invalid statements.

Fixing this problem requires different performance tradeoffs, indicating that the performance results reported by papers building on this protocol (USENIX Security 2013, CRYPTO 2014, NDSS 2014, EUROCRYPT 2015, IEEE S&P 2014, IEEE S&P 2015) are, to a greater or lesser extent, inaccurate.

12:17 [Pub][ePrint] On the (Fast) Algebraic Immunity of Boolean Power Functions, by Yusong Du and Baodian Wei and Fangguo Zhang and Huang Zhang

  The (fast) algebraic immunity, including (standard) algebraic immunity and the resistance against fast algebraic attacks, has been considered as an important cryptographic property for Boolean functions used in stream ciphers. This paper is on the determination of the (fast) algebraic immunity of a special class of Boolean functions, called Boolean power functions. An n-variable Boolean power function f can be represented as a monomial trace function over finite field GF(2^n). To determine the (fast) algebraic immunity of Boolean power functions one may need the arithmetic in GF(2^n), which may be not computationally efficient compared with the operations over GF(2). We provide two sufficient conditions for Boolean power functions such that their immunities can determined only by the computations in GF(2). We show that Niho functions and a number of odd variables Kasami functions can satisfy the conditions.

12:17 [Pub][ePrint] On the Resistance of Prime-variable Rotation Symmetric Boolean Functions against Fast Algebraic Attacks, by Yusong Du and Baodian Wei and Fangguo Zhang and Huang Zhang

  Boolean functions used in stream ciphers should have many cryptographic properties in order to help resist different kinds of cryptanalytic attacks. The resistance of Boolean functions against fast algebraic attacks is an important cryptographic property. Deciding the resistance of an n-variable Boolean function against fast algebraic attacks needs to determine the rank of a square matrix over finite field GF(2). In this paper, for rotation symmetric Boolean functions in prime n variables, exploiting the properties of partitioned matrices and circulant matrices, we show that the rank of such a matrix can be obtained by determining the rank of a reduced square matrix with smaller size over GF(2), so that the computational complexity decreases by a factor of n to the power omega for large n, where omega is approximately equal to 2.38 and is known as the exponent of the problem of computing the rank of matrices.

15:17 [Pub][ePrint] Cryptanalysis of Round-Reduced LED, by Ivica Nikoli\\\'c and Lei Wang and Shuang Wu

  In this paper we present known-plaintext single-key and chosen-key attacks on round-reduced LED-64 and LED-128.

We show that with an application of the recently proposed slidex attacks,

one immediately improves the complexity of the previous single-key 4-step attack on LED-128. Further, we explore the possibility of

multicollisions and show single-key attacks on 6 steps of LED-128. A generalization of our multicollision attack

leads to the statement that no 6-round cipher with two subkeys that alternate, or 2-round cipher with

linearly dependent subkeys, is secure in the single-key model. Next, we exploit the possibility of finding pairs of inputs that follow

a certain differential rather than a differential characteristic, and obtain chosen-key differential distinguishers

for 5-step LED-64, as well as 8-step and 9-step LED-128. We provide examples of inputs that follow the 8-step differential,

i.e. we are able to practically confirm our results on 2/3 of the steps of LED-128. We introduce a new type of

chosen-key differential distinguisher, called random-difference distinguisher, and

successfully penetrate 10 of the total 12 steps of LED-128. We show that this type of attack is generic

in the chosen-key model, and can be applied to any 10-round cipher with two alternating subkeys.

15:17 [Pub][ePrint] Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing, by Alex Biryukov and Daniel Dinu and Dmitry Khovratovich

  Memory-hard functions are becoming an important tool in the design of password hashing schemes, cryptocurrencies, and more generic proof-of-work primitives that are x86-oriented and can not be computed on dedicated hardware more efficiently.

We develop a simple and cryptographically secure approach to the design of such functions and show how to exploit the architecture of modern CPUs and memory chips to make faster and more secure schemes compared to existing alternatives such as scrypt. We also propose cryptographic criteria for the components, that prevent cost reductions using time-memory tradeoffs and side-channel leaks. The concrete proof-of-work instantiation, which we call Argon2, can fill GBytes of RAM within a second, is resilient to various tradeoffs, and is suitable for a wide range of applications, which aim to bind a computation to a certain architecture.

Concerning potential DoS attacks, our scheme is lightweight enough to offset the bottleneck from the CPU to the memory bus thus leaving sufficient computing power for other tasks. We also propose parameters for which our scheme is botnet resistant. As an application, we suggest a cryptocurrency design with fast and memory-hard proof-of-work, which allows memoryless verification.

15:17 [Pub][ePrint] Conversions among Several Classes of Predicate Encryption and Their Applications, by Shota Yamada and Nuttapong Attrapadung and Goichiro Hanaoka

  Predicate encryption is an advanced form of public-key encryption that yield high flexibility in terms of access control. In the literature, many predicate encryption schemes have been proposed such as fuzzy-IBE, KP-ABE, CP-ABE, (doubly) spatial encryption (DSE), and ABE for arithmetic span programs. In this paper, we study relations among them and show that some of them are in fact equivalent by giving conversions among them. More specifically, our main contributions are as follows:

- We show that monotonic, small universe KP-ABE (CP-ABE) with bounds on the size of attribute sets and span programs (or linear secret sharing matrix) can be converted into DSE. Furthermore, we show that DSE implies non-monotonic CP-ABE (and KP-ABE) with the same bounds on parameters. This implies that monotonic/non-monotonic KP/CP-ABE (with the bounds) and DSE are all equivalent in the sense that one implies another.

- We also show that if we start from KP-ABE without bounds on the size of span programs (but bounds on the size of attribute sets), we can obtain ABE for arithmetic span programs. The other direction is also shown: ABE for arithmetic span programs can be converted into KP-ABE.These results imply, somewhat surprisingly, KP-ABE without bounds on span program sizes is in fact equivalent to ABE for arithmetic span programs, which was thought to be more expressive or at least incomparable.

By applying these conversions to existing schemes, we obtain many non-trivial consequences. We obtain the first non-monotonic, large universe CP-ABE (that supports span programs) with constant-size ciphertexts, the first ABE for arithmetic span programs with adaptive security, the first ciphertext-policy version of ABE for arithmetic span programs, the first KP-ABE with constant-size private keys, and even more.

We also obtain the first attribute-based signature scheme that supports non-monotone span programs and achieves constant-size signatures via our technique.

15:17 [Pub][ePrint] Non-Repudiable Provable Data Possession in Cloud Storage, by Hongyuan Wang and Liehuang Zhu and Yijia Lilong and Chang Xu

  Provable data possession (PDP) and Proof of Retrievability (POR) are techniques for a client to verify whether an untrusted server (i.e. the cloud storage provider) possesses the original data entirely, and many PDP and POR schemes have been proposed to resolve above issue so far. But another question comes up: driven by profits, a malicious client may accuse an honest server and deny the correct verification in many circumstances. As far as we know, none of the existing private verification schemes that are not based on a third party has settled this matter.

In this paper, we give a method to reform any private verification PDP/POR scheme into a non-repudiable PDP/POR scheme. And then we propose an instantiation, the first Non-repudiable PDP (NRPDP) scheme of private verification, which can provide mutual proof to protect both the client and server. Based on homomorphic verifiable tags and commitment function, our solution allows both the client and the server to prove themselves and verify the other side respectively. To achieve better performance, we improve the NRPDP scheme to obtain an E-NRPDP scheme, which can save the storage cost of the server and reduce the I/O costs to raise efficiency.

We prove the security of NRPDP scheme in the random oracle model, and implement a prototype based on our NRPDP scheme. Then we utilize big data as much as 10G to evaluate the performance in a realistic cloud platform. The experiments show our scheme can be executed efficiently as the original PDP/POR scheme and guarantee non-repudiation efficaciously. Our method is universal and practical, which means that it can be applied in any private PDP/POR schemes to guarantee non-repudiation.

15:17 [Pub][ePrint] A New Classification of 4-bit Optimal S-boxes and its Application to PRESENT, RECTANGLE and SPONGENT, by Wentao Zhang and. Zhenzhen Bao and. Vincent Rijmen and. Meicheng Liu

  In this paper, we present a new classification of 4-bit optimal S-boxes. All optimal 4-bit S-boxes can be classified into 183 different categories, among which we specify 3 platinum categories. Under the design criteria of the PRESENT (or SPONGENT) S-box, there are 8064 different S-boxes up to adding constants before and after an S-box. The 8064 S-boxes belong to 3 different categories, we show that the S-box should be chosen from one out of the 3 categories or other categories for better resistance against linear cryptanalysis. Furthermore, we study in detail how the S-boxes in the 3 platinum

categories influence the security of PRESENT, RECTANGLE and SPONGENT88 against differential and linear cryptanalysis. Our results show that the S-box selection has a great influence on the security of the schemes. For block ciphers or hash functions with 4-bit S-boxes as confusion layers and bit permutations as diffusion layers, designers can extend the range of S-box selection to the 3 platinum categories and select their S-box very carefully. For PRESENT, RECTANGLE and SPONGENT88 respectively, we get a set of potentially best/better S-box candidates from the 3 platinum categories. These potentially best/better S-boxes can be further investigated to see if they can be used to improve the security-performance tradeoff of the 3 cryptographic algorithms.

15:17 [Pub][ePrint] Dickson Polynomials that are Involutions, by Pascale Charpin and Sihem Mesnager and Sumanta Sarkar

  Dickson polynomials which are permutations are interesting combinatorial objects and well studied. In this paper, we describe Dickson polynomials of the first kind in $\\mathbb{F}_2[x]$ that are involutions over finite fields of characteristic $2$. Such description is obtained using modular arithmetic\'s tools. We give results related to the cardinality and the number of fixed points (in the context of cryptographic application) of this corpus. We also present a class of Dickson involutions with high degree.

12:17 [Pub][ePrint] Dumb Crypto in Smart Grids: Practical Cryptanalysis of the Open Smart Grid Protocol, by Philipp Jovanovic and Samuel Neves

  This paper analyses the cryptography used in the Open Smart Grid Protocol

(OSGP). The authenticated encryption (AE) scheme deployed by OSGP is a

non-standard composition of RC4 and a home-brewed MAC, the ``OMA digest\'\'.

We present several practical key-recovery attacks against the OMA digest. The

first and basic variant can achieve this with a mere $13$ queries to an OMA

digest oracle and negligible time complexity. A more sophisticated version

breaks the OMA digest with only $4$ queries and a time complexity of about

$2^{25}$ simple operations. A different approach only requires one arbitrary

valid plaintext-tag pair, and recovers the key in an average of $144$

\\emph{message verification} queries, or one ciphertext-tag pair and $168$

\\emph{ciphertext verification} queries.

Since the encryption key is derived from the key used by the OMA digest, our

attacks break both confidentiality and authenticity of OSGP.