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).

09:17 [Pub][ePrint] Graded Multilinear Maps from Lattices, by Craig Gentry and Sergey Gorbunov and Shai Halevi

  Graded multilinear encodings have found extensive applications in cryptography ranging from

non-interactive key exchange protocols, to broadcast and attribute-based encryption, and even to software obfuscation.

Despite seemingly unlimited applicability, essentially only two candidate constructions are known (GGH and CLT). In this work, we describe a new graded multilinear encoding scheme from lattices.

Our construction encodes Learning With Errors (LWE) samples

in short square matrices of higher dimensions. Addition and multiplication of the encodings corresponds naturally to addition and multiplication

of the LWE secrets. Comparisons of any two encodings

can be performed publicly at any level.

The security of our scheme relies on a hardness of a natural problem which can be thought of as analogous to standard LWE problem.

09:17 [Pub][ePrint] High-speed Polynomial Multiplication Architecture for Ring-LWE and SHE Cryptosystems, by Donald Donglong Chen and Nele Mentens and Frederik Vercauteren and Sujoy Sinha Roy and Ray C.C. Cheung and Dere

  Polynomial multiplication is the basic and most computationally intensive operation in ring-Learning With Errors (ring-LWE) encryption and ``Somewhat\" Homomorphic Encryption (SHE) cryptosystems. In this paper, the Fast Fourier Transform (FFT) with a linearithmic complexity of $O(n\\log n)$, is exploited in the design of a high-speed polynomial multiplier. A constant geometry FFT datapath is used in the computation to simplify the control of the architecture. The contribution of this work is three-fold. First, parameter sets which support both an efficient modular reduction design and the security requirements for ring-LWE encryption and SHE are provided. Second, a versatile pipelined architecture accompanied with an improved dataflow are proposed to obtain a high-speed polynomial multiplier. Third, the proposed architecture supports polynomial multiplications for different lengths $n$ and moduli $p$. The experimental results on a Spartan-6 FPGA show that the proposed design results in a speedup of 3.5 times on average when compared with the state of the art. It performs a polynomial multiplication in the ring-LWE scheme ($n = 256, p = 1049089$) and the SHE scheme ($n = 1024, p = 536903681$) in only 6.3$\\mu$s and 33.1$\\mu$s, respectively.

09:17 [Pub][ePrint] Universally Composable Secure Group Communication, by TIAN Youliang, PENG Changgen

  This paper analyzes group communication within the universally

composable framework. We first propose the group communication

model, identity-based signcrytion model and group key distribution model in the UC framework by

designing the ideal functionality $\\mathcal {F}_{SAGCOM}$, $\\mathcal

{F}_{IDSC}$ and $\\mathcal {F}_{GKD}$, respectively. Then, we construct

a UC secure identity-based signcryption protocol $\\pi_{IDSC}$. Moreover,

we shows that the identity-based signcryption $\\pi_{IDSC}$ securely realizes the ideal functionality $\\mathcal {F}_{IDSC}$ if

and only if the corresponding protocol IDSC is secure. Finally, based on the identity-based protocol, we propose a group communication scheme

$\\pi_{SAGCOM}$, which can securely realizes the ideal functionality

$\\mathcal {F}_{SAGCOM}$ in the $(\\mathcal {F}_{IDSC},\\mathcal

{F}_{GKD})$-hybrid model.

09:17 [Pub][ePrint] An Equivalent Condition on the Switching Construction of Differentially 4-uniform Permutations on $\\gf_{2^{2k}}$ from the Inverse Function, by Xi Chen, Yazhi Deng, Min Zhu and Longjiang Qu

  Differentially 4-uniform permutations on $\\gf_{2^{2k}}$ with high nonlinearity are often chosen as Substitution boxes in block ciphers. Recently, Qu et al. used the powerful switching method to construct such permutations from the inverse function [9],[10]. More precisely, they studied the functions of the form G(x)=1/x+f(1/x),

