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

15:56 [Event][New] nullcon International Security Conference

  From February 4 to February 7
Location: Goa, India
More Information:

03:17 [Pub][ePrint] Zipf\'s Law in Passwords, by Ding Wang, Gaopeng Jian, Haibo Cheng, Qianchen Gu, Chen Zhu, Ping Wang

  Despite more than thirty years of research efforts, textual passwords are still enveloped in mysterious veils. In this work, we make a substantial step forward in understanding the distributions of passwords and measuring the strength of password datasets by using a statistical approach. We first show that Zipf\'s law perfectly exists in real-life passwords by conducting linear regressions on a corpus of 56 million passwords. As one specific application of this observation, we propose the number of unique passwords used in regression and the slope of the regression line together as a metric for assessing the strength of password datasets, and prove it in a mathematically rigorous manner. Furthermore, extensive experiments (including optimal attacks, simulated optimal attacks and state-of-the-art cracking sessions) are performed to demonstrate the practical effectiveness of our metric. To the best of knowledge, our new metric is the first one that is both easy to approximate and accurate to facilitate comparisons, providing a useful tool for the system administrators to gain a precise grasp of the strength of their password datasets and to adjust the password policies more reasonably.

03:17 [Pub][ePrint] Verifiable Member and Order Queries on a List in Zero-Knowledge, by Esha Ghosh and Olga Ohrimenko and Roberto Tamassia

  We introduce a formal model for order queries on lists in zero knowledge in the traditional authenticated data structure model.

We call this model Privacy-Preserving Authenticated List (PPAL).

In this model, the queries are performed on the list stored in the (untrusted) cloud where data integrity and privacy have to

be maintained. To realize an efficient authenticated data structure, we first adapt consistent data query model.

To this end we introduce a formal model called Zero-Knowledge List (ZKL) scheme which generalizes consistent membership queries in zero-knowledge

to consistent membership and order queries on a totally ordered set in zero knowledge. We present a construction of ZKL based on zero-knowledge set

and homomorphic integer commitment scheme. Then we discuss why this construction is not as efficient as desired in cloud applications and

present an efficient construction of PPAL based on bilinear accumulators and bilinear maps which is provably secure and zero-knowledge.

03:17 [Pub][ePrint] Client-Server Concurrent Zero Knowledge with Constant Rounds and Guaranteed Complexity, by Ran Canetti and Abhishek Jain and Omer Paneth

  The traditional setting for concurrent zero knowledge considers a server that proves a statement in zero-knowledge to multiple clients in multiple concurrent sessions, where the server\'s actions in a session are independent of all other sessions. Persiano and Visconti [ICALP 05] show how keeping a limited amount of global state across sessions allows the server to significantly reduce the overall complexity while retaining the ability to interact concurrently with an unbounded number of clients. Specifically, they show a protocol that has only slightly super-constant number of rounds; however the communication complexity in each session of their protocol depends on the number of other sessions and has no a priori bound. This has the drawback that the client has no way to know in advance the amount of resources required for completing a session of the protocol up to the moment where the session is completed.

We show a protocol that does not have this drawback. Specifically, in our protocol the client obtains a bound on the communication complexity of each session at the start of the session. Additionally the protocol is constant-rounds. Our protocol is fully concurrent, and assumes only collision-resistant hash functions. The proof requires considerably different techniques than those of Persiano and Visconti. Our main technical tool is an adaptation of the \"committed-simulator\" technique of Deng et. al [FOCS 09].

03:17 [Pub][ePrint] Constant-Round Leakage-Resilient Zero-Knowledge Arguments of Knowledge for NP, by Hongda Li, Qihua Niu, Guifang Huang

  Garg, Jain, and Sahai first consider zero knowledge proofs in the presence of leakage on the local state of the prover, and present a leakage-resilient-zero-knowledge proof system for HC (Hamiltonian Cycle) problem. Their construction is called $(1+\\varepsilon)$-leakage-resilient zero-knowledge, for any constant $\\varepsilon>0$, because the total length of the leakage the simulator needs is $(1+\\varepsilon)$ times as large as that of the leakage received by the verifier. In recent, Pandey provides a constant-round leakage-resilient zero-knowledge argument satisfying the ideal requirement of $\\varepsilon=0$. Whether there exist constant round leakage-resilient zero-knowledge arguments of knowledge for all NP languages is an interesting problem. This paper focuses on this problem and presents a constant-round construction of leakage-resilient zero-knowledge arguments of knowledge for the HC problem.

03:17 [Pub][ePrint] Type 2 Structure-Preserving Signature Schemes Revisited, by Sanjit Chatterjee and Alfred Menezes

  Abe, Groth, Ohkubo and Tibouchi recently presented structure-preserving signature schemes using Type 2 pairings. The schemes are claimed to enjoy the fastest signature verification. By properly accounting for subgroup membership testing of group elements in signatures, we show that the schemes are not as efficient as claimed. We present natural Type 3 analogues of the Type 2 schemes, and show that the Type 3 schemes are superior to their Type 2 counterparts.

