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

19:17 [Pub][ePrint] A Generic Chosen-Ciphertext Key-Leakage Secure Public Key Encryption Scheme from Hash Proof System, by Rupeng Yang, Qiuliang Xu, Yongbin Zhou, Chengyu Hu, and Zuoxia Yu

  We present a new generic construction of public key encryption (PKE) scheme that is secure against a-posteriori chosen-ciphertext λ-key-leakage attacks (LR-CCA-2 secure) from any universal hash proof system (HPS). Our construction relies only on the existence of universal hash proof systems, which makes our scheme simple, clean and efficient. Furthermore, our construction is a potential way to construct LR-CCA-2 secure PKE scheme from minimal assumption.

19:17 [Pub][ePrint] New Insight into the Isomorphism of Polynomials problem IP1S and its Use in Cryptography, by Gilles Macario-Rat and Jérôme Plût and Henri Gilbert

  This paper investigates the mathematical structure of the ``Isomorphism of Polynomial with One Secret\'\' problem (IP1S). Our purpose is to understand why for practical parameter values of IP1S most random instances are easily solvable (as first observed by Bouillaguet et al.).

We show that the structure of the problem is directly linked to the

structure of quadratic forms in odd and even characteristic. We describe a completely new method allowing to efficiently solve most instances. Unlike previous solving techniques, this is not based upon Gröbner basis computations.

19:17 [Pub][ePrint] Algebraic Properties of the Cube Attack, by Frank-M. Quedenfeld and Christopher Wolf

  Cube attacks can be used to analyse and break cryptographic primitives that have an easy algebraic description. One example for such a primitive is the stream cipher /Trivium.

In this article we give a new framework for cubes that are useful in the cryptanalytic context. In addition, we show how algebraic modelling of a cipher can greatly be improved when taking both cubes and linear equivalences between variables into account. When taking many instances of Trivium, we empirically show a saturation effect, i.e., the number of variables to model an attack will become constant for a given number of rounds. Moreover, we show how to systematically find cubes both for general primitives and also specifically for Trivium. For the latter, we have found all cubes up to round 446 and draw some conclusions on their evolution between rounds. All techniques in this article are general and can be applied to any cipher.

19:17 [Pub][ePrint] Linearly Homomorphic Structure Preserving Signatures: New Methodologies and Applications, by Dario Catalano and Antonio Marcedone and Orazio Puglisi

  At Crypto 2013 Libert, Peters, Joye and Yung introduced the notion of Linearly Homomorphic Structure Preserving Signatures (LHSPS) as a tool to perform verifiable computation on encrypted data and to create constant-size non malleable commitments to group elements. In this paper we improve our understanding of LHSPS by putting forward new methodologies and applications. First, we present a generic transform that converts LHSPS which are secure against weak random message attack (RMA) into ones that achieve full security guarantees. Next we give evidence that RMA secure linearly homomorphic structure preserving signatures are interesting in their own right by showing applications in the context of on-line/off-line homomorphic and network coding signatures. This notably provides what seems to be the first instantiations of homomorphic signatures achieving on-line/off-line efficiency trade-offs.

19:17 [Pub][ePrint] Cryptosystems Resilient to Both Continual Key Leakages and Leakages from Hash Function, by Guangjun Fan and Yongbin Zhou and Chengyu Hu and Dengguo Feng

  Yoneyama et al. introduced Leaky Random Oracle Model (LROM for short) at ProvSec2008 in order to discuss security (or insecurity) of cryptographic schemes which use hash functions as building blocks when leakages from pairs of input and output of hash functions occur in the experiment of security definition. This kind of leakages occurs due to various attacks caused by sloppy usages or implementations. Their results showed that this kind of leakages may threaten the security of some cryptographic scheme. However, an important fact is that such attacks would leak not only pairs of input and output of hash functions, but also the secret key. Therefore, LROM is very limited in the sense that it considers leakages from pairs of input and output of hash functions alone, instead of taking into consideration other possible leakages from the secret key simultaneously. On the other hand, many recent leakage models mainly concentrate on leakages from the secret key and ignore leakages from hash functions for a cryptographic scheme exploiting hash functions. This is a weakness of these leakage models and there exist some schemes in these leakage models but is not secure any more when leakages from hash functions occur.

In this paper, we present an augmented model of both LROM and some leakage models. In our new model, both the secret key and pairs of input and output of hash functions can be leaked. Furthermore, the secret key can be leaked continually during the whole lifecycle of a cryptographic scheme. Hence, our new model is more universal and stronger than LROM and some leakage models (e.g. only computation leaks model and bounded memory leakage model). As an application example, we also present a public key encryption scheme which is provably IND-CCA secure in our new model.

19:17 [Pub][ePrint] Fully, (Almost) Tightly Secure IBE from Standard Assumptions, by Jie Chen and Hoeteck Wee

  We present the first fully secure Identity-Based Encryption scheme

(IBE) from the standard assumptions where the security loss depends

only on the security parameter and is independent of the number of

secret key queries. This partially answers an open problem posed by

Waters (Eurocrypt 2005). Our construction combines Waters\' dual

system encryption methodology (Crypto 2009) with the Naor-Reingold

pseudo-random function (J. ACM, 2004) in a novel way. The security

of our scheme relies on the DLIN assumption in prime-order groups.

19:17 [Pub][ePrint] Group Signature with relaxed-privacy and revocability for VANET, by Mohammad Saiful Islam Mamun and Atsuko Miyaji

  This paper adapts a new group signature (GS) scheme to

