International Association for Cryptologic Research

# IACR News Central

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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.