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-01-30
01:17 [Pub][ePrint] An Efficient CCA2-Secure Variant of the McEliece Cryptosystem in the Standard Model, by Roohallah Rastaghi

  Recently, a few CCA2-secure (IND-CCA2) variant of the McEliece cryptosystem in the standard model were introduced. All these

schemes are based on Rosrn-Segev approach and lossy trapdoor function

and utilize k-repetition paradigm. The main drawback of these chemes is that they are need additional encryption and have large key size compared to the original scheme, which intricate the public-key size problem in the code-based cryptosystem. Furthermore, full CCA2-security of these schemes achieved by using a strongly unforgeable one-time signature scheme, and so, the resulting scheme need separate encryption. Therefore,‎ the proposed schemes are not efficient.‎

In this manuscript, we propose a new and efficient IND-CCA2 variant of the McEliece cryptosystem in the standard model. The main novelty is that, unlike previous approaches, our approach is a generic ransformation and can be applied to any code-based one-way cryptosystem (both the McEliece and the Niederreiter cryptosystems). Our approach also leads to the elimination of the encryption repetition and using strongly unforgeable one-time signature scheme. This novel approach is more efficient, the publick/secret keys are as in the original scheme and the encryption/decryption complexity are comparable to the original scheme.‎ CCA2-security of the proposed scheme can be reduced in the standard model to the McEliece assumptions. To the best of our knowledge, this is the first variant of the code-based cryptosystem that is IND-CCA2 in the standard model without using k-repetition paradigm and strongly

unforgeable one-time signature scheme.‎



01:17 [Pub][ePrint] Trace Expression of r-th Root over Finite Field, by Gook Hwa Cho and Namhun Koo and Eunhye Ha and Soonhak Kwon

  Efficient computation of $r$-th root in $\\mathbb F_q$ has many

applications in computational number theory and many other related

areas. We present a new $r$-th root formula which generalizes

M\\\"{u}ller\'s result on square root, and which provides a possible

improvement of the Cipolla-Lehmer algorithm for general case. More

precisely, for given $r$-th power $c\\in \\mathbb F_q$, we show that

there exists $\\alpha \\in \\mathbb F_{q^r}$ such that

$Tr\\left(\\alpha^\\frac{(\\sum_{i=0}^{r-1}q^i)-r}{r^2}\\right)^r=c$

where $Tr(\\alpha)=\\alpha+\\alpha^q+\\alpha^{q^2}+\\cdots

+\\alpha^{q^{r-1}}$ and $\\alpha$ is a root of certain irreducible

polynomial of degree $r$ over $\\mathbb F_q$.



01:17 [Pub][ePrint] Complexity of Multi-Party Computation Functionalities, by Hemanta K. Maji and Manoj Prabhakaran and Mike Rosulek

  The central objects of secure multiparty computation are the \"multiparty functions\" (or functionalities) that it seeks to securely realize. In this article we survey a set of results that constitute a Cryptographic Complexity Theory. This theory classifies and compares multiparty functions according to their secure computability and reducibility to each other. The basic questions studied, under various notions of security and reducibility, include:

