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

18:17 [Pub][ePrint] Using Indistinguishability Obfuscation via UCEs, by Christina Brzuska and Arno Mittelbach

  We provide the first standard model construction for a powerful class of Universal Computational Extractors (UCEs; Bellare et al. Crypto 2013) based on indistinguishability obfuscation. Our construction suffices to instantiate correlation-secure hash functions and universal one-way functions.

For many cryptographic primitives and in particular for correlation-secure hash functions all known constructions are in the random-oracle model. Indeed, recent negative results by Wichs (ITCS 2013) rule out a large class of techniques to prove the security of correlation-secure hash functions in the standard model. Our construction is based on puncturable PRFs (Sahai und Waters; STOC 2014) and indistinguishability obfuscation. However, our proof also relies on point obfuscation under auxiliary inputs (AIPO). This is crucial in light of Wichs\' impossibility result. Namely, Wichs proves that it is often hard to reduce two-stage games (such as UCEs) to a \"one-stage assumption\" such as DDH. In contrast, AIPOs and their underlying assumptions are inherently two-stage and, thus, allow us to circumvent Wichs\' impossibility result.

Our positive result is also noteworthy insofar as Brzuska, Farshim and Mittelbach (Crypto 2014) have shown recently, that iO and some variants of UCEs are mutually exclusive. Our results, hence, validate some of the new UCE notions that emerged as a response to the iO-attack.

18:17 [Pub][ePrint] Privacy-Enhanced Participatory Sensing with Collusion-Resistance and Data Aggregation, by Felix Günther and Mark Manulis and Andreas Peter

  Participatory sensing enables new paradigms and markets for information collection based on the ubiquitous availability of smartphones, but also introduces privacy challenges for participating users and their data. In this work, we review existing security models for privacy-preserving participatory sensing and propose several improvements that are both of theoretical and practical significance.

We first address an important drawback of prior work, namely the lack of consideration of collusion attacks that are highly relevant for such multi-user settings. We explain why existing security models are insufficient and why previous protocols become insecure in the presence of colluding parties. We remedy this problem by providing new security and privacy definitions that guarantee meaningful forms of collusion resistance. We propose new collusion-resistant participatory sensing protocols satisfying our definitions: a generic construction that uses anonymous identity-based encryption (IBE) and its practical instantiation based on the Boneh-Franklin IBE scheme.

We then extend the functionality of participatory sensing by adding the ability to perform aggregation on the data submitted by the users, without sacrificing their privacy. We realize this through an additively-homomorphic IBE scheme which in turn is constructed by slightly modifying the Boneh-Franklin IBE scheme. From a practical point of view, the resulting scheme is suitable for calculations with small sensor readings/values such as temperature measurements, noise levels, or prices, which is sufficient for many applications of participatory sensing.

18:17 [Pub][ePrint] Cryptanalysis of and Improvement on Biometric-based User Authentication Scheme for C/S System, by Younsung Choi, Dongho Won

  Password-based authentication schemes are convenient, but vulnerable to simple dictionary attacks. Cryptographic secret keys are safe, but difficult to memorize. More recently, biometric information has been used for authentication schemes. Das proposed a biometric-based authentication scheme, but it has various vulnerabilities. Jiping et al. improved Das\'s scheme, but some vulnerabilities remain. In this paper, we analyze the cryptanalysis of Jiping et al.\'s authentication scheme and propose the security enhanced biometric-based user authentication scheme for the C/S System.

18:17 [Pub][ePrint] Yao\'s millionaires\' problem and decoy-based public key encryption by classical physics, by Dima Grigoriev and Vladimir Shpilrain

  We use various laws of classical physics to offer several solutions of Yao\'s millionaires\' problem without using any one-way functions. We also describe several informationally secure public key encryption protocols, i.e., protocols secure against passive computationally unbounded adversary. This introduces a new paradigm of decoy-based cryptography, as opposed to ``traditional\" complexity-based cryptography. In particular, our protocols do not employ any one-way functions.

