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

2012-11-12
12:36 [Job][New] Postdoc, Karlsruhe Institute of Technology, Germany

  There is one open postdoc position in the group of Dennis Hofheinz at the Karlsruhe Institute of Technology. The focus of our group is on all kinds of provable security, and in particular on public-key cryptography and cryptographic protocols.

Candidates should have a strong publication record. Knowledge of German is not required. There is funding for one year, with a possible extension. Review of applications starts immediately and will continue until the position is filled. The starting date is flexible.



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

  We formalize a new cryptographic primitive, Message-Locked Encryption (MLE), where the key under which encryption and decryption are performed is itself derived from the message. MLE provides a way to achieve secure deduplication (space-efficient secure outsourced storage), a goal currently targeted by numerous cloud-storage providers. We provide definitions both for privacy and for a form of integrity that we call tag consistency. Based on this foundation, we make both practical and theoretical contributions. On the practical side, we provide ROM security analyses of a natural family of MLE schemes that includes deployed schemes. On the theoretical side the challenge is standard model solutions, and we make connections with deterministic encryption, hash functions secure on correlated inputs and the sample-then-extract paradigm to deliver schemes under different assumptions and for different classes of message sources. Our work shows that MLE is a primitive of both practical and theoretical interest.



19:17 [Pub][ePrint] Pairings on Generalized Huff Curves, by Abdoul Aziz Ciss and Djiby Sow

  This paper presents the Tate pairing computation on generalized Huff curves proposed by Wu and Feng in \\cite{Wu}. In fact, we extend the results of the Tate pairing computation on the standard Huff elliptic curves done previously by Joye, Tibouchi and Vergnaud in \\cite{Joux}. We show that the addition step of the Miller loop can be performed in $1\\mathbf{M}+(k+15)\\mathbf{m}+2\\mathbf{c}$ and the doubling one in $1\\mathbf{M} + 1\\mathbf{S} + (k + 12) \\mathbf{m} + 5\\mathbf{s} + 2\\mathbf{c}$ on the generalized Huff curve.



19:17 [Pub][ePrint] New Preimage Attack on MDC-4, by Deukjo Hong and Daesung Kwon

  In this paper, we provide some cryptanalytic results for

double-block-length (DBL) hash modes of block ciphers, MDC-4. Our

preimage attacks follow the framework of Knudsen et al.\'s

time/memory trade-off preimage attack on MDC-2. We find how to apply

it to our objects. When the block length of the underlying block

cipher is $n$ bits, the most efficient preimage attack on MDC-4

requires time and space about $2^{3n/2}$, which is to be compared to

the previous best known preimage attack having time complexity of

$2^{7n/4}$. Additionally, we propose an enhanced version of MDC-4,

MDC-4$^*$ based on a simple idea. It is secure against our preimage

attack and previous attacks and has the same efficiency as MDC-4.



19:17 [Pub][ePrint] Cryptanalysis of Double-Block-Length Hash Mode MJH, by Deukjo Hong and Daesung Kwon

  A double-block-length (DBL) hash mode of block ciphers, MJH has been

proved to be collision-resistant in the ideal cipher model upto

$2^{2n/3- \\log n}$ queries. In this paper we provide first

cryptanalytic results for MJH. We show that a collision attack on

MJH has the time complexity below the birthday bound. When block

ciphers with 128-bit blocks are used, it has time complexity around

$2^{124}$, which is to be compared to the birthday attack having

complexity $2^{128}$. We also give a preimage attack on MJH. It has

the time complexity of $2^{3n/2+1}$ with $n$-bit block ciphers,

which is to be compared to the brute force attack having complexity

$2^{2n}$.



19:17 [Pub][ePrint] Secure Outsourced Attribute-based Encryption, by Jin Li and Jingwei Li and Xiaofeng Chen and Chunfu Jia and Duncan S. Wong

  Attribute-Based Encryption (ABE) is a promising cryptographic primitive which significantly enhances the versatility of access control mechanisms. Due to the high expressiveness of ABE policies, the computational complexities of ABE key-issuing (by Attribute Authorities (AAs)) and decryption (by eligible users) are getting prohibitively high. Despite that the existing Outsourced ABE solutions are able to offload some intensive computing tasks to a third party, for example, a cloud, so to relieve the local burden of eligible users during decryption, the high computational complexity of the key-issuing at the AAs has yet to be addressed, while an ABE system will continue to grow with more users being included, and with the user revocation being considered in practice which will trigger more key (re-)issuing.

Aiming at tackling the challenges above, for the first time, we propose a Secure Outsourced ABE system, which not only supports secure outsourced decryption, but also provides secure outsourced key-issuing. Unlike the current outsourced ABE systems, our new method offloads all access policy and attribute related operations in the key-issuing process or decryption to a Key Generation Service Provider (KGSP) and a Decryption Service Provider (DSP), respectively, leaving only a constant number of simple operations for the AAs and eligible users to perform locally. Furthermore, we show that both outsourcing processes (to KGSP and to DSP) are secure, namely, the KGSP and the DSP would not be able to recover the keys or decrypt the ciphertexts, respectively.

