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 get this service 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 [Pub][ePrint] Breaking pairing-based cryptosystems using $\\eta_T$ pairing over $GF(3^{97})$, by Takuya Hayashi and Takeshi Shimoyama and Naoyuki Shinohara and Tsuyoshi Takagi

  There are many useful cryptographic schemes, such as ID-based encryption,

short signature, keyword searchable encryption, attribute-based encryption,

functional encryption, that use a bilinear pairing.

It is important to estimate the security of such pairing-based cryptosystems in cryptography.

The most essential number-theoretic problem in pairing-based cryptosystems is

the discrete logarithm problem (DLP)

because pairing-based cryptosystems are no longer secure once the underlining DLP is broken.

One efficient bilinear pairing is the $\\eta_T$ pairing defined over a supersingular

elliptic curve $E$ on the finite field $GF(3^n)$ for a positive integer $n$.

The embedding degree of the $\\eta_T$ pairing is $6$;

thus, we can reduce the DLP over $E$ on $GF(3^n)$ to that over the finite field $GF(3^{6n})$.

In this paper, for breaking the $\\eta_T$ pairing over $GF(3^n)$, we discuss

solving the DLP over $GF(3^{6n})$ by using the function field sieve (FFS),

which is the asymptotically fastest algorithm for solving a DLP

over finite fields of small characteristics.

We chose the extension degree $n=97$ because it has been intensively used in benchmarking

tests for the implementation of the $\\eta_T$ pairing,

and the order (923-bit) of $GF(3^{6\\cdot 97})$ is substantially larger than

the previous world record (676-bit) of solving the DLP by using the FFS.

We implemented the FFS for the medium prime case (JL06-FFS),

and propose several improvements of the FFS,

for example, the lattice sieve for JL06-FFS and the filtering adjusted to the Galois action.

Finally, we succeeded in solving the DLP over $GF(3^{6\\cdot 97})$.

The entire computational time of our improved FFS requires about 148.2 days using 252 CPU cores.

Our computational results contribute to the secure use of pairing-based cryptosystems with the $\\eta_T$ pairing.

21:17 [Pub][ePrint] Edwards model of elliptic curves defined over any fields, by Oumar DIAO and Emmanuel FOUOTSA

  In this paper, we present a generalization of Edwards model for elliptic curve which is defined over any field and in particular for field of characteristic 2. This model generalize the well known Edwards model of \\cite{Edw07} over characteristic zero field, moreover it define an ordinary elliptic curve over binary fields.

For this, we use the theory of theta functions and an intermediate model embed in $\\mathbb{P}^3$ that we call a level $4$-theta model. We then present an arithmetic of this level $4$-theta model and of our Edwards model using Riemann relations of theta functions. The group laws are complete, i.e. none exceptional case for adding a pair of points; their are also unified, i.e. formulas using for addition and for doubling are the same. Over binary fields we have very efficient arithmetics on ordinary elliptic curve, but over odd field our explicit addition laws are not competitives. Nevertheless, we give efficient differential addition laws on level $4$-theta model and on Edwards model defined over any fields.

21:17 [Pub][ePrint] Algebraic Differential Fault Attacks on LED using a Single Fault Injection, by Xinjie Zhao and Shize Guo and Fan Zhang and Tao Wang and Zhijie Shi and Keke Ji

  This paper proposes a new fault attack technique on the LED block

cipher using a single fault injection by combining algebraic

side-channel attack (ASCA) and differential fault attack (DFA). We

name it as algebraic differential fault attack (ADFA). Firstly, a

boolean equation set is constructed for LED using algebraic

techniques. Then, the fault differences of the S-Box inputs in the

last round of LED are deduced by DFA and represented using algebraic

equations by the multiple deductions-based ASCA (MDASCA) technique

proposed in COSADE 2012. Finally, the key is recovered by solving

the equation set with the CryptoMiniSat solver. We show that, as to

ADFA on LED under the single nibble-based fault model, the 64-bit

key can be recovered within one minute on a common PC with a success

rate of 79\\%, which is more efficient than previous work. We modify

the CryptoMiniSat solver to count and output multiple solutions for

the key, and conduct ADFA to calculate the reduced key search space

for DFA. The key search space of LED is reduced to $2^6 \\sim

2^{17}$, which is different from previous work. We also successfully

extend ADFA on LED to other fault models using a single fault

injection, such as byte based fault model and nibble based diagonal

fault model, where traditional DFAs are difficult to work. The

results show that ADFA is an efficient and generic fault analysis

technique which significantly improves DFA.

