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

21:17 [Pub][ePrint] The Locality of Searchable Symmetric Encryption, by David Cash and Stefano Tessaro

  This paper proves a lower bound on the trade-off between server storage size and the locality of memory accesses in searchable symmetric encryption (SSE). Namely, when encrypting an index of $N$ identifier/keyword pairs, the encrypted index must have size $\\omega(N)$ \\emph{or} the scheme must perform searching with $\\omega(1)$ non-contiguous reads to memory \\emph{or} the scheme must read many more bits than is necessary to compute the results. Recent implementations have shown that non-locality of server memory accesses create a throughput-bottleneck on very large databases. Our lower bound shows that this is due to the security notion and not a defect of the constructions. An upper bound is also given in the form of a new SSE construction with an $O(N\\log N)$ size encrypted index that performs $O(\\log N)$ reads during a search.

15:17 [Pub][ePrint] Optimality of Non-Adaptive Strategies: The Case of Parallel Games, by Grégory Demay and Peter Gaži and Ueli Maurer and Björn Tackmann

  Most cryptographic security proofs require showing that two

systems are indistinguishable. A central tool in such

proofs is that of a game, where winning the game means

provoking a certain condition, and it is shown that the two

systems considered cannot be distinguished unless this

condition is provoked. Upper bounding the probability of

winning such a game, i.e., provoking this condition, for an

arbitrary strategy is usually hard, except in the special

case where the best strategy for winning such a game is

known to be non-adaptive.

A sufficient criterion for ensuring the optimality of

non-adaptive strategies is that of conditional equivalence

to a system, a notion introduced in [Mau02]. In this

paper, we show that this criterion is not necessary

to ensure the optimality of non-adaptive strategies by

giving two results of independent interest: 1) the

optimality of non-adaptive strategies is not preserved under

parallel composition; 2) in contrast, conditional

equivalence is preserved under parallel composition.

15:17 [Pub][ePrint] On the Powers of 2, by Robert Granger and Thorsten Kleinjung and Jens Zumbr\\\"agel

  In 2013 the function field sieve algorithm for computing discrete logarithms in finite fields of small characteristic underwent a series of dramatic improvements, culminating in the first heuristic quasi-polynomial time algorithm, due to Barbulescu, Gaudry, Joux and Thom\\\'e. In this article we present an alternative descent method which is built entirely from the on-the-fly degree two elimination method of

G\\\"olo\\u{g}lu, Granger, McGuire and Zumbr\\\"agel. This also results in a heuristic quasi-polynomial time algorithm, for which the descent does not require any relation gathering or linear algebra eliminations and interestingly, does not require any smoothness assumptions about non-uniformly distributed polynomials. These properties make the new descent method readily applicable at currently viable bitlengths and better suited to theoretical analysis.

15:17 [Pub][ePrint] How to Avoid Obfuscation Using Witness PRFs, by Mark Zhandry

  Recently, program obfuscation has proven to be an extremely powerful tool and has been used to construct a variety of cryptographic primitives with amazing properties. However, current candidate obfuscators are far from practical and rely on unnatural hardness assumptions about multilinear maps. In this work, we bring several applications of obfuscation closer to practice by showing that a weaker primitive called witness pseudorandom functions (witness PRFs) suces. Applications include multiparty key exchange without trusted setup, polynomially-many hardcore bits for any one-way function, and more. We then show how to instantiate witness PRFs from multilinear maps. Our witness PRFs are simpler and more ecient than current obfuscation candidates, and involve very natural hardness assumptions about the underlying maps.

12:17 [Pub][ePrint] Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding, by Andris Ambainis and Ansis Rosmanis and Dominique Unruh

  Quantum zero-knowledge proofs and quantum proofs of knowledge are

inherently difficult to analyze because their security analysis uses

rewinding. Certain cases of quantum rewinding are handled by the

results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012),

yet in general the problem remains elusive. We show that this is not

only due to a lack of proof techniques: relative to an oracle, we show

that classically secure proofs and proofs of knowledge are insecure in

the quantum setting.

More specifically, sigma-protocols, the Fiat-Shamir construction, and

Fischlin\'s proof system are quantum insecure under assumptions that

are sufficient for classical security. Additionally, we show that for

similar reasons, computationally binding commitments provide almost no

security guarantees in a quantum setting.

To show these results, we develop the \"pick-one trick\", a general

technique that allows an adversary to find one value satisfying a

given predicate, but not two.

