International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. 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).

2013-11-03
19:17 [Pub][ePrint] Limits of Extractability Assumptions with Distributional Auxiliary Input, by Elette Boyle and Rafael Pass

  Extractability, or \"knowledge,\" assumptions (such as the \"knowledge-of-exponent\" assumption) have recently gained popularity in the cryptographic community--leading to the study of primitives such as extractable one-way functions, extractable hash functions, succinct non- interactive arguments of knowledge (SNARKs), and extractable obfuscation, and spurring the development of a wide spectrum of new applications relying on these primitives. For most of these applications, it is required that the extractability assumption holds even in the presence of attackers receiving some auxiliary information that is sampled from some fixed efficiently computable distribution Z.

We show that, assuming the existence of collision-resistant hash functions, there exists a pair of efficient distributions Z, Z\'; such that either:

o extractable one-way functions w.r.t. Z do not exist, or

o extractability obfuscations for Turing machines w.r.t. Z do not exist.

A corollary of this result shows that assuming existence of fully homomorphic encryption with decryption in NC1, there exist efficient distributions Z, Z\' such that either

o extractability obfuscations for NC1 w.r.t. Z do not exist, or

o SNARKs for NP w.r.t. Z\' do not exist.

To achieve our results, we develop a \"succinct punctured program\" technique, mirroring the powerful \"punctured program\" technique of Sahai and Waters (ePrint\'13), and present several other applications of this new technique.



19:17 [Pub][ePrint] Adaptive Witness Encryption and Asymmetric Password-based Cryptography, by Mihir Bellare and Viet Tung Hoang

  This paper defines adaptive soundness (AS) security for witness encryption and applies it to provide the first non-invasive schemes for asymmetric password-based encryption (A-PBE). A-PBE offers significant gains over classical, symmetric password-based encryption (S-PBE) in the face of attacks that compromise servers to recover hashed passwords. We also show by counter-example that the original soundness security (SS) requirement of GGSW does not suffice for the security of their own applications, and show that AS fills the gap.



19:17 [Pub][ePrint] Symmetric Digit Sets for Elliptic Curve Scalar Multiplication without Precomputation, by Clemens Heuberger and Michela Mazzoli

  We describe a method to perform scalar multiplication on two classes of

ordinary elliptic curves, namely $E: y^2 = x^3 + Ax$ in prime characteristic

$p\\equiv 1$ mod~4, and $E: y^2 = x^3 + B$ in prime characteristic $p\\equiv 1$