the specific needs of certain application e.g., a vehicular adhoc network (VANET). Groth GS is the first efficient GS scheme in the BSZ-model with security proofs in the standard model. We modify the Groth GS in order to meet a restricted, but arguably sufficient set of privacy proper-ties. Although there are some authentication schemes using GS none of them satisfy all the desirable security and privacy properties. Either they follow GSs that rely on Random Oracle Model, or unable to satisfy potential application requirements. In particular, link management which allows any designated entities to link messages, whether they are coming from the same member or a certain group of members without revealing their identities; opening soundness that prevents malicious accusations by the opener against some honest member of the group; revocation system that privileges from fraudulent member like the traditional Public Key infrastructure (PKI). In order to achieve the aforementioned security properties together, we propose a new GS model where linkability, sound

opening and revocability properties are assembled in a single scheme. The novelty of our proposal stems from extending the Groth GS by relaxing strong privacy properties to a scheme with a lightly lesser privacy in order to fit an existing VANET application requirements. In addition, we partially minimize the Groth GS scheme to expedite efficiency.

07:17 [Pub][ePrint] Tree Based Symmetric Key Broadcast Encryption, by Sanjay Bhattacherjee and Palash Sarkar

  The most influential broadcast encryption (BE) scheme till date was introduced in 2001 by Naor, Naor and Lotspiech (NNL) and is based on binary trees. This paper generalizes the ideas of NNL to obtain BE schemes based on $k$-ary trees for any $k\\geq 2$. The treatment is uniform across all $k$ and essentially provides a single scheme which is parameterized by the arity of the underlying tree. We perform an extensive analysis of the header length and user storage of the scheme. It is shown that for a $k$-ary tree with $n$ users out of which $r$ are revoked, the maximum header length is $\\min(2r-1,n-r,\\lceil n/k\\rceil)$. An expression for the expected header length is obtained and it is shown that the expression can be evaluated in $O(r\\log n)$ time. Experimental results indicate that for values of $r$ one would expect in applications such as pay TV systems, the average header length decreases as $k$ increases. The number of keys to be stored by any user is shown to be at most $(\\chi_k-2)\\ell_0(\\ell_0+1)/2$, where $\\ell_0=\\lceil\\log_k n\\rceil$ and $\\chi_k$ is the number of cyclotomic cosets modulo $2^k-1$. In particular, when the number of users is more than $1024$, we prove that the user storage required for $k=3$ is less than that of $k=2$. For higher values of $k$, the user storage is greater than that for binary trees. The option of choosing the value of $k$ provides a designer of a BE system with a wider range of trade-offs between average header length and user storage.

07:17 [Pub][ePrint] Wide-weak Privacy Preserving RFID Mutual Authentication Protocol, by Raghuvir Songhela and Manik Lal Das

  Radio Frequency IDentification (RFID) systems are gaining enormous

interests at industry due to their vast applications such as supply chain, access control, inventory, transport, health care and home appliances. Although tag identification is the primary security goal of an RFID system, privacy issue is equally, even more, important concern in RFID system because of pervasiveness of RFID tags. Over the years, many protocols have been proposed for RFID tags\' identification using different cryptographic primitives. It has been observed that most of them provide tags\' identification, but they fail to preserve tags\' privacy. It has been also proven that public-key primitives are essential for strong privacy and security

requirements in RFID systems. In this paper, we present a mutual authentication protocol for RFID systems using elliptic curves arithmetic.

Precisely, the proposed protocol provides narrow-strong and wide-weak

privacy and resists tracking attacks under standard complexity assumption. The protocol is compared with related works and found efficient in comparison to others.

07:17 [Pub][ePrint] Improvement of Lin-Tzeng Solution to Yao\'s Millionaires Problem and Its Cheating Advantage Analysis, by Zhengjun Cao and Lihua Liu

  In 2005, Lin and Tzeng proposed a solution to Yao\'s Millionaires problem in the setting of semi-honest parties. At the end of the protocol only the party (Alice) who is responsible for setting up the system parameters knows the outcome. It does not specify how to have the other party (Bob) know the result. In this note, we present an improvement of the Lin-Tzeng solution. It requires that Alice and Bob alternately perform the original protocol twice. Under the reasonable assumption that a participator does not deviate from the prescribed steps before he/she obtains the outcome, Alice and Bob can almost simultaneously obtain the result. To the best of our knowledge, it is the first time to show that one participator has only an advantage of $\\mbox{ln}\\,n/n$ possibility to cheat the other in the reasonable setting.

07:17 [Pub][ePrint] Proofs of Data Possession and Retrievability Based on MRD Codes, by Shuai Han and Shengli Liu and Kefei Chen and Dawu Gu

  Proofs of Data Possession (PoDP) scheme is essential to data outsourcing. It provides an efficient audit to convince a client that his/her file is available at the storage server, ready for retrieval when needed. An updated version of PoDP is Proofs of Retrievability (PoR), which proves the client\'s file can be recovered by interactions with the storage server. We propose a PoDP/PoR scheme based on Maximum Rank Distance (MRD) codes. The client file is encoded block-wise to generate homomorphic tags with help of an MRD code. In an audit, the storage provider is able to aggregate the blocks and tags into one block and one tag, due to the homomorphic property of tags. The algebraic structure of MRD codewords enables the aggregation to be operated over a binary field, which simplifies the computation of storage provider to be the most efficient XOR operation. We also prove two security notions, unforgeability served for PoDP and soundness served for PoR with properties of MRD codes. Meanwhile, the storage provider can also audit itself to locate and correct errors in the data storage to improve the reliability of the system, thanks to the MRD code again.