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

2013-10-15
09:17 [Pub][ePrint] Integral Distinguishers for Reduced-round Stribog, by Riham AlTawy and Amr M. Youssef

  In January 2013, the Stribog hash function officially replaced GOST R 34.11-94 as the new Russian cryptographic hash standard GOST R 34.11-2012. Stribog is an AES-based primitive and is considered as an asymmetric reply to the new SHA-3 selected by NIST. In this paper we investigate the structural integral properties of reduced version of the Stribog compression function and its internal permutation. Specifically, we present a forward and backward higher order integrals that can be used to distinguish 4 and 3.5 rounds, respectively. Moreover, using the start from the middle approach, we combine the two proposed integrals to get 6.5-round and 7.5-round distinguishers for the internal permutation and 6-round and 7-round distinguishers for the compression function.



09:17 [Pub][ePrint] Security Analysis of Password-Authenticated Key Retrieval, by SeongHan Shin and Kazukuni Kobara

  A PAKR (Password-Authenticated Key Retrieval) protocol and its multi-server system allow one party (say, client), who has a rememberable password, to retrieve a long-term static key in an exchange of messages with at least one other party (say, server) that has a private key associated with the password. In this paper, we analyze the only one PAKR (named as PKRS-1) standardized in IEEE 1363.2 [9] and its multi-server system (also, [11]) by showing that any passive/active attacker can find out the client\'s password and the static key with off-line dictionary attacks. This result is contrary to the security statement of PKRS-1 (see Chapter 10.2 of IEEE 1363.2 [9]).



09:17 [Pub][ePrint] On Extractability Obfuscation, by Elette Boyle and Kai-Min Chung and Rafael Pass

  We initiate the study of {\\em extractability obfuscation}, a notion first suggested by Barak et al. (JACM 2012): An extractability obfuscator eO for a class of algorithms M guarantees that if an efficient attacker A can distinguish between obfuscations eO(M_1), eO(M_2) of two algorithms M_1,M_2 \\in M, then A can efficiently recover (given M_1 and M_2) an input on which M_1 and M_2 provide different outputs.

- We rely on the recent candidate virtual black-box obfuscation constructions to provide candidate constructions of extractability obfuscators for NC^1; next, following the blueprint of Garg et~al. (FOCS 2013), we show how to bootstrap the obfuscator for NC^1 to an obfuscator for all non-uniform polynomial-time Turing machines. In contrast to the construction of Garg et al., which relies on indistinguishability obfuscation for NC^1, our construction enables succinctly obfuscating non-uniform {\\em Turing machines} (as opposed to circuits), without turning running-time into description size.

- We introduce a new notion of {\\em functional witness encryption}, which enables encrypting a message m with respect to an instance x, language L, and function f, such that anyone (and only those) who holds a witness w for x\\in L can compute f(m,w) on the message and particular known witness. We show that functional witness encryption is, in fact, equivalent to extractability obfuscation.

- We demonstrate other applications of extractability extraction, including the first construction of fully (adaptive-message) indistinguishability-secure functional encryption for an unbounded number of key queries and unbounded message spaces.

- We finally relate indistinguishability obfuscation and extractability obfuscation and show special cases when indistinguishability obfuscation can be turned into extractability obfuscation.



09:17 [Pub][ePrint] A Closer Look at Multiple-Forking: Leveraging (In)dependence for a Tighter Bound, by Sanjit Chatterjee and Chethan Kamath

  Boldyreva et al. introduced the notion of multiple forking (MF) as an extension of (general) forking to accommodate nested oracle replay attacks. The primary objective of a (multiple) forking algorithm is to separate out the oracle replay attack from the actual simulation of protocol to the adversary, and this is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing the MF Algorithm incurs a significant degradation of O(q^2n), where q denotes the upper bound on the underlying random oracle calls and n, the number of forkings. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for the success of the MF Algorithm. A careful analysis of the protocols (and corresponding security argument) employing multiple forking allow us to relax the overly restrictive conditions of the original MF Algorithm. To achieve this, we club two consecutive invocations of the underlying wrapper into a single logical unit of wrapper Z. We then use Z to formulate the notion of \"dependency\" and \"independency\" among different rounds of the wrapper in the MF Algorithm. The (in)dependency conditions lead to a general framework for multiple forking and significantly better bound for the MF Algorithm. Leveraging (in)dependency to the full reduces the degradation from O(q^2n) to O(q^n). Finally, we study the effect of these observations on the security of the existing schemes. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.



