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

13:17 [Pub][ePrint] Proofs of Retrievability with Public Verifiability and Constant Communication Cost in Cloud, by Jiawei Yuan and Shucheng Yu

  For data storage outsourcing services, it is important to allow data owners to efficiently and securely verify that the storage sever stores their data correctly. To address this issue, several proof-of-retrievability(POR) schemes have been proposed wherein a storage sever must prove to a verifier that all of a client\'s data is stored correctly. While existing POR schemes offer decent solutions addressing various practical issues, they either have a non-trivial (linear or quadratic) communication complexity, or only support private verication - only the data owner can verify the remotely stored data. It remains open to design a POR scheme that achieves both public verifiability and constant communication cost simultaneously.

In this paper, we solve this open problem and propose the first POR scheme with public verifiability and constant communication cost. In our proposed scheme, the message exchanged between the prover and verifier is composed of a const number of the underlying group elements. Different from existing private POR construction, our scheme allows public verification and releases the data owners from burden of being staying online. Thorough analysis and experiments on Amazon S3 show that our proposed scheme is efficient and practical. We prove the security of our scheme based on Computational Diffie-Hellman Assumption, Strong Diffie-Hellman Assumption and Bilinear Strong Diffie-Hellman Assumption.

13:17 [Pub][ePrint] Discarding the Endpoints makes the Cryptanalytic Time-Memory Trade-Offs even Faster, by Gildas Avoine and Adrien Bourgeois and Xavier Carpent

  Cryptanalytic time-memory trade-offs were introduced by Hellman in 1980 in order to perform key-recovery attacks on cryptosystems. A major advance was presented at Crypto 2003 by Oechslin, with the rainbow table variant that outperforms Hellman\'s seminal work.

This paper introduces the fingerprint tables, which drastically reduce the number of false alarms during the attack compared to the rainbow tables. The key point of our technique consists in storing in the tables the fingerprints of the chains instead of their endpoints. The fingerprint tables provide a time-memory trade-off that is about two times faster than the rainbow tables on usual problem sizes. We experimentally illustrate the performance of our technique, and demonstrate that it is faster than Ophcrack, a Windows LM Hash password cracker considered so far to be the fastest one ever implemented.

13:17 [Pub][ePrint] Generic Related-key Attacks for HMAC, by Thomas Peyrin and Yu Sasaki and Lei Wang

  In this article we describe new generic distinguishing and forgery attacks in the related-key scenario (using only a single related-key) for the HMAC construction. When HMAC uses a k-bit key, outputs an n-bit MAC, and is instantiated with an l-bit inner iterative hash function processing m-bit message blocks where m=k, our distinguishing-R attack requires about 2^{n/2} queries which improves over the currently best known generic attack complexity 2^{l/2} as soon as l>n. This means that contrary to the general belief, using wide-pipe hash functions as internal primitive will not increase the overall security of HMAC in the related-key model when the key size is equal to the message block size.

We also present generic related-key distinguishing-H, internal state recovery and forgery attacks. Our method is new and elegant, and uses a simple cycle-size detection criterion. The issue in the HMAC construction (not present in the NMAC construction) comes from the non-independence of the two inner hash layers and we provide a simple patch in order to avoid this generic attack. Our work finally shows that the choice of the opad and ipad constants value in HMAC is important.

13:17 [Pub][ePrint] Square root computation over even extension fields , by Gora Adj and Francisco Rodr\\\'iguez-Henr\\\'iquez

  This paper presents a comprehensive study of the computation of square roots over finite extension fields.

We propose two novel algorithms for computing square roots over even field extensions

of the form $\\F_{q^{2}}$, with $q=p^n,$ $p$ an odd prime and $n\\geq 1$. Both algorithms have an associate

computational cost roughly equivalent to one exponentiation in $\\F_{q^{2}}$.

The first algorithm is devoted to the case when $q\\equiv 1 \\bmod 4$, whereas the second one handles the case when

$q\\equiv 3 \\bmod 4$. Numerical comparisons show that the two algorithms presented in this paper are competitive

and in some cases more efficient than the square root methods previously known.

13:17 [Pub][ePrint] Improved (Pseudo) Preimage Attack and Second Preimage Attack on Round-Reduced Gr{\\o}stl, by Jian Zou and Wenling Wu and Shuang Wu and Le Dong

  Gr{\\o}stl is one of the five finalists in the third round of SHA-3

competition hosted by NIST. In this paper, we use many techniques to

improve the pseudo preimage attack on Gr{\\o}stl hash function, such

as subspace preimage attack and guess-and-determine technique. We

present improved pseudo preimage attacks on 5-round Gr{\\o}stl-256

and 8-round Gr{\\o}stl-512 respectively. The complexity of the above

two attacks are ($2^{239.90},2^{240.40}$) (in time and memory) and

($2^{499.50},2^{499}$) respectively. Furthermore, we propose pseudo

preimage attack and pseudo second preimage attack on 6-round

Gr{\\o}stl-256. The complexity of our 6-round pseudo preimage and

second preimage attack is ($2^{253.26},2^{253.67}$) and

($2^{251.0},2^{252.0}$) respectively. As far as we know, these are

the best known attacks on round-reduced Gr{\\o}stl hash function.

13:17 [Pub][ePrint] The k-BDH Assumption Family: Bilinear Map Cryptography from Progressively Weaker Assumptions, by Karyn Benson and Hovav Shacham and Brent Waters

  Over the past decade bilinear maps have been used to build a large variety of cryptosystems.

In addition to new functionality, we have concurrently seen the emergence of many strong assumptions.

In this work, we explore how to build bilinear map cryptosystems under progressively weaker assumptions.

We propose $k$-BDH, a new family of progressively

weaker assumptions that generalizes the decisional bilinear

