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-10-28
21:17 [Pub][ePrint]

Threshold Implementations provide provable security against first-order power analysis attacks for hardware and software implementations. Like masking, the approach relies on secret sharing but it differs in the implementation of logic functions. At \\textsc{Eurocrypt} 2011 Moradi et al. published the to date most compact Threshold Implementation of AES-128 encryption. Their work shows that the number of required random bits may be an additional evaluation criterion, next to area and speed. We present a new Threshold Implementation of AES-128 encryption that is 18\\% smaller, 7.5\\% faster and that requires 8\\% less random bits than the implementation from \\textsc{Eurocrypt} 2011. In addition, we provide results of a practical security evaluation based on real power traces in adversary-friendly conditions. They confirm the first-order attack resistance of our implementation and show good resistance against higher-order attacks.

21:17 [Pub][ePrint]

In 2012, Alagheband and Aref presented a dynamic and secure key manage

ment model for hierarchical heterogeneous sensor networks. They proposed a signcryption algorithm which is the main building block in their key management model. They proved the algorithm is as strong as the elliptical curve discrete logarithm problem. In this work,

we study the security of their signcryption algorithm. It is regretful that we found their algorithm is insecure. The adversary can impersonate the base station by sending forged messages to the cluster leaders after capturing the signcrypted messages. Hence, the key management model proposed by them is insecure. Then, we propose an improved signcryption algorithm to fix this weakness.

21:17 [Pub][ePrint]

We show that it is possible to upgrade an obfuscator for a weak complexity class $\\weak$ into an obfuscator for arbitrary polynomial size circuits, assuming that the class $\\weak$ can compute pseudorandom functions. Specifically, under standard intractability assumptions (e.g., hardness of factoring, Decisional Diffie--Hellman, or Learning with Errors), the existence of obfuscators for $\\NC^1$ or even $\\TC^0$ implies the existence of general-purpose obfuscators for $\\classP$. Previously, such a bootstrapping procedure was known to exist under the assumption that there exists a fully-homomorphic encryption whose decryption algorithm can be computed in $\\weak$. Our reduction works with respect to virtual black-box obfuscators and relativizes to ideal models.

21:17 [Pub][ePrint]

We describe a new algorithm for masking look-up tables of block-ciphers at any order, as a countermeasure against side-channel attacks. Our technique is a generalization of the classical randomized table countermeasure against first-order attacks. We prove the security of our new algorithm against t-th order attacks in the usual Ishai-Sahai-Wagner model from Crypto 2003; we also improve the bound on the number of shares from n>=4t+1 to n>= 2t+1 for an adversary who can adaptively move its probes between successive executions.

Our algorithm has the same time complexity O(n^2) as the Rivain-Prouff algorithm for AES, and its extension by Carlet et al. to any look-up table. In practice for AES our algorithm is less efficient than Rivain-Prouff, which can take advantage of the special algebraic structure

of the AES Sbox; however for DES our algorithm performs slightly better.

21:17 [Pub][ePrint]

We show that if there exist indistinguishability obfuscators for a certain class C of circuits then there do not exist independent-auxiliary-input virtual-black-box (VBB) obfuscators for any family of circuits that compute a pseudo-entropic function. A function f_k is pseudo-entropic if it is hard, given oracle access to f_k but without asking explicitly on a value x, to distinguish f_k(x) from a random variable with some real entropy.

This strengthens the bound of Goldwasser and Kalai [FOCS 05, ePrint 13] that rules out dependent-auxiliary-input VBB obfuscation for the same set of circuit families, assuming inditinguishability obfuscators for another class, C\', of circuits. That is, while they only rule out the case where the adversary and the simulator obtain auxiliary information that depends on the actual (secret) obfuscated function, we rule out even the case where the auxiliary input depends only

on the (public) family of programs.

21:17 [Pub][ePrint]