In addition, we consider the scenario that a KGSP or DSP may be dishonest and could maliciously generate some incorrect returning values rather than following the outsourced operations. Therefore, in this paper, we also propose another ABE construction which allows the AAs and eligible users to check the correctness of outsourced operations in an efficient way. The security of the construction is analyzed under a recently formalized model called Refereed Delegation of Computation (RDoC).



19:17 [Pub][ePrint] On the Complexity of the BKW Algorithm on LWE, by Martin R. Albrecht and Carlos Cid and Jean-Charles Faugère and Robert Fitzpatrick and Ludovic Perret

  In this paper we present a study of the complexity of the Blum-Kalai-Wasserman (BKW) algorithm when applied to the Learning with Errors (LWE) problem, by providing refined estimates for the data and computational effort requirements for solving concrete instances of the LWE problem. We apply this refined analysis to suggested parameters for various LWE-based cryptographic schemes from the literature and, as a result, provide new upper bounds for the concrete hardness of these LWE-based schemes.



19:17 [Pub][ePrint] Efficient Methods for Practical Fully Homomorphic Symmetric-key Encrypton, Randomization and Verification, by Aviad Kipnis and Eliphaz Hibshoosh

  We present high performance non-deterministic fully-homomorphic methods for practical randomization of data (over commutative ring), and symmetric-key encryption of random mod-N data (over ring of reidues mod-N) well suited for crypto applications. These methods secure, for example, the multivariate input or the coefficients of a polynomial function running in an open untrusted environment. We show that random plaintext is the sufficient condition for proof of security for the homomorphic encryption. The efficient nature of the methods - one large-numbers multiplication per encryption and six for the product of two encrypted values - motivates and enables the use of low cost collaborative security platforms for crypto applications such as keyed-hash or private key derivation algorithms. Such a platform is comprised of a low-cost and low performance security element supported by an untrusted high performance server running the homomorpic algorithms. The methods employed may also provide enhanced protection for some existing crypto algorithms against certain attacks. Specifically, it is shown how to secure OSS public-key signature against Pollard attack. Further, we demonstrate how the homomorphic randomization of data can offer protection for an AES-key against side-channel attacks. Finally, the methods provide both fault detection and verification of computed-data integrity.



19:17 [Pub][ePrint] Cryptanalysis and Improvement of a Multi-Receiver Generalized Signcryption Scheme, by Cai-xue Zhou

  Generalized signcryption (GSC) scheme can adaptively work as an encryption scheme, a signature scheme or a signcryption scheme with only one algorithm. It is very suitable for storage-constrained environments. In this paper, we analyze a multi-receiver GSC scheme, and show that it cannot achieve indistinguishability-adaptive chosen ciphertext attack (IND-CCA2) secure in the pure encryption mode and hybrid encryption mode. We further propose a revised version of the scheme, which resolves the security issues of the original scheme without sacrificing its high efficiency and simple design. Our improved scheme can be proved to be IND-CCA2 secure and existentially unforgeable-adaptive chosen message attack (EUF-CMA) under computational Diffie-Hellman (CDH) assumption.



19:17 [Pub][ePrint] Coarse-grained integer - Smooth? Rough? Both!, by Daniel Loebenberger and Michael Nüsken

  We count ]B, C]-grained, k-factor integers which are simultaneously B-rough and C-smooth and have a fixed number k of prime factors. Our aim is to exploit explicit versions of the prime number theorem as much as possible to get good explicit bounds for the count of such integers. This analysis was inspired by certain inner procedures in the general number field sieve. The result should at least provide some insight in what happens there.

We estimate the given count in terms of some recursively defined functions. Since they are still difficult to handle, only another approximation step reveals their orders.

Finally, we use the obtained bounds to perform numerical experiments that show how good the desired count can be approximated for the parameters of the general number field sieve in the mentioned inspiring application.



19:17 [Pub][ePrint] Preimage and Pseudo-Collision Attacks on Step-Reduced SM3 Hash Function, by Gaoli Wang and Yanzhao Shen

  SM3~\\cite{SM3hf} is the Chinese cryptographic hash standard which was announced in 2010 and designed by Wang $et\\ al.$. It is based on the Merkle-Damg\\r{a}rd design and its compression function can be seen as a block cipher used in Davies-Meyer mode. It uses message block of length 512 bits and outputs hash value of length 256 bits.

This paper studies the security of SM3 hash function against preimage attack and pseudo-collision attack. We propose preimage attacks on 29-step and 30-step SM3, and pseudo-preimage attacks on 31-step and 32-step SM3 out of 64 steps. The complexities of these attacks are $2^{245}$ 29-step operations, $2^{251.1}$ 30-step operations, $2^{245}$ 31-step operations and $2^{251.1}$ 32-step operations, respectively. These (pseudo) preimage attacks are all from the first step of the reduced SM3. Meanwhile, these (pseudo) preimage attacks can be converted into pseudo-collision attacks on SM3 reduced to 29 steps, 30 steps, 31 steps and 32 steps with complexities of $2^{122}$, $2^{125.1}$, $2^{122}$ and $2^{125.1}$ respectively. As far as we know, the previously best known preimage attacks on SM3 cover 28 steps (from the first step) and 30 steps (from the 7-th step), and there is no publicly published result on (pseudo) collision attack on SM3.