International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

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

2014-08-21
03:17 [Pub][ePrint]

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]

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]

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]

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]

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]

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]

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]

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.

2014-08-20
23:42 [Election]

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

21:17 [Pub][ePrint]

We demonstrate physical side-channel attacks on a popular software implementation of RSA and ElGamal, running on laptop computers. Our attacks use novel side channels, based on the observation that the \"ground\" electric potential, in many computers, fluctuates in a computation-dependent way. An attacker can measure this signal by touching exposed metal on the computer\'s chassis with a plain wire, or even with a bare hand. The signal can also be measured at the remote end of Ethernet, VGA or USB cables.

Through suitable cryptanalysis and signal processing, we have extracted 4096-bit RSA keys and 3072-bit ElGamal keys from laptops, via each of these channels, as well as via power analysis and electromagnetic probing. Despite the GHz-scale clock rate of the laptops and numerous noise sources, the full attacks require a few seconds of measurements using Medium Frequency signals (around 2 MHz), or one hour using Low Frequency signals (up to 40 kHz).

21:17 [Pub][ePrint]

This work deals with the various requirements of encryption and authentication in cryptographic applications. The approach

is to construct suitable modes of operations of a block cipher to achieve the relevant goals. A variety

of schemes suitable for specific applications are presented. While none of the schemes are built completely from scratch,

there is a common unifying framework which connects them. All the schemes described have been implemented and the implementation

details are publicly available. Performance figures are presented when the block cipher is the AES and the Intel AES-NI

instructions are used. These figures suggest that the constructions presented here compare well with previous works

such as the famous OCB mode of operation. In terms of features, the constructions provide several new offerings which

are not present in earlier works. This work significantly widens the range of choices of an actual designer of

cryptographic system.