09:17 [Pub][ePrint] Efficient Modular Arithmetic for SIMD Devices, by Wilke Trei

  This paper describes several new improvements of modular arithmetic and how to exploit them in order to gain more efficient implementations of commonly used algorithms, especially in cryptographic applications. We further present a new record for modular multiplications per second on a single desktop computer as well as a new record for the ECM factoring algorithm. This new results allow building personal computers which can handle more than 3 billion modular multiplications per second for a 192 bit module at moderate costs using modern graphic cards.



09:17 [Pub][ePrint] RKA-KDM secure encryption from public-key encryption, by Florian Böhl and Gareth T. Davies and Dennis Hofheinz

  We construct secret-key encryption (SKE) schemes that are secure against related-key attacks and in the presence of key-dependent messages (RKA-KDM secure). We emphasize that RKA-KDM security is not merely the conjunction of individual security properties, but covers attacks in which ciphertexts of key-dependent messages under related keys are available. Besides being interesting in their own right, RKA-KDM secure schemes allow to garble circuits with XORs very efficiently (Applebaum, TCC 2013). Until now, the only known RKA-KDM secure SKE scheme (due to Applebaum) is based on the LPN assumption. Our schemes are based on various other computational assumptions, namely DDH, LWE, QR, and DCR.

We abstract from Applebaum\'s construction and proof, and formalize three generic technical properties that imply RKA-KDM security: one property is IND-CPA security, and the other two are the existence of suitable oracles that produce ciphertexts under related keys, resp. of key-dependent messages. We then give simple SKE schemes that achieve these properties. Our constructions are variants of known KDM-secure public-key encryption schemes. To additionally achieve RKA security, we isolate suitable homomorphic properties of the underlying schemes in order to simulate ciphertexts under related keys in the security proof.

From a conceptual point of view, our work provides a generic and extensible way to construct encryption schemes with multiple special security properties.



09:17 [Pub][ePrint] Leakage-Resilient Chosen-Ciphertext Secure Public-Key Encryption from Hash Proof System and One-Time Lossy Filter, by Baodong Qin and Shengli Liu

  We present a new generic construction of a public-key encryption (PKE) scheme secure against leakage-resilient chosen-ciphertext attacks (LR-CCA), from any Hash Proof System (HPS) and any one-time lossy filter (OT-LF). Efficient constructions of HPSs and OT-LFs from the DDH and DCR assumptions suggest that our construction is a practical approach to LR-CCA security. Most of practical PKEs with LR-CCA security, like variants of Cramer-Shoup scheme, rooted from Hash Proof Systems, but with leakage rates at most $1/4-o(1)$ (defined as the ratio of leakage amount to secret-key size). The instantiations of our construction from the DDH and DCR assumptions result in LR-CCA secure PKEs with leakage rate of $1/2-o(1)$.

On the other hand, our construction also creates a new approach for constructing IND-CCA secure (leakage-free) PKE schemes, which may be of independent interest.



09:17 [Pub][ePrint] Privacy-Preserving Multi-Party Reconciliation Secure in the Malicious Model (Extended version), by Georg Neugebauer and Lucas Brutschy and Ulrike Meyer and Susanne Wetzel

  The problem of fair and privacy-preserving ordered set reconciliation arises in a variety of applications like auctions, e-voting, and appointment reconciliation. While several multi-party protocols have been proposed that solve this problem in the semi-honest model, there are no multi-party protocols that are secure in the malicious model so far. In this paper, we close this gap. Our newly proposed protocols are shown to be secure in the malicious model based on a variety of novel non-interactive zero-knowledge-proofs. We describe the implementation of our protocols and evaluate their performance in comparison to protocols solving the problem in the semi-honest case.



