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

2013-12-29
13:17 [Pub][ePrint] Theoretical Bitcoin Attacks with less than Half of the Computational Power (draft), by Lear Bahack

  A widespread security claim of the Bitcoin system, presented in the original Bitcoin whitepaper, states that the security of the system is guaranteed as long as there is no attacker in possession of half or more of the total computational power used to maintain the system. This claim, however, is proved based on theoretically flawed assumptions.

In the paper we analyze two kinds of attacks based on two theoretical flaws: the Block Discarding Attack and the Difficulty Raising Attack. We argue that the current theoretical limit of attacker\'s fraction of total computational power essential for the security of the system is in a sense not $\\frac{1}{2}$ but a bit less than $\\frac{1}{4}$, and outline proposals for protocol change that can raise this limit to be as close to $\\frac{1}{2}$ as we want.

The basic idea of the Block Discarding Attack has been noted as early as 2010, and lately was independently though-of and analyzed by both author of this paper and authors of a most recently pre-print published paper. We thus focus on the major differences of our analysis, and try to explain the unfortunate surprising coincidence. To the best of our knowledge, the second attack is presented here for the first time.



13:17 [Pub][ePrint] How to Fake Auxiliary Input, by Dimitar Jetchev and Krzysztof Pietrzak

  Consider a joint distribution $(X,A)$ on a set ${\\cal X}\\times\\{0,1\\}^\\ell$. We show that for any family ${\\cal F}$ of distinguishers $f \\colon {\\cal X} \\times \\{0,1\\}^\\ell \\rightarrow \\{0,1\\}$, there exists a simulator $h \\colon {\\cal X} \\rightarrow \\{0,1\\}^\\ell$ such that

\\begin{enumerate}

\\item no function in ${\\cal F}$ can distinguish $(X,A)$ from $(X,h(X))$ with advantage $\\epsilon$,

\\item $h$ is only $O(2^{3\\ell}\\epsilon^{-2})$ times less efficient than the functions in ${\\cal F}$.

\\end{enumerate}

For the most interesting settings of the parameters (in particular, the cryptographic case where $X$ has superlogarithmic min-entropy, $\\epsilon > 0$ is negligible and ${\\cal F}$ consists of circuits of polynomial size), we can make the simulator $h$ \\emph{deterministic}.

As an illustrative application of this theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt\'09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES.

Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem.



13:17 [Pub][ePrint] A new class of hyper-bent functions and Kloosterman sums, by Chunming Tang, Yanfeng Qi

  This paper is devoted to the characterization of hyper-bent functions.

Several classes of hyper-bent functions have been studied, such as

Charpin and Gong\'s $\\sum\\limits_{r\\in R}\\mathrm{Tr}_{1}^{n}

(a_{r}x^{r(2^m-1)})$ and Mesnager\'s $\\sum\\limits_{r\\in R}\\mathrm{Tr}_{1}^{n}(a_{r}x^{r(2^m-1)})

+\\mathrm{Tr}_{1}^{2}(bx^{\\frac{2^n-1}{3}})$, where $R$ is a set of representations of the cyclotomic

cosets modulo $2^m+1$ of full size $n$ and $a_{r}\\in \\mathbb{F}_{2^m}$.

In this paper, we generalize their results and consider a class of Boolean functions of the form $\\sum_{r\\in R}\\sum_{i=0}^{2}Tr^n_1(a_{r,i}x^{r(2^m-1)+\\frac{2^n-1}{3}i})

+Tr^2_1(bx^{\\frac{2^n-1}{3}})$, where $n=2m$, $m$ is odd, $b\\in\\mathbb{F}_4$, and $a_{r,i}\\in \\mathbb{F}_{2^n}$.

With the restriction of $a_{r,i}\\in \\mathbb{F}_{2^m}$, we present the characterization of hyper-bentness of these functions with character sums. Further, we reformulate this characterization in terms of the number of points on

hyper-elliptic curves. For some special cases, with the help of Kloosterman sums and cubic sums, we determine the characterization for some hyper-bent functions including functions with four, six and ten traces terms. Evaluations of Kloosterman sums at three general points are used in the characterization. Actually, our results can generalized to the general

