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





2013-03-31
00:17 [Pub][ePrint] On the Classification of Differential Invariants for Multivariate Post-Quantum Cryptosystems\", by Ray Perlner and Daniel Smith-Tone

  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] Cryptanalysis of Some Double-Block-Length Hash Modes of Block Ciphers with $n$-Bit Block and $n$-Bit Key, by Deukjo Hong and Daesung Kwon

  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.



00:17 [Pub][ePrint] Machine-Generated Algorithms, Proofs and Software for the Batch Verification of Digital Signature Schemes, by Joseph A. Akinyele and Matthew Green and Susan Hohenberger and Matthew W. Pagano

  As devices everywhere increasingly communicate with each other, many security applications will require low-bandwidth signatures that can be processed quickly. Pairing-based signatures can be very short, but are often costly to verify. Fortunately, they also tend to have efficient batch verification algorithms. Finding these batching algorithms by hand, however, can be tedious and error prone.

We address this by presenting AutoBatch, an automated tool for generating batch verification code in either Python or C++ from a high level representation of a signature scheme. AutoBatch outputs both software and, for transparency, a LaTeX file describing the batching algorithm and arguing that it preserves the unforgeability of the original scheme.

We tested AutoBatch on over a dozen pairing-based schemes to demonstrate that a computer could find competitive batching solutions in a reasonable amount of time. Indeed, it proved highly competitive. In particular, it found an algorithm that is significantly faster than a batching algorithm from Eurocrypt 2010. Another novel contribution is that it handles cross-scheme batching, where it searches for a common algebraic structure between two distinct schemes and attempts to batch them together.

In this work, we expand upon an extended abstract on AutoBatch appearing in ACM CCS 2012 in a number of ways. We add a new loop-unrolling technique and show that it helps cut the batch verification cost of one scheme by roughly half. We describe our pruning and search algorithms in greater detail, including pseudocode and diagrams. All experiments were also re-run using the RELIC pairing library. We compare those results to our earlier results using the MIRACL library, and discuss why RELIC outperforms MIRACL in all but two cases. Automated proofs of several new batching algorithms are also included.

AutoBatch is a useful tool for cryptographic designers and implementors, and to our knowledge, it is the first attempt to outsource to machines the design, proof writing and implementation of signature batch verification schemes.



00:17 [Pub][ePrint] Distinguishing Attacks on RC4 and A New Improvement of the Cipher, by Jing Lv and Bin Zhang and Dongdai Lin

  RC4, designed by Rivest in 1987, is the most widely deployed stream cipher in practical applications. In this paper, two new class of statistical biases inherent in RC4 are depicted and it is shown that the RC4 keystream is distinguishable from random no matter how many initial bytes have been dumped.

RC4A, proposed by Paul and Preneel at FSE 2004 to strengthen the security of RC4, is also found to be vulnerable to similar attacks. Instead, a new pseudorandom bit generator RC4B is proposed, which is believed to provide better immunity against the known attacks.



00:17 [Pub][ePrint] A generic construction for voting correctness at minimum cost - Application to Helios, by Veronique Cortier and David Galindo and Stephane Glondu and Malika Izabachene

  Most voting schemes aim at providing verifiability: voters should be able to check that their ballots did contribute to the outcome (individual verifiability) and that the tallying authorities did their job properly (universal verifiability). Surprisingly, verifiability still does not answer a very simple and natural question: how can I be sure that the published result corresponds to the (sum of) intended votes of the voters? This property is called correctness by Juels, Catalano, and Jakobsson. Actually, even a prominent voting system like Helios does not achieve correctness in the case of a dishonest bulletin board, since it may add ballots.

We generalize the aforementioned definition of correctness to account for a malicious bulletin board (full correctness) and we provide a generic construction that transforms a correct voting scheme into a fully correct voting scheme. This construction simply requires to send credentials to the voters, with no additional infrastructure. We further provide a simple and natural criteria that implies voting correctness, which can then be turned into full correctness due to our construction. As an application, we build a variant of Helios that is both fully correct, verifiable and private.

Real-world elections often require threshold cryptosystems so that any t out of l trustees can proceed to tallying. We describe a fully distributed (with no dealer) threshold cryptosystem suitable for Helios (in particular, suitable to partial decryption). In doing so we happen to revisit the seminal multi-authority election system from Cramer, Gennaro and Schoenmakers. Altogether, we provide the first proof of privacy, verifiability and correctness for a fully distributed Helios voting scheme (and its enhanced version with credentials), together with its detailed description. This also implies, to our knowledge, the first formal proofs of privacy, verifiability and correctness for the scheme by Cramer et al. Last but not least, we provide an open source implementation of our variant of Helios.