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

22:17 [Pub][ePrint] Shielding circuits with groups, by Eric Miles and Emanuele Viola

  We show how to efficiently compile any given circuit C into a leakage-resistant circuit C\' such that any function on the wires of C\' that leaks information during a computation C\'(x) yields advantage in computing the product of |C\'|^{Omega(1)} elements of the alternating group A_u. In combination with new compression bounds for A_u products, also obtained here, C\' withstands leakage from virtually any class of functions against which average-case lower bounds are known. This includes communication protocols, and AC^0 circuits augmented with few arbitrary symmetric gates. If NC^1 \\neq TC^0 then then the construction resists TC^0 leakage as well. In addition, we extend the construction to the multi-query setting by relying on a simple secure hardware component.

We build on Barrington\'s theorem [JCSS \'89] and on the previous leakage-resistant constructions by Ishai et al. [Crypto \'03] and Faust et al. [Eurocrypt \'10]. Our construction exploits properties of A_u beyond what is sufficient for Barrington\'s theorem.

22:17 [Pub][ePrint] Generalized (Identity-Based) Hash Proof System and Its Applications , by Yu Chen and Zongyang Zhang and Dongdai Lin and Zhenfu Cao

  In this work, we generalize the paradigm of hash proof system (HPS) proposed by Cramer and Shoup~\\cite{CS2002}.

In the central of our generalization, we lift subset membership problem to distribution distinguish problem.

Our generalized HPS clarifies and encompass all the known public-key encryption (PKE) schemes

that essentially implement the idea of hash proof system.

Moreover, besides existing smoothness property, we introduce an additional property named anonymity for HPS.

As a natural application, we consider anonymity for PKE in the presence of key-leakage,

and provide a generic construction of leakage-resilient anonymous PKE from anonymous HPS.

We then extend our generalization to the identity-based setting.

Concretely, we generalize the paradigm of identity-based hash proof system (IB-HPS)

proposed by Boneh~\\textit{et al.}~\\cite{BGH2007} and Alwen~\\textit{et al.}~\\cite{Alwen2010},

and introduce anonymity for it. As an interesting application of anonymous IB-HPS,

we consider security for public-key encryption with keyword search (PEKS) in the presence of token-leakage,

and provide a generic construction of leakage-resilient secure PEKS from leakage-resilient anonymous IBE,

which in turn is based on anonymous IB-HPS.

15:11 [Job][New] Post-Doc, University of Twente, the Netherlands

  The Distributed and Embedded Security Group at the University of Twente is searching for a suitable candidate for a post-doctoral research position to be involved in our system security research, especially related to security of industrial control systems. Suitable candidates are requested to apply immediately. Candidate selection will continue until the position is filled.

15:03 [Event][New] PETS'13: Privacy Enhancing Technologies Symposium

  Submission: 19 February 2013
Notification: 30 March 2013
From July 10 to July 12
Location: Bloomington, Indiana, USA
More Information:

15:03 [Event][New] WISTP '03: Seventh Workshop in Information Security Theory and Practices

  Submission: 31 January 2013
Notification: 15 March 2013
From May 28 to May 30
Location: Heraklion, Greece
More Information:

16:17 [Pub][ePrint] Defensive Leakage Camouflage, by E. Brier and Q. Fortier and R. Korkikian and K. W. Magld and D. Naccache and G. Ozari de Almeida and A. Pommellet and A. H. Ragab and J. Vuillemin

  This paper considers the transfer of digital data over {\\sl leaky and noisy} communication channels. We develop defensive strategies exploiting the fact that noise prevents the attacker from accurately measuring leakage.

The defense strategy described in this paper pairs each useful data element $k$ with a camouflage value $v$ and simultaneously transmits both $k$ and $v$ over the channel. This releases an emission $e(k,v)$. We wish to select the camouflage values $v(k)$ as a function of $k$ in a way that makes the quantities $e(k,v(k))$ as {\\sl indistinguishable} as possible from each other.

We model the problem and show that optimal camouflage values can be computed from side-channels under very weak physical assumptions. The proposed technique is hence applicable to a wide range of readily available technologies.

We propose algorithms for computing optimal camouflage values when the number of samples per trace is moderate (typically $\\leq 6$) and justify our models by a statistical analysis.

We also provide experimental results obtained using FPGAs.

16:17 [Pub][ePrint] On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography, by Nir Bitansky and Omer Paneth

  The traditional notion of {\\em program obfuscation} requires that an obfuscation $\\tilde{f}$ of a program $f$ computes the exact same function as $f$, but beyond that, the code of $\\tilde{f}$ should not leak any information about $f$. This strong notion of {\\em virtual black-box} security was shown by Barak et al. (CRYPTO 2001) to be impossible to achieve, for certain {\\em unobfuscatable function families}. The same work raised the question of {\\em approximate obfuscation}, where the obfuscated $\\tilde{f}$ is only required to approximate $\\tilde{f}$; that is, $\\tilde{f}$ only agrees with $f$ on some input distribution.

We show that, assuming {\\em trapdoor permutations}, there exist families of {\\em robust unobfuscatable functions} for which even approximate obfuscation is impossible. That is, obfuscation is impossible even if the obfuscated $\\tilde{f}$ only agrees with $f$ with probability slightly more than $\\frac{1}{2}$, on a uniformly sampled input (below $\\frac{1}{2}$-agreement, the function obfuscated by $\\tilde{f}$ is not uniquely defined). Additionally, we show that, assuming only one-way functions, we can rule out approximate obfuscation where $\\tilde{f}$ is not allowed to err, but may refuse to compute $f$ with probability close to $1$.