case: $a_{r,i}\\in \\mathbb{F}_{2^n}$. And we explain this for characterizing binomial, trinomial and quadrinomial hyper-bent functions.



13:17 [Pub][ePrint] A Unified Security Model of Authenticated Key Exchange with Specific Adversarial Capabilities, by Weiqiang Wen and Libin Wang

  The most widely accepted models in the security proofs of Authenticated Key Exchange protocols are the Canetti-Krawczyk model and the extended Canetti-Krawczyk model. They are shown to be incomparable due to the subtleties that they admit different adversarial queries and the definitions of the queries are not specific and strict enough to allow a rigorous comparison be made. Concerning the security of one-round implicitly authenticated Diffie-Hellman key exchange protocols, we present a stronger security model that characterizes specific adversarial capabilities and encompass the Ephemeral Key Reveal and the Session-State Reveal simultaneously. To demonstrate the usability of our model, a new protocol based on the OAKE protocol is proposed, which satisfies the presented stronger security notion and at the same time attains high efficiency as the OAKE protocol. The protocol is proven secure in random oracle model under the gap Diffie-Hellman assumption.



13:17 [Pub][ePrint] PRE^{+}: Dual of Proxy Re-encryption and Its Application, by Xu An Wang and Yunlong Ge and Xiaoyuan Yang

  In Eurocrypt\'98, Blaze et al. introduced the concept of proxy re-encryption (PRE). It allows a semi-trusted proxy to convert a ciphertext originally intended for Alice into one which

can be decrypted by Bob, without the proxy knowing the corresponding plaintext. PRE has found many applications, such as in encrypted e-mail forwarding[8], distributed secure file systems[1,2], multicast[10] cloud computation etc. However, all the PRE schemes until now require the delegator (or the delegator and the delegatee cooperatively) to generate the re-encryption keys. We observe

that this is not the only way to generate the re-encryption keys, the encrypter also has the ability to generate re-encryption keys. Based on this observation, we introduce a new primitive: PRE^{+},

which is almost the same as the traditional PRE except the re-encryption keys generated by the encrypter. Interestingly, this PRE^{+} can be viewed as the dual of the traditional PRE. Compared

with PRE, PRE can easily achieve the non-transferable property and message-level based fine-grained delegation, while these two properties are very desirable in practical applications. We first

categorize PRE^{+} as the single-hop and multi-hop variant and discuss its potential applications, then we give the definition and security model for the single-hop PRE^{+}, construct a concrete scheme and

prove its security. Finally we conclude our paper with many interesting open problems.



13:17 [Pub][ePrint] Poly-Many Hardcore Bits for Any One-Way Function, by Mihir Bellare and Stefano Tessaro

  We show how to extract an arbitrary polynomial number of simultaneously hardcore bits from any one-way function. Our construction is based on differing-input obfuscation.



13:17 [Pub][ePrint] General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction, by Akinori Kawachi and Yoshio Okamoto and Keisuke Tanaka and Kenji Yasunaga

  We provide a general construction of a rational secret-sharing

protocol in which the secret can be reconstructed in expected three rounds.

Our construction converts any rational secret-sharing protocol

to a protocol with an expected three-round reconstruction in a black-box manner.

Our construction works in synchronous but non-simultaneous channels,

and preserves a strict Nash equilibrium of the original protocol.

Combining with an existing protocol,

we obtain a rational secret-sharing protocol

that achieves a strict Nash equilibrium with the optimal coalition resilience

of $\\ceil{\\frac{n}{2}}-1$ for expected constant-round protocols,

where $n$ is the number of players.

Although the coalition resilience of $\\ceil{\\frac{n}{2}}-1$ is shown to be optimal

as long as we consider constant-round protocols,

we circumvent this limitation by considering players

who do not prefer to reconstruct \\emph{fake} secrets.

By assuming such players,

we construct an expected constant-round protocol that achieves a strict Nash equilibrium

with coalition resilience of $n-1$.

We also extend our construction to a protocol that preserves \\emph{immunity}

to unexpectedly behaving (or malicious) players.

