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

22:17 [Pub][ePrint] Differential Indistinguishability for Cryptographic Primitives with Imperfect Randomness, by Michael Backes and Aniket Kate and Sebastian Meiser and Tim Ruffing

  Indistinguishability-based definitions of cryptographic primitives such as encryption, commitments, and zero-knowledge proofs are proven to be impossible to realize in scenarios where parties only have access to non-extractable sources of randomness (Dodis et al., FOCS 2004). In this work we demonstrate that it is, nevertheless, possible to quantify this secrecy loss for non-extractable sources such as the (well-studied) Santha-Vazirani (SV) sources. In particular, to establish meaningful security guarantees in scenarios where such imperfect randomness sources are used, we define and study differential indistinguishability, a generalization of indistinguishability inspired by the notion of differential privacy.

We analyze strengths and weaknesses of differential indistinguishability both individually as well as under composition, and we interpret the resulting differential security guarantees for encryption, commitments, and zero-knowledge proofs.

Surprisingly, indistinguishability with uniform randomness carries over to differential indistinguishability with SV randomness: We show that all primitives that are secure under a traditional indistinguishibility-based definition are differentially secure when they use (a bounded amount of) SV randomness instead of uniform randomness.

22:17 [Pub][ePrint] Riding the Saddle Point: asymptotics of the capacity-achieving simple decoder for bias-based traitor tracing, by Sarah Ibrahimi and Boris Skoric and Jan-Jaap Oosterwijk

  We study the asymptotic-capacity-achieving score function that was recently proposed by Oosterwijk et al. for bias-based traitor tracing codes. For the bias function we choose the Dirichlet distribution with a cutoff. Using Bernstein\'s inequality and Bennett\'s inequality, we upper bound the false positive and false negative error probabilities. From these bounds we derive sufficient conditions for the scheme parameters. We solve these conditions in the limit of large coalition size $c_0$ and obtain asymptotic solutions for the cutoff, the sufficient code length and the corresponding accusation threshold.

The code length converges to its asymptote approximately as $c_0^{-1/2}$, which is faster than the $c_0^{-1/3}$ of Tardos\' score function.

22:17 [Pub][ePrint] Formal Analysis of CRT-RSA Vigilant\'s Countermeasure Against the BellCoRe Attack, by Pablo Rauzy and Sylvain Guilley

  In our paper at PROOFS 2013, we formally studied a few known countermeasures to protect CRT-RSA against the BellCoRe fault injection attack. However, we left Vigilant\'s countermeasure and its alleged repaired version by Coron et al. as future work, because the arithmetical framework of our tool was not sufficiently powerful. In this paper we bridge this gap and then use the same methodology to formally study both versions of the countermeasure. We obtain surprising results, which we believe demonstrate the importance of formal analysis in the field of implementation security. Indeed, the original version of Vigilant\'s countermeasure is actually broken, but not as much as Coron et al. thought it was. As a consequence, the repaired version they proposed can be simplified. It can actually be simplified even further as two of the nine modular verifications happen to be unnecessary. Fortunately, we could formally prove the simplified repaired version to be resistant to the BellCoRe attack, which was considered a \"challenging issue\" by the authors of the countermeasure themselves.

22:17 [Pub][ePrint] Constant-Round Black-Box Construction of Composable Multi-Party Computation Protocol, by Susumu Kiyoshima and Yoshifumi Manabe and Tatsuaki Okamoto

  We present the first general MPC protocol that satisfies the following: (1) the construction is black-box, (2) the protocol is universally composable in the plain model, and (3) the number of rounds is constant. The security of our protocol is proven in angel-based UC security under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries and constant-round semi-honest oblivious transfer protocols that are secure against quasi-polynomial-time adversaries. We obtain the MPC protocol by constructing a constant-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries. To justify the use of such a sub-exponential hardness assumption in obtaining our constant-round CCA-secure commitment scheme, we show that if black-box reductions are used, there does not exist any constant-round CCA-secure commitment scheme under any falsifiable polynomial-time hardness assumptions.

22:17 [Pub][ePrint] A Note on Bilinear Groups of a Large Composite Order, by Zhengjun Cao and Lihua Liu

  We remark that the structure of bilinear groups of a large composite order(at least 1024 bits) could make group operation inefficient and lose the advantages of elliptic curve cryptography which gained mainly from smaller parameter size. As of 2013, the longest parameter recommended by NIST for elliptic curves has 571 bits.

