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

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2013-12-01
19:17 [Pub][ePrint]

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]

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]

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]

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]

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]

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.

2013-11-30
07:17 [Pub][ePrint]

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]

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]

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

07:17 [Pub][ePrint]

Online ciphers encrypt an arbitrary number of plaintext blocks and output ciphertext blocks which only depend on the preceding plaintext blocks. All online ciphers proposed so far are essentially serial, which significantly limits their performance on parallel architectures such as modern general-purpose CPUs or dedicated hardware. We propose the first parallelizable online cipher, COPE. It performs two calls to the underlying block cipher per plaintext block and is fully parallelizable in both encryption and decryption. COPE is proven secure against chosen-plaintext attacks assuming the underlying block cipher is a strong PRP. We then extend COPE to create COPA, the first parallelizable, online authenticated cipher with nonce-misuse resistance. COPA only requires two extra block cipher calls to provide integrity. The privacy and integrity of the scheme is proven secure assuming the underlying block cipher is a strong PRP. Our implementation with Intel AES-NI on a Sandy Bridge CPU architecture shows that both COPE and COPA are about \\textit{5 times faster} than their closest competition: TC1, TC3, and McOE-G. This high factor of advantage emphasizes the paramount role of parallelizability on up-to-date computing platforms.