where f is a Boolean function. They proved that if f is a preferred Boolean function (PBF), then G is a permutation polynomial over $\\gf_{2^n}$ whose differential uniformity is at most 4. However, as pointed out in [9],f is a PBF is a sufficient but not necessary condition. In this paper, a sufficient and necessary condition for G to be a differentially 4-uniform permutation is presented. We also show that G can not be an almost perfect nonlinear (APN) function. As an application, a new class of differentially 4-uniform permutations where f are not PBFs are constructed. By comparing this family with previous constructions, the number of permutations here is much bigger. The obtained functions in this paper may provide more choices for the design of Substitution boxes.

09:17 [Pub][ePrint] FPGA Trojans through Detecting and Weakening of Cryptographic Primitives, by Pawel Swierczynski and Marc Fyrbiak and Philipp Koppe and Christof Paar

  This paper investigates a novel attack vector against

cryptography realized on FPGAs, which can pose a serious threat

to real-world implementations. We demonstrate how a simple

bitstream modification can seriously weaken crypto algorithms,

which we show by example of the AES and 3DES. The attack is

performed by modifying the FPGA bitstream that configures the

hardware elements during initialization. It has been known for a

long time that cloning of FPGA designs, even if the bitstream

is encrypted, is a relatively easy task. However, due to the

proprietary format of the bitstream, a meaningful modification

of an unknown FPGA bitstream is very challenging. While

some previous work had addressed bitstream reverse-engineering,

so far it has not been evaluated how difficult it is to detect

and modify cryptographic elements. We outline two possible

practical attacks that can lead to serious security implications.

We target the non-linear S-boxes of crypto algorithms of a

synthesized FPGA design that can be either implemented as

Boolean equations in look-up tables, or as precomputed set

of values that are stored in the memory of the FPGA. We

demonstrate that it is possible to detect and apply meaningful

changes to cryptographic elements inside an unknown propriety

and undocumented bitstream. Furthermore, we also show how

an AES key can be revealed within seconds by modifying the

bitstream. Finally, we propose countermeasures that can raise

the bar for an adversary to successfully perform an attack.

09:17 [Pub][ePrint] Round-Optimal Password-Protected Secret Sharing and T-PAKE in the Password-Only Model, by Stanislaw Jarecki and Aggelos Kiayias and Hugo Krawczyk

  In a Password-Protected Secret Sharing (PPSS) scheme with parameters (t,n) (formalized by Bagherzandi et al), a user Alice stores secret information s among n servers so that she can later recover the information solely on the basis of her password. The security requirement is similar to a (t,n)-threshold secret sharing, i.e., Alice can recover her secret as long as she can communicate with t + 1 honest servers but an attacker gaining access to t servers cannot learn information about the secret. In particular, the system is secure against o-line attacks by an attacker controlling up to t servers. On the other hand, accounting for inevitable on-line attacks one allows the attacker an advantage proportional to the fraction of dictionary passwords tested in on-line interactions with the user and servers.

We present the first round-optimal PPSS scheme, requiring just one message from user to server, and from server to user, and that works in the password-only setting where users do not have access to an authenticated public key. The scheme uses an Oblivious PRF whose security we define using a UC-style ideal functionality and denote as V-OPRF due to its verifiability, and for which we show concrete, very practical realizations in the random oracle model, as well as standard-model instantiations. As an important application we use this scheme to build the first single-round password-only Threshold-PAKE protocol in the CRS and ROM models for arbitrary (t,n) parameters with no PKI requirements for any party (clients or servers) and no inter-server communication. Our T-PAKE protocols are built by combining suitable key exchange protocols on top of our V-OPRF-based PPSS schemes. We prove T-PAKE security via a generic composition theorem showing the security of any such composed protocol.

09:17 [Pub][ePrint] A note on CCA2-protected McEliece Cryptosystem with a systematic public key, by Pavol Zajac

  We show that the plaintext of some of the proposed CCA2 conversions of McEliece cryptosystem with a public key in systematic form can be recovered faster than with a general linear decoding. This is due to the fact that an attacker only needs to recover a part of the cleartext to decrypt the relevant plaintext.

