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-04-02
15:17 [Pub][ePrint] Ideal and Perfect Hierarchical Secret Sharing Schemes based on MDS codes, by Appala Naidu Tentu and Prabal Paul and V Ch Venkaiah

  An ideal conjunctive hierarchical secret sharing scheme, constructed based on the Maximum Distance Separable (MDS) codes, is proposed in this paper. The scheme, what we call, is computationally perfect. By computationally perfect, we mean, an authorized set can always reconstruct the secret in polynomial time whereas for an unauthorized set this is computationally hard. Also, in our scheme, the size of the ground field is independent of the parameters of the access structure. Further, it is efficient and requires $O(n^3)$, where $n$ is the number of participants.

Keywords: Computationally perfect, Ideal, Secret sharing scheme, Conjunctive hierarchical access structure, Disjunctive hierarchical access structure, MDS code.



15:17 [Pub][ePrint] Power Analysis Attacks against FPGA Implementations of KLEIN, by Shaohua Tang and Jianhao Wu and Weijian Li and Zheng Gong

  KLEIN is a family of block ciphers proposed by Zheng Gong et al. at RFIDSec 2011, and its lightweight features are suitable for resource-constrained devices. However, the original design of KLEIN does not consider the potential attacks by power analysis methods. This paper presents power analysis attacks against a FPGA implementation of KLEIN by the authors of KLEIN. The attacking strategy, attacking point and complexity of our attacks via power analysis against KLEIN are discussed in detail. Besides, the implementation of the attacks is also described, and the experimental data is given. A lot of attacking experiments are launched by this paper, and the experiments confirm that the success probability of our attacks is nearly 100%. Finally, a defensive countermeasure against our attacks is proposed.



15:17 [Pub][ePrint] Improved Differential Fault Analysis on ARIA using Small Number of Faults, by Yuseop Lee, Kitae Jeong, Jaechul Sung, Seokhie Hong

  In [15], Li et al. firstly proposed a differential fault analysis on ARIA-128. This attack requires average 45 random byte fault injections. In 2012, Park et al. proposed the improve DFA by using 33 random byte fault injection. Also Kim proposed differential fault analysis based on multi byte fault model. In this model, the number of fault injections is reduce to 13 and If access to the decryption oracle is allowed, only 7 faults are required. In this paper, we propose improved differential fault analysis on ARIA. Based on random byte fault model, the proposed attacks can recover the secret key of ARIA-128/192/256 by using 6 fault injections within a few minutes. Moreover, in cases of ARIA-128 and ARIA-256, it is possible to recover the secret key using only 4 fault injections under a fault assumption where an attacker can induce some faults during both encryption and decryption process, respectively.

Our results on ARIA-192/256 are the first known DFA results on them.



15:17 [Pub][ePrint] A generalisation of Miller\'s algorithm and applications to pairing computations on abelian varieties, by David Lubicz and Damien Robert

  In this paper, we use the theory of theta functions to generalize to

all abelian varieties the usual Miller\'s algorithm to compute a

function associated to a principal divisor. We also explain how to

use the Frobenius morphism on abelian varieties defined over a

finite field in order to shorten the loop of the Weil and Tate

pairings algorithms. This extend preceding results about ate and

twisted ate pairings to all abelian varieties. Then building upon

the two preceding ingredients, we obtain a variant of optimal

pairings on abelian varieties. Finally, by introducing new addition

formulas, we explain how to compute optimal pairings on Kummer

varieties. We compare in term of performance the resulting

algorithms to the algorithms already known in the genus one and two

case.



12:17 [Pub][ePrint] The Vernam cipher is robust to small deviations from randomness, by Boris Ryabko

  The Vernam cipher (or one-time pad) has played an important rule in cryptography because it is a perfect secrecy system.

For example, if an English text (presented in binary system) $X_1 X_2 ... $ is enciphered according to the formula $Z_i = (X_i + Y_i) \\mod 2 $, where $Y_1 Y_2 ...$ is a key sequence generated by the Bernoulli source with equal probabilities of 0 and 1, anyone who knows $Z_1 Z_2 ... $ has no information about $X_1 X_2 ... $

without the knowledge of the key $Y_1 Y_2 ...$. (The best strategy is to guess $X_1 X_2 ... $ not paying attention to $Z_1 Z_2 ... $.)

But what should one say about secrecy of an analogous method where the key sequence $Y_1 Y_2 ...$ is generated by the Bernoulli

source with a small bias, say, $P(0) = 0.49, $ $ P(1) = 0.51$?

To the best of our knowledge, there are no theoretical estimates for the secrecy of such a system, as well as for the general case where $X_1 X_2 ... $ (the plaintext) and key sequence are described by stationary ergodic processes.

We consider the running-key ciphers where the plaintext and the key are generated by stationary ergodic sources and show how to estimate the secrecy of such systems. In particular, it is shown that, in a certain sense, the Vernam cipher is robust to small deviations from randomness.





2013-04-01
15:17 [Pub][ePrint] Cryptanalysis of RC4(n,m) Stream Cipher, by Mohammad Ali Orumiehchiha and Josef Pieprzyk and Elham Shakour and Ron Steinfeld

  $RC4(n,m)$ is a stream cipher based on RC4 and is designed by G. Gong $et ~al.$. It can be seen as a generalization of the famous RC4 stream cipher designed by Ron Rivest. The authors of $RC4(n,m)$ claim that the cipher resists all the attacks that are successful against the original RC4. The paper reveals cryptographic weaknesses of the $RC4(n,m)$ stream cipher. We develop two attacks. The first one is based on non-randomness of internal state and allows to distinguish it from a truly random cipher by an algorithm that has access to $2^{4\\cdot n}$ bits of the keystream. The second attack exploits low diffusion of bits in the KSA and PRGA algorithms and recovers all bytes of the secret key. This attack works only if the initial value of the cipher can be manipulated.

