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

2015-01-23
16:17 [Pub][ePrint] Non-committing encryption from $\\Phi$-hiding, by Brett Hemenway and Rafail Ostrovsky and Alon Rosen

  A multiparty computation protocol is said to be adaptively secure if it retains its security even in the presence of an adversary who can corrupt

participants as the protocol proceeds. This is in contrast to the static corruption model where the adversary is forced to choose which participants

to corrupt before the protocol begins.

A central tool for constructing adaptively secure protocols is non-committing encryption (Canetti, Feige, Goldreich and Naor, STOC \'96). The

original protocol of Canetti et al. had ciphertext expansion that was quadratic in the security parameter, and prior to this work, the

best known constructions had ciphertext expansion that was linear in the security parameter.

In this work, we present the first non-committing encryption scheme that achieves ciphertext expansion that is logarithmic in the message length.

Our construction has optimal round complexity (2-rounds), where (just as in all previous constructions) the first message consists of a public-key

of size $\\tilde{\\bigoh}(n \\secpar)$ where $n$ is the message length and $\\secpar$ is the security parameter. The second message consists

of a ciphertext of size $\\bigoh( n \\log n + \\secpar )$. The security of our scheme is proved based on the $\\Phi$-hiding problem.



16:17 [Pub][ePrint] Richer Efficiency/Security Trade-offs in 2PC, by Vladimir Kolesnikov and Payman Mohassel and Ben Riva and Mike Rosulek

  The dual-execution protocol of Mohassel \\& Franklin (PKC 2006) is a highly efficient (each party garbling only one circuit) 2PC protocol that achieves malicious security apart from leaking an {\\em arbitrary, adversarially-chosen} predicate about the honest party\'s input. We present two practical and orthogonal approaches to improve the security of the dual-execution technique.

First, we show how to greatly restrict the predicate that an adversary can learn in the protocol, to a natural notion of ``only computation leaks\'\'-style leakage. Along the way, we identify a natural security property of garbled circuits called {\\em property-enforcing} that may be of independent interest.

Second, we address a complementary direction of reducing the probability that the leakage occurs. We propose a new dual-execution protocol --- with a very light cheating-detection phase and each party garbling $s+1$ circuits --- in which a cheating party learns a bit with probability only $2^{-s}$. Our concrete measurements show approximately $35\\%$ reduction in communication for the AES circuit, compared to the best combination of state of the art techniques for achieving the same security notion.

Combining the two results, we achieve a rich continuum of practical trade-offs between efficiency \\& security, connecting the covert, dual-execution and full-malicious guarantees.



16:17 [Pub][ePrint] Better Algorithms for LWE and LWR, by Alexandre Duc and Florian Tramèr and Serge Vaudenay

  The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so that concrete parameters can be proposed. The BKW algorithm was proposed by Blum et al. as an algorithm to solve the Learning Parity with Noise problem (LPN), a subproblem of LWE. This algorithm was then adapted to LWE by Albrecht et al.

In this paper, we improve the algorithm proposed by Albrecht et al. by using multidimensional Fourier transforms. Our algorithm is, to the best of our knowledge, the fastest LWE solving algorithm. Compared to the work of Albrecht et al. we greatly simplify the analysis, getting rid of integrals which were hard to evaluate in the final complexity. We also remove some heuristics on rounded Gaussians. Some of our results on rounded Gaussians might be of independent interest. Moreover, we also analyze algorithms solving LWE with discrete Gaussian noise.

Finally, we apply the same algorithm to the Learning With Rounding problem (LWR) for prime q, a deterministic counterpart to LWE. This problem is getting more and more attention and is used, for instance, to design pseudorandom functions. To the best of our knowledge, our algorithm is the first algorithm applied directly to LWR. Furthermore, the analysis of LWR contains some technical results of independent interest.





2015-01-22
19:17 [Pub][ePrint] Linearly Homomorphic Encryption Scheme from DDH, by Guilhem Castagnos and Fabien Laguillaumie

  We design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime p and which supports an unbounded number of additions modulo p from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime p can be scaled to fit the application needs.



19:17 [Pub][ePrint] On Obfuscation with Random Oracles, by Ran Canetti and Yael Tauman Kalai and Omer Paneth

  Assuming trapdoor permutations, we show that there exist function families that cannot be VBB-obfuscated even if both the obfuscator and the obfuscated program have access to a random oracle. Specifically, these families are the robust unobfuscatable families of [Bitansky-Paneth, STOC 13].

Our result stands in contrast to the general VBB obfuscation algorithms in more structured idealized models where the oracle preserves certain algebraic homomorphisms [Canetti-Vaikuntanathan, ePrint 13; Brakerski-Rothblum, TCC 14; Barak et al., Eurocrypt 14].



19:17 [Pub][ePrint] On Solving Lpn using BKW and Variants, by Sonia Bogos and Florian Tramer and Serge Vaudenay

  The Learning Parity with Noise problem (LPN) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive analysis of the existing LPN solving algorithms, both for the general case and for the sparse secret scenario. In practice, the LPN-based cryptographic constructions use as a reference the security parameters proposed by Levieil and Fouque. But, for these parameters, there remains a gap between the theoretical analysis and the practical complexities of the algorithms we consider. The new theoretical analysis in this paper provides tighter bounds on the complexity of LPN solving algorithms and narrows this gap between theory and practice. We show that for a sparse secret there is another algorithm that outperforms BKW and its variants. Following from our results, we further propose practical parameters for different security levels.



19:17 [Pub][ePrint] Stretching Groth-Sahai: NIZK Proofs of Partial Satisfiability, by Carla Ràfols

  Groth, Ostrovsky and Sahai constructed a non-interactive Zap for NP-languages by observing that

the common reference string of their proof system for circuit satisfiability admits what they call correlated key generation.

The latter means that it is possible to create from scratch two common reference strings in such a way that it can be publicly verified that at least one of them guarantees perfect soundness while

it is computationally infeasible to tell which one. Their technique also implies that it is possible to have NIWI Groth-Sahai proofs for certain types of equations over bilinear groups in the plain model. We extend the result of Groth, Ostrovsky and Sahai in several directions. Given as input some predicate $P$ computable by some monotone span program over a finite field, we show how to generate a set of common reference strings in such a way that it can be publicly verified that the subset of them which guarantees perfect soundness is accepted by the span program. We give several different flavors of the technique suitable for different applications scenarios and different equation types. We use this to stretch the expressivity of Groth-Sahai proofs and construct NIZK proofs of partial satisfiability of sets of equations in a bilinear group and more efficient Groth-Sahai NIWI proofs without common reference string for a larger class of equation types. Finally, we apply our results to significantly reduce the size of the signatures of the ring signature scheme of Chandran, Groth and Sahai or to have a more efficient proof in the standard model that a commitment opens to an element of a public list.



19:17 [Pub][ePrint] Improved Meet-in-the-Middle Distinguisher on Feistel Schemes, by Li Lin, Wenling Wu

  Improved meet-in-the-middle cryptanalysis with efficient tabulation technique has been shown to be a very powerful form of cryptanalysis against SPN block ciphers. However, few literatures show the effectiveness of this cryptanalysis against Balanced-Feistel-Networks (BFN) and Generalized-Feistel-Networks (GFN) ciphers due to the stagger of affected trail and special truncated differential trail. In this paper, we describe a versatile and powerful algorithm for searching the best improved meet-in-the-middle distinguisher with efficient tabulation technique on word-oriented BFN and GFN block ciphers, which is based on recursion and greedy algorithm. To demonstrate the usefulness of our approach, we show key recovery attacks on 14/16-round CLEFIA-192/256 which are the best attacks. We also propose key recovery attacks on 13/15-round Camellia-192/256 (without $FL/FL^{-1}$).



19:17 [Pub][ePrint] Interactive Message-Locked Encryption and Secure Deduplication, by Mihir Bellare and Sriram Keelveedhi

  This paper considers the problem of secure storage of outsourced data in a way that permits deduplication. We are for the first time able to provide privacy for messages that are both correlated and dependent on the public system parameters. The new ingredient that makes this possible is interaction. We extend the message-locked encryption (MLE) primitive of prior work to interactive message-locked encryption (iMLE) where upload and download are protocols. Our scheme, providing security for messages that are not only correlated but allowed to depend on the public system parameters, is in the standard model. We explain that interaction is not an extra assumption in practice because full, existing deduplication systems are already interactive.



19:17 [Pub][ePrint] Tight Bounds for Keyed Sponges and Truncated CBC, by Peter Gazi and Krzysztof Pietrzak and Stefano Tessaro

  We prove (nearly) tight bounds on the concrete PRF-security of

two constructions of message-authentication codes (MACs):

(1) The truncated CBC-MAC construction, which operates as

plain CBC-MAC (without prefix-free encoding of messages), but

only returns a subset of the output bits.

(2) The MAC derived from the sponge hash-function family by

pre-pending a key to the message, which is the de-facto standard

method for SHA-3-based message authentication.

The tight analysis of keyed sponges is our main result

and we see this as an important step in validating SHA-3-based

authentication before its deployment. Still, our analysis crucially

relies on the one for truncated CBC as an intermediate step of

independent interest. Indeed, no previous security analysis of

truncated CBC was known, whereas only significantly weaker bounds have

been proved for keyed sponges following different approaches.

Our bounds are tight for the most relevant ranges of parameters, i.e.,

for messages of length (roughly) $\\ell \\le \\min\\{2^{n/4},2^r\\}$

blocks, where $n$ is the state size and $r$ is the desired output

length; and for $q \\ge \\ell$ queries. Our proofs rely on a novel

application of Patarin\'s H-coefficient method to iterated MAC

constructions.





2015-01-20
10:17 [Pub][ePrint] Group Signature with Deniability: How to Disavow a Signature, by Ai Ishida, Keita Emura, Goichiro Hanaoka, Yusuke Sakai, and Keisuke Tanaka

  Group signature is a class of digital signatures with enhanced privacy. By using this type of signature, a user can prove membership of a specific group without revealing his identity, but in the case of a dispute, for a given signature, an authority can expose the identity of its signer. However, in some situations wherein it is necessary to only know whether a specified user is the signer of the given signature, the naive use of a group signature may be problematic since if the specified user is NOT the actual signer, then the identity of the actual signer will be exposed.

In this paper, inspired by this problem, we propose the notion of a deniable group signature, where with respect to a signature and a user, the opener can issue a proof that the opening result of the signature is NOT the specified user without revealing the actual signer. We also describe a fairly practical construction by extending the Groth group signature scheme (ASIACRYPT 2007). In particular, a denial proof in our scheme consists of 96 group elements, which is about twice the size of a signature in the Groth scheme. The proposed scheme is provably secure under the same assumptions as those of the Groth scheme.