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



19:17 [Pub][ePrint] A unidirectional conditional proxy re-encryption scheme based on non-monotonic access structure, by Bin Wang

  Recently, Fang et al. [6] introduced an interactive(bidirectional) conditional proxy re-encryption(C-PRE) scheme such that a proxy can only convert ciphertexts that satisfy access policy set by a delegator. Their scheme supports monotonic access policy expressed by \"OR\" and \"AND\" gates. In addition, their scheme is called interactive since generation of re-encryption keys requires interaction between the delegator and delegatee. In this paper, we study the problem of constructing a unidirectional(non-interactive) C-PRE scheme supporting non-monotonic access policy expressed by \"NOT\", \"OR\" and \"AND\" gates. A security model for unidirectional C-PRE schemes is also proposed in this paper. To yield a unidirectional C-PRE scheme supporting non-monotonic access policy, we extend the unidirectional PRE scheme presented by Libert et al. [8] by using the ideas from the non-monotonic attributed based encryption (ABE) scheme presented by Ostrovsky et al. [9]. Furthermore, the security of our C-PRE scheme is proved under the modified 3-weak Decision Bilinear Diffie-Hellman Inversion assumption in the standard model.



19:17 [Pub][ePrint] Practical Covertly Secure MPC for Dishonest Majority - or: Breaking the SPDZ Limits, by Ivan Damgard and Marcel Keller and Enrique Larraia and Valerio Pastro and Peter Scholl and Nigel P. Smart

  SPDZ (pronounced \"Speedz\") is the nickname of the MPC protocol of Damg°ard et al. from Crypto 2012. SPDZ provided various efficiency innovations on both the theoretical and practical sides compared to previous work in the preprocessing model. In this paper we both resolve a number of open problems with SPDZ; and present several

theoretical and practical improvements to the protocol.

In detail, we start by designing and implementing a covertly secure key generation protocol for distributed BGV secret keys. In prior work this was assumed to be provided by a given setup functionality. Protocols for distributingBGV secret keys are likely to be of wider applicability than to the SPDZ protocol alone.

We then construct both a covertly and actively secure preprocessing phase, both of which compare favourably with previous work in terms of efficiency and provable security. We also build a new online phase, which solves a major problem of the SPDZ protocol: namely prior to this work preprocessed data could be used for only one function evaluation and then had to be recomputed from scratch for the next evaluation, while our online phase can support reactive functionalities. This improvement comes mainly from the fact that our construction does not require players to reveal the MAC keys to check correctness of MAC\'d values.

Since our focus is also on practical instantiations, our implementation offloads as much computation as possible into the preprocessing phase, thus resulting in a faster online phase. Moreover, a better analysis of the parameters of the underlying cryptoscheme and a more specific choice of the field where computation is performed allow us to obtain a better optimized implementation. Improvements are also due to the fact that our construction is in the random oracle model, and the practical implementation is multi-threaded.