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 get this service 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).

13:17 [Pub][ePrint] Using the Joint Distributions of a Cryptographic Function in Side Channel Analysis, by Yanis Linge and Cecile Dumas and Sophie Lambert-Lacroix

  The Side Channel Analysis is now a classic way to retrieve a secret key in the smart-card world. Unfortunately, most of the ensuing attacks require the plaintext or the ciphertext used by the embedded algorithm. In this article, we present a new method for exploiting the leakage of a device without this constraint. Our attack is based on a study of the leakage distribution of internal data of a cryptographic function and can be performed not only at the beginning or the end of the algorithm, but also at every instant that involves the secret key. This paper focuses on the distribution study and the resulting attack. We also propose a way to proceed in a noisy context using smart distances. We validate our proposition by practical results on an AES128 software implemented on a ATMega2561 and on the DPA contest v4.

13:17 [Pub][ePrint] On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary Input , by Sanjam Garg and Craig Gentry and Shai Halevi and Daniel Wichs

  The notion of differing-inputs obfuscation (diO) was introduced by Barak et al. (CRYPTO 2001). It guarantees that for any two circuits $C_0, C_1$, for which it is difficult to use their description and come up with an input $x$ on which they differ $C_0(x) \\neq C_1(x)$, it should also be difficult to distinguish the obfuscation of $C_0$ from that of $C_1$. This is a strengthening of indistinguishability obfuscation, where the above is only guaranteed for circuits that agree on all inputs: $C_0(x) = C_1(x)$ for all $x$. Two recent works of Ananth et al. (ePrint 2013) and Boyle et al. (TCC 2014) study the notion of diO in the setting where the attacker is also given some auxiliary information related to the circuits, showing that this notion leads to many interesting applications. One of these applications is extractable witness encryption, defined by Goldwasswer et al. (CRYPTO \'13), which in turn leads to constructions of functional encryption and reusable garbling schemes that work directly on Turing Machines rather than circuits.

In this work, we show that the existence of general-purpose diO with general auxiliary input leads to a surprising ``implausible\'\' consequence: in particular, it would show the impossibility of obfuscating a specific circuit $C^*$ with specific auxiliary input $\\aux^*$ in a way that hides some specific information. In particular, we put forth the assumption that such special-purpose obfuscation exists, and under this assumption, we show that general-purpose diO does not exist. This special-purpose obfuscation assumption isn\'t implied by diO itself and hence we do not get an unconditional impossibility result. However, the special-purpose obfuscation assumption is a falsifiable assumption which we do not know how to break for candidate obfuscation schemes. Showing the existence of general-purpose diO with general auxiliary input would necessitate showing how to break this assumption. We also give a similar result showing the impossibility of extractable witness encryption under the same special-purpose obfuscation assumption.

13:17 [Pub][ePrint] Privacy Preserving Enforcement of Sensitive Policies in Outsourced and Distributed Environments, by Muhammad Rizwan Asghar

  The enforcement of sensitive policies in untrusted environments is still an open challenge for policy-based systems. On the one hand, taking any appropriate security decision requires access to these policies. On the other hand, if such access is allowed in an untrusted environment then confidential information might be leaked by the policies. The key challenge is how to enforce sensitive policies and protect content in untrusted environments. In the context of untrusted environments, we mainly distinguish between outsourced and distributed environments. The most attractive paradigms concerning outsourced and distributed environments are cloud computing and opportunistic networks, respectively.

In this dissertation, we present the design, technical and implementation details of our proposed policy-based access control mechanisms for untrusted environments. First of all, we provide full confidentiality of access policies in outsourced environments, where service providers do not learn private information about policies during the policy deployment and evaluation phases. Our proposed architecture is such that we are able to support expressive policies and take into account contextual information before making any access decision. The system entities do not share any encryption keys and even if a user is deleted, the system is still able to perform its operations without requiring any action. For complex user management, we have implemented a policy-based Role-Based Access Control (RBAC) mechanism, where users are assigned roles, roles are assigned permissions and users execute permissions if their roles are active in the session maintained by service providers. Finally, we offer the full-fledged RBAC policies by incorporating role hierarchies and dynamic security constraints.

In opportunistic networks, we protect content by specifying expressive access control policies. In our proposed approach, brokers match subscriptions against policies associated with content without compromising privacy of subscribers. As a result, an unauthorised broker neither gains access to content nor learns policies and authorised nodes gain access only if they satisfy fine-grained policies specified by publishers. Our proposed system provides scalable key management in which loosely-coupled publishers and subscribers communicate without any prior contact. Finally, we have developed a prototype of the system that runs on real smartphones and analysed its performance.

13:17 [Pub][ePrint] How to Delegate Computations: The Power of No-Signaling Proofs, by Yael Tauman Kalai and Ran Raz and Ron Rothblum

  We construct a 1-round delegation scheme (i.e., argument-system)

for every language computable in time t=t(n), where the running

time of the prover is poly(t) and the running time of the

verifier is n*polylog(t). In particular, for every language in P

we obtain a delegation scheme with almost linear time

verification. Our construction relies on the existence of a

computational sub-exponentially secure private information

retrieval (PIR) scheme.

The proof exploits a curious connection between the problem of

computation delegation and the model of multi-prover interactive

proofs that are sound against no-signaling (cheating) strategies,

a model that was studied in the context of multi-prover

interactive proofs with provers that share quantum entanglement,

and is motivated by the physical principle that information

cannot travel faster than light.

For any language computable in time t=t(n), we construct a

multi-prover interactive proof (MIP) that is sound against

no-signaling strategies, where the running time of the provers is

poly(t), the number of provers is polylog(t), and the running

time of the verifier is n*polylog(t).

In particular, this shows that the class of languages that have

polynomial-time MIPs that are sound against no-signaling

strategies, is exactly EXP. Previously, this class was only known

to contain PSPACE.

To convert our MIP into a 1-round delegation scheme, we use the

method suggested by Aiello et-al (ICALP, 2000), which makes use

of a PIR scheme. This method lacked a proof of security. We prove

that this method is secure assuming the underlying MIP is secure

against no-signaling provers.

13:17 [Pub][ePrint] Formal Treatment of Distributed Trust in Electronic Voting, by Stephan Neumann and Melanie Volkamer

  Electronic voting systems are among the most security critical distributed systems. Different trust concepts are implemented to mitigate the risk of conspiracies endangering security properties. These concepts render systems often very complex and end users no longer recognize whom they need to trust. Correspondingly, specific trust considerations are necessary to support users. Recently, resilience terms have been proposed in order to express, which entities can violate the addressed security properties in particular by illegal collaborations. However, previous works derived these resilience terms manually. Thus, successful attacks can be missed. Based on this approach, we propose a framework to formally and automatically derive these terms. Our framework comprises a knowledge calculus, which allows us to model knowledge and reason about knowledge of collaborating election entities. The introduced framework is applied to deduce previously manually derived resilience terms of three remote electronic voting systems, namely Polyas, Helios and the Estonian voting system. Thereby, we were able to discover mistakes in previous derivations.

13:17 [Pub][ePrint] Near-linear time, Leakage-resilient Key Evolution Schemes from Expander Graphs, by Adam Smith and Ye Zhang

  We develop new schemes for deterministically updating a stored

cryptographic key that provide security against an internal

adversary who can control the update computation and leak bounded

amounts of information to the outside world. Our schemes are much

more efficient than the previous schemes for this model, due to Dziembowski,

Kazana and Wichs (CRYPTO 2011). Specifically, our update operation

runs in time quasilinear in the key length, rather than quadratic,

while offering a similar level of leakage resilience.

In order to design our scheme, we strengthen the connections between

the model of Dziembowski et al. and ``pebbling games\'\', showing that

random-oracle-based key evolution schemes are secure as long as the

graph of the update function\'s calls to the oracle has

appropriate combinatorial properties. This builds on a connection

between pebbling and the random oracle model first established by

Dwork, Naor and Wee (CRYPTO 2005). Our scheme\'s efficiency relies on the

existence (which we show) of families of ``local\'\'

bipartite expander graphs of constant degree.

13:17 [Pub][ePrint] SNR to Success Rate: Reaching the Limit of Non-Profiling DPA, by Suvadeep Hajra and Debdeep Mukhopadhyay

  Profiling power attacks like Template attack and Stochastic attack optimizes their performance by jointly evaluating the leakages of multiple sample points. However, such multivariate approaches are rare among non-profiling DPA attacks, since integration of the leakage of a higher Signal-to-Noise Ratio (SNR) sample point with the leakages of lower SNR sample points might result in a decrease in the overall performance. We study the issue of optimally combining the leakages of multiple sample points using a linear function in great details. In this work, our contributions are three-fold: 1) we first derive a relation between the success rate of a CPA attack and the SNR of the power traces, 2) we introduce a multivariate leakage model for Virtex-5 FPGA device, and 3) using the proposed multivariate leakage model, we derive the linear Finite Impulse Response (FIR) filter coefficients which maximizes the SNR of the output leakage, thus optimizes the success rate of the CPA attacks in a non-profiling setup.

