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

2015-04-01
15:17 [Pub][ePrint] Practical Cryptanalysis of Full Sprout with TMD Tradeoff Attacks, by Muhammed F. Esgin and Orhun Kara

  A new lightweight stream cipher, Sprout, has been presented at FSE 2015. The main concern in the design philosophy of the cipher is to decrease the internal state size without compromising the security against Time-Memory-Data (TMD) tradeoff attacks. In this work, we have mounted a TMD tradeoff attack to Sprout using $2^d$ output bits in $2^{71.7-d}$ encryptions of Sprout along with $2^{d}$ table lookups. The memory complexity is $2^{85-d}$ where $d\\leq 40$. In one instance, it is possible to recover the key in faster than $2^{33}$ encryption time if we have $2^{40}$ bits of keystream output by using tables of 770 Terabytes in total. The offline phase of preparing the tables consists of solving roughly $2^{42}$ system of linear equations with 20 unknowns.



15:17 [Pub][ePrint] Automating Fast and Secure Translations from Type-I to Type-III Pairing Schemes, by Joseph A. Akinyele and Christina Garman and Susan Hohenberger

  Pairing-based cryptography has exploded over the last decade, as this algebraic setting offers good functionality and efficiency. However, there is a huge security gap between how schemes are usually analyzed in the academic literature and how they are typically implemented. The issue at play is that there exist multiple types of pairings: Type-I called \"symmetric\" is typically how schemes are presented and proven secure in the literature, because it is simpler and the complexity assumptions can be weaker; however, Type-III called \"asymmetric\" is typically the most efficient choice for an implementation in terms of bandwidth and computation time.

There are two main complexities when moving from one pairing type to another. First, the change in algebraic setting invalidates the original security proof. Second, there are usually multiple (possibly thousands) of ways to translate from a Type-I to a Type-III scheme, and the \"best\" translation may depend on the application.

Our contribution is the design, development and evaluation of a new software tool, AutoGroup+, that automatically translates from Type-I to Type-III pairings. The output of AutoGroup+ is: (1) \"secure\" provided the input is \"secure\" and (2) optimal based on the user\'s efficiency constraints (excluding software and run-time errors). Prior automation work for pairings was either not guaranteed to be secure or only partially automated and impractically slow. This work addresses the pairing security gap by realizing a fast and secure translation tool.



15:17 [Pub][ePrint] Two Operands of Multipliers in Side-Channel Attack, by Takeshi Sugawara, Daisuke Suzuki, and Minoru Saeki

  The single-shot collision attack on RSA proposed by Hanley et al. is studied focusing on the difference between two operands of multipliers. There are two consequences. Firstly, designing order of operands can be a cost-effective countermeasure. We show a concrete example in which operand order determines success and failure of the attack. Secondly, countermeasures can be ineffective if the asymmetric leakage is considered. In addition to the main results, the attack by Hanley et al. is extended using the signal-processing technique of the big mac attack. An experimental result to successfully analyze an FPGA implementation of RSA with the multiply-always method is also presented.



15:17 [Pub][ePrint] Secret Shared Random Access Machine, by Shlomi Dolev and Yin Li

  Secure and private computations over RAM are preferred over computations with circuits or Turing machines. Secure and private RAM executions become more and more important in the scope avoiding information leakage when executing programs over a single computer as well as over the clouds. In this paper, we propose a distributed scheme for evaluating RAM programs without revealing any information on the computation including the program the data and the result. We use the Shamir secret sharing to share all the program instructions and private string matching technique to ensure the execution of the right instruction sequence. We stress that our scheme obtains information theoretic security and does not rely on any computational hardness assumptions, therefore, gaining indefinite private and secure RAM execution of perfectly unrevealed programs.



15:17 [Pub][ePrint] Fully Secure Unbounded Revocable Attribute-Based Encryption in Prime Order Bilinear Groups via Subset Difference Method, by Pratish Datta and Ratna Dutta and Sourav Mukhopadhyay

  Providing an efficient revocation mechanism for attribute-based encryption (ABE) is of

utmost importance since over time an user\'s credentials may be revealed or expired. All previously

known revocable ABE (RABE) constructions (a) essentially utilize the complete subtree (CS) scheme

for revocation purpose, (b) are bounded in the sense that the size of the public parameters depends

linearly on the size of the attribute universe and logarithmically on the number of users in the

system, and (c) are either selectively secure, which seems unrealistic in a dynamic system such as

RABE, or fully secure but built in a composite order bilinear group setting, which is undesirable from

the point of view of both efficiency and security. This paper presents the first fully secure unbounded

RABE using subset difference (SD) mechanism for revocation which greatly improves the broadcast

efficiency compared to the CS scheme. Our RABE scheme is built on a prime order bilinear group

setting resulting in practical computation cost, and its security depends on the Decisional Linear

assumption.



15:17 [Pub][ePrint] Accelerating Somewhat Homomorphic Evaluation using FPGAs, by Erd\\.{i}n\\c{c} \\\"{O}zt\\\"{u}rk and Yark{\\i}n Dor\\\"{o}z and Berk Sunar and Erkay Sava\\c{s}

  After being introduced in 2009, the first fully homomorphic encryption (FHE) scheme has created significant excitement in academia and industry. Despite rapid advances in the last 6 years, FHE schemes are still not ready for deployment due to an efficiency bottleneck. Here we introduce a custom hardware accelerator optimized for a class of reconfigurable logic to bring LTV based somewhat homomorphic encryption (SWHE) schemes one step closer to deployment in real-life applications. The accelerator we present is connected via a fast PCIe interface to a CPU platform to provide homomorphic evaluation services to any application that needs to support blinded computations. Specifically we introduce a number theoretical transform based multiplier architecture capable of efficiently handling very large polynomials. When synthesized for the Xilinx Virtex 7 family the presented architecture can compute the product of large polynomials in under $6.25$~msec making it the fastest multiplier design of its kind currently available in the literature and is more than 102 times faster than a software implementation. Using this multiplier we can compute a relinearization operation in $526$ msec. When used as an accelerator, for instance, to evaluate the AES block cipher, we estimate a per block homomorphic evaluation performance of $442$~msec yielding performance gains of $28.5$ and $17$ times over similar CPU and GPU implementations, respectively.



