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-02-10
22:17 [Pub][ePrint] Equivalent Key Recovery Attacks against HMAC and NMAC with Whirlpool Reduced to 7 Rounds, by Jian Guo and Yu Sasaki and Lei Wang and Meiqin Wang and Long Wen

  A main contribution of this paper is an improved analysis against HMAC instantiating with reduced Whirlpool. It recovers equivalent keys, which are often denoted as Kin and Kout, of HMAC with 7-round Whirlpool, while the previous best attack can work only for 6 rounds. Our approach is applying the meet-in-the-middle (MITM) attack on AES to recover MAC keys of Whirlpool. Several techniques are proposed to bypass different attack scenarios between a block cipher and a MAC, e.g., the chosen plaintext model of the MITM attacks on AES cannot be used for HMAC-Whirlpool. Besides, a larger state size and different key schedule designs of Whirlpool leave us a lot of room to study. As a result, equivalent keys of HMAC with 7-round Whirlpool are recovered with a complexity of (Data, Time, Memory) = (2^481.7, 2^482.3, 2^481).



22:17 [Pub][ePrint] Fully Structure-Preserving Signatures and Shrinking Commitments, by Masayuki Abe and Markulf Kohlweiss and Miyako Ohkubo and Mehdi Tibouchi

  Structure-preserving signatures are schemes in which

public keys, messages, and signatures are all collections of source group elements of

some bilinear groups. In this paper, we introduce fully structure-preserving signature

schemes, with the additional requirement that even secret keys should be group elements.

This new type of structure-preserving signatures allows for

efficient non-interactive proofs of knowledge of the secret key and is

useful in designing cryptographic protocols with strong security guarantees

based on the simulation paradigm where the simulator has to extract the

secret keys on-line.

To gain efficiency, we construct shrinking structure-preserving trapdoor

commitments. This is by itself an important primitive and of independent

interest as it appears to contradict a known impossibility result. We argue that a relaxed binding

property lets us circumvent the impossibility result while still retaining the

usefulness of the primitive in important applications as mentioned above.



22:17 [Pub][ePrint] On the Existence and Constructions of Vectorial Boolean Bent Functions, by Yuwei Xu and Chuankun Wu

  Recently, obtaining vectorial Boolean bent functions of the form $Tr^{n}_{m}(P(x))$, where $P(x)\\in \\mathbb{F}_{2^{n}}[x]$, from Boolean bent functions of the form $Tr^{n}_{1}(P(x))$ has attracted several attentions and some open problems about this issue were proposed. This paper first provides three constructions of vectorial Boolean bent functions in the form $Tr^{n}_{m}(P(x))$, where two of them imply answers to two open problems proposed by E.Pasalic et al. and A.Muratovi\\\'{c}-Ribi\\\'{c} et al. respectively. And by analyzing known types of Boolean bent functions of the form $Tr^{n}_{1}(P(x))$, the existence and constructions of several types of vectorial Boolean bent functions in the form $Tr^{n}_{m}(P(x))$ are obtained.



22:17 [Pub][ePrint] Fully Homomorphic Encryption from Ring-LWE:Identity-Based,Arbitrary Cyclotomic,Tighter Parameters, by GU Chun-xiang and. Xin Dan and. ZHENG Yong-hui and. KANG Yuan-ji

  Fully homomorphic is an encryption scheme that allows for data to be stored and processed in an encrypted format, which gives the cloud provider a solution to host and process data without even knowing what the message is. In previous identity-based homomorphic encryption scheme, computing efficiency is complicated and expensive. In this work, based on Regev\'s work, we propose a sampling trapdoor one-way function in arbitrary cyclotomic rings . Then construct a leveled identity-based homomorphic encryption scheme from ring learning with errors, which has advantage in computational efficiency and key management, by using user\'s identity as the unique public key. This scheme is proved IND-CPA secure in the random oracle model, relied to hardness of decision ring learning with errors problem.