12:17 [Pub][ePrint] Multi-target DPA attacks: Pushing DPA beyond the limits of a desktop computer, by Luke Mather and Elisabeth Oswald and Carolyn Whitnall

  Following the pioneering CRYPTO \'99 paper by Kocher et al., differential power analysis (DPA) was initially geared around low-cost computations performed using standard desktop equipment with minimal reliance on device-specific assumptions. In subsequent years, the scope was broadened by, e.g., making explicit use of (approximate) power models. An important practical incentive of so-doing is to reduce the data complexity of attacks, usually at the cost of increased computational complexity. It is this trade-off which we seek to explore in this paper. We draw together emerging ideas from several strands of the literature---high performance computing, post-side-channel global key enumeration, and effective combination of separate information sources---by way of advancing (non-profiled) `standard DPA\' towards a more realistic threat model in which trace acquisitions are scarce but adversaries are well resourced. Using our specially designed computing platform (including our parallel and scalable DPA implementation, which allows us to work efficiently with as many as 2^{32} key hypotheses), we demonstrate some dramatic improvements that are possible for `standard DPA\' when combining DPA outcomes for several intermediate targets. Unlike most previous `information combining\' attempts, we are able to evidence the fact that the improvements apply even when the exact trace locations of the relevant information (i.e. the `interesting points\') are not known a priori but must be searched simultaneously with the correct subkey.

12:17 [Pub][ePrint] Cryptanalysis and Improvement on Robust Three-Factor Remote User Authentication Scheme with Key Agreement for Multimedia System, by Younsung Choi and Dongho Won

  A three-factor authentication combines biometrics information with user password and smart card to provide security-enhanced user authentication. An proposed user authentication scheme improved Das\'s scheme. But An\'s scheme is not secure against denial of service attack in login phase, forgery attack. Li et al. pointed out them and proposed three-factor remote user authentication scheme with key agreement. However, Li et al\'s scheme still has some security problem. In this paper, we present a cryptanalysis and improvement of Li et al.\'s remote user authentication scheme.

12:17 [Pub][ePrint] Redefining the Transparency Order, by Kaushik Chakraborty and Subhamoy Maitra and Sumanta Sarkar and Bodhisatwa Mazumdar and Debdeep Mukhopadhyay

  In this paper, we consider the multi-bit Differential Power Analysis (DPA) in the Hamming weight model. In this regard, we revisit the definition of Transparency Order (TO) from the work of Prouff (FSE 2005) and find that the definition has certain limitations. Although this work has been quite well referred in the literature, surprisingly, these limitations remained unexplored for almost a decade. The existing definition of TO (by Prouff) for an S-box

$F: \\F_2^n \\rightarrow \\F_2^m$ considers maximization on $\\beta \\in \\F_2^m$. However, we show that the expression suggested by Prouff is always maximum when $\\beta$ is either all-zero or all-one, that makes the maximization over all $\\beta \\in \\F_2^m$ redundant. Digging TO deeper, we note that the existing definition of TO assumes certain cross-correlation terms between the co-ordinate Boolean functions of $F$ as zero. This is not true in general and thus we need to accommodate these terms in the definition. Further the definition is based on the assumption that the co-ordinate functions in

the S-boxes are balanced (which is indeed logical for practical S-boxes), but unfortunately the measure has been calculated for bent functions (which are not balanced) in Prouff\'s paper and subsequent works. We analyse the definition from scratch, modify it and finally provide a substantially improved and logical definition that can theoretically capture DPA in Hamming weight model for hardware implementation with precharge logic. In this regard, our analysis comes with numerical data for AES S-Box and the family of S-Boxes described in the context of Prince.

12:17 [Pub][ePrint] Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an FPGA Cluster, by Erich Wenger and Paul Wolfger

  Using FPGAs to compute the discrete logarithms of elliptic curves is a well known method. However, until now only CPU clusters succeeded in computing new elliptic curve discrete logarithm records. This work presents a high-speed FPGA implementation that was used to compute the discrete logarithm of a 113-bit Koblitz curve. The core of the design is a fully unrolled, highly pipelined, self-sufficient Pollard\'s rho iteration function. An 18-core Virtex-6 FPGA cluster computed the discrete logarithm of a 113-bit Koblitz curve in extrapolated 24 days. Until now, no attack on such a large Koblitz curve succeeded using so minimal resources or in such a short time frame.