09:17 [Pub][ePrint] A Dynamic Cube Attack on $105$ round Grain v1, by Subhadeep Banik

  As far as the Differential Cryptanalysis of reduced round Grain v1 is concerned, the best results were those published by Knellwolf et al. in Asiacrypt $2011$. In an extended version of the paper, it was shown that it was possible to retrieve {\\bf (i)} $5$ expressions in the Secret Key bits for a variant of Grain v1 that employs $97$ rounds (in place of $160$) in its Key Scheduling process using $2^{27}$ chosen IVs and {\\bf (ii)} $1$ expression in Secret Key bits for a variant that employs $104$ rounds in its Key Scheduling using $2^{35}$ chosen IVs. However, the second attack on $104$ rounds, had a success probability of around $50$\\%, which is to say that the attack worked for only around one half of the Secret Keys.

In this paper we propose a dynamic cube attack on $105$ round Grain v1, that has a success probability of $100$\\%, and thus we report an improvement of $8$ rounds over the previous best attack on Grain v1 that attacks the entire Keyspace. We take the help of the tool $\\Delta${\\sf Grain}$_{\\sf KSA}$, proposed by Banik at ACISP 2014, to track the differential trails induced in the internal state of Grain v1 by any difference in the IV bits, and we prove that a suitably introduced difference in the IV leads to a distinguisher for the output bit produced in the $105^{th}$ round. This, in turn, helps determine the values of $6$ expressions in the Secret Key bits.

09:17 [Pub][ePrint] Mersenne factorization factory, by Thorsten Kleinjung and Joppe W. Bos and Arjen K. Lenstra

  We present work in progress to fully factor seventeen Mersenne numbers using a variant of the special number field sieve where sieving on the algebraic side is shared among the numbers. It is expected that it reduces the overall factoring effort by more than 50\\%. As far as we know this is the first practical application of Coppersmith\'s ``factorization factory\'\' idea. Most factorizations used a new double-product approach that led to additional savings in the matrix step.

09:17 [Pub][ePrint] Multi-Bit Differential Fault Analysis of Grain-128 with Very Weak Assumptions, by Prakash Dey and Abhishek Chakraborty and Avishek Adhikari and Debdeep Mukhopadhyay

  Very few differential fault attacks (DFA) were reported on {\\em Grain-128} so far.

In this paper we present a generic attack strategy that allows the adversary to challenge the cipher under different multi-bit fault models with faults at a targeted keystream generation round even if bit arrangement of the actual cipher device is unknown. Also unique identification of fault locations is not necessary.

To the best of our knowledge, this paper assumes the weakest adversarial power ever considered in the open literature for DFA on {\\em Grain-128} and develops the most realistic attack strategy so far on {\\em Grain-128}.

In particular, when a random area within $k \\in \\{1,2,3,4,5\\}$ neighbourhood bits can only be disturbed by a single fault injection at the first keystream generation round ($k$-neighbourhood bit fault), without knowing the locations or the exact number of bits the injected fault has altered, our attack strategy always breaks the cipher with $5$ faults.

In a weaker setup even if bit arrangement of the cipher device is unknown, bad-faults (at the first keystream generation round) are rejected with probabilities $0.999993$, $0.999979$, $0.999963$, $0.999946$ and $0.999921$ assuming that the adversary will use only 1, 2, 3, 4 and 5 neighbourhood bit faults respectively for {\\em key-IV} recovery.

09:17 [Pub][ePrint] Pleco and Plectron -- Two Provably Secure Password Hashing Algorithms, by Bo Zhu and Xinxin Fan and Guang Gong

  Password-based authentication has been widely deployed in practice due to its simplicity and efficiency. Storing passwords and deriving cryptographic keys from passwords in a secure manner are crucial for many security systems and services. However, choices of well-studied password hashing algorithms are extremely limited, as their security requirements and design principles are different from common cryptographic algorithms. In this paper, we propose two simple and practical password hashing algorithms, Pleco and Plectron. They are built upon well-understood cryptographic algorithms, and combine advantages of symmetric and asymmetric primitives. By employing the Rabin cryptosystem, we prove that the one-wayness of Pleco is at least as strong as the hard problem of integer factorization. In addition, both password hashing algorithms are designed to be sequential memory-hard, in order to thwart large-scale password cracking by parallel hardware, such as GPUs, FPGAs, and ASICs. Moreover, total computation and memory consumptions of Pleco and Plectron are tunable through their cost parameters.