International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) 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).

15:17 [Pub][ePrint] On the (Im)possibility of Projecting Property\\\\, by Jae Hong Seo

  Projecting bilinear pairings have frequently been used for designing cryptosystems since they were first derived from composite order bilinear groups. There have been only a few studies on the (im)possibility of projecting bilinear pairings. Groth and Sahai (EUROCRYPT 2008) showed that projecting bilinear pairings can be achieved in a prime-order group setting. They constructed both projecting asymmetric bilinear pairings and projecting symmetric bilinear pairings, where a bilinear pairing $e$ is symmetric if it satisfies $e(g,h)=e(h,g)$ for any group elements $g$ and $h$; otherwise, it is asymmetric. Subsequently, Freeman (EUROCRYPT 2010) generalized Groth-Sahai\'s projecting asymmetric bilinear pairings.

In this paper, we provide impossibility results on projecting bilinear pairings in a prime-order group setting. More precisely, we specify the lower bounds of

1. the image size of a projecting asymmetric bilinear pairing

2. the image size of a projecting symmetric bilinear pairing

3. the computational cost for a projecting asymmetric bilinear pairing

4. the computational cost for a projecting symmetric bilinear pairing

in a prime-order group setting naturally induced from the $k$-linear assumption, where the computational cost means the number of generic operations.

Our lower bounds regarding a projecting asymmetric bilinear pairing are tight, i.e., it is impossible to construct a more efficient projecting asymmetric bilinear pairing than the constructions of Groth-Sahai and Freeman. However, our lower bounds regarding a projecting symmetric bilinear pairing differ from Groth and Sahai\'s results regarding a symmetric bilinear pairing; We fill these gaps by constructing projecting symmetric bilinear pairings.

In addition, on the basis of the proposed symmetric bilinear pairings, we construct more efficient instantiations of cryptosystems that essentially use the projecting symmetric bilinear pairings in a modular fashion. Example applications include new instantiations of the Boneh-Goh-Nissim cryptosystem, the Groth-Sahai non-interactive proof system, and Seo-Cheon round optimal blind signatures proven secure under the DLIN assumption. These new instantiations are more efficient than the previous ones, which are also provably secure under the DLIN assumption. These applications are of independent interest.

15:17 [Pub][ePrint] Enhanced Ownership Transfer Protocol for RFID in an Extended Communication Model, by Jorge Munilla, Alberto Peinado, Guoming Yang and Willy Susilo

  Ownership Transfer Protocols for RFID allow transferring the

rights over a tag from a current owner to a new owner in a secure

and private way. Recently, Kapoor and Piramuthu have proposed two

schemes which overcome most of the security weaknesses detected in

previously published protocols. Still, this paper reviews that

work and points out that such schemes still present some practical

and security issues. In particular, they do not manage to

guarantee the privacy of the new owner without the presence of a

Trusted Third Party, and we find that the assumed communication

model is not suitable for many practical scenarios. We then

propose here a lightweight protocol that can be used in a wider

range of applications, and which incorporates recently defined

security properties such as Tag Assurance, Undeniable Ownership

Transfer, Current Ownership Proof and Owner Initiation. Finally,

this protocol is complemented with a proposed Key Change Protocol,

based on noisy tags, which provides privacy to the new owner

without either resorting to a Trusted Third Party or assuming an

Isolated Environment.

15:17 [Pub][ePrint] A family of 6-to-4-bit S-boxes with large linear branch number, by Daniel Loebenberger and Michael Nüsken

  We propose a family of 6-to-4-bit S-boxes with linear branch number 3. Since they also fulfill various further desirable properties, such S-boxes can serve as a building block for various block ciphers.

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


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.

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.