12:17 [Pub][ePrint] On the Limits of Authenticated Key Exchange Security with an Application to Bad Randomness, by Michèle Feltz and Cas Cremers

  State-of-the-art authenticated key exchange (AKE) protocols are proven secure in game-based security models. These models have considerably evolved in strength from the original Bellare-Rogaway model. However, so far only informal impossibility results, which suggest that no protocol can be secure against stronger adversaries, have been sketched. At the same time, there are many different security models being used, all of which aim to model the strongest possible adversary. In this paper we provide the first systematic analysis of the limits of game-based security models. Our analysis reveals that different security goals can be achieved in different relevant classes of AKE protocols. From our formal impossibility results, we derive strong security models for these protocol classes and give protocols that are secure in them. In particular, we analyse the security of AKE protocols in the presence of adversaries who can perform attacks based on chosen randomness, in which the adversary controls the randomness used in protocol sessions. Protocols that do not modify memory shared among sessions, which we call stateless protocols, are insecure against chosen-randomness attacks. We propose novel stateful protocols that provide resilience even against this worst case randomness failure, thereby weakening the security assumptions required on the random number generator.

12:17 [Pub][ePrint] Compact VSS and Efficient Homomorphic UC Commitments, by Ivan Damgård and Bernardo David and Irene Giacomelli and Jesper Buus Nielsen

  We present a new compact verifiable secret sharing scheme, based on

this we present the first construction of a homomorphic UC commitment

scheme that requires only cheap symmetric cryptography, except for a

small number of seed OTs. To commit to a $k$-bit string, the amortized

communication cost is $O(k)$ bits. Assuming a sufficiently efficient

pseudorandom generator, the computational complexity is $O(k)$ for the

verifier and $O(k^{1+\\epsilon})$ for the committer (where $\\epsilon

12:17 [Pub][ePrint] On the Enumeration of Double-Base Chains with Applications to Elliptic Curve Cryptography, by Christophe Doche

  The Double-Base Number System (DBNS) uses two bases, $2$ and $3$, in order to represent any

integer $n$.

A Double-Base Chain (DBC) is a special case of a DBNS expansion. DBCs have been introduced to speed up

the scalar multiplication $[n]P$ on certain families of elliptic curves used in cryptography.

In this context, our contributions are twofold.

First, given integers $n$, $a$, and $b$, we outline a recursive algorithm

to compute the number of different DBCs with a \\lt{} dividing $2^a3^b$ and representing $n$. A


modification of the algorithm allows to

determine the number of DBCs with a specified length as well as the actual expansions. In turn, this

gives rise to a method to compute an optimal DBC representing $n$, i.e. an expansion with minimal


Our implementation is able to return an optimal expansion for most integers up to $2^{60}$ bits

in a few minutes.

Second, we introduce an original and potentially more efficient approach to compute a random

scalar multiplication $[n]P$, called controlled DBC. Instead of generating a random integer $n$

and then trying to find an

optimal, or at least a short DBC to represent it, we propose to directly generate $n$ as a

random DBC with a chosen length $\\ell$ and \\lt{} $2^a3^b$.

To inform the selection of those parameters, in particular $\\ell$, which drives the

trade-off between the

efficiency and the security of the

underlying cryptosystem, we

enumerate the total number of DBCs having a certain length $\\ell$ and a given

\\lt{} $2^a3^b$.

The comparison between this total number of DBCs and the total number of

integers that we wish to represent a priori provides some guidance regarding the selection of

suitable parameters. Our experiments indicate that the controlled DBC provides a speedup of at

least $6.98\\%$ and up to $8\\%$ for sizes from $192$ to $512$ bits. Experiments involve elliptic

curves defined over $\\F_p$, using the Inverted Edwards coordinate system and state of the art

scalar multiplication techniques.