International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) 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).

09:17 [Pub][ePrint] An Efficient Homomorphic Encryption Protocol for Multi-User Systems, by Liangliang Xiao and Osbert Bastani and I-Ling Yen

  The homomorphic encryption problem has been an open one for three decades. Recently, Gentry has proposed a full solution. Subsequent works have made improvements on it. However, the time complexities of these algorithms are still too high for practical use. For example, Gentry\'s homomorphic encryption scheme takes more than 900 seconds to add two 32 bit numbers, and more than 67000 seconds to multiply them. In this paper, we develop a non-circuit based symmetric-key homomorphic encryption scheme. It is proven that the security of our encryption scheme is equivalent to the large integer factorization problem, and it can withstand an attack with up to m ln⁡poly⁡(λ) chosen plaintexts for any predetermined m, where λ is the security parameter. Multiplication, encryption, and decryption are almost linear in mλ, and addition is linear in mλ. Performance analyses show that our algorithm runs multiplication in 108 milliseconds and addition in a tenth of a millisecond for λ=1024 and m=16.

We further consider practical multiple-user data-centric applications. Existing homomorphic encryption schemes only consider one master key. To allow multiple users to retrieve data from a server, all users need to have the same key. In this paper, we propose to transform the master encryption key into different user keys and develop a protocol to support correct and secure communication between the users and the server using different user keys. In order to prevent collusion between some user and the server to derive the master key, one or more key agents can be added to mediate the interaction.

09:17 [Pub][ePrint] A Multivariate based Threshold Ring Signature Scheme, by Albrecht Petzoldt and Stanislav Bulygin and Johannes Buchmann

  In \\cite{SS11}, Sakumoto et al. presented a new multivariate identification scheme, whose security is based solely on the MQ-Problem of solving systems of quadratic equations over finite fields. In this paper we extend this scheme to a threshold ring identification and signature scheme. Our scheme is the first multivariate scheme of this type and generally the first multivariate signature scheme with special properties. Despite the fact that we need more rounds to achieve given levels of security, the signatures are at least twice shorter than those obtained by other post-quantum (e.g. code based) constructions. Furthermore, our scheme offers provable security, which is quite a rare fact in multivariate cryptography.

09:17 [Pub][ePrint] The BlueJay Ultra-Lightweight Hybrid Cryptosystem , by Markku-Juhani O. Saarinen

  We report on the development of BlueJay, a

hybrid Rabin-based public key encryption cryptosystem that

is suitable for ultra-lightweight (total 2000-3000 GE) platforms

such as microsensors and RFID authentication tags. The design

is related to authors\' Passerine and the Oren-Feldhofer WIPR

proposals, but is suitable to a wider array of applications.

The encryption mechanism is significantly faster and the

implementation more lightweight than RSA (even with public

exponent 3) and ECC with the same security level. Hardware

implementations of the asymmetric encryption component of

the hybrid cryptosystem require less than a thousand gate

equivalents in addition to the memory storage required for

the payload and public key data. An inexpensive, milliscale

MCU SoC BlueJay implementation is reported and compared

to RSA-AES on the same platform. The private key operation

(not performed by the light-weight device but by the sensor

network base station or a data acquisition reader) has roughly

the same complexity as the RSA private key operation.

09:17 [Pub][ePrint] Multi-Instance Security and its Application to Password-Based Cryptography, by Mihir Bellare and Stefano Tessaro and Thomas Ristenpart

  This paper develops a theory of multi-instance (mi) security and

applies it to provide the first proof-based support for the classical

practice of salting in password-based cryptography. Mi-security comes

into play in settings (like password-based cryptography) where it is

computationally feasible to compromise a single instance, and provides

a second line of defense, aiming to ensure (in the case of passwords,

via salting) that the effort to compromise all of some large number

$m$ of instances grows linearly with m. The first challenge is

definitions, where we suggest LORX-security as a good metric for mi

security of encryption and support this claim by showing it implies

other natural metrics, illustrating in the process that even lifting

simple results from the si setting to the mi one calls for new

techniques. Next we provide a composition-based framework to transfer

standard single-instance (si) security to mi-security with the aid of

a key-derivation function. Analyzing password-based KDFs from the

PKCS#5 standard to show that they meet our indifferentiability-style

mi-security definition for KDFs, we are able to conclude with the

first proof that per password salts amplify mi-security as hoped in

practice. We believe that mi-security is of interest in other domains

and that this work provides the foundation for its further theoretical

development and practical application.

09:17 [Pub][ePrint] On The Security of One-Witness Blind Signature Schemes, by Foteini Baldimtsi and Anna Lysyanskaya

  Blind signatures have proved an essential building block for applications that protect privacy while

ensuring unforgeability, i.e., electronic cash and electronic voting. One of the oldest, and most ecient blind

signature schemes is the one due to Schnorr that is based on his famous identication scheme. Although it

was proposed over twenty years ago, its unforgeability remains an open problem, even in the random-oracle

model. In this paper, we show that current techniques for proving security in the random oracle model do not

work for the Schnorr blind signature. Our results generalize to other important blind signatures, such as the

one due to Brands. Brands\' blind signature is at the heart of Microsoft\'s newly implemented UProve system,

which makes this work relevant to cryptographic practice as well.

09:17 [Pub][ePrint] Beyond the Limitation of Prime-Order Bilinear Groups, and Round Optimal Blind Signatures, by Jae Hong Seo and Jung Hee Cheon

  At Eurocrypt 2010, Freeman proposed a transformation from pairing-based schemes in composite-order bilinear groups to equivalent ones in prime-order bilinear groups. His transformation can be applied to pairing-based cryptosystems exploiting only one of two properties of composite-order bilinear groups: cancelling and projecting. At Asiacrypt 2010, Meiklejohn, Shacham, and Freeman showed that prime-order bilinear groups according to Freeman\'s construction cannot have two properties simultaneously except negligible probability and, as an instance of implausible conversion, proposed a (partially) blind signature scheme whose security proof exploits both the cancelling and projecting properties of composite-order bilinear groups.

In this paper, we invalidate their evidence by presenting a security proof of the prime-order version of their blind signature scheme. Our security proof follows a different strategy and exploits only the projecting property. Instead of the cancelling property, a new property, that we call {\\em translating}, on prime-order bilinear groups plays an important role in the security proof, whose existence was not known in composite-order bilinear groups. With this proof, we obtain a $2$-move (i.e., round optimal) (partially) blind signature scheme (without random oracle) based on the decisional linear assumption in the common reference string model, which is of independent interest.

As the second contribution of this paper, we construct prime-order bilinear groups that possess both the cancelling and projecting properties at the same time by considering more general base groups. That is, we take a rank $n$ $\\zp$-submodule of $\\zp^{n^2}$, instead of $\\zp^n$, to be a base group $G$, and consider the projections into its rank 1 submodules. We show that the subgroup decision assumption on this base group $G$ holds in the generic bilinear group model for $n=2$, and provide an efficient membership-checking algorithm to $G$, which was trivial in the previous setting.

Consequently, it is still open whether there exists a cryptosystem on composite-order bilinear groups that cannot be constructed on prime-order bilinear groups.

09:17 [Pub][ePrint] Using Symmetries in the Index Calculus for Elliptic Curves Discrete Logarithm, by Jean-Charles Faugère and Pierrick Gaudry and Louise Huot and Guénaël Renault

  In 2004, an algorithm is introduced to solve the DLP for elliptic

curves defined over a non prime finite field $\\F_{q^n}$. One of the

main steps of this algorithm requires decomposing points of the curve

$E(\\F_{q^n})$ with respect to a factor base, this problem is denoted PDP. In this paper, we will apply this algorithm to the case of Edwards curves, the well known family of elliptic curves that allow faster arithmetic as shown by Bernstein and Lange. More precisely, we show how to take advantage of some symmetries of twisted Edwards and

twisted Jacobi intersections curves to gain an exponential factor

$2^{3 (n-1)}$ to solve the corresponding PDP. Practical experiments

supporting the theoretical result are also given. For instance, the

complexity of solving the ECDLP for twisted Edwards curves defined

over $\\F_{q^5}$, with $q\\approx2^{64}$, is supposed to be $2^{160}$

operations in $E(\\F_{q^5})$ using generic algorithms compared to

$2^{127}$ operations (multiplication of two $32$ bits words) with

our method. For these parameters the PDP is untractable with the

original algorithm.

The main tool to achieve these results relies on the use of the

symmetries during the polynomial system solving step. Also, we use a

recent work on a new strategy for the change of ordering of Gröbner

basis which provides a better heuristic complexity of the total

solving process.

09:17 [Pub][ePrint] Aggregate Signcryption, by Alexander W. Dent

  Signcryption schemes provide an efficient messaging system for data that needs to be sent with data confidentiality, data integrity and data origin authentication. However, the bandwidth overhead for the use of signcryption in a network in which a large number of messages need to be sent may be high. Motivated by aggregate signature schemes, we propose the concept of an aggregate signcryption scheme. An aggregate signcryption scheme allows distinct signcryption ciphertexts intended for the same recipient to be merged into a single signcryption ciphertext of smaller size without losing any of their security guarantees. This has the potential to provide significant bandwidth savings. We propose security models for this scheme, analyse the trivial generic constructions, propose an efficient new scheme, and analyse the bandwidth requirements of these schemes for a practical distributed database application.

08:59 [Event][New] Provable Privacy Workshop

  Submission: 4 May 2012
Notification: 1 June 2012
From July 9 to July 10
Location: Vigo, Spain
More Information:

07:49 [News] CryptoDB updates

  CryptoDB has been updated with best paper awards, coauthor relationships, and DOIs.

21:17 [Pub][ePrint] Replay attacks that violate ballot secrecy in Helios, by Ben Smyth

  Helios 2.0 is a web-based end-to-end verifiable electronic voting system, suitable for use in low-coercion environments. In this paper we identify a vulnerability in Helios which allows an adversary to compromise the privacy of voters whom cast abstention votes. The vulnerability can be attributed to the absence of ballot independence and the use of homomorphic ElGamal encryption, in particular, these properties can be exploited by an adversary to construct a ballot related to an abstention vote cast by an honest voter and this ballot can be submitted by a corrupt voter to influence the election outcome, thereby introducing information that can be used to violate privacy. We demonstrate the attack by breaking privacy in a mock election using the current Helios implementation. It is unlikely that the vulnerability will be exploited in a real-world election and therefore our results are largely theoretical. Nonetheless, we cannot expect any computational proofs of ballot secrecy without fixing this vulnerability and, moreover, the attack methodology may be of interest -- in particular, it could represent a viable threat to existing protocols in the literature -- thus providing motivation to report these results.