We then demonstrate the power of robust unobfuscatable functions by exhibiting new implications to resettable protocols that so far have been out of our reach. Concretely, we obtain a new non-black-box simulation technique that reduces the assumptions required for resettably-sound zero-knowledge protocols to {\\em one-way functions}, as well as reduce round-complexity. We also present a new simplified construction of simultaneously resettable zero-knowledge protocols that does not rely on collision-resistent hashing. Finally, we construct a three-message simultaneously resettable $\\WI$ {\\em argument of knowledge} (with a non-black-box knowledge extractor). Our constructions are based on a special kind of ``resettable slots\" that are useful for a non-black-box simulator, but not for a resetting prover.

16:17 [Pub][ePrint] Twisted Edwards-Form Elliptic Curve Cryptography for 8-bit AVR-based Sensor Nodes, by Dalin Chu and Johann Gro{\\ss}sch{\\\"a}dl and Zhe Liu

  Wireless Sensor Networks (WSNs) pose a number of unique security challenges that demand innovation in several areas including the design of cryptographic primitives and protocols. Despite recent progress, the efficient implementation of Elliptic Curve Cryptography (ECC) for WSNs is still a very active research topic and techniques to further reduce the time and energy cost of ECC are eagerly sought. This paper presents an optimized ECC implementation that we developed from scratch to comply with the severe resource constraints of 8-bit sensor nodes such as the MICAz and IRIS motes. Our ECC software uses Optimal Prime Fields (OPFs) as underlying algebraic structure and supports two different families of elliptic curves, namely Weierstra{\\ss}-form and twisted Edwards-form curves. Due to the combination of efficient field arithmetic and fast group operations, we achieve an execution time of $5.9 \\cdot 10^6$ clock

cycles for a full 160-bit scalar multiplication on an 8-bit ATmega128

microcontroller, which is 2.78 times faster than the widely-used TinyECC library. Our implementation also shows that the energy cost of ephemeral ECDH key exchange between two MICAz (or IRIS) motes amounts to only 38.7 mJ per mote (including radio communication). A mote with a standard AA battery pack could theoretically perform up to 174,278 ECDH key exchanges before running out of energy.

16:17 [Pub][ePrint] Time-memory Trade-offs for Near-collisions, by Gaƫtan Leurent

  In this work we consider generic algorithms to find near-collisions

for a hash function. If we consider only hash computations, it is

easy to compute a lower-bound for the complexity of near-collision

algorithms, and to build a matching algorithm. However, this

algorithm needs a lot of memory, and makes than 2^{n/2} memory

accesses. Recently, several algorithms have been proposed without

this memory requirement; they require more hash evaluations, but the

attack is actually more practical. They can be divided in two main

categories: some are based on truncation, and some are based on

covering codes.

In this paper, we give a new insight to the generic complexity of a

near-collision attack. First, we consider time-memory trade-offs for

truncation-based algorithms. For a practical implementation, it seems

reasonable to assume that some memory is available and we show that

taking advantage of this memory can significantly reduce the

complexity. Second, we show a new method combining truncation and

covering codes. The new algorithm is always at least as good as the

previous works, and often gives a significant improvement. We

illustrate our results by giving a 10-near collision for MD5: our

algorithm has a complexity of 2^45.4 using 1TB of memory while the

best previous

16:17 [Pub][ePrint] Non-Interactive Key Exchange, by Eduarda S.V. Freire and Dennis Hofheinz and Eike Kiltz and Kenneth G. Paterson

  Non-interactive key exchange (NIKE) is a fundamental but much-overlooked cryptographic primitive. It appears as a major contribution in the ground-breaking paper of Diffie and Hellman, but NIKE has remained largely unstudied since then. In this paper, we provide different security models for this primitive and explore the relationships between them. We then give constructions for secure NIKE in the Random Oracle Model based on the hardness of factoring and in the standard model based on the hardness of a variant of the decisional Bilinear Diffie Hellman Problem for asymmetric pairings. We also study the relationship between NIKE and public key encryption (PKE), showing that a secure NIKE scheme can be generically converted into an IND-CCA secure PKE scheme. This conversion also illustrates the fundamental nature of NIKE in public key cryptography.

16:17 [Pub][ePrint] Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond, by Shafi Goldwasser and Yael Kalai and Raluca Ada Popa and Vinod Vaikuntanathan and Nickolai Zeldovich

  Functional encryption is a powerful primitive: given an encryption

$\\Enc(x)$ of a value $x$ and a secret key $\\sk_f$ corresponding to a

circuit $f$, it enables efficient computation of $f(x)$ without revealing any additional information about $x$. Constructing functional encryption schemes with succinct ciphertexts that guarantee security for even a single secret key (for a general function $f$) is an important open problem with far reaching applications, which this paper addresses.

Our main result is a functional encryption scheme \\textit{for any general function $f$ of depth $d$, with succinct ciphertexts} whose size grows with the depth $d$ rather than the size of the circuit for $f$. We prove the security of our construction based on the intractability of the learning with error (LWE) problem. More generally, we show how to construct a functional encryption scheme

from \\textit{any} public-index predicate encryption scheme and fully homomorphic encryption scheme.

Previously, the only known constructions of functional encryption were either for specific inner product predicates, or for a weak form of functional encryption where the ciphertext size grows

with the size of the circuit for $f$.

We demonstrate the power of this result, by using it to construct a

\\textit{reusable circuit garbling scheme with input and circuit privacy}: an open problem that was studied extensively by the cryptographic community during the past 30 years since Yao\'s introduction of a one-time circuit garbling method in the mid 80\'s. Our scheme also leads to a new paradigm for general function obfuscation which we call token-based obfuscation. Furthermore, we show applications of our scheme to homomorphic encryption for Turing machines where the evaluation runs in input-specific time rather than worst case time, and to publicly verifiable and secret delegation.