12:17 [Pub][ePrint] Pipelineable On-Line Encryption, by Farzaneh Abed and Scott Fluhrer and John Foley and Christian Forler and Eik List and Stefan Lucks and David McGrew and Jakob Wenzel

  Correct authenticated decryption requires the receiver to buffer the decrypted message until the authenticity check has been performed. In high-speed networks, which must handle large message frames at low latency, this behavior becomes practically infeasible. This paper proposes CCA-secure on-line ciphers as a practical alternative to AE schemes since the former provide some defense against malicious message modifications. Unfortunately, all published on-line ciphers so far are either inherently sequential, or lack a CCA-security proof.

This paper introduces POE, a family of on-line ciphers that combines provable security against chosen-ciphertext attacks with pipelineability to support efficient implementations. POE combines a block cipher and an e-AXU family of hash functions. Different instantiations of POE are given, based on different universal hash functions and suitable for different platforms. Moreover, this paper introduces POET, a provably secure on-line AE scheme, which inherits pipelineability and chosen-ciphertext-security from POE and provides additional resistance against nonce-misuse attacks.

12:17 [Pub][ePrint] Torsion Limits and Riemann-Roch Systems for Function Fields and Applications, by Ignacio Cascudo and Ronald Cramer and Chaoping Xing

  The Ihara limit (or constant) $A(q)$ has been a central problem of study in the asymptotic theory of global function fields (or equivalently, algebraic curves over finite fields). It addresses global function fields with many rational points and,

so far, most applications of this theory do not

require additional properties. Motivated by recent applications, we require global function fields

with the additional property that their zero class divisor groups contain at most a small number of $d$-torsion points. We capture this with the notion of torsion limit, a new asymptotic quantity for global function fields.

It seems that it is even harder to determine values of this new quantity than the Ihara constant.

Nevertheless, some non-trivial upper bounds are derived.

Apart from this new asymptotic quantity and bounds on it, we also introduce Riemann-Roch systems of equations. It turns out that this type of equation system

plays an important role in the study of several other problems in each of these areas: arithmetic secret sharing, symmetric bilinear complexity of multiplication in finite fields, frameproof codes and the theory of error correcting codes.

Finally, we show how our new asymptotic quantity, our bounds on it and Riemann-Roch systems can be used to improve results in these areas.

06:17 [Pub][ePrint] An Efficient Abuse-Free Fair Contract-Signing Protocol Based on RSA Signature and Σ-protocol, by Xi-Jun Lin and Lin Sun

  A fair contract-signing protocol is an important mechanism which allows two participants to sign a digital contract via the public computer networks in a fair way. Based on the RSA signature scheme and Σ-protocol, we propose a new contract-signing protocol in this paper. The proposed protocol is not only fair and optimistic, but also efficient and abuse-free. Moreover, security and efficiency analysis are provided.

06:17 [Pub][ePrint] The M3lcrypt Password Based Key Derivation Function, by Isaiah Makwakwa

  M3lcrypt (canonical M3lcryptH) is a password based key derivation

function built around the Merkle-Damgard hash function H. It supports

large [pseudo]random salt values ( 128-bit) and password lengths.

06:17 [Pub][ePrint] ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation, by Nir Bitansky and Omer Paneth

  We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes:



ZAP (or, equivalently, non-interactive zero-knowledge in the common random string model) from indistinguishability obfuscation and one-way functions.


NIWIs from indistinguishability obfuscation and one-way permutations.


The previous construction of ZAPs [Dwork and Naor, FOCS 00] was based on trapdoor permutations. The two previous NIWI constructions were based either on ZAPs and a derandomization-type complexity assumption [Barak, Ong, and Vadhan CRYPTO 03], or on a specific number theoretic assumption in bilinear groups [Groth, Sahai, and Ostrovsky, CRYPTO 06].

21:17 [Pub][ePrint] Trial multiplication is not optimal but... On the symmetry of finite cyclic groups (Z/pZ)∗, by Antonio Sanso

  The Discrete Logarithm Problem is at the base of the famous Diffie Hellman key agreement algorithm and many others. The key idea behind Diffie Helmann is the usage of the Discrete Logarithm function in (Z/pZ)∗ as a trap door function. The Discrete Logarithm function output in (Z/pZ)∗ seems to escape to any attempt of finding some sort of pattern. Nevertheless some new characterization will be introduced together with a novel and more efficient trial multi- plication algorithm.