22:17 [Pub][ePrint] On the Security of the COPA and Marble Authenticated Encryption Algorithms against (Almost) Universal Forgery Attack, by Jiqiang Lu

  COPA is a block-cipher-based authenticated encryption mode with a provable birthday-bound security under the assumption that the underlying block cipher is a strong pseudorandom permutation, and its instantiation with the AES block cipher is called AES-COPA. Marble is an AES-based COPA-like authenticated encryption algorithm with a full security. In this paper, we analyse the security of COPA and Marble against universal forgery attacks. We present beyond-birthday-bound (almost) universal forgery attacks on the COPA when used with constant or variable associate data, and present (almost) universal forgery attacks on the Marble when used without associated data or with (variable) associate data. Our attacks on the COPA with variable associate data have a complexity very near the birthday bound, and their applications to AES-COPA show that the security claim of AES-COPA against tag guessing may be not correct; and our attacks on the (newest as well as initial version of) Marble with associate data show that Marble does not provide a full security that the designer claimed. Like many recently published cryptanalytic results on message authentication algorithms with a provable birthday-bound security, our attacks on COPA do not violate its security proofs, but provide a comprehensive understanding of its security against universal forgery attack, show that the success probability of a universal forgery on the COPA is larger than the ideal bound $2^{-n}$ of the standard forgery-resistance, and boil down to an existing open question: Should a message authentication algorithm with a weaker security claim than the standard forgery-resistance be regarded as a sound design?



22:17 [Pub][ePrint] The Fairy-Ring Dance: Password Authenticated Key Exchange in a Group, by Feng Hao and Xun Yi and Liqun Chen and Siamak F. Shahandashti

  In this paper, we study Password Authenticated Key Exchange (PAKE) in a group. First, we present a generic ``fairy-ring dance\'\' construction that transforms any secure two-party PAKE scheme to a group PAKE protocol while preserving the round efficiency in the optimal way. Based on this generic construction, we present two concrete instantiations based on using SPEKE and J-PAKE as the underlying PAKE primitives respectively. The first protocol, called SPEKE+, accomplishes authenticated key exchange in a group with explicit key confirmation in just two rounds. This is more round-efficient than any existing group PAKE protocols in the literature. The second protocol, called J-PAKE+, requires one more round than SPEKE+, but is computationally faster. Finally, we present full implementations of SPEKE+ and J-PAKE+ with detailed performance measurements. Our experiments suggest that both protocols are feasible for practical applications in which the group size may vary from three to several dozen. This makes them useful, as we believe, for a wide range of applications -- e.g., to bootstrap secure communication among a group of smart devices in the Internet of Things (IoT).



14:23 [Job][New] Post-Doctoral Research Fellow Positions, Centre for Secure Information Technologies (CSIT), Queen’s University Belfast, UK

  Applications are invited for Post-Doctoral Research Fellow positions to conduct research into the design and implementation of practical, robust and physically secure lattice-based cryptographic architectures as part of the EU H2020 SAFEcrypto project. The SAFEcrypto consortium comprises 6 other partners (HWCommunications, Ruhr Universität Bochum, RSA, Thales, INRIA and Universitá della Svizzera Italiana) and post holders will be expected to collaborate with these partners.

Applicants must have at least a 2:1 Honours Degree in Electrical and Electronics Engineering, Computer Science, Mathematics or closely related discipline and a PhD, or expect, within 6 months, to obtain a PhD, in a relevant subject. At least 3 years relevant research experience in one or more of the following is essential: embedded systems design; FPGA or ASIC hardware design; integrated hardware/software design. Evidence of a strong publication record commensurate with career stage and experience is also essential.

(Ref: 15/103726)

07:17 [Pub][ePrint] The Sum Can Be Weaker Than Each Part, by Gaëtan Leurent and Lei Wang

  In this paper we study the security of summing the outputs of two

independent hash functions, in an effort to increase the security of the

resulting design, or to hedge against the failure of one of the hash

functions. The exclusive-or (XOR) combiner H1(M)+H2(M) is one of the

two most classical combiners, together with the concatenation combiner

H1(M)||H2(M). While the security of the concatenation of two hash

functions is well understood since Joux\'s seminal work on

multicollisions, the security of the sum of two hash functions has been

much less studied.

The XOR combiner is well known as a good PRF and MAC combiner, and is

used in practice in TLS versions 1.0 and 1.1. In a hash function

setting, Hoch and Shamir have shown that if the compression functions

are modeled as random oracles, or even weak random oracles (i.e. they

can easily be inverted -- in particular H1 and H2 offer no security),

H1+H2 is indifferentiable from a random oracle up to the birthday bound.