09:17 [Pub][ePrint] Bias-based modeling and entropy analysis of PUFs, by Robbert van den Berg and Boris Skoric and Vincent van der Leest

  Physical Unclonable Functions (PUFs) are increasingly becoming

a well-known security primitive for secure key storage

and anti-counterfeiting. For both applications it is imperative

that PUFs provide enough entropy. The aim of this paper

is to propose a new model for binary-output PUFs such as

SRAM, DFF, Latch and Buskeeper PUFs, and a method to

accurately estimate their entropy. In our model the measurable

property of a PUF is its set of cell biases. We determine

an upper bound on the \'extractable entropy\', i.e. the number

of key bits that can be robustly extracted, by calculating the

mutual information between the bias measurements done at

enrollment and reconstruction.

In previously known methods only uniqueness was studied

using information-theoretic measures, while robustness was

typically expressed in terms of error probabilities or distances.

It is not always straightforward to use a combination of these

two metrics in order to make an informed decision about

the performance of different PUF types. Our new approach

has the advantage that it simultaneously captures both of

properties that are vital for key storage: uniqueness and

robustness. Therefore it will be possible to fairly compare

performance of PUF implementations using our new method.

Statistical validation of the new methodology shows that

it clearly captures both of these properties of PUFs. In other

words: if one of these aspects (either uniqueness or robustness)

is less than optimal, the extractable entropy decreases.

Analysis on a large database of PUF measurement data shows

very high entropy for SRAM PUFs, but rather poor results

for all other memory-based PUFs in this database.



09:17 [Pub][ePrint] New Trapdoor Projection Maps for Composite-Order Bilinear Groups, by Sarah Meiklejohn and Hovav Shacham

  An asymmetric pairing over groups of composite order is a bilinear map $e: G_1 \\times G_2 \\to G_T$ for groups $G_1$ and $G_2$ of composite order $N=pq$. We observe that a recent construction of pairing-friendly elliptic curves in this setting by Boneh, Rubin, and Silverberg exhibits surprising and unprecedented structure: projecting an element of the order-$N^2$ group $G_1 \\oplus G_2$ onto the bilinear groups $G_1$ and $G_2$ requires knowledge of a trapdoor. This trapdoor, the square root of a certain number modulo $N$, seems strictly weaker than the trapdoors previously used in composite-order bilinear cryptography.

In this paper, we describe, characterize, and exploit this surprising structure. It is our thesis that the additional structure available in these curves will give rise to novel cryptographic constructions, and we initiate the study of such constructions. Both the subgroup hiding and SXDH assumptions appear to hold in the new setting; in addition, we introduce custom-tailored assumptions designed to capture the trapdoor nature of the projection maps into $G_1$ and $G_2$. Using the old and new assumptions, we describe an extended variant of the Boneh-Goh-Nissim cryptosystem that allows a user, at the time of encryption, to restrict the homomorphic operations that may be performed. We also present a variant of the Groth-Ostrovsky-Sahai NIZK, and new anonymous IBE, signature, and encryption schemes.



09:17 [Pub][ePrint] Parallel authenticated encryption with the duplex construction, by Pawel Morawiecki and Josef Pieprzyk

  The authentication encryption (AE) scheme based on the duplex construction can no be paralellized at the algorithmic level. To be competitive with some block cipher based modes like OCB (Offset CodeBook) or GCM (Galois Counter Mode), a scheme should allow parallel processing. In this note we show how parallel AE can be realized within the framework provided by the duplex construction. The first variant, pointed by the duplex designers, is a tree-like structure. Then we simplify the scheme replacing the final node by the bitwise xor operation and show that such a scheme has the same security level.