13:17 [Pub][ePrint] Compact Hardware Implementation of Ring-LWE Cryptosystems, by Sujoy Sinha Roy and Frederik Vercauteren and Nele Mentens and Donald Donglong Chen and Ingrid Verbauwhede

  In this paper we propose an efficient and compact hardware implementation of a polynomial multiplier based on the Fast Fourier Transform (FFT) for use in ring-LWE cryptosystems. We optimize the forward wrapped convolution by merging the pre-processing and the FFT and propose an advanced memory access scheme which reduces the number

of memory accesses and the number of RAM slices used in the design.

These techniques result in a hardware implementation of a polynomial multiplier for the ring-LWE cryptosystem of dimension 256 that uses only 281 slices and one block RAM on a Virtex V.

Finally, we also propose a modification of a ring-LWE encryption system

that reduces the number of FTT operations from five to four resulting

in a near 20% speed-up.

13:17 [Pub][ePrint] LHash: A Lightweight Hash Function (Full Version), by Wenling Wu and Shuang Wu and Lei Zhang and Jian Zou and Le Dong

  In this paper, we propose a new lightweight hash function

supporting three different digest sizes: 80, 96 and 128 bits,

providing preimage security from 64 to 120 bits, second preimage

and collision security from 40 to 60 bits. LHash requires about

