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

00:17 [Pub][ePrint] Mix-Compress-Mix Revisited: Dispensing with Non-invertible Random Injection Oracles, by Mohammad Reza Reyhanitabar and Willy Susilo

  We revisit the problem of building dual-model secure (DMS) hash functions that are simultaneously

provably collision resistant (CR) in the standard model and provably pseudorandom oracle (PRO) in an idealized

model. Designing a DMS hash function was first investigated by Ristenpart and Shrimpton (ASIACRYPT

2007); they put forth a generic approach, called Mix-Compress-Mix (MCM), and showed the feasibility of the

MCM approach with a secure (but inefficient) construction. An improved construction was later presented by

Lehmann and Tessaro (ASIACRYPT 2009). The proposed construction by Ristenpart and Shrimpton requires

a non-invertible (pseudo-) random injection oracle (PRIO) and the Lehmann-Tessaro construction requires a

non-invertible random permutation oracle (NIRP). Despite showing the feasibility of realizing PRIO and NIRP

objects in theory-using ideal ciphers and (trapdoor) one-way permutations- these constructions suffer from several

efficiency and implementation issues as pointed out by their designers and briefly reviewed in this paper.

In contrast to the previous constructions, we show that constructing a DMS hash function does not require any

PRIO or NIRP, and hence there is no need for additional (trapdoor) one-way permutations. In fact, Ristenpart and

Shrimpton posed the question of whether MCM is secure under easy-to-invert mixing steps as an open problem in

their paper.We resolve this question in the affirmative in the fixed-input-length (FIL) hash setting. More precisely,

we show that one can sandwich a provably CR function, which is sufficiently compressing, between two random

invertible permutations to build a provably DMS compression function. Any multi-property-preserving (MPP)

domain extender that preserves CR and PRO can then be used to convert such a DMS compression function

to a full-fledged DMS hash function. Interestingly, there are efficient off-the-shelf candidates for all the three

ingredients (provably CR compression functions, random invertible permutations, and MPP domain extenders)

from which one can choose to implement such a DMS hash function in practice. Further, we also explain the

implementation options as well as a concrete instantiation.

00:17 [Pub][ePrint] Short Signatures From Diffie-Hellman: Realizing Short Public Key, by Jae Hong Seo

  In EUROCRYPT 2005, Waters proposed a signature scheme based on the computational Diffie-Hellman (DH) assumption without random oracles. His scheme is the first and sole signature scheme in the category of (hash-and-sign) signature schemes secure under the DH assumption in the standard model and has also been applied to the design of numerous protocols in the various cryptographic areas. However, the Waters signature scheme suffered from a large public key of $\\Theta(\\lambda)$ group elements, where $\\lambda$ is the security parameter. Realizing standard model DH-based signature scheme, in which both the signature and the public key are short, has been an open problem.

We propose short signatures from the DH assumption, which has a sublinear size public key. More precisely, our proposal produces a public key of $\\Theta(\\sqrt{\\frac{\\lambda}{\\log \\lambda}})$ group elements. Our construction is inspired from two techniques for short signatures such as using programmable hashes and using tags. From two previous techniques, we first derive a signature scheme with a somewhat short public key of $\\Theta(\\frac{\\lambda}{\\log\\lambda})$, and then we developed a new technique for {\\em asymmetric trade} between the public key size and the signature size. In particular, by adding one field element in each signature, we can reduce the public key size to $O(\\sqrt{\\frac{\\lambda}{\\log \\lambda}})$ group elements, so that the resulting signature size is two group elements and two field elements.

We also propose a variant by applying a technique for compressing tag vectors so that the resulting signatures has a shorter signature size (two group elements and one field element) by augmenting signing/verification costs and adding constant factor in public key size (that is, public key size is still $\\Theta(\\sqrt\\frac{\\lambda}{\\log\\lambda})$ group elements). Note that we limit ourselves to dealing with only polynomial-time reductions in all security proofs.