In this work, we focus on the preimage resistance of the sum of two

narrow-pipe n-bit hash functions, following the Merkle-Damgård or HAIFA

structure (the internal state size and the output size are both n bits).

We show a rather surprising result: the sum of two such hash functions,

e.g. SHA-512+Whirlpool, can never provide n-bit security for preimage

resistance. More precisely, we present a generic preimage attack with a

complexity of O(2^5n/6). While it is already known that the XOR

combiner is not preserving for preimage resistance (i.e. there might be

some instantiations where the hash functions are secure but the sum is

not), our result is much stronger: for any narrow-pipe functions, the

sum is not preimage resistant.

Besides, we also provide concrete preimage attacks on the XOR combiner

(and the concatenation combiner) when one or both of the compression

functions are weak; this complements Hoch and Shamir\'s proof by showing

its tightness for preimage resistance.

Of independent interests, one of our main technical contributions is a

novel structure to control simultaneously the behavior of independent

hash computations which share the same input message. We hope that

breaking the pairwise relationship between their internal states will

have applications in related settings.



07:17 [Pub][ePrint] Factoring N=p^r q^s for Large r and s, by Jean-Sebastien Coron and Jean-Charles Faugere and Guenael Renault and Rina Zeitoun

  Boneh et al. showed at Crypto 99 that moduli of the form N=p^r q can be factored in polynomial time when r=log p. Their algorithm is based on Coppersmith\'s technique for finding small roots of polynomial equations. In this paper we show that N=p^r q^s can also be factored in polynomial time when r or s is at least (log p)^3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli N with k prime factors; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the k exponents is large enough.



07:17 [Pub][ePrint] Non-Interactive Zero-Knowledge Proofs of Non-Membership, by Olivier Blazy and Céline Chevalier and Damien Vergnaud

  Often, in privacy-sensitive cryptographic protocols, a party commits to a secret message m and later needs to prove that $m$ belongs to a language L or that m does not belong to L (but this party does not want to reveal any further information). We present a method to prove in a non-interactive way that a committed value does not belong to a given language L.

Our construction is generic and relies on the corresponding proof of membership to L. We present an efficient realization of our proof system by combining {smooth projective hash functions} and the Groth-Sahai proof system.

In 2009, Kiayias and Zhou introduced {zero-knowledge proofs with witness elimination} which enable to prove that a committed message $m$ belongs to a language L (with a witness w) in such a way that the verifier accepts the interaction only if w does not belong to a set determined by a public relation Q and some private input w\' of the verifier. We show that the protocol they proposed is flawed and that a dishonest prover can actually make a verifier accept a proof for any message m in L even if (w,w\') in Q. Using our non-interactive proof of non-membership of committed values, we are able to fix their protocol and improve its efficiency.

Our approach finds also efficient applications in other settings, e.g. in anonymous credential systems and privacy-preserving authenticated identification and key exchange protocols.



07:17 [Pub][ePrint] Oblivious Network RAM, by Dana Dachman-Soled and Chang Liu and Charalampos Papamanthou and Elaine Shi and Uzi Vishkin

  Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted CPU to securely

access untrusted memory, such that the access patterns reveal nothing about sensitive data.

ORAM is known to have broad applications in secure processor design and secure multi-party

computation for big data. Unfortunately, due to a well-known logarithmic lower bound by

Goldreich and Ostrovsky (Journal of the ACM, \'96), ORAM is bound to incur a moderate cost

in practice. In particular, with the latest developments in ORAM constructions, we are quickly

approaching this limit, and the room for performance improvement is small.

In this paper, we consider new models of computation in which the cost of obliviousness

can be fundamentally reduced in comparison with the standard ORAM model. We propose

the Oblivious Network RAM model of computation, where a CPU communicates with multiple

memory banks, such that the adversary observes only which bank the CPU is communicating

with, but not the address offset within each memory bank. In other words, obliviousness within

each bank comes for free--either because the architecture prevents a malicious party from ob-

serving the address accessed within a bank, or because another solution is employed to obfuscate

memory accesses within each bank--and hence we only need to obfuscate the communication

patterns between the CPU and the memory banks. We present several new constructions for

obliviously simulating general or parallel programs in the Network RAM model. We describe

applications of the Network RAM model in secure processor design and in distributed storage

applications with a network adversary.