21:17 [Pub][ePrint] Oblivious Transfer with Hidden Access Control from Attribute-Based Encryption, by Jan Camenisch and Maria Dubovitskaya and Robert R. Enderlein and Gregory Neven

  The notion of oblivious transfer with hidden access control policies (HACOT) was recently proposed by Camenisch et al.~(Public-Key Cryptography~2011).

This primitive allows a user to anonymously query a database where each record is protected by a hidden attribute-based access control policy.

At each query, the user either learns the value of a single record if the attributes in his key satisfy the policy, or the mere fact that his

attributes do not satisfy the policy.

The database, even when colluding with the key issuer, learns nothing about the identity of the user, the index or the access policy of the record, or whether access was granted or denied.

At the same time, the database can keep an eye on the overall access frequency to prevent the data from being ``crawled\'\'.

In this paper, we present a new HACOT scheme which is more efficient and offers more expressive policies

than the scheme presented by Camenisch et al.

We construct our HACOT protocol based on a hidden ciphertext-policy attribute-based encryption (HP-ABE) scheme by Nishide et al.:

users are issued HACOT decryption keys based on HP-ABE attributes and HACOT records are encrypted under HP-ABE policies.

However, as we will see, this simple approach does not work and we need to extend the Nishide et al.\\

scheme as follows.

First, we add protocols that allows users to verify that the public key of the issuer and ciphertexts are correctly formed.

Second, we reserve one attribute and give the corresponding decryption key only to the database.

Thereby users can no longer decrypt records by themselves but require the help of the database.

Third, we provide a joint decryption protocol between the user and the database, so that the

database does not learn which ciphertext is decrypted.

The latter will also allow one to optionally add revocation of the users\' access.

We prove our construction secure by a reduction to the security of Nishide et al.\'s scheme, the Symmetric External Diffie-Hellman (SXDH) and Simultaneous Flexible Pairing (SFP) assumptions.

21:17 [Pub][ePrint] A Differential Fault Attack on Grain-128a using MACs, by Subhadeep Banik and Subhamoy Maitra and Santanu Sarkar

  The $32$-bit MAC of Grain-128a is a linear combination of the first 64 and then the alternative keystream bits. In this paper we describe a successful differential fault attack on Grain-128a, in which we recover the secret key by observing the correct and faulty MACs of certain chosen messages. The attack works due to certain properties of the Boolean functions and corresponding choices of the taps from the LFSR. We present methods to identify the fault locations and then construct set of linear equations to obtain the contents of the LFSR and the NFSR. Our attack requires less than $2^{11}$ fault injections

and invocations of less than $2^{12}$ MAC generation routines.

21:17 [Pub][ePrint] A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption, by Liangliang Xiao and I-Ling Yen

  Order-preserving encryption (OPE) preserves the order of data in their ciphertexts and, hence, allows range search on the encrypted data without needing to decrypt them. Security analysis of OPE schemes is very important because OPE is not a perfect encryption algorithm (the ciphertexts leak the ordering information of the plaintexts). Most of the existing security analysis for the OPE schemes are informal: they are either based on author-defined attacks or experiments. The authors in \\cite{Bol09} initiate the cryptographic study of the OPE scheme. They define the security notion POPF-CCA to qualify the security of OPE. In POPF-CCA, the ``ideal\" OPE object is defined where the encryption function is uniformly randomly selected from all order-preserving functions (generally the ``ideal\" OPE object is not computationally feasible), and a (constructed) ``real\" OPE scheme is secure under POPF-CCA if it is computationally indistinguishable from the ideal object. In other words, although the ``ideal\" OPE object is not computationally feasible, it is used as the security goal, and a (constructed) ``real\" OPE scheme is secure if it is as secure as the ``ideal\" OPE object. Such approach conceives the assumption (but not clearly stated and proved) that the ``ideal\" OPE object is the most secure OPE. But the correctness of the assumption is an easily ignored problem.

In this paper, we investigate the security of the OPE in more depth. We first give example to show that the ``ideal\" OPE object may not always be the most secure OPE. It indicates that we need to use the ``ideal\" encryption object more cautiously in the security analysis of OPE. Additionally we extend the concept of OPE to generalized OPE (GOPE). Unlike OPE, the ciphertexts of GOPE may not be numbers, but GOPE still enables the comparisons on the encrypted data without needing to decrypt them. We present two GOPEs in polynomial-sized and superpolynomial-sized domains that satisfy stronger notions of security than that of the ideal OPE object, respectively.