817 GE and 1028 GE with a serialized implementation. In faster

implementations based on function $T$, LHash requires 989 GE and

1200 GE with 54 and 72 cycles per block, respectively.

Furthermore, its energy consumption evaluated by energy per bit is

also remarkable. LHash allows to make trade-offs among security,

speed, energy consumption and implementation costs by adjusting

parameters. The design of LHash employs a kind of Feistel-PG structure in

the internal permutation, and this structure can

utilize permutation layers on

nibbles to improve the diffusion speed. The adaptability of LHash

in different environments is good, since different versions of

LHash share the same basic computing module. The low-area

implementation comes from the hardware-friendly S-box and linear

diffusion layer. We evaluate the resistance of LHash against known

attacks and confirm that LHash provides a good security margin.

13:17 [Pub][ePrint] Theoretical Bitcoin Attacks with less than Half of the Computational Power (draft), by Lear Bahack

  A widespread security claim of the Bitcoin system, presented in the original Bitcoin whitepaper, states that the security of the system is guaranteed as long as there is no attacker in possession of half or more of the total computational power used to maintain the system. This claim, however, is proved based on theoretically flawed assumptions.

In the paper we analyze two kinds of attacks based on two theoretical flaws: the Block Discarding Attack and the Difficulty Raising Attack. We argue that the current theoretical limit of attacker\'s fraction of total computational power essential for the security of the system is in a sense not $\\frac{1}{2}$ but a bit less than $\\frac{1}{4}$, and outline proposals for protocol change that can raise this limit to be as close to $\\frac{1}{2}$ as we want.

The basic idea of the Block Discarding Attack has been noted as early as 2010, and lately was independently though-of and analyzed by both author of this paper and authors of a most recently pre-print published paper. We thus focus on the major differences of our analysis, and try to explain the unfortunate surprising coincidence. To the best of our knowledge, the second attack is presented here for the first time.

13:17 [Pub][ePrint] How to Fake Auxiliary Input, by Dimitar Jetchev and Krzysztof Pietrzak

  Consider a joint distribution $(X,A)$ on a set ${\\cal X}\\times\\{0,1\\}^\\ell$. We show that for any family ${\\cal F}$ of distinguishers $f \\colon {\\cal X} \\times \\{0,1\\}^\\ell \\rightarrow \\{0,1\\}$, there exists a simulator $h \\colon {\\cal X} \\rightarrow \\{0,1\\}^\\ell$ such that


\\item no function in ${\\cal F}$ can distinguish $(X,A)$ from $(X,h(X))$ with advantage $\\epsilon$,

\\item $h$ is only $O(2^{3\\ell}\\epsilon^{-2})$ times less efficient than the functions in ${\\cal F}$.


For the most interesting settings of the parameters (in particular, the cryptographic case where $X$ has superlogarithmic min-entropy, $\\epsilon > 0$ is negligible and ${\\cal F}$ consists of circuits of polynomial size), we can make the simulator $h$ \\emph{deterministic}.

As an illustrative application of this theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt\'09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES.

Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem.