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-04-13
09:17 [Pub][ePrint] On the Security of an Improved Password Authentication Scheme Based on ECC, by Ding Wang and Chun-guang Ma

  The design of secure remote user authentication schemes for mobile applications is still an open and quite challenging problem, though many schemes have been published lately. Recently, Islam and Biswas pointed out that Lin and Hwang et al.\'s password-based authentication scheme is vulnerable to various attacks, and then presented an improved scheme based on elliptic curve cryptography (ECC) to overcome the drawbacks. Based on heuristic security analysis, Islam and Biswas claimed that their scheme is secure and can withstand all related attacks. In this paper, however, we show that Islam and Biswas\'s scheme cannot achieve the claimed security goals and report its flaws: (1) It is vulnerable to offline password guessing attack, stolen verifier attack and denial of service (DoS) attack; (2) It fails to preserve user anonymity. The cryptanalysis demonstrates that the scheme under study is unfit for practical use.



09:17 [Pub][ePrint] Security Analysis and Enhancement for Prefix-Preserving Encryption Schemes, by Liangliang Xiao and I-Ling Yen

  Prefix-preserving encryption (PPE) is an important type of encryption scheme, having a wide range of applications, such as IP addresses anonymization, prefix-matching search, and rang search. There are two issues in PPE schemes, security proof and single key requirement.

Existing security proofs for PPE only reduce the security of a real PPE scheme to that of the ideal PPE object by showing their computational indistinguishability \\cite{Ama07,Xu02}. Such security proof is incomplete since the security of the ideal encryption object is unknown. Also, existing prefix-preserving encryption schemes only consider a single encryption key, which is infeasible for a practical system with multiple users (Implying that all users should have the single encryption key in order to encrypt or decrypt confidential data).

In this paper we develop a novel mechanism to analyze the security of the ideal PPE object. We follow the modern cryptographic approach and create a new security notion IND-PCPA. Then, we show that such weakened security notion is necessary and the ideal PPE object is secure under IND-PCPA.

We also design a new, security-enhanced PPE protocol to support its use in multi-user systems, where no single entity in the system knows the PPE key. The protocol secret shares and distributes the PPE key to a group of key agents and let them ``distributedly encrypt\'\' critical data. We develop a novel distributed PPE algorithm and the corresponding request and response protocols. Experimental results show that the protocol is feasible in practical systems.



09:17 [Pub][ePrint] Extending Order Preserving Encryption for Multi-User Systems, by Liangliang Xiao and I-Ling Yen and Dung T. Huynh

  Several order preserving encryption (OPE) algorithms have been developed in the literature to support search on encrypted data. However, existing OPE schemes only consider a single encryption key, which is infeasible for a practical system with multiple users (implying that all users should have the single encryption key in order to encrypt or decrypt confidential data). In this paper, we develop the first protocols, DOPE and OE-DOPE, to support the use of OPE in multi-user systems. First, we introduce a group of key agents into the system and invent the DOPE protocol to enable \"distributed encryption\" to assure that the OPE encryption key is not known by any entity in the system. However, in DOPE, if a key agent is compromised, the share of the secret data that is sent to this key agent is compromised. To solve the problem, we developed a novel oblivious encryption (OE) protocol based on the oblivious transfer concept to deliver and encrypt the shares obliviously. Then, we integrate it with DOPE to obtain the OE-DOPE protocol. Security of OE-DOPE is further enhanced with additional techniques. Both DOPE and OE-DOPE can be used with any existing OPE algorithms while retaining all the advantages of OPE without requiring the users to share the single encryption key, making the OPE approach feasible in practical systems.



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.