o Which functionalities are securely realizable (or are \"trivial\" - i.e., can be reduced to any functionality)?

o Which functionalities are \"complete\" - i.e., those to which any functionality can be reduced?

o More generally, which functionalities are reducible to which? Outside of triviality and completeness, this question is relatively less explored.

Reductions yield relative measures of complexity among various functionalities. In the information- theoretic setting, absolute complexity measures have also been considered. In particular, we discuss results regarding which functions have t-private protocols (in which security is required against a passive adversary corrupting t out of n players) and how this set changes as t increases from 1 to n.

We treat separately the results on two-party functionalities, for which the cryptographic complexity is much better understood. In particular, we present unified combinatorial characterizations of completeness and triviality for secure function evaluation using notions of isomorphism and the common information functionality (called the kernel) of a given functionality. Beyond completeness and triviality, we also discuss results on general reducibility, and, in the computationally bounded setting, the connection between these reductions and computational hardness assumptions.

We briefly discuss results on reactive functionalities, which are much less studied than non-reactive (secure function evaluation) functionalities. Finally, we conclude with a selection of open problems.



01:17 [Pub][ePrint] Differential Fault Attack on the PRINCE Block Cipher, by Ling Song and Lei Hu

  PRINCE is a new lightweight block cipher proposed at the ASIACRYPT\'2012 conference. In this paper two observations on the linear layer of the cipher are presented. Based on the observations a differential fault attack is applied to the cipher under a random nibble-level fault model. The attack uniquely determines the 128-bit key of the cipher using less than 7 fault injections averagely. In the case with 4 fault injections, the attack limits the key to a space of size less than $2^{18}$ statistically.





2013-01-24
22:17 [Pub][ePrint] New Cube Root Algorithm Based on Third Order Linear Recurrence Relation in Finite Field, by Gook Hwa Cho and Namhun Koo and Eunhye Ha and Soonhak Kwon

  In this paper, we present a new cube root algorithm in finite

field $\\mathbb{F}_{q}$ with $q$ a power of prime, which extends

the Cipolla-Lehmer type algorithms \\cite{Cip,Leh}. Our cube root

method is inspired by the work of M\\\"{u}ller \\cite{Muller} on

quadratic case. For given cubic residue $c \\in \\mathbb{F}_{q}$

with $q \\equiv 1 \\pmod{9}$, we show that there is an irreducible

polynomial $f(x)=x^{3}-ax^{2}+bx-1$ with root $\\alpha \\in

\\mathbb{F}_{q^{3}}$ such that $Tr(\\alpha^{\\frac{q^{2}+q-2}{9}})$

is a cube root of $c$. Consequently we find an efficient cube root

algorithm based on third order linear recurrence sequence arising

from $f(x)$. Complexity estimation shows that our algorithm is

better than previously proposed Cipolla-Lehmer type algorithms.



22:17 [Pub][ePrint] The IITM Model: a Simple and Expressive Model for Universal Composability, by Ralf Kuesters and Max Tuengerthal

  The universal composability paradigm allows for the modular design and analysis of cryptographic protocols. It has been widely and successfully used in cryptography. However, devising a coherent yet simple and expressive model for universal composability is, as the history of such models shows, highly non-trivial. For example, several partly severe problems have been pointed out in the literature for the UC model.

In this work, we propose a coherent model for universal composability, called the IITM model (``Inexhaustible Interactive Turing Machine\'\'). A main feature of the model is that it is stated without a priori fixing irrelevant details, such as a specific way of addressing of machines by session and party identifiers, a specific modeling of corruption, or a specific protocol hierarchy. In addition, we employ a very general notion of runtime. All reasonable protocols and ideal functionalities should be expressible based on this notion in a direct and natural way, and without tweaks, such as (artificial) padding of messages or (artificially) adding extra messages.

Not least because of these features, the model is simple and expressive. Also the general results that we prove, such as composition theorems, hold independently of how such details are fixed for concrete applications.

Being inspired by other models for universal composability, in particular the UC model and because of the flexibility and expressivity of the IITM model, conceptually, results formulated in these models directly carry over to the IITM model.



22:17 [Pub][ePrint] RSA private key reconstruction from random bits using SAT solvers, by Constantinos Patsakis

  SAT solvers are being used more and more in Cryptanalysis, with mixed results regarding their efficiency, depending on the structure of the algorithm they are applied. However, when it comes to integer factorization, or more specially the RSA problem, SAT solvers prove to be at least inefficient. The running times are too long to be compared with any well known integer factorization algorithm, even when it comes to small RSA moduli numbers.

The recent work on cold boot attacks has sparkled again the interest on partial key exposure attacks and in RSA key reconstruction. In our work, contrary to the lattice-based approach that most of these

works use, we use SAT solvers. For the special case where the public exponent $e$ is equal to three, we provide a more efficient modeling of RSA as an instance of a satisfiability problem, and manage to reconstruct the private key, given a part of the key, even for public keys of 1024 bits in few seconds.



22:17 [Pub][ePrint] Anonymity Guarantees of the UMTS/LTE Authentication and Connection Protocol, by Ming-Feng Lee and Nigel P. Smart and Bogdan Warinschi and Gaven Watson

  The UMTS/LTE protocol for mobile phone networks has been designed to offer a limited form of anonymity for mobile phone uses. In this paper we quantify precisely what this limited form of anonymity actually provides via a formal security model. The model considers an execution where the home and roaming network providers are considered as one entity. We consider two forms of anonymity, one where the mobile stations under attacked are statically selected before the execution, and a second one where the adversary selects these stations adaptively. We prove that the UMTS/LTE protocol meets both of these security definitions. Our analysis requires new assumptions on the underlying keyed functions for UMTS, which whilst probably true have not previously been brought to the fore.



22:17 [Pub][ePrint] More on linear hulls of PRESENT-like ciphers and a cryptanalysis of full-round EPCBC-96, by Stanislav Bulygin

  In this paper we investigate the linear hull effect in the light-weight block cipher EPCBC. We give an efficient method of computing linear hulls with high capacity. We then apply found hulls to derive attacks on the full 32 rounds of EPCBC--96 and 20 rounds of EPCBC-48. Using the developed methods we revise the work of J.Y. Cho from 2010 and obtain an attack based on multidimensional linear approximations on 26 rounds of PRESENT--128. The results show that designers of block ciphers should take seriously the threat coming from the linear hull attacks and not just limit themselves to proving bounds based solely on linear characteristics.



22:17 [Pub][ePrint] A Differential Fault Attack on MICKEY 2.0, by Subhadeep Banik and Subhamoy Maitra

  In this paper we present a differential fault attack on the stream cipher MICKEY 2.0 which is in eStream\'s hardware portfolio. While fault attacks have already been reported against the other two eStream hardware candidates Trivium and Grain, no such analysis is known for MICKEY. Using the standard assumptions for fault attacks, we show that by injecting around $2^{16.7}$ faults and performing $2^{32.5}$ computations on an average, it is possible to recover the entire internal state of MICKEY at the beginning of the key-stream generation

phase.



22:17 [Pub][ePrint] On the security of an identity-based authenticated group key agreement protocol for imbalanced mobile networks, by Haiyan Sun

  Recently, Islam and Biswas proposed a pairing-free identity-based authenticated group key agreement protocol for imbalanced mobile networks. However, in this letter, we point out that this protocol cannot resist passive attack, and cannot provide forward secrecy for joining operation and backward secrecy for leaving operation.