21:17 [Pub][ePrint] SipHash: a fast short-input PRF, by Jean-Philippe Aumasson and Daniel J. Bernstein

  SipHash is a family of pseudorandom functions optimized for short inputs. Target applications include network traffic authentication and hash-table lookups protected against hash-flooding denial-of-service attacks. SipHash is simpler than MACs based on universal hashing, and faster on short inputs. Compared to dedicated designs for hash-table lookup, SipHash has well-defined security goals and competitive performance. For example, SipHash processes a 16-byte input with a fresh key in 140 cycles on an AMD FX-8150 processor, which is much faster than state-of-the-art MACs. We propose that hash tables switch to SipHash as a hash function.

21:17 [Pub][ePrint] On Hashing Graphs, by Ashish Kundu, Elisa Bertino

  Collision resistant one-way hashing schemes are the basic building blocks of almost all crypto-systems. Use of graph-structured data models are on the rise -- in graph databases, representation of biological and healthcare data as well as in modeling systems for representing system topologies. Therefore, the problem of hashing graphs with respect to crypto-systems needs to be studied and addressed. The traditional Merkle Hash technique cannot be applied as it is because graphs are more complex data structures than trees. In this paper, we make the following contributions: (1) we define the formal security model of hashing schemes for graphs, (2) we define the formal security model of leakage-free hashing schemes for graphs, (3) we describe a hashing scheme for hashing directed and undirected graphs that uses Merkle hash technique, (4) and a hashing scheme that uses structural information instead of Merkle hash technique, (5) we define leakage-free hashing schemes for graphs. Our constructions use graph traversal techniques and are highly efficient with respect to updates to graphs: they require as little as two (O(1)) hash values to be updated to refresh the hash of the graph, while the Merkle Hash Technique and Search DAG schemes for trees and DAGs respectively require as many as O(|V|) and O(|V|+|E|).

21:17 [Pub][ePrint] On Reconfigurable Fabrics and Generic Side-Channel Countermeasures, by Robert Beat and Philipp Grabher and Dan Page and Stefan Tillich and Marcin Wójcik

  The use of field programmable devices in security-critical applications is growing in popularity; in part, this can be attributed to their potential for balancing metrics such as efficiency and algorithm agility. However, in common with non-programmable alternatives, physical attack techniques such as fault and power analysis are a threat. We investigate a family of next-generation field programmable devices, specifically those based on the concept of time sharing,within this context: our results support the premise that extra, inherent flexibility in such devices can offer a range of possibilities for low-overhead, generic countermeasures against physical attack.

21:17 [Pub][ePrint] Hash Combiners for Second Pre-Image Resistance, Target Collision Resistance and Pre-Image Resistance have Long Output, by Arno Mittelbach

  A $(k,l)$ hash-function combiner for property $P$ is a construction that, given access to $l$ hash functions, yields a single cryptographic hash function which has property $P$ as long as at least $k$ out of the $l$ hash functions have that property. Hash function combiners are used to hedge against the failure of one or more of the individual components. One example of the application of hash function combiners are the previous versions of the TLS and SSL protocols \\cite{RFC:6101,RFC:5246}.

The concatenation combiner which simply concatenates the outputs of all hash functions is an example of a robust combiner for collision resistance. However, its output length is, naturally, significantly longer than each individual hash-function output, while the security bounds are not necessarily stronger than that of the strongest input hash-function. In 2006 Boneh and Boyen asked whether a robust black-box combiner for collision resistance can exist that has an output length which is significantly less than that of the concatenation combiner \\cite{C:BonBoy06}. Regrettably, this question has since been answered in the negative for fully black-box constructions (where hash function and adversary access is being treated as black-box), that is, combiners (in this setting) for collision resistance roughly need at least the length of the concatenation combiner to be robust \\cite{C:BonBoy06,C:CRSTVW07,EC:Pietrzak07,C:Pietrzak08}.

In this paper we examine weaker notions of collision resistance, namely: \\emph{second pre-image resistance} and \\emph{target collision resistance} \\cite{FSE:RogShr04} and \\emph{pre-image resistance}. As a generic brute-force attack against any of these would take roughly $2^n$ queries to an $n$-bit hash function, in contrast to only $2^{n/2}$ queries it would take to break collision resistance (due to the birthday bound), this might indicate that combiners for weaker notions of collision resistance can exist which have a significantly shorter output than the concatenation combiner (which is, naturally, also robust for these properties). Regrettably, this is not the case.

21:17 [Pub][ePrint] Never trust a bunny, by Daniel J. Bernstein and Tanja Lange

  ``Lapin\'\' is a new RFID authentication protocol proposed at FSE 2012.

``Ring-LPN\'\' (Ring-Learning-Parity-with-Noise) is a new computational problem proposed in the same paper; there is a proof relating the security of Lapin to the difficulty of Ring-LPN. This paper presents an attack against Ring-LPN-512 and Lapin-512.The attack is not practical but nevertheless violates specific security claims in the FSE 2012 paper.