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

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]

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]

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 (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]

$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]

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]

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]

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] 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] 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. 2013-03-31 00:17 [Pub][ePrint] Multivariate Public Key Cryptography(MPKC) has become one of a few options for security in the quantum model of computing. Though a few multivariate systems have resisted years of effort from the cryptanalytic community, many such systems have fallen to a surprisingly small pool of techniques. There have been several recent attempts at formalizing more robust security arguments in this venue with varying degrees of applicability. We present an extension of one such recent measure of security against a differential adversary which has the benefit of being immediately applicable in a general setting on unmodified multivariate schemes. 00:17 [Pub][ePrint] In this paper, we make attacks on DBL (Double-Block-Length) hash modes of block ciphers with n-bit key and n-bit block. Our preimage attack on MDC-4 scheme requires the time complexity$2^{3n/2}$, which is significantly improved compared to the previous results. Our collision attack on the hash function of MJH scheme has time complexity less than$2^{124}$for n = 128. Our preimage attack on the compression functions of MJH scheme find a preimage with time complexity of$2^n$. It is converted to a preimage attack on the hash function with time complexity of$2^{3n/2+1}$. Our preimage attack on the compression functions of MJH scheme find a preimage with time complexity of$2^{3n/2}$. It is converted to a second-preimage attack on the hash function with time complexity of$2^{7n/4+1}\$. These attacks are helpful for understanding the security of the hash modes together with their security proofs.