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] Branching Heuristics in Differential Collision Search with Applications to SHA-512, by Maria Eichlseder and Florian Mendel and Martin Schläffer

  In this work, we present practical semi-free-start collisions for SHA-512 on up to 38 (out of 80) steps with complexity $2^{40.5}$. The best previously published result was on 24 steps. The attack is based on extending local collisions as proposed by Mendel et al. in their Eurocrypt 2013 attack on SHA-256. However, for SHA-512, the search space is too large for direct application of these techniques. We achieve our result by improving the branching heuristic of the guess-and-determine approach to find differential characteristics and

conforming message pairs. Experiments show that for smaller problems like 27 steps of SHA-512, the heuristic can also speed up the

collision search by a factor of $2^{20}$.

21:17 [Pub][ePrint] On the security of Xu et al.\'s authentication and key agreement scheme for telecare medicine information systems, by SK Hafizul Islam

  In 2014, Xu et al. proposed a two-factor mutual authentication and

key agreement scheme for telecare medicine information system (TIMS)

based on elliptic curve cryptography (ECC). However, it has been

shown that Xu et al.\'s scheme is not suitable for practical use as

it is many problems. As a remedy, an improved scheme is proposed

with better security and functionality attributes.

21:17 [Pub][ePrint] Actively Private and Correct MPC Scheme in $t < n/2$ from Passively Secure Schemes with Small Overhead, by Dai Ikarashi and Ryo Kikuchi and Koki Hamada and Koji Chida

  Recently, several efforts to implement and use an unconditionally secure multi-party computation (MPC) scheme have been put into practice. These implementations are {\\em passively} secure MPC schemes in which an adversary must follow the MPC schemes. Although passively secure MPC schemes are efficient, passive security has the strong restriction concerning the behavior of the adversary. We investigate how secure we can construct MPC schemes while maintaining comparable efficiency with the passive case, and propose a construction of an {\\em actively} secure MPC scheme from passively secure ones. Our construction is secure in the $t < n/2$ setting, which is the same as the passively secure one. Our construction operates not only the theoretical minimal set for computing arbitrary circuits, that is, addition and multiplication, but also high-level operations such as shuffling and sorting. We do not use the broadcast channel in the construction. Therefore, privacy and correctness are achieved but {\\em robustness} is absent; if the adversary cheats, a protocol may not be finished but anyone can detect the cheat (and may stop the protocol) without leaking secret information. Instead of this, our construction requires $O((c_B n + n^2)\\kappa)$ communication that is comparable to one of the best known passively secure MPC schemes, $O((c_M n + n^2)\\log n)$, where $\\kappa$ denote the security parameter, $c_B$ denotes the sum of multiplication gates and high-level operations, and $c_M$ denotes the number of multiplication gates. Furthermore, we implemented our construction and confirmed that its efficiency is comparable to the current astest passively secure implementation.

21:17 [Pub][ePrint] Collision Attack on 5 Rounds of Grøstl, by Florian Mendel and Vincent Rijmen and Martin Schläffer

  In this article, we describe a novel collision attack for up to 5 rounds of the Grøstl hash function. This significantly improves upon the best previously published results on 3 rounds. By using a new type of differential trail spanning over more than one message block we are able to construct collisions for Grøstl on 4 and 5 rounds with complexity of $2^{67}$ and $2^{120}$, respectively. Both attacks need $2^{64}$ memory. Due to the generic nature of our attack we can even construct meaningful collisions in the chosen-prefix setting with the same attack complexity.

21:17 [Pub][ePrint] Publicly Evaluable Pseudorandom Functions and Their Applications, by Yu Chen and Zongyang Zhang

  We put forth the notion of publicly evaluable pseudorandom functions (PEPRFs),

which can be viewed as a non-trivial extension of the standard pseudorandom functions (PRFs). Briefly, PEPRFs are defined over domain $X$ where there exists an average-case hard NP language $L$, and each secret key $sk$ is associated with a public key $pk$. For any $x \\in L$, in addition to evaluate $\\mathsf{F}_{sk}(x)$ using $sk$ as in the standard PRFs, one is also able to evaluate $\\mathsf{F}_{sk}(x)$ with $pk$, $x$ and a witness $w$ for $x \\in L$. We consider two security notions for PEPRFs. The basic one is weak pseudorandomness which stipulates PEPRF can not be distinguished from a uniform random function only at randomly chosen inputs. The strengthened one is adaptive weak pseudorandomness

which requires PEPRF remains weak pseudorandom even when the adversary is given adaptive access to an evaluation oracle.

We conduct a formal study of PEPRFs, focusing on applications, constructions, and extensions.

We show how to construct chosen-plaintext secure (CPA) and chosen-ciphertext secure (CCA) public-key encryption (PKE) from (adaptive) PEPRFs. The construction is simple, black-box, and admits a direct proof of security. We provide evidence that (adaptive) PEPRFs exist by showing the constructions from both hash proof system and extractable hash proof system.

We introduce the notion of publicly samplable PRFs (PSPRFs), which is a relaxation of PEPRFs, but nonetheless imply PKE. We show (adaptive) PSPRFs are implied by (adaptive) trapdoor relations, yet the latter are further implied by (adaptive) trapdoor functions. This helps us to unify and clarify many PKE schemes from different paradigms and general assumptions under the notion of PSPRFs. We also view adaptive PSPRFs as a candidate of the weakest general assumption for CCA-secure PKE.

We explore similar extension on recently emerging predicate PRFs, putting forth the notion of publicly evaluable predicate PRFs, which, as an immediate application, imply predicate encryption.

We propose a variant of PEPRFs, which we call publicly evaluable and verifiable functions (PEVFs). Compared to PEPRFs, PEVFs have an addition promising property named public verifiability at the cost of the best possible security inherently degrades to hard to compute on average. We justify the applicability of PEVFs by presenting a simple construction of ``hash-and-sign\'\' signatures, both in the random oracle model and standard model.

21:17 [Pub][ePrint] Simulation-Time Security Margin Assessment against Power-Based Side Channel Attacks, by Alessandro Barenghi and Gerardo Pelosi and Francesco Regazzoni

  A sound design time evaluation of the security of a digital device is

a goal which has attracted a great amount of research effort lately.

Common security metrics for the attack consider either the theoretical leakage of the device, or assume as a security metric the

number of measurements needed in order to be able to always recover the secret key. In this work we provide a combined security

metric taking into account the computational effort needed to lead

the attack, in combination with the quantity of measurements to

be performed, and provide a practical lower bound for the security

margin which can be employed by a secure hardware designer. This

paper represents a first exploration of a design-time security metric

incorporating the computational effort required to lead a power-

based side channel attack in the security level assessment of the

device. We take into account in our metric the possible presence of

masking and hiding schemes, and we assume the best measurement

conditions for the attacker, thus leading to a conservative estimate

of the security of the device. We provide a practical validation of

our security metric through an analysis of transistor-level accurate

power simulations of a 128-bit AES core implemented on a 65 nm


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.