Apart from the secret key, the cipher uses two other inputs, namely, initial value and initial vector. Although these inputs are fixed in the cipher specification, some applications may allow the inputs to be under the attacker control. Assuming that the attacker can control the initial value, we show a distinguisher for the cipher and a secret key recovery attack that for the \\textit{L}-bit secret key, is able to recover it with about $(L/n)\\cdot 2^n $ steps. The attack has been implemented on a standard PC and can reconstruct the secret key of RC(8,32) in less than a second.



15:17 [Pub][ePrint] Malleable Signatures: Complex Unary Transformations and Delegatable Anonymous Credentials, by Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Sarah Meiklejohn

  A signature scheme is malleable if, on input a message m and a signature $\\sigma$, it is possible to efficiently compute a signature $\\sigma\'$ on a related message $m\' = T(m)$, for a transformation T that is allowable with respect to this signature scheme. Previous work considered various useful flavors of allowable transformations, such as quoting and sanitizing messages. In this paper, we explore a connection between malleable signatures and anonymous credentials, and give the following contributions:

-We define and construct malleable signatures for a broad category of allowable transformation classes, with security properties that are stronger than those that have been achieved previously. Our construction of malleable signatures is generically based on malleable zero-knowledge proofs, and we show how to instantiate it under the Decision Linear assumption.

-We construct delegatable anonymous credentials from signatures that are malleable with respect to an appropriate class of transformations; we also show that our construction of malleable signatures works for this class of transformations. The resulting concrete instantiation is the first to achieve security under a standard assumption (Decision Linear) while also scaling linearly with the number of delegations.



15:17 [Pub][ePrint] A New Class of Product-sum Type Public Key Cryptosystem,K(V)$\\Sigma\\Pi$PKC,Constructed Based on Maximum Length Code, by Masao KASAHARA

  The author recently proposed a new class of knapsack type PKC referred to as K(II)$\\Sigma\\Pi$PKC [1]. In K(II)$\\Sigma\\Pi$PKC with old algorithm DA[I], Bob randomly constructs a very small subset of Alice\'s set of public key whose order is very large, under the condition that the coding rate $\\rho$ satisfies $0.01 < \\rho < 0.2$. In K(II)$\\Sigma\\Pi$PKC, no secret sequence such as super-increasing sequence or shifted-odd sequence but the sequence whose components are constructed by a product of the same number of many prime numbers of the same size, is used. In this paper we present a new algorithm, DA(II) for decoding K(II)$\\Sigma\\Pi$PKC.We show that with new decoding algorithm, DA(II), K(II)$\\Sigma\\Pi$PKC yields a higher coding rate and a smaller size of public key compared with K(II)$\\Sigma\\Pi$PKC using old decoding algorithm, DA(I). We further present a generalized version of K(II) $\\Sigma\\Pi$PKC, referred to as K(\\v)$\\Sigma\\Pi$PKC. We finally present a new decoding algorithm DA(III) and show that, in K(V)$\\Sigma\\Pi$PKC with DA(III), the relation, $r_F\\simeq 0, \\rho \\simeq \\frac{2}{3}$ holds, where $r_F$ is the factor ratio that will be defined in this paper. We show that K(V)$\\Sigma\\Pi$PKC yields a higher security compared with K(II) $\\Sigma\\Pi$PKC.



15:17 [Pub][ePrint] On the evaluation of modular polynomials, by Andrew V. Sutherland

  We present two algorithms that, given a prime ell and an elliptic curve E/Fq, directly compute the polynomial $\\Phi_\\ell(j(E),Y)\\in\\Fq[Y] whose roots are the j-invariants of the elliptic curves that are ell-isogenous to E. We do not assume that the modular polynomial Phi_ell(X,Y) is given. The algorithms may be adapted to handle other types of modular polynomials, and we consider applications to point counting and the computation of endomorphism rings. We demonstrate the practical efficiency of the algorithms by setting a new point-counting record, modulo a prime q with more than 5,000 decimal digits, and by evaluating a modular polynomial of level ell=100,019.



15:17 [Pub][ePrint] Collusion-Resistant Domain-Specific Pseudonymous Signatures, by Julien Bringer and Herve Chabanne and Alain Patey

  At ISC 2012, Bender et al. introduced the notion of domain-specific pseudonymous signatures for ID documents. With this primitive, a user can sign with domain-specific pseudonyms, that cannot be linked across domains but that are linkable in a given domain. However, their security model assumes non-collusion of malicious users, which is a strong assumption. We therefore propose improvements to their construction. Our main contribution is a new pseudonymous signature scheme based on group signatures that is collusion-resistant.



15:17 [Pub][ePrint] Practical Multilinear Maps over the Integers, by Jean-Sebastien Coron and Tancrede Lepoint and Mehdi Tibouchi

  Extending bilinear elliptic curve pairings to multilinear maps is a long-standing open problem. The first plausible construction of such multilinear maps has recently been described by Garg, Gentry and Halevi, based on ideal lattices. In this paper we describe a

different construction that works over the integers instead of ideal lattices, similar to the DGHV fully homomorphic encryption scheme. We also describe a different technique for proving the full randomization of encodings: instead of Gaussian linear sums, we apply the classical leftover hash lemma over a quotient lattice. We show that our construction is relatively practical: for reasonable security parameters a one-round 7-party Diffie-Hellman key exchange requires about $25$ seconds per party.