03:17 [Pub][ePrint] Improved Timing Attacks on ECDSA, by Vikram Singh

  We improve the timing attack on ECDSA in [1] by Brumley and Tuveri. We use the Gaussian heuristic to analyse the length of error vectors in the lattice Close Vector Problem in order to determine the problems which are theoretically solvable. Then we cost each solution using a strengthened lattice reduction algorithm and Schnorr-Euchner enumeration to determine which problems are practically solvable. The original work by Brumley and Tuveri resulted in OpenSSL\'s ECDSA being updated to remove the timing information they exploited, so that application is not vulnerable to our improvements. However we publish this work as a general advance in side-channel recovery techniques which may be applicable in related scenarios.

03:17 [Pub][ePrint] Generic Hardness of the Multiple Discrete Logarithm Problem, by Aaram Yun

  We study generic hardness of the multiple discrete logarithm problem, where the solver has to solve $n$ instances of the discrete logarithm problem simultaneously. There are known generic algorithms which perform $O(\\sqrt{n p})$ group operations, where $p$ is the group order, but no generic lower bound was known other than the trivial bound. In this paper we prove the tight generic lower bound, showing that the previously known algorithms are asymptotically optimal. We establish the lower bound by studying hardness of a related computational problem which we call the search-by-hyperplane-queries problem.

03:17 [Pub][ePrint] Pattern Matching Encryption, by Melissa Chase and Emily Shen

  In this paper, we consider a setting where a user wants to outsource storage of a large amount of private data, and then perform pattern matching queries on the data; that is, given a data string $s$ and a

``pattern\'\' string $p$, find all occurrences of $p$ as a substring of $s$.

We formalize the security properties desired in this type of setting by defining a type of encryption called \\emph{queryable

encryption}. In a queryable encryption scheme, a user can encrypt a

message $M$ under a secret key, and using the secret key can

generate tokens for queries $q$. Applying a token for a query $q$

to an encryption of $M$ gives the answer to the query $q$ on $M$. We consider security against both honest-but-curious and malicious adversaries, and define properties guaranteeing both the correctness of the user\'s results and the privacy of the user\'s data. Following the line of work started by \\cite{CGKO06}, to allow for efficient constructions, we allow the protocol to leak some information about the user\'s data, however we ensure that this leakage can be precisely captured in the definition. In addition, we allow the query protocol to involve a small constant number of rounds of interaction.

We construct a queryable encryption scheme for pattern matching queries that is correct and secure in the malicious model. Our construction is based on efficient symmetric-key building blocks and scales well with the size of the input: encryption of a data string of length $n$ with security parameter $\\lambda$ takes $O(n)$ time and produces a ciphertext of size $O(n\\lambda)$, and a query for a pattern string of length $m$ that occurs $k$ times takes $O(m+k)$ time and three rounds of communication.

03:17 [Pub][ePrint] Automated Design, Implementation, and Evaluation of Arbiter-based PUF on FPGA using Programmable Delay Lines, by Mehrdad Majzoobi, Akshat Kharaya, Farinaz Koushanfar, Srinivas Devadas

  This paper proposes a novel approach for automated implementation of an arbiter-based physical unclonable function (PUF)

on field programmable gate arrays (FPGAs). We introduce a high resolution programmable delay logic (PDL) that is implemented

by harnessing the FPGA lookup-table (LUT) internal structure. PDL allows automatic fine tuning of delays that

can mitigate the timing skews caused by asymmetries in interconnect routing and systematic variations. To thwart the arbiter metastability problem, we present and analyze methods for majority voting of responses. A method to classify and group challenges into different robustness sets is introduced that enhances the corresponding responses\' stability in the face of operational variations. The trade-off between response stability and response entropy (uniqueness) is investigated through comprehensive measurements. We exploit the correlation between the impact of temperature and power supply on responses and perform less costly power measurements to predict the temperature impact on PUF. The measurements are performed on 12 identical Virtex 5 FPGAs across 9 different accurately controlled operating temperature and voltage supply points. A database of challenge response pairs (CRPs) are collected and made openly available for the research community.

23:42 [Election] IACR 2014 Election: Nominations open


IACR 2014 Election

The 2014 election is being held to fill three of nine IACR Director positions. The election will again be run electronically and further information will be available on the IACR website.

Nominations Are Now Open

Nominations are due by October 10, 2014. A nomination form is available at the elections page.

Election of Directors

The directors whose terms are expiring are
  • Josh Benaloh (director)
  • Shai Halevi (director)
  • Moti Yung (director)

Election Committee

  • Michel Abdalla (Returning Officer)
  • Anna Lysyanskaya
  • Bart Preneel (Chair)