Then we obtain a protocol that achieves a Nash equilibrium

with coalition resilience of $\\ceil{\\frac{n}{2}}-t-1$

in the presence of $t$ unexpectedly behaving players for any constant $t \\geq 1$.

The same protocol also achieves a strict Nash equilibrium in the absence of malicious players.





2013-12-27
13:37 [Job][New] Research Fellow, University of Tartu, Estonia

  Coding and Cryptography Group at the University of Tartu, Estonia, is looking for a research fellow for a project on design and decoding of LDPC codes. The ideal candidate will have strength in one or more of the following areas:

• LDPC codes and iterative decoding algorithms

• Optimization methods applied to error correction

• Mathematical foundations of coding theory

• Any area related to coding theory

The project is a collaboration with the University of Bergen, Norway, and the University of Valladolid, Spain. Salary is at least 2000 euro per month before taxes plus social benefits, depending on qualification and experience. Some travel money will also be provided. Cost of living in Estonia is quite low, see e.g. http://www.expatistan.com/cost-of-living. Employment contract is for two years.

A successful candidate should:

• Hold a Ph.D. degree

• Have a strong background in coding theory or a related field

• Have an international publication record at outstanding venues

To apply, please submit the following documents (by email):

• Application letter

• Research statement

• Curriculum vitae

• Publication list

• Document about academic degree, if available

• Two letters of reference (make sure they reach us by the application deadline)

Deadline for applications: 1 February 2014

Do not hesitate to contact us in case of questions.





2013-12-20
16:48 [Job][New] Fully funded Ph.D., Ecole normale supérieure (Paris Area, France)

  The objective of this thesis is the forensic reconstruction of partially erased data of various types. The problem that we will tackle is formalized as follows: We consider a data object instance as the result of a function F(t,r) where t encodes the objet type and r is a random number. The OS can create objects, erase them or update them. Erasure is done by forgetting the object’s reference and hence implicitly recycling the space on which it was written. The problem consists in reconstructing algorithmically erased data objects of various types and modeling the conditions under which various assortments of types subject to a given number of rewriting cycles can still be recovered. The methods that will be developed will subsequently be applied to iOS and Android.

The candidate should have solid programming and algorithmic skills. Prior knowledge of reverse engineering tools such as IDA Pro is a plus. The candidate will interact with zero-day exploit hunters and physical reverse engineering experts and will have access to very advanced computing and forensic facilities. This proposal is reserved to French nationals only and is fully funded.

Interested candidates should contact directly david.naccache (at) ens.fr

16:17 [Pub][ePrint] Multiple-Use Transferable E-Cash , by Pratik Sarkar

  Ecash is a concept of electronic cash which would allow users to carry money in form of digital coins. Transaction can be done both offline and online in absence of a third party/financial institution. This paper proposes an offline model which supports multiple usage of transferable ecoin. The protocol is based on RSA, digital signature and a two-step encryption process. In this two step encryption, the user account details are encrypted in the coin using unique numbers in each step. The first encryption takes place during the successful receipt of the coin, where a receive end number is used for encryption,which is unique for every receipt. The second step of encryption takes place during successful spending of the coin,where a spending end receive number is used for encryption, which is unique for every spenfing of the coin. These two unique numbers comprise the major part of encryption in this model, prevents double spending and preserves user anonymity.



16:17 [Pub][ePrint] Weaknesses in a Recently Proposed RFID Authentication Protocol, by Mete Akg\\\"{u}n, M. Ufuk \\c{C}a\\v{g}layan

  Many RFID authentication protocols have been proposed to provide desired security and privacy level for RFID systems. Almost all of these protocols are based symmetric cryptography because of the limited resources of RFID tags. Recently Cheng et. al have been proposed an RFID security protocol based on chaotic maps. In this paper, we analyze the security of this protocol and discover its vulnerabilities. We firstly present a de-synchronization attack in which a passive adversary makes the shared secrets out-of-synchronization by eavesdropping just one protocol session. We secondly present a secret disclosure attack in which a passive adversary extracts secrets of a tag by eavesdropping just one protocol session. An adversary having the secrets of the tag can launch some other attacks.