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-10-25
15:17 [Pub][ePrint] Breaking Public Keys - How to Determine an Unknown RSA Public Modulus, by Hans-Joachim Knobloch

  Not surprisingly, the common use of any public key crypto system involves publishing the public key and keeping the private key secret. There are however a few applications where both the private and public key are kept secret, thereby effectively converting a public key crypto algorithm to a symmetric algorithm.

We show that if the RSA cryptosystem is used in such a symmetric application, it is possible to determine the public RSA modulus if the public exponent is known and short, such as 3 or F4=65537, and two or more plaintext/ciphertext (or, if RSA is used for signing, signed value/signature) pairs are known.



15:17 [Pub][ePrint] A Novel Approach for RSA-based Certificateless Signature Scheme, by Nishant Doshi

  In the conventional signature scheme, the sender will sign the message and send it to the receiver, who is verify based on the certificate of the sender (provided by trusted third party prior to communication). However, this lead to a certificate management problem as third party need to maintain all certificates and if there are many third parties (hierarchical). The solution to this problem lead to a certificateless signature scheme in which receiver only requires ID (unique identity) of the sender. The approaches in literatures are based on the bilinear map. However, the time for pairing is more as that of the exponent operation of the RSA (Public Key Cryptography) scheme. Recently, Zhang et al, proposed the RSA-based certificateless scheme. We show that this scheme is insecure and proposed the scheme that overcomes the attack on Zhang et al\'s scheme.



15:17 [Pub][ePrint] An Efficient Three-Party Authenticated Key Exchange Protocol for Mobile-Commerce Environments Using Elliptic Curve Cryptography, by Nishant Doshi

  In the three party authentication key exchange

(3PAKE) protocol, more than two parties can communicate and

set up common shared secret key using the server. Recently,

Tan et al. proposed an enhanced 3PAKE scheme based on

elliptic curve cryptography (ECC) to minimize the operations and

make compatible for mobile commerce environments. However,

Nose showed the scheme of Tan et al. is susceptible to the

impersonation attack and the man-in-middle attack. However, in

this paper we have shown that Tan et al. protocol is susceptible to

the known session-specific temporary information attack and the

clock synchronization attack too. Afterwards, we have proposed

the protocol that withstands against the above mentioned attacks.

In addition, our proposed approach is based on the hash function

in place of the encryption/decryption function that was used in

Tan et al. scheme.



15:17 [Pub][ePrint] Biclique Cryptanalysis of the PRESENT and LED Lightweight Ciphers, by Farzaneh Abed and Christian Forler and Eik List and Stefan Lucks and Jakob Wenzel

  In this paper, we propose the first full-round attacks on the PRESENT and LED lightweight ciphers. In our attacks, we use the independent-biclique approach which has been developed recently. The proposed attacks on PRESENT-80 and PRESENT-128 require $2^{60}$ and $2^{56}$ chosen plaintexts, and have time complexities of $2^{79.54}$ and $2^{127.42}$, respectively. Our attacks on LED-64 and LED-128 need $2^{56}$ and $2^{64}$ chosen plaintexts and the time complexities are equivalent to $2^{63.40}$ and $2^{127.25}$ encryptions.



15:17 [Pub][ePrint] Attribute-Based Encryption for Circuits from Multilinear Maps, by Amit sahai and Brent Waters

  In this work, we provide the first construction of Attribute-Based

Encryption (ABE) for general circuits. Our construction is based on

the existence of multilinear maps. We prove selective security of

our scheme in the standard model under the natural multilinear

generalization of the BDDH assumption. Our scheme achieves both

Key-Policy and Ciphertext-Policy variants of ABE.



15:17 [Pub][ePrint] Factor-4 and 6 (De)compression for Values of Pairings using Trace Maps, by Tomoko Yonemura and Taichi Isogai and Hirofumi Muratani and Yoshikazu Hanatani

  The security of pairing-based cryptosystems relies on the hardness of the discrete logarithm problems in elliptic curves and in finite fields related to the curves, namely, their embedding fields. Public keys and ciphertexts in the pairing-based cryptosystems are composed of points on the curves or values of pairings. Although the values of the pairings belong to the embedding fields, the representation of the field is inefficient in size because the size of the embedding fields is usually larger than the size of the elliptic curves. We show factor-4 and 6 compression and decompression for the values of the pairings with the supersingular elliptic curves of embedding degrees 4 and 6, respectively. For compression, we use the fact that the values of the pairings belong to algebraic tori

that are multiplicative subgroups of the embedding fields. The algebraic tori can be expressed by the affine representation or the trace representation. Although the affine representation allows decompression maps, decompression maps for the trace representation has not been known. In this paper, we propose a trace representation with decompression maps for the characteristics 2 and 3. We first construct efficient decompression maps for trace maps by adding extra information to the trace representation. Our decompressible trace representation with additional information is as efficient as the affine representation is in terms of the costs of compression, decompression and exponentiation, and the size.



15:17 [Pub][ePrint] Improved Impossible Differential Attack on Reduced Version of Camellia-192/256, by Ya Liu and Dawu Gu and Zhiqiang Liu and Wei Li

  As an ISO/IEC international standard, Camellia has been used various cryptographic applications. In this paper, we improve previous attacks on Camellia-192/256 with key-dependent layers $FL/FL^{-1}$ by using the intrinsic weakness of keyed functions. Specifically, we present the first impossible differential attack on 13-round Camellia with $2^{121.6}$ chosen ciphertexts and $2^{189.9}$ 13-round encryptions, while the analysis for the biggest number of rounds in previous results on Camellia-192 worked on 12 rounds. Furthermore, we successfully attack 14-round Camellia-256 with $2^{122.1}$ chosen ciphertexts and $2^{229.3}$ 14-round encryptions. Compared with the previously best known attack on 14-round Camellia-256, the time complexity of our attack is reduced by $2^{8.9}$ times and the data complexity is comparable.



15:17 [Pub][ePrint] Extending Brickell-Davenport Theorem to Non-Perfect Secret Sharing Schemes, by Oriol Farras and Carles Padro

  One important result in secret sharing is Brickell-Davenport Theorem: every ideal perfect secret sharing scheme defines a matroid that is uniquely determined by the access structure. Even though a few attempts have been made, there is no satisfactory definition of ideal secret sharing scheme for the general case, in which non-perfect schemes are considered as well. Without providing another unsatisfactory definition of ideal non-perfect secret sharing scheme, we present a generalization

of Brickell-Davenport Theorem to the general case. After analyzing that result under a new point of view and identifying its combinatorial nature, we present a characterization of the (not necessarily perfect)

secret sharing schemes that are associated to matroids. Some optimality properties of such schemes are discussed.



15:17 [Pub][ePrint] Evaluating User Privacy in Bitcoin, by Elli Androulaki and Ghassan Karame and Marc Roeschlin and Tobias Scherer and Srdjan Capkun

  Bitcoin is quickly emerging as a popular digital payment system. However, in spite of its reliance on pseudonyms, Bitcoin raises a number of privacy concerns due to the fact that all of the transactions that take place are publicly announced in the system.

In this paper, we investigate the privacy guarantees of Bitcoin in the setting where Bitcoin is used as a primary currency for the daily transactions of individuals. More specifically, we evaluate the privacy that is provided by Bitcoin (i) by analyzing the genuine Bitcoin system and (ii) through a simulator that mimics Bitcoin client\'s behavior in the context where Bitcoin is used for all transactions within a university. In this setting, our results show that the profiles of almost 40% of the users can be, to a large extent, recovered even when users adopt privacy measures recommended by Bitcoin. To the best of our knowledge, this is the first work that comprehensively analyzes, and evaluates the privacy implications of Bitcoin. As a by-product, we have designed and implemented the first simulator of Bitcoin; our simulator can be used to model the interaction between Bitcoin users in generic settings.



15:17 [Pub][ePrint] A Novel Permutation-based Hash Mode of Operation FP and the Hash Function SAMOSA, by Souradyuti Paul and Ekawat Homsirikamol and Kris Gaj

  The contribution of the paper is two-fold. First, we design a novel permutation-based hash mode of operation FP, and analyze its security. The FP mode is derived by replacing the hard-to-invert primitive of the FWP mode -- designed by Nandi and Paul, Indocrypt 2010 -- with an easy-to-invert permutation; since easy-to-invert permutations with good cryptographic properties are normally easier to design, and are more efficient than the hard-to-invert functions, the FP mode is more suitable in practical applications than the FWP mode.

We show that any n-bit hash function that uses the FP mode is indifferentiable from a random oracle up to 2^n/2 queries (up to a constant factor), if the underlying 2n-bit permutation is free from any structural weaknesses. Based on our further analysis and experiments, we conjecture that the FP mode is resistant to all non-trivial generic attacks with work less than the brute force, mainly due to its large internal state. We compare the FP mode with other permutation-based hash modes, and observe that it displays the so-far best security/rate trade-off.

To put this into perspective, our second contribution is a proposal for a concrete hash function SAMOSA using the new mode and the $P$-permutations of the SHA-3 finalist Groestl. Based on our analysis we claim that the SAMOSA family cannot be attacked with work significantly less than the brute force. We also provide hardware implementation (FPGA) results for SAMOSA to compare it with the SHA-3 finalists. In our implementations, SAMOSA family consistently beats Groestl, Blake and Skein in the throughput to area ratio. With more efficient underlying permutation, it seems possible to design a hash function based on the FP mode that can achieve even higher performances.



15:17 [Pub][ePrint] Taking proof-based verified computation a few steps closer to practicality (extended version), by Srinath Setty and Victor Vu and Benjamin Braun and Andrew J. Blumberg and Michael Walfish

  We describe Ginger, a built system for unconditional, general-purpose,

and nearly practical verification of outsourced computation. Ginger is

based on Pepper, which uses the PCP theorem and cryptographic techniques

to implement an \\emph{efficient argument} system (a kind of interactive

protocol). Ginger slashes the query size and costs via theoretical

refinements that are of independent interest; broadens the computational

model to include (primitive) floating-point fractions, inequality

comparisons, logical operations, and conditional control flow; and

includes a parallel GPU-based implementation that dramatically reduces

latency.