Non-malleable codes, defined by Dziembowski, Pietrzak and Wichs (ICS \'10), provide roughly the following guarantee: if a codeword $c$ encoding some message $x$ is tampered to $c\' = f(c)$ such that $c\' \\neq c$, then the tampered message $x\'$ contained in $c\'$ reveals no information about $x$. Non-malleable codes have applications to immunizing cryptosystems against tampering attacks and related-key attacks.

One cannot have an efficient non-malleable code that protects against all efficient tampering functions $f$. However, in this work we show the next best thing\'\': for any polynomial bound $s$ given a-priori, there is an efficient non-malleable code that protects against all tampering functions $f$ computable by a circuit of size $s$. More generally, for any family of tampering functions $\\F$ of size $|\\F| \\leq 2^{s}$, there is an efficient non-malleable code that protects against all $f \\in \\F$. The rate of our codes, defined as the ratio of message to codeword size, approaches $1$. Our results are information-theoretic and our main proof technique relies on a careful probabilistic method argument using limited independence. As a result, we get an efficiently samplable family of efficient codes, such that a random member of the family is non-malleable with overwhelming probability. Alternatively, we can view the result as providing an efficient non-malleable code in the common reference string\'\' (CRS) model.

We also introduce a new notion of non-malleable key derivation, which uses randomness $x$ to derive a secret key $y = h(x)$ in such a way that, even if $x$ is tampered to a different value $x\' = f(x)$, the derived key $y\' = h(x\')$ does not reveal any information about $y$. Our results for non-malleable key derivation are analogous to those for non-malleable codes.

As a useful tool in our analysis, we rely on the notion of leakage-resilient storage\'\' of Davi, Dziembowski and Venturi (SCN \'10) and, as a result of independent interest, we also significantly improve on the parameters of such schemes.

2013-10-24
18:17 [Pub][ePrint]

Bideniable encryption allows both sender and receiver in a public-key setting to simultaneously claim that a different message of their choice was transmitted, and support this claim by a good-looking encryption and key-generation randomness, respectively. A weaker version with two variants of algorithms is called flexible or multi-distributional deniability, a stronger one-algorithm version is called full deniability. Bendlin et al. (ASIACRYPT 2011) showed that certain kinds of fully-deniable schemes are constructible using corresponding flexible schemes. In this paper, we show that their construction in the bideniable case has a flaw, and we provide a fixed scheme. Our construction relies on a deterministic subset matching algorithm that assigns to each nonempty subset of a finite set its proper subset reduced by exactly one element. Although this algorithm is crucial in our construction, it may also be of independent interest.

18:17 [Pub][ePrint]

In this paper, we present a heuristic algorithm for solving exact, as

well as approximate, SVP and CVP for lattices. This algorithm is based

on a new approach which is very different from and complementary to the

sieving technique. This new approach frees us from the kissing number bound and allows us to solve SVP and CVP in lattices of dimension $n$ in time $2^{0.377n}$ using memory $2^{0.292n}$. The key idea is to no longer work with a single lattice but to move the problems around in a tower of related lattices. We initiate the algorithm by sampling very short vectors in a dense overlattice of the original lattice that admits a quasi-orthonormal basis and hence an efficient enumeration of vectors of bounded norm. Taking sums of vectors in the sample, we construct short vectors in the next lattice of our tower. Repeating this, we climb all the way to the top of the tower and finally obtain solution vector(s) in the initial lattice as a sum of vectors of the overlattice just below it. The complexity analysis relies on the Gaussian heuristic. This heuristic is backed by experiments in low and high dimensions that closely reflect these estimates when solving hard lattice problems in the average case.

18:17 [Pub][ePrint]

Protocols for the protected execution of programs, like those based on a hardware root of trust, will become of fundamental importance for computer security. In parallel to such protocols, there is therefore a need to develop models and tools that allow formal specification and automated verification of the desired security properties. Still, current protocols lack realistic models and automated proofs of security. This is due to several challenges that we address in this paper.

We consider the classical setting of applied pi-calculus and ProVerif, that we enrich with several generic models that allow verification of protocols designed for a given computing platform. Our contributions include models for specifying platform states and for dynamically loading and executing protected programs. We also propose a new method to make ProVerif terminate on a challenging search space - the one obtained by allowing an unbounded number of extensions and resets for the platform configuration registers of the TPM.

We illustrate our methods with the case study of a protocol for a dynamic root of trust (based on a TPM), which includes dynamic loading, measurement and protected execution of programs. We prove automatically with ProVerif that code integrity and secrecy of sealed data hold for the considered protocol.

18:17 [Pub][ePrint]

A fundamental question about (reusable) circuit garbling schemes is: how small can the garbled circuit be? Our main result is a reusable garbling scheme which produces garbled circuits that are the same size as the original circuit plus an additive poly(secp) bits, where secp is the security parameter. Save the additive poly(secp) factor, this is the best one could hope for. In contrast, all previous constructions of even single-use garbled circuits incurred a multiplicative poly(secp) blowup.

Our techniques result in constructions of attribute-based and (single key secure) functional encryption schemes where the secret key of a circuit C consists of C itself, plus poly(secp) additional bits. All of these constructions are based on the subexponential hardness of the learning with errors problem.

We also study the dual question of how short the garbled inputs can be, relative to the original input. We demonstrate a (different) reusable circuit garbling scheme, based on multilinear maps, where the size of the garbled input is the same as that of the original input, plus a poly(secp) factor. This improves on the result of Applebaum, Ishai, Kushilevitz and Waters (CRYPTO 2013)

who showed such a result for single-use garbling. Similar to the above, this also results in attribute-based and (single key secure) functional encryption schemes where the size of the ciphertext encrypting an input x is the same as that of x, plus poly(secp) additional bits.

18:17 [Pub][ePrint]

In many pairing-based protocols more than one party is involved, and some or all of them may be required to calculate pairings.

Commonly it is the pairing calculation itself which takes most time.

However some parties may be better equipped than others in terms of computational power. By exploiting the bilinearity

property there are established ways to off-load the pairing calculation to an untrusted third party. Here we observe

that this third party may in fact be one of the other participants in the protocol. In this way a protocol may be unbalanced\'\'

by shifting the computational load from one participant to another, which may be an advantage in some circumstances.

In this paper we focus on some simple key exchange protocols.

Surprisingly we find that unbalancing a key exchange protocol can endow it with the property of full forward secrecy, even if it did not originally possess it.

Finally we show that a new condition on the choice of pairing-friendly curve can help to minimize the overall computation.