mod 3. On these curves, the 4-th and 6-th roots of unity act as (computationally

efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width-$w$-NAF (non-adjacent form) digit expansion of positive integers to the complex base of $\\tau$, where $\\tau$ is a zero of the characteristic polynomial $x^2 - tx + p$ of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo $\\tau$ in the endomorphism ring, whereby we construct a digit set consisting of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve.



19:17 [Pub][ePrint] How to Certify the Leakage of a Chip?, by Fran├žois Durvaux and Fran├žois-Xavier Standaert and Nicolas Veyrat-Charvillon

  Evaluating side-channel attacks and countermeasures requires determining the amount of information leaked by a target device. For this purpose, information extraction procedures published so far essentially combine a \"leakage model\" with a \"distinguisher\". Fair evaluations ideally require exploiting a perfect leakage model (i.e. exactly corresponding to the true leakage distribution) with a Bayesian distinguisher. But since such perfect models are generally unknown, density estimation techniques have to be used to approximate the leakage distribution. This raises the fundamental problem that all security evaluations are potentially biased by both estimation and assumption errors. Hence, the best that we can hope is to be aware of these errors. In this paper, we provide and implement methodological tools to solve this issue. Namely, we show how sound statistical techniques allow both quantifying the leakage of a chip, and certifying that the amount of information extracted is close to the maximum value that would be obtained with a perfect model.



19:17 [Pub][ePrint] A reduction of semigroup DLP to classic DLP, by Matan Banin and Boaz Tsaban

  We present a polynomial-time reduction of the discrete logarithm problem in any periodic (a.k.a. torsion)

semigroup (SGDLP) to the same problem in a subgroup of the same semigroup.

It follows that SGDLP can be solved in polynomial time by quantum computers, and that

SGDLP has subexponential algorithms whenever the classic DLP in the corresponding groups has subexponential algorithms.



19:17 [Pub][ePrint] Key Derivation Without Entropy Waste, by Yevgeniy Dodis and Krzysztof Pietrzak and Daniel Wichs

  We revisit the classical problem of converting an imperfect source of randomness into a usable cryptographic key. Assume that we have some cryptographic application $P$ that expects a uniformly random $m$-bit key $R$ and ensures that the best attack (in some complexity class) against $P(R)$ has success probability at most $\\delta$. Our goal is to design a key-derivation function (KDF) $h$ that converts any random source $X$ of min-entropy $k$ into a sufficiently ``good\'\' key $h(X)$,

guaranteeing that $P(h(X))$ has comparable security $\\delta\'$ which is `close\' to $\\delta$.

Seeded randomness extractors provide a generic way to solve this problem for \\emph{all} applications $P$, with resulting security $\\delta\' = O(\\delta)$, provided that we start with entropy $k\\ge m+2\\logdel-O(1)$. By a result of Radhakrishnan and Ta-Shma, this bound on $k$ (called the ``RT-bound\'\') is also known to be tight in general. Unfortunately, in many situations the loss of $2\\logdel$ bits of entropy is unacceptable. This motivates the study KDFs with less entropy waste by placing some restrictions on the source $X$ or the application $P$.

In this work we obtain the following new positive and negative results in this regard:

- Efficient samplability of the source $X$ does not help beat the RT-bound for general applications. This resolves the SRT (samplable RT) conjecture of Dachman-Soled et al.~\\cite{DGKM12} in the affirmative, and also shows that the existence of computationally-secure extractors beating the RT-bound implies the existence of one-way functions.

- We continue in the line of work initiated by Barak et al. \\cite{BDK+11} and construct new information-theoretic KDFs which beat the RT-bound for large but restricted classes of applications. Specifically, we design efficient KDFs that work for all unpredictability applications $P$ (e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extract \\emph{all} of the entropy $k = m$ with a very modest security loss $\\delta\'=O(\\delta\\cdot \\log (1/\\delta))$, or alternatively, (2) achieve essentially optimal security $\\delta\' = O(\\delta)$ with a very modest entropy loss $k \\ge m+\\log\\log(1/\\delta)$. In comparison, the best prior results from \\cite{BDK+11} for this class of applications would only guarantee $\\delta\'=O(\\sqrt{\\delta})$ when $k=m$, and would need $k\\ge m+\\logdel$ to get $\\delta\'=O(\\delta)$.

- The weaker bounds of \\cite{BDK+11} hold for a larger class of so-called ``square-friendly\'\' applications (which includes all unpredictability, but also some important indistinguishability, applications). Unfortunately, we show that these weaker bounds are tight for the larger class of applications.

- We abstract out a clean, information-theoretic notion of $(k,\\delta,\\delta\')$-unpredictability extractors, which guarantee ``induced\'\' security $\\delta\'$ for any $\\delta$-secure unpredictability application $P$, and characterize the parameters achievable for such unpredictability extractors. Of independent interest, we also relate this notion to the previously-known notion of (min-entropy) condensers, and improve the state-of-the-art parameters for such condensers.



19:17 [Pub][ePrint] Efficient Statistical Zero-Knowledge Authentication Protocols for Smart Cards Secure Against Active \\& Concurrent Quantum Attacks, by Mohammad Sadeq Dousti and Rasool Jalili

  We demonstrate how to construct statistical zero-knowledge authentication protocols for smart cards based on general assumptions. The main protocol is only secure against active attacks, but we present a modification based on trapdoor commitments which can resist concurrent attacks as well. Both protocols are instantiated using lattice-based constructs, which are secure against quantum attacks. We illustrate the practicality of our protocols on smart cards in terms of storage, computation, communication, and round complexity, and it is shown that our protocols are superior to known lattice-based zero-knowledge protocols in these aspects.



19:17 [Pub][ePrint] An Approach to Reduce Storage for Homomorphic Computations, by Jung Hee Cheon and Jinsu Kim

  We introduce a hybrid homomorphic encryption by combining public key encryption (PKE) and somewhat homomorphic encryption (SHE) to reduce storage for most applications of somewhat or fully homomorphic encryption (FHE). In this model, one encrypts messages with a PKE and computes on encrypted data using a SHE or a FHE after homomorphic decryption.

To obtain efficient homomorphic decryption, our hybrid schemes is constructed by combining IND-CPA PKE schemes without complicated message paddings with SHE schemes with large integer message space. Furthermore, we remark that if the underlying PKE is multiplicative on a domain closed under addition and multiplication, this scheme has an important advantage that one can evaluate a polynomial of arbitrary degree without recryption.

We propose such a scheme by concatenating ElGamal and Goldwasser-Micali scheme over a ring $\\Z_N$ for a composite integer $N$ whose message space is $\\Z_N^\\times$.

To be used in practical applications, homomorphic decryption of the base PKE is too expensive. We accelerate the homomorphic evaluation of the decryption by introducing a method to reduce the degree of exponentiation circuit at the cost of additional public keys. Using same technique, we give an efficient solution to the open problem~\\cite{KLYC13} partially.

As an independent interest, we obtain another generic conversion method from private key SHE to public key SHE. Differently from Rothblum~\\cite{RothTCC11}, it is free to choose the message space of SHE.



19:17 [Pub][ePrint] Ambiguous One-Move Nominative Signature Without Random Oracles, by Dennis Y. W. Liu and Duncan S. Wong and Qiong Huang

  Nominative Signature is a useful tool in situations where a signature has to be created jointly by two parties, a nominator (signer) and a nominee (user), while only the user can verify and prove to a third party about the validity of the signature. In this paper, we study the existing security models of nominative signature and show that though the existing models have captured the essential security requirements of nominative signature in a strong sense, especially on the unforgeability against malicious signers/users and invisibility, they are yet to capture a requirement regarding the privacy of the signer and the user, and this requirement has been one of the original ones since the notion of nominative signature was first introduced. In particular, we show that it is possible to build a highly efficient nominative signature scheme which can be proven secure in the existing security models, while in practice it is obvious to find out from the component(s) of a nominative signature on whether a particular signer or user has involved in the signature generation, which may not be desirable in some actual applications. We therefore propose an enhanced security property, named \"Ambiguity\", and also propose a new \\emph{one-move} nominative scheme for fulfilling this new security requirement without random oracles, and among the various types of nominative signature, one-move is the most efficient type. Furthermore, this new scheme is at least 33% more efficient during signature generation and 17% shorter in signature size when compared with the existing one-move signature schemes without random oracles even that the existing ones in the literature may not satisfy this new Ambiguity requirement.



19:17 [Pub][ePrint] PUF-Based RFID Authentication Secure and Private under Complete Memory Leakage, by Daisuke Moriyama and Shin\'ichiro Matsuo and Moti Yung

  RFID tags are getting their presence noticeable on smartphones,

credit cards, toll payment devices, and other objects. They are

expected to become an important tool for e-commerce, logistics,

point-of-sale transactions, and so on, representing ``things\'\' and

``human holding things\'\' in transactions. Since a huge amount of tags are expected to be needed to be attached to various ``objects,\'\' a low-cost tag manufacturing is necessary. Thus, it is hard to imagine they will implement hardware protection mechanisms (like co-processor, TPMs). Therefore, side-channel (leakage) attacks are a critical threat. Another threat that is well known in the RFID topic is tag tracing and violation of privacy.

In this paper, we consider physically unclonable functions (PUFs) as tamper resilient building block and propose security model with memory leaking adversary, trying to violate security and privacy of tags (we note that PUFs are structure-less and there is a hope they can be put on top of RFID chips more so than TPMs). We then design the first provably secure and provably private RFID authentication protocol withstanding information leakage from the non-volatile memory of the tag, and provides the two properties of: (1) security against impersonation, and (2) privacy protection against tag tracing.



19:17 [Pub][ePrint] Cryptanalysis of Zorro, by Jian Guo and Ivica Nikolic and Thomas Peyrin and Lei Wang

  At CHES 2013 was presented a new block cipher called Zorro. Although it uses only 4 S-boxes per round, the designers showed the resistance of the cipher against various attacks, and concluded the cipher has a large security margin. In this paper, we give a key recovery attack on the full cipher in the single-key model that works for $2^{64}$ out of $2^{128}$ keys. Our analysis is based precisely on the fact that the non-linear layer has only 4 S-boxes. We exploit this twice in a two-stage attack: first, we show that Zorro has an equivalent description that does not have constants in the rounds, and then, we launch an internal differential attack on the newly described cipher. With computer verifications we confirm the correctness of the analysis.

Our attack is the first to use internal differentials for block ciphers, thus we adapt Daemen\'s attack on Even-Mansour construction

to the case of internal differentials (instead of differentials), which allows us to recovery to full key.

This work provides as well insights on alternative descriptions of general Zorro-type ciphers (incomplete non-linear layers),

the importance of well chosen constants, and the advantages of Daemen\'s attack.