15:17 [Pub][ePrint] Security Analysis of Re-Encryption RPC Mix Nets, by Ralf Kuesters and Tomasz Truderung

  Re-Encryption randomized partial checking (RPC) mix nets were introduced by Jakobsson, Juels, and Rivest in 2002 and since then have been employed in prominent modern e-voting systems and in politically binding elections in order to provide verifiable elections in a simple and efficient way. Being one of or even the most used mix nets in practice so far, these mix nets are an interesting and valuable target for rigorous security analysis.

In this paper, we carry out the first formal cryptographic analysis of re-encryption RPC mix nets. We show that these mix nets, with fixes recently proposed by Khazaei and Wikstr{\\\"o}m, provide a good level of verifiability, and more precisely, accountability: cheating mix servers, who try to manipulate the election outcome, are caught with high probability. Moreover, we show that all attacks that would break the privacy of voters\' inputs are caught with a probability of at least $1/4$. In many cases, for example, when penalties are severe or reputation can be lost, adversaries might not be willing to take this risk, and hence, would behave in a way that avoids this risk. Now, for such a class of ``risk-avoiding\'\' adversaries, we show that re-encryption RPC mix nets provide a good level of privacy, even if only one mix server is honest.



15:17 [Pub][ePrint] The Uniform Distribution of Sequences Generated by Iteration of Polynomials, by Emil Lerner

  Consider a collection $f$ of polynomials $f_i(x)$, $i=1, \\ldots,s$, with integer coefficients such that polynomials $f_i(x)-f_i(0)$, $i=1, \\ldots,s$, are linearly independent. Denote by $D_m$ the discrepancy for the set of points $\\left(\\frac{f_1(x) \\bmod m}{m},\\ldots,\\frac{f_s(x) \\bmod m}{p^n}\\right)$ for all $x \\in \\{0,1,\\ldots,m\\}$, where $m=p^n$, $n \\in N$, and $p$ is a prime number. We prove that $D_m\\to 0$ as $n\\to\\infty$, and $D_m

15:17 [Pub][ePrint] Identity-Based Encryption Secure Against Selective Opening Chosen-Ciphertext Attack, by Junzuo Lai and Robert H. Deng and Shengli Liu and Jian Weng and Yunlei Zhao

  Security against selective opening attack (SOA) requires that in a multi-user setting, even if an adversary has access to all ciphertexts from users, and adaptively corrupts some fraction of the users by exposing not only their messages but also the random coins, the remaining unopened messages retain their privacy. Recently, Bellare, Waters and Yilek considered SOA-security in the identity-based setting, and presented the first identity-based encryption (IBE) schemes that are proven secure against selective opening chosen plaintext attack (SO-CPA). However, how to achieve SO-CCA security for IBE is still open.

In this paper, we introduce a new primitive called extractable IBE, which is a hybrid of one-bit IBE and identity-based key encapsulation mechanism (IB-KEM), and define its IND-ID-CCA security notion. We present a generic construction of SO-CCA secure IBE from an IND-ID-CCA secure extractable IBE with ``One-Sided Public Openability\'\'(1SPO), a collision-resistant hash function and a strengthened cross-authentication code. Finally, we propose two concrete constructions of extractable 1SPO-IBE schemes, resulting in the first simulation-based SO-CCA secure IBE schemes without random oracles.



15:17 [Pub][ePrint] Secure Random Linear Code Based Public Key Encryption Scheme RLCE, by Yongge Wang

  As potential post-quantum cryptographic schemes, lattice based encryption schemes

and linear codes based encryption schemes

have received extensive attention in recent years.

Though LLL reduction algorithm has been one of the major cryptanalysis techniques

for lattice based cryptographic systems, cryptanalysis techniques for linear codes

based cryptographic systems are generally scheme specific. In recent years,

several important techniques such as

Sidelnikov-Shestakov attack and filtration attacks have been

developed to crypt-analyze linear codes based encryption schemes.

Though most of these cryptanalysis techniques

are relatively new, they prove to be very powerful and many systems have been broken

using these techniques. Thus it is important to systematically investigate and

design linear code based cryptographic systems that are immune against these attacks.

This paper proposes linear code based encryption schemes RLCE which share

many characteristics with random linear codes. Our analysis shows

that the scheme RLCE is secure against existing attacks and we expect that

the security of the RLCE scheme is equivalent to the hardness of decoding random linear codes.



15:17 [Pub][ePrint] A Note on the Lindell-Waisbard Private Web Search Scheme, by Zhengjun Cao and Lihua Liu

  In 2010, Lindell and Waisbard proposed a private web search scheme for malicious adversaries. At the end of the scheme, each party obtains one search word and query the search engine with the word. We remark that a malicious party could query the search engine with a false word instead of the word obtained. The malicious party can link the true word to its provider if the party publicly complain for the false searching result. To fix this drawback, each party has to broadcast all shares so as to enable every party to recover all search words and query the search engine with all these words.

We also remark that there is a very simple method to achieve the same purpose of private shuffle. When a user wants to privately query the search engine with a word, he can choose another n-1 padding words to form a group of $n$ words and permute these words randomly. Finally, he queries the search engine with these words.