00:17 [Pub][ePrint] Improved Security Bounds for Key-Alternating Ciphers via Hellinger Distance, by John Steinberger

  A $t$-round key alternating cipher can be viewed as an abstraction of AES. It defines a cipher $E$ from $t$ fixed public permutations $P_1, \\ldots, P_t : \\{0,1\\}^n \\ra \\{0,1\\}^n$ and a key $k = k_0\\Vert \\cdots \\Vert k_t \\in \\{0,1\\}^{n(t+1)}$ by setting $E_{k}(x) = k_t \\oplus P_t(k_{t-1} \\oplus P_{t-1}(\\cdots k_1 \\oplus P_1(k_0 \\oplus x) \\cdots))$. The indistinguishability of $E_k$ from a random truly random permutation by an adversary who also has oracle access to the (public) random permutations $P_1, \\ldots, P_t$ was investigated for $t = 2$ by Even and Mansour and, much later, by Bogdanov et al. The former proved indistinguishability up to $2^{n/2}$ queries for $t = 1$ while the latter proved indistinguishability up to $2^{2n/3}$ queries for $t \\geq 2$ (ignoring low-order terms). Our contribution is to improve the analysis of Bogdanov et al$.$ by showing security up to $2^{3n/4}$ queries for $t \\geq 3$. Given that security cannot exceed $2^{\\frac{t}{t+1}n}$ queries, this is in particular achieves a tight bound for the case $t = 3$, whereas, previously, tight bounds had only been achieved for $t = 1$ (by Even and Mansour) and for $t = 2$ (by Bogdanov et al$.$). Our main technique is an improved analysis of the elegant \\emph{sample distinguishability} game introduced by Bogdanov et al. More specifically, we succeed in eliminating adaptivity by considering the Hellinger advantage of an adversary, a notion that we introduce here. To our knowledge, our result constitutes the first time Hellinger distance (a standard measure of ``distance\'\' between random variables, and a cousin of statistical distance) is used in a cryptographic indistinguishability proof.

00:17 [Pub][ePrint] Approaches for the Parallelization of Software Implementation of Integer Multiplication, by Vladislav Kovtun and Andrew Okhrimenko

  In this paper there are considered several approaches for the increasing performance of software implementation of integer multiplication algorithm for the 32-bit & 64-bit platforms via parallelization. The main idea of algorithm parallelization consists in delayed carry mechanism using which authors have proposed earlier [11]. The delayed carry allows to get rid of connectivity in loop iterations for sums accumulation of products, which allows parallel execution of loops iterations in separate threads. Upon completion of sum accumulation threads, it is necessary to make corrections in final result via assimilation of carries. First approach consists in optimization of parallelization for the two execution threads and second approach is an evolution of the first approach and is oriented on three and more execution threads. Proposed approaches for parallelization allow increasing the total algorithm computational complexity, as for one execution thread, but decrease total execution time on multi-core CPU.

00:17 [Pub][ePrint] An Efficient Signcryption Scheme from q-Diffie-Hellman Problems, by Jayaprakash Kar

  Confidentiality and authenticity are two fundamental security requirement of Public key Cryptography. These are achieved by encryption scheme and digital signatures respectively. Here we present a provably secure signcryption scheme in random oracle

model by modifying Libert et al\'s scheme [2]. Our scheme is more e±cient and secure than Libert et al\'s scheme. Tan [1] proved that this scheme is not secure against non-adaptive chosen cipher text attacks. It has been also proved that the semantically secure

symmetric encryption scheme proposed in the Libert et al\'s scheme is not su±cient to guarantee to be secure against adaptive chosen ciphertext attacks. Here we proposed a modified version of Libert et al\'s scheme. The security of which is proven using two as-

sumptions, namely the Strong Diffie-Hellman (SDH) and Diffie-Hellman Inversion (DHI)

in the random oracle model.

00:17 [Pub][JoC] Polynomial Runtime and Composability


Abstract  We devise a notion of polynomial runtime suitable for the simulation-based security analysis of multi-party cryptographic protocols. Somewhat surprisingly, straightforward notions of polynomial runtime lack expressivity for reactive tasks and/or lead to an unnatural simulation-based security notion. Indeed, the problem has been recognized in previous works, and several notions of polynomial runtime have already been proposed. However, our new notion, dubbed reactive polynomial time, is the first to combine the following properties: –  it is simple enough to support simple security/runtime analyses, –  it is intuitive in the sense that all intuitively feasible protocols and attacks (and only those) are considered polynomial-time, –  it supports secure composition of protocols in the sense of a universal composition theorem. We work in the Universal Composability (UC) protocol framework. We remark that while the UC framework already features a universal composition theorem, we develop new techniques to prove secure composition in the case of reactively polynomial-time protocols and attacks.

  • Content Type Journal Article
  • Pages 1-67
  • DOI 10.1007/s00145-012-9127-4
  • Authors

    • Dennis Hofheinz, Karlsruhe Institute of Technology, Karlsruhe, Germany
    • Dominique Unruh, University of Tartu, Tartu, Estonia
    • Jörn Müller-Quade, Karlsruhe Institute of Technology, Karlsruhe, Germany

    • Journal Journal of Cryptology
    • Online ISSN 1432-1378
    • Print ISSN 0933-2790

From: Thu, 16 Aug 2012 16:03:17 GMT

17:48 [Conf][Crypto] CRYPTO 2012 on Facebook

  CRYPTO 2012 starts today!!

Follow us on facebook --

If you have any conference-related stories or photos to share, please email

06:17 [Pub][ePrint] Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming, by Carles Padro and Leonor Vazquez and An Yang

  Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants.

By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding

to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.

06:17 [Pub][ePrint] T-MATCH: Privacy-Preserving Item Matching for Storage-Only RFID Tags, by Kaoutar Elkhiyaoui and Erik-Oliver Blass and Refik Molva

  RFID-based tag matching allows a reader Rk to determine whether two tags Ti and Tj store

some attributes that jointly fulfill a boolean constraint. The challenge in designing a matching mechanism

is tag privacy. While cheap tags are unable to perform any computation, matching has to be

achieved without revealing the tags\' attributes. In this paper, we present T-MATCH, a protocol for secure

and privacy preserving RFID tag matching. T-MATCH involves a pair of tags Ti and Tj , a reader

Rk, and a backend server S. To ensure tag privacy against Rk and S, T-MATCH employs a new technique

based on secure two-party computation that prevents Rk and S from disclosing tag attributes. For

tag privacy against eavesdroppers, each tag Ti in T-MATCH stores an IND-CPA encryption of its attribute.

Such an encryption allows Rk to update the state of Ti by merely re-encrypting Ti\'s ciphertext.

T-MATCH targets cheap tags that cannot perform any computation, but are only required to store 150


06:17 [Pub][ePrint] Computational Entropy and Information Leakage, by Benjamin Fuller and Leonid Reyzin

  We investigate how information leakage reduces computational entropy of a random variable X. Recall that HILL and metric computational entropy are parameterized by quality (how distinguishable is X from a variable Z that has true entropy) and quantity (how much true entropy is there in Z).

We prove an intuitively natural result: conditioning on an event of probability p reduces the quality of metric entropy by a factor of p and the quantity of metric entropy by log 1/p note that this means that the reduction in quantity and quality is the same, because the quantity of entropy is measured on logarithmic scale). Our result improves previous bounds of Dziembowski and Pietrzak (FOCS 2008), where the loss in the \\emph{quantity} of entropy was related to its original quality. The use of metric entropy simplifies the analogous the result of Reingold et. al. (FOCS 2008) for HILL entropy.

Further, we simplify dealing with information leakage by investigating conditional metric entropy. We show that, conditioned on leakage of \\lambda bits, metric entropy gets reduced by a factor 2^\\lambda in quality and \\lambda in quantity.

06:17 [Pub][ePrint] New results on nonexistence of generalized bent functions, by Yupeng Jiang and Yingpu Deng

  We get two kinds of new results on nonexistence of generalized bent function. The first one is Based on Feng\'s results by using Schmidt\'s field descent method. For the second kind, considering special property of the field $\\mathbb{Q}(\\zeta_{23^e})$, We get new nonexistence results of generalized bent functions with type $[3,2\\cdot23^e]$.