From the practical point of view, such an algebraic structure is unlikely applicable to cryptographic schemes.

22:17 [Pub][ePrint] Multi-ciphersuite security and the SSH protocol, by Benjamin Dowling and Florian Giesen and Florian Kohlar and Jörg Schwenk and Douglas Stebila

  Real-world cryptographic protocols, such as the Transport Layer Security (TLS) and Secure Shell (SSH) protocols, support the negotiation of different combinations of cryptographic algorithms, often known as ciphersuites. An individual ciphersuite can be modelled as an authenticated and confidential channel establishment (ACCE) protocol, and recently all widely deployed TLS ciphersuites have been individually proven ACCE-secure. In practice, users often re-use long-term keys across ciphersuites, for example using the same digital signature key in two different signed Diffie--Hellman (DH) ciphersuites. Recently, a cross-ciphersuite attack on TLS was discovered in which a signed elliptic curve DH structure can be interpreted as a signed finite-field DH structure, breaking authentication. Thus, ACCE security of individual ciphersuites does not generically imply collective security when long-term keys are re-used across ciphersuites.

We investigate the security of multi-ciphersuite protocols with re-used long-term keys. We show how to \"open\" the ACCE definition slightly so that, after each ciphersuites has been proven secure individually, they can then be used together in a secure multi-ciphersuite protocol, even when long-term keys are re-used across ciphersuites, provided the ciphersuites\' messages satisfy an independence property. We apply our definitions and composition theorem to the SSH protocol, showing that signed Diffie--Hellman SSH ciphersuites are individually ACCE-secure; they also satisfy the preconditions of our composition theorem, and thus SSH is multi-ciphersuite-secure even with re-use of long-term keys.

22:17 [Pub][ePrint] RDAS: A Symmetric Key Scheme for Authenticated Query Processing in Outsourced Databases, by Lil Maria Rodriguez-Henriquez and Debrup Chakraborty

  In this paper we address the problem of authenticated query processing in outsourced databases.

An authenticated query processing mechanism allows a client to verify the validity of the query responses that it gets from an untrusted and remote server, who stores the client\'s database

on its behalf.

We introduce a general framework called RDAS for the problem of authenticated query processing, and define the

security goals for this task in line with concrete provable security. We propose several schemes which enable

a client to verify both the completeness and correctness of the query responses of a server. All the schemes follow

the proposed framework and are provably secure in terms of the proposed security definition. The novelty of the proposed schemes

is that they use bitmap indexes as a main component for providing authentication. Bitmap indexes have recently seen

lot of applications for accelerated query processing and many commercial databases implement such indexes. Bitmaps have not been

previously used for a security goal. We show that the proposed schemes can match in both

functionality and efficiency compared to the existing schemes. We also implement the schemes on a real database and provide extensive

experimental studies on the schemes

22:17 [Pub][ePrint] Iterated group products and leakage resilience against NC^1, by Eric Miles

  We show that if NC^1 \\neq L, then for every element g of the alternating group A_t, circuits of depth O(log t) cannot distinguish between a uniform vector over (A_t)^t with product = g and one with product = identity. Combined with a recent construction by the author and Viola in the setting of leakage-resilient cryptography [STOC \'13], this gives a compiler that produces circuits withstanding leakage from NC^1 (assuming NC^1 \\neq L). For context, leakage from NC^1 breaks nearly all previous constructions, and security against leakage from P is impossible.

We build on work by Cook and McKenzie [J.\\ Algorithms \'87] establishing the relationship between L = logarithmic space and the symmetric group S_t. Our techniques include a novel algorithmic use of commutators to manipulate the cycle structure of permutations in A_t.

22:17 [Pub][ePrint] Fast Prime Field Elliptic Curve Cryptography with 256 Bit Primes, by Shay Gueron and Vlad Krasnov

  This paper studies software optimization of Elliptic Curve Cryptography with 256-bit prime fields. We propose a constant-time implementation of the NIST and SECG standardized curve P-256, that can be seamlessly integrated into OpenSSL. This accelerates Perfect Forward Secrecy TLS handshakes that use ECDSA and/or ECDHE, and can help improving the efficiency of TLS servers. We report significant performance improvements for ECDSA and ECDH, on several architectures. For example, on the latest Intel Haswell microarchitecture, our ECDSA sign is 2.33x faster than OpenSSL\'s implementation.

22:17 [Pub][ePrint] Interactive Encryption, Message Authentication, and Anonymous Key Exchange, by Yevgeniy Dodis and Dario Fiore

  Public-Key Encryption (PKE) and Message Authentication (PKMA, aka as digital signatures) are fundamental cryptographic primitives. Traditionally, both notions are defined as non-interactive (i.e., single-message). In this work, we initiate rigorous study of (possibly) {\\em interactive} PKE and PKMA schemes. We obtain the following results demonstrating the power of interaction to resolve questions which are either open or impossible in the non-interactive setting.


One of the most well known open questions in the area of PKE is to build, in a ``black-box way\'\', so called chosen ciphertext attack (CCA-) secure PKE from chosen plaintext attack (CPA-) secure PKE. In contrast, we show a simple $2$-round CCA-secure PKE from any (non-interactive) CPA-secure PKE (in fact, these primitives turn out to be equivalent). Similarly, although non-interactive PKMA schemes can be inefficiently built from any one-way function, no efficient signature schemes are known from many popular number-theoretic assumptions, such as factoring, CDH or DDH. In contrast, we show an efficient $2$-round PKMA from most popular assumptions, including factoring, CDH and DDH.

Advanced Properties.

It is well known that no non-interactive signature (resp. encryption) scheme can be {\\em deniable} (resp. {\\em forward-secure}), since the signature (resp. ciphertext) can later ``serve as an evidence of the sender\'s consent\'\' (resp. ``be decrypted if the receiver\'s key is compromised\'\'). We also formalize a related notion of {\\em replay-secure} (necessarily) interactive PKMA (resp. PKE) schemes, where the verifier (resp. encryptor) is assured that the ``current\'\' message can only be authenticated (resp. decrypted) by the secret key owner {\\em now}, as opposed to some time in the past (resp. future). We observe that our 2-round PKMA scheme is both replay-secure and (passively) deniable, and our 2-round PKE scheme is both replay- and forward-secure. We also define and construct stronger forms of necessarily interactive PKE/PKMA schemes, called {\\em confirmed encryption} and {\\em confidential authentication}.

Anonymous Key Exchange.

We extend our definitional framework for interactive PKE and PKMA schemes to give definitions and constructions of (necessarily interactive) {\\em anonymous key exchange} (1-KE), where an anonymous (unkeyed) party establishes a key with an authenticated (keyed) party. Unlike the prior work, defining 1-KE by ``downgrading\'\' the hairy and complex definition of {\\em mutually authenticated} key exchange (2-KE), our definition is very ``short\'\' and easy to understand. We also show simple and general connections between anonymous KE and (interactive) confirmed PKE/confidential PKMA schemes. As a result, we obtain old and new schemes for anonymous KE in a clean and modular manner. For example, we obtain the first $2$-round anonymous KE which is both (passively) deniable and forward-secure.

22:17 [Pub][ePrint] On the Relation of Random Grid, Probabilistic and Deterministic Visual Cryptography, by Roberto De Prisco and Alfredo De Santis

  Visual cryptography is a special type of secret sharing. Two models of visual cryptography have been independently studied: deterministic visual cryptography, introduced by Naor and Shamir, and random grid visual cryptography, introduced by Kafri and Keren. In the context of the deterministic model, Yang has introduced a third model, the probabilistic visual cryptography model. The connection between the probabilistic and the deterministic models have been explored.

In this paper we show that there is a strict relation between the random grid model and the deterministic model. More specically we show that to any random grid scheme corresponds a deterministic scheme and viceversa. This allows us to use results known in a model also in the other model. In fact, the random grid model is equivalent to the probabilistic model with no pixel expansion. Exploiting the (many) results known in the deterministic model we are able to improve several schemes and to provide many upper bounds for the random grid model. Exploiting some results known for the random grid model, we are also able to provide new schemes for the deterministic model. A side eect of this paper is that future new results for any one of the two models (random grid and deterministic) should not ignore, and in fact be compared to, the results known in the other model.