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

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.

07:17 [Pub][ePrint] Parallelizable and Authenticated Online Ciphers, by Elena Andreeva and Andrey Bogdanov and Atul Luykx and Bart Mennink and Elmar Tischhauser and Kan Yasuda

  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.

07:17 [Pub][ePrint] APE: Authenticated Permutation-Based Encryption for Lightweight Cryptography, by Elena Andreeva and Beg\\\"ul Bilgin and Andrey Bogdanov and Atul Luykx and Bart Mennink and Nicky Mouha and Kan Yasuda

  The domain of lightweight cryptography focuses on cryptographic algorithms for extremely constrained devices. It is very costly to avoid nonce reuse in such environments, because this requires either a secure pseudorandom number generator (PRNG), or non-volatile memory to store a counter. At the same time, a lot of cryptographic schemes actually require the nonce assumption for their security. In this paper, we propose APE as the first permutation-based authenticated encryption scheme that is resistant against nonce misuse. We formally prove that APE is secure, based on the security of the underlying permutation. To decrypt, APE processes the ciphertext blocks in reverse order, and uses inverse permutation calls. APE therefore requires a permutation that is both efficient for forward and inverse calls. We instantiate APE with the permutations of three recent lightweight hash function designs: \\quark, \\photon, and \\spongent. For any of these permutations, an implementation that supports both encryption and decryption requires less than 1.9~kGE and 2.8~kGE for 80-bit and 128-bit security levels, respectively.

07:17 [Pub][ePrint] Improved Authenticity Bound of EAX, and Refinements, by Kazuhiko Minematsu and Stefan Lucks and Tetsu Iwata

  EAX is a mode of operation for blockciphers to implement an authenticated encryption. The original paper of EAX proved that EAX is unforgeable up to $O(2^{n/2})$ data with one verification query. However, this generally guarantees a rather weak bound for the unforgeability under multiple verification queries, i.e., only $(2^{n/3})$ data is acceptable.

This paper provides an improvement over the previous security proof, by showing that EAX is unforgeable up to $O(2^{n/2})$ data with multiple verification queries. Our security proof is based on the techniques appeared in a paper of FSE 2013 by Minematsu et al. which studied the security of a variant of EAX called EAX-prime.

We also provide some ideas to reduce the complexity of EAX while keeping our new security bound. In particular, EAX needs three blockcipher calls and keep them in memory as a pre-processing, and our proposals can effectively reduce three calls to one call. This would be useful when computational power and memory are constrained.

07:17 [Pub][ePrint] A fast integer-based batch full-homomorphic encryption scheme over finite field, by Long Zhang and Qiuling Yue

  In view of the problems that the plaintext space is too small in the existing schemes. In this paper, a new improved scheme is presented by improving the DGHV scheme. The plaintext space of the improved scheme is extended from finite prime field $F_{2}$ in the original scheme to finite prime field $F_{p}$. Combine and apply the method of encryption in the batch encryption scheme was proposed in 2013, and the plaintext space is further extended to finite fields $F_{q}$.

The new improved scheme encrypts the message by applying the modular mathematical operation

and the Chinese remainder theorem, and the security of the scheme is based on the the difficulty of approximate greatest common divisor problem and the spare subset sum problem. The improved scheme we got has the advantages of encrypt fast, and the size of ciphertext is small. So compared with the original scheme, it is better for practical application.

04:17 [Pub][ePrint] ECC-Based Non-Interactive Deniable Authentication with Designated Verifier, by Yalin Chen and Jue-Sam Chou2

  Recently, researchers have proposed many non-interactive deniable authentication (NIDA) protocols. Most of them claim that their protocols possess full deniability. However, after reviewing, we found that they either cannot achieve full deniability, or suffer KCI or SKCI attack; moreover, lack efficiency, because they are mainly based on DLP, factoring problem, or bilinear pairings. Due to this observation, and that ECC provides the security equivalence to RSA and DSA by using much smaller key size, we used Fiat-Shamir heuristic to propose a novel ECC-based NIDA protocol for achieving full deniability as well as getting more efficient than the previous schemes. After security analyses and efficiency comparisons, we confirmed the success of the usage. Therefore, the proposed scheme was more suitable to be implemented in low power mobile devices than the others.

04:17 [Pub][ePrint] Secure Multiparty Computations on BitCoin, by Marcin Andrychowicz and Stefan Dziembowski and Daniel Malinowski and Ɓukasz Mazurek

  itCoin is a decentralized digital currency, introduced in 2008, that has recently gained noticeable popularity. Its main features are: (a) it lacks a central authority that controls the transactions, (b) the list of transactions is publicly available, and (c) its syntax allows more advanced transactions than simply transferring the money. The goal of this paper is to show how these properties of BitCoin can be used in the area of secure multiparty computation protocols (MPCs).

Firstly, we show that the BitCoin system provides an attractive way to construct a version of \"timed commitments\", where the committer has to reveal his secret within a certain time frame, or to pay a fine. This, in turn, can be used to obtain fairness in some multiparty protocols. Secondly, we introduce a concept of multiparty protocols that work \"directly on BitCoin\". Recall that the standard definition of the MPCs guarantees only that the protocol \"emulates the trusted third party\". Hence ensuring that the inputs are correct, and the outcome is respected is beyond the scope of the definition. Our observation is that the BitCoin system can be used to go beyond the standard \"emulation-based\" definition, by constructing protocols that link their inputs and the outputs with the real BitCoin transactions.

As an instantiation of this idea we construct protocols for secure multiparty lotteries using the BitCoin currency, without relying on a trusted authority (one of these protocols uses the BitCoin-based timed commitments mentioned above). Our protocols guarantee fairness for the honest parties no matter how the looser behaves. For example: if one party interrupts the protocol then her money is lost and transferred to the honest participants. Our protocols are practical (to demonstrate it we performed their transactions in the actual BitCoin system), and can be used in real life as a replacement for the online gambling sites. We think that this paradigm can have also other applications. We discuss some of them.

04:17 [Pub][ePrint] Efficient Leakage-Resilient Signature Schemes in the Generic Bilinear Group Model, by Fei Tang, Hongda Li, Qihua Niu, and Bei Liang

  We extend the techniques of Kiltz et al. (in ASIACRYPT 2010) and Galindo et al. (in SAC 2012) to construct two efficient leakage-resilient signature schemes. Our schemes based on Boneh-Lynn-Shacham (BLS) short signature and Waters signature schemes, respectively. Both of them are more efficient than Galindo et al.\'s scheme, and can tolerate leakage of (1-o(1))/2 of the secret key at every signature invocation. The security of the proposed schemes are proved in the generic bilinear group model (additionally, in our first scheme which based on the BLS short signature, a random oracle is needed for the proof).