Diffie-Hellman (DBDH) assumption. We give evidence in the generic

group model that each assumption in our family is strictly weaker

than the assumptions before it. DBDH has been used for proving many

schemes secure, notably identity-based and functional encryption

schemes; we expect that our $k$-BDH will lead to generalizations of

many such schemes.

To illustrate the usefulness of our $k$-BDH family, we

construct a family of selectively secure Identity-Based Encryption (IBE) systems based on it. Our system can be viewed

as a generalization of the Boneh-Boyen IBE, however, the construction and proof require new ideas to

fit the family. We then extend our methods to produces hierarchical IBEs and CCA

security; and give a fully secure variant. In addition, we discuss the opportunities and challenges of building

new systems under our weaker assumption family.

13:17 [Pub][ePrint] A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem, by Jintai Ding

  We use a variant of learning with errors (LWE) problem, a simple and direct extension of the original LWE problem to the case of a small secret, which we call

a small LWE problem (SLWE), to build a new simple and provably secure key exchange scheme. The basic idea behind the construction can be viewed as certain type of bilinear pairing with errors (PE). We build a more efficient implementation of our scheme using a similar LWE problem but solely based on matrices, and we extend our construction further using the ring LWE problem, where the provable security is based on the hardness of the ring LWE problem.

13:17 [Pub][ePrint] Cryptography Using CAPTCHA Puzzles, by Abishek Kumarasubramanian and Rafail Ostrovsky and Omkant Pandey and Akshay Wadia

  A \\captcha is a puzzle that is easy for humans but hard to solve for computers.

A formal framework,

modelling \\captcha puzzles (as hard AI problems), was introduced by

Ahn, Blum, Hopper, and Langford (\\cite{AhnBHL03}, Eurocrypt 2003). Despite their

attractive features and wide adoption in practice, the use of \\captcha puzzles

for general cryptographic applications has been limited.

In this work, we explore various ways to formally model \\captcha puzzles and their human component


explore new applications for \\captcha. We show that by defining \\captcha with

additional (strong but realistic) properties,

it is possible to broaden \\captcha applicability, including using it to learning a machine\'s

``secret internal state.\'\'

To facilitate this, we introduce

the notion of an human-extractable \\captcha, which we believe may be of independent interest.

We show that this type of \\captcha yields a \\emph{constant round} protocol for \\emph{fully}

concurrent non-malleable zero-knowledge. To enable this we also define and

construct a \\captcha -based commitment scheme which admits ``straight line\'\' extraction.

We also explore

\\captcha definitions in the setting of Universal Composability (UC). We show that there are two (incomparable) ways to

model \\captcha within the UC framework that lead to different results.

In particular, we show that in the so called

\\emph{indirect access model}, for every polynomial time functionality $\\calf$

there exists a protocol that UC-realizes $\\calf$ using human-extractable \\captcha, while for the so-called

\\emph{direct access model}, UC is impossible, even with the help of human-extractable \\captcha.

The security of our constructions using human-extractable \\captcha

is proven against the (standard) class of

all polynomial time adversaries. In contrast, most previous works guarantee

security only against a very limited class of adversaries, called the

\\emph{conservative} adversaries.

13:17 [Pub][ePrint] The Weakness of Integrity Protection for LTE, by Teng Wu and Guang Gong

  In this paper, we concentrate on the security issues of the integrity protection of LTE and present two different forgery attacks. For the first attack, referred to as a {\\em linear forgery attack}, EIA1 and EIA3, two integrity protection algorithms of LTE, are insecure if the initial value (IV) can be repeated twice during the life cycle of an integrity key (IK). Because of the linearity of EIA1 and EIA3, given two valid Message Authentication Codes (MACs) our algorithm can forge up to $2^{32}$ valid MACs. Thus, the probability of finding a valid MAC is dramatically increased. Although the combination of IV and IK never repeats in the ordinary case, in our well-designed scenario, the attacker can make the same combination occur twice. The duplication provides the opportunity to conduct our linear forgery attack, which may harm the security of communication. To test our linear forgery attack algorithm, we generate two counter check messages and successfully forge the third one. We also examine the attack timing by simulating real communication. From the experimental results, our attack is applicable. The second attack is referred to as a {\\em trace extension forgery attack}, which works only in theory. However, this attack is more general than the linear forgery attack. Known only one MAC and message pair, we can construct a different message, who has the same MAC as the original one, with the probability $\\frac{1}{2^{16}}$. In this attack, trace function is applied to the message to shrink the guessing space.

13:17 [Pub][ePrint] Root Optimization of Polynomials in the Number Field Sieve, by Shi Bai and Richard P. Brent and Emmanuel Thom\\\'e

  The general number field sieve (GNFS) is the most efficient

algorithm known for factoring large integers. It consists of several

stages, the first one being polynomial selection. The quality of the

chosen polynomials in polynomial selection can be modelled in terms of

size and root properties. In this paper, we describe some algorithms for

selecting polynomials with very good root properties.

13:17 [Pub][ePrint] Integrated PKE and PEKS - Stronger Security Notions and New Constructions , by Yu Chen and Jiang Zhang and Zhenfeng Zhang and Dongdai Lin

  In this paper we investigate the security for integrated public-key encryption (PKE)

and public-key encryption with keyword search (PEKS) schemes. We observe that the security

notions for integrated PKE and PEKS schemes considered in the existing literature are not strong

enough to capture practical attacks, thus define a new notion named joint CCA-security which is

shown to be stronger than the previous ones. We also propose two simple and efficient constructions

of jointly CCA-secure integrated PKE and PEKS schemes from anonymous (hierarchical) identity-

based encryption schemes. Besides, we review the consistency for PEKS schemes and improve

previous results.