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

16:17 [Pub][ePrint] Power and Timing Side Channels for PUFs and their Efficient Exploitation, by Ulrich Rührmair and Xiaolin Xu and Jan Sölter and Ahmed Mahmoud and Farinaz Koushanfar and Wayne Burleson

  This paper discusses combined modeling and side

channel attacks on Strong Physical Unclonable Functions (Strong

PUFs). We illustrate our method by the example of the two

currently most secure (CCS 2010, IEEE T-IFS 2013) electrical

Strong PUFs, so-called XOR Arbiter PUFs and Lightweight

PUFs, and successfully attack them at sizes and complexities

far beyond the reach of pure modeling techniques (CCS 2010,

IEEE T-IFS 2013).

Our approach makes use of the first power and timing

side channels on PUFs reported in the literature. Both provide

information on the single outputs of the many parallel Arbiter

PUFs inside an XOR Arbiter PUF or Lightweight PUF, and

indicate how many of these single outputs (in sum) were equal

to one (and how many were equal to zero) before they entered

the final XOR gate. Taken for itself, this side channel information

is of little value. But if combined with suitably adapted machine

learning techniques, it substantially changes attack performance:

It reduces the empirically estimated complexities for modeling the

above two PUFs from exponential (CCS 2010, IEEE T-IFS) to

low degree polynomial.

The practical viability of our attacks is firstly demonstrated

by SPICE simulations, and by subsequent ML experiments on

numerically simulated CRPs. We thereby confirm attacks on the

two above PUFs for up to 16 XORs and challenge bitlengths

of up to 512. Secondly, we execute a full experimental proof-ofconcept

for our timing side channel, successfully attacking FPGA implementations of the two above PUF types for 8, 12, and 16

XORs, and bitlengths 64, 128, 256 and 512. We implement these

sizes for the first time in the literature in silicon, and subsequently attack them successfully by our new methods. We remark that in recent works (CCS 2010, IEEE T-IFS 2013), 8 XOR architectures

with bitlength 512 had been explicitly suggested as secure and

beyond the reach of current attacks.

Finally, we discuss efficient countermeasures against our power

and timing side channels. They could and should be used to secure

future Arbiter PUF generations against the latter.

16:17 [Pub][ePrint] Improved Boomerang Attacks on Round-Reduced SM3 and BLAKE-256, by Dongxia Bai and Hongbo Yu and Gaoli Wang and Xiaoyun Wang

  In this paper we study the security of hash functions SM3 and BLAKE-256 against boomerang attack. SM3 is designed by X. Wang et al. and published by Chinese Commercial Cryptography Administration Office for the use of electronic certification service system in China. BLAKE is one of the five finalists of the NIST SHA-3 competition submitted by J.-P. Aumasson et al. For SM3, we present boomerang distinguishers for the compression function reduced to 34/35/36/37/38 steps out of 64 steps, with time complexities $2^{31.4}$, $2^{33.6}$, $2^{73.4}$, $2^{93}$ and $2^{192}$ respectively. Then we show some incompatible problems existed in the previous boomerang attacks on SM3. Meanwhile, we launch boomerang attacks on up to 7 and 8 rounds keyed permutation of BLAKE-256 which are the first valid $7$-round and $8$-round boomerangs for BLAKE-256. Especially, since our distinguishers on 34/35-step compression function of SM3 and 7-round keyed permutation of BLAKE-256 are practical, we are able to obtain boomerang quartets of these attacks. As far as we know, these are the best results against round-reduced SM3 and BLAKE-256.

22:17 [Pub][ePrint] Identity-Based Key-Encapsulation Mechanism from Multilinear Maps, by Hao Wang and Lei Wu Zhihua Zheng

  We construct an Identity-Based Key Encapsulation Mechanism (IB-KEM) in a generic \"leveled\" multilinear map setting and make it translated to the GGH framework, which defined an \"approximate\" version of a multilinear group family from ideal lattices. Then, we prove their security in the selective-ID model.

22:17 [Pub][ePrint] Fair Two-Party Computations via the BitCoin Deposits, by Marcin Andrychowicz and Stefan Dziembowski and Daniel Malinowski and Łukasz Mazurek


22:17 [Pub][ePrint] An improved compression technique for signatures based on learning with errors, by Shi Bai and Steven D. Galbraith

  We present a new approach to the compression technique of Lyubashevsky et al for lattice-based signatures based on learning with errors (LWE).

Our ideas seem to be particularly suitable for signature schemes whose security, in the random oracle model, is based on standard worst-case computational assumptions. Our signatures are shorter than any previous proposal for provably-secure signatures based on standard lattice problems: at the 128-bit level we improve signature size from (more than) 16500 bits to around 9000 to 12000 bits.

22:17 [Pub][ePrint] Lattice Decoding Attacks on Binary LWE, by Shi Bai and Steven D. Galbraith

  We consider the binary-LWE problem, which is the learning with errors problem when the entries of the secret vector are chosen from $\\{ 0, 1\\}$ or $\\{ -1, 0, 1 \\}$ (and the error vector is sampled from a discrete Gaussian distribution). Our main result is an algorithm for binary-LWE that first translates the problem to the inhomogeneous short integer solution (ISIS) problem, and then solves the closest vector problem using a re-scaling of the lattice. We also discuss modulus switching as an approach to the problem. Our conclusions are that binary-LWE is easier than general LWE. We give experimental results that will be of help when choosing parameters for binary-LWE to achieve certain security levels.

22:17 [Pub][ePrint] (Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens, by Seung Geol Choi and Jonathan Katz and Dominique Schröder and Arkady Yerukhimovich and Hong Sheng Z

  We continue the line of work initiated by Katz (Eurocrypt 2007) on using tamper-proof hardware for universally composable secure computation. As our main result, we show an efficient oblivious-transfer (OT) protocol in which two parties each create and exchange a single, stateless token and can then run an unbounded number of OTs. Our result yields what we believe is the most practical and efficient known approach for oblivious transfer based on tamper-proof tokens, and implies that the parties can perform (repeated) secure computation of arbitrary functions without exchanging additional tokens.

Motivated by this result, we investigate the minimal number of stateless tokens needed for universally composable OT/secure computation. We prove that our protocol is optimal in this regard for constructions making black-box use of the tokens (in a sense we define). We also show that nonblack-box techniques can be used to obtain a construction using only a single stateless token.

22:17 [Pub][ePrint] Trust Views for the Web PKI, by Johannes Braun, Florian Volk, Johannes Buchmann and Max Mühlhäuser

  The steadily growing number of certication authorities (CAs)

assigned to the Web Public Key Infrastructure (Web PKI) and trusted

by current browsers imposes severe security issues. Apart from being

impossible for relying entities to assess whom they actually trust, the

current binary trust model implemented with the Web PKI makes each

CA a single point of failure. In this paper, we present the concept of

trust views to manage variable trust levels for exactly those CAs actually

required by a relying entity. This reduces the set of trusted CAs

and minimizes the risk to rely on malicious certicates issued due to CA

failures or compromises.

19:17 [Pub][ePrint] Is Bitcoin a Decentralized Currency?, by Arthur Gervais and Ghassan Karame and Srdjan Capkun and Vedran Capkun

  Bitcoin has achieved large-scale acceptance and popularity by promising its users a low-cost, anonymous, and completely decentralized exchange of transactions. However, recent incidents and observations are revealing the true limits of decentralization in the Bitcoin system. In this article, we show that the vital operations and decisions that Bitcoin is currently undertaking are not decentralized. More specifically, we show that a limited set of entities currently control

the services, decision making, mining, and the incident resolution processes in Bitcoin. We also show that third-party entities can unilaterally decide to \"devalue\" any specific set of Bitcoin addresses pertaining to any entity participating in the system. Finally, we explore possible avenues to enhance the decentralization in the Bitcoin system.


  At Eurocrypt\'12, Pandey and Rouselakis~\\cite{PR12} proposed the notion of property preserving symmetric encryption ({\\PPE}).

They defined several security notions for {\\PPE} and studied their relationship. They also proposed a concrete scheme which preserves

the orthogonality of encrypted vectors. The proposed construction is claimed to achieve the strongest security notion

of property preserving encryption, called {\\LoR} security. In this work, we take a critical look at the three security theorems in the context of {\\PPE} from~\\cite{PR12}. In particular, we show

that the Pandey-Rouselakis construction does not even satisfy the weakest notion of security for {\\PPE}. We also note that

their separation results between different notions of security for {\\PPE} stand vacuous in the absence of any concrete example. We fill up this gap in the separation results of~\\cite{PR12} by suggesting an example construction of


19:17 [Pub][ePrint] Provable Security Proofs and their Interpretation in the Real World, by Vikram Singh

  This paper analyses provable security proofs, using the EDL signature scheme as its case study, and interprets their benefits and drawbacks when applied to the real world.

Provable security has been an area of contention. Some, such as Koblitz and Menezes, give little credit to the potential extra security provided and argue that it is a distracting goal. However, others believe that an algorithm with a security proof is superior to one without it, and are prepared to accept the impact to performance that their use might involve. Goldreich has been notable for his defence of the security proof, and for his opposition to the view of Koblitz and Menezes.

This paper is designed to help the reader make their own decisions on security proofs. We achieve this by giving an introduction to the typical security model used, then give a description of the EDL signature scheme and its tight reduction to the CDH problem in the Random Oracle Model, then analyse the proof\'s assumptions, meaning, validity and overhead for real world security.