Number: 7
Title: A Unified Framework for Small Secret Exponent Attack on RSA
Authors: Noboru Kunihiro, Naoyuki Shinohara and Tetsuya Izu
Affiliations: The University of Tokyo, NICT and Fujitsu Labs.
Abstract: We address a lattice based method on small secret exponent attack on RSA
scheme. 
Boneh and Durfee reduced the attack into solving a bivariate
modular equation: $x(N+1+y)+1 ¥equiv 0 (¥bmod¥; e)$, where $N$ is an RSA
 moduli and $e$ is the RSA public key. 
%Several methods have been proposed in the literature.
Boneh and Durfee proposed a lattice based algorithm for solving the
 problem.  When the secret exponent $d$ is less than $N^{0.292}$, their
 method breaks RSA scheme.  Since the lattice used in the analysis is
 not full-rank, the analysis is not easy. Bl¥"omer and May gave another
 algorithm.  Although their bound $d ¥leq N^{0.290}$ is worse than
 Boneh--Durfee's result, their method used a full rank lattice.
 However, the proof for their bound is still complicated.
Herrmann and May gave an elementary proof for the Boneh--Durfee's bound
 $d ¥leq N^{0.292}$.
In this
 paper, we first give an elementary proof for achieving Bl¥"omer--May's
 bound: $d ¥leq N^{0.290}$.  Our proof employs unravelled linearization
 technique introduced by Herrmann and May and is rather simpler than
 Bl¥"omer--May's proof.  Then, we provide a unified framework to
 construct a lattice that are used for solving the problem,
 which includes two previous method: Herrmann--May's and Bl¥"omer--May's
 methods as a special case.  Furthermore, we prove that Boneh--Durfee's
 bound: $d ¥leq N^{0.292}$ is still optimal in our unified framework.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 8
Title: Duplexing the sponge: single-pass authenticated encryption and other applications
Authors: Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche
Affiliations: STMicroelectronics, NXP Semiconductors
Abstract: This paper proposes a novel construction, called duplex, closely related to the sponge construction, that accepts message blocks to be hashed and—at no extra cost—provides digests on the input blocks received so far. It can be proven equivalent to a cascade of sponge functions and hence inherits its security against generic attacks. The main application proposed here is an authenticated encryption mode based on the duplex construction. This mode is efficient, namely, enciphering and authenticating together require only a single call to the underlying permutation per block, and is readily usable in, e.g., key wrapping. Furthermore, it is the first mode of this kind to be based on a permutation instead of a block cipher and to natively support intermediate tags. The duplex construction can be used to efficiently realize other modes, such as a reseedable pseudo-random bit sequence generators and a sponge variant that overwrites part of the state with the input block rather than to XOR it in.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 15
Title: Cryptographic Analysis of All 4 x 4 - Bit S-Boxes
Authors: Markku-Juhani O. Saarinen
Affiliations: Revere Security
Abstract: Abstract. We present cryptanalytic results of an exhaustive search of all 16!
bijective 4-bit S-Boxes. Previously only affine equivalence classes have exhaustively analyzed in a 2007 work by Leander and Poschmann. We extend on this
work by giving further properties of the optimal S-Box linear equivalence classes.
In our main analysis we consider two S-Boxes to be cryptanalytically equivalent
if they are isomorphic up to the permutation of input and output bits and a XOR
of a constant in the input and output. We have enumerated all such equivalence
classes with respect to their differential and linear properties. These equivalence classes are equivalent not only in their differential and linear bounds but also have equivalent algebraic properties, branch number and circuit complexity. We describe a "golden" set of S-boxes that have ideal cryptographic properties. We also present a comparison table of S-Boxes from a dozen published cryptographic algorithms.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 18
Title: Cryptanalysis of Reduced Versions of the Camellia Block Cipher
Authors: Jiqiang Lu, Yongzhuang Wei, Jongsung Kim, and Pierre-Alain Fouque
Affiliations: Ecole Normale Superieure, Guilin University of Electronic Technology, and Kyungnam University
Abstract: The Camellia block cipher has a 128-bit block length, a user key length of 128, 192 or 256 bits, and a total of 18 rounds for a 128-bit key and 24 rounds for a 192 or 256-bit key. It is an ISO international standard. In this paper, we describe a common flaw in certain previous cryptanalytic results for Camellia and give possible approaches to correct them. Finally, by taking advantage of
the early abort technique and a few observations on the key schedule, we present impossible differential attacks on 14-round Camellia without the $\mbox{FL}/\mbox{FL}^{-1}$ functions under 192 key bits and 16-round Camellia  without the
$\mbox{FL}/\mbox{FL}^{-1}$ functions  under 256 key bits. The 14-round attack requires $2^{117}$ chosen plaintexts and has a time complexity of $2^{182.2}$ encryptions; and the 16-round attack requires $2^{123}$ known plaintexts and has a time complexity of $2^{249}$ encryptions.  In terms of the numbers of attacked rounds, these are better than any previously known  cryptanalytic results for  Camellia without the $\mbox{FL}/\mbox{FL}^{-1}$ functions under 192/256 key bits.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 20
Title: Combined Differential and Linear Cryptanalysis of Reduced-Round {\sc PRINTcipher}
Authors: Ferhat Karakoç, Hüseyin Demirci, A. Emre Harmanci
Affiliations: TUBITAK BILGEM UEKAE, Istanbul Technical University
Abstract: In this paper we analyze the security of {\sc PRINTcipher} using a technique that combines differential and linear cryptanalysis. 
The proposed technique is different from differential-linear cryptanalysis.
We use linear approximations to increase the probability of differential characteristics.
We show that specific choices of some of the key bits gives rise to a certain differential characteristic probability, which is far higher than the best characteristic probability claimed by the designers.  
We give the underlying mechanism of this probability increase. 
We have developed attacks on 29 and 31 rounds of {\sc PRINTcipher-48} for $4.54\%$ and $0.036\%$ of the keys, respectively. 
Moreover, we have implemented the proposed attack algorithm on 20 rounds of the cipher.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 24
Title: On CCA-Secure Somewhat Homomorphic Encryption
Authors: J. Loftus, A. May, N.P. Smart and F. Vercauteren
Affiliations: Universities of Bristol, Bochum and Leuven
Abstract: It is well known that any encryption scheme which supports any form of homomorphic operation cannot be secure against adaptive chosen ciphertext attacks. The question then arises as to what is the most stringent security definition which is achievable by homomorphic encryption schemes. Prior work has shown that various schemes which support a single homomorphic encryption scheme can be shown to be IND-CCA1, i.e. secure against lunchtime attacks. In this paper we extend this analysis to the recent fully homomorphic encryption scheme proposed by Gentry, as refined by Gentry, Halevi, Smart and Vercauteren. We show that the basic Gentry scheme is not IND-CCA1; indeed a trivial lunchtime attack allows one to recover the secret key. We then show that a minor modification to the variant of the somewhat homomorphic encryption scheme of Smart and Vercauteren will allow one to achieve IND-CCA1, indeed PA-1, in the standard model assuming a lattice based knowledge assumption. In the Appendices we examine the security of the scheme against another security notion, namely security in the presence of ciphertext validity checking oracles; and show why CCA-like notions are important in applications in which multiple parties submit encrypted data to the ``cloud'' for secure processing.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 28
Title: Practical Attack on the Full MMB Block Cipher
Authors: Keting Jia, Jiazhe Chen, Meiqin Wang, Xiaoyun Wang
Affiliations: Institute for Advanced Study, Tsinghua University.  Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University
Abstract: Modular Multiplication based Block Cipher (MMB) is a block cipher designed by Daemen \emph{et al.} as an alternative to the IDEA block cipher. In this paper, we give a practical sandwich attack on MMB with adaptively chosen plaintexts and ciphertexts. By constructing a 5-round sandwich distinguisher of the full 6-round MMB with probability 1, we recover the main key of MMB with text complexity $2^{40}$ and time complexity  $2^{30}$ MMB encryptions. We also present a chosen plaintexts attack on the full MMB by employing the rectangle-like sandwich attack, which the complexity is $2^{66.5}$ texts, $2^{66}$ MMB encryptions and $2^{70.5}$ bytes of memory. In addition, we introduce an improved differential attack on MMB with $2^{96}$ chosen plaintexts, $2^{66}$ encryptions and $2^{66}$ bytes of memory. Especially, even if MMB is extended to 7 rounds, the improved differential attack is applicable with the same complexity as that of the full MMB.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 29
Title: New Insights on Impossible Differential Cryptanalysis
Authors: Charles Bouillaguet and Orr Dunkelman and Pierre-Alain Fouque and Gaetan Leurent
Affiliations: Ecole normale superieure (France) and University of Haifa (Israel) and Weizmann Institute (Israel) and University of Luxembourg (Luxembourg)
Abstract: Since its introduction, impossible differential cryptanalysis has been
applied to many ciphers. Besides the specific application of the technique
in various instances, there are some very basic results which apply to
generic structures of ciphers, e.g., the well known
5-round impossible differential
of Feistel ciphers with bijective round functions. 
-
In this paper we present
a new approach for the construction and the usage of impossible differentials
for Generalized Feistel structures.
The results allow to extend the previous impossible differentials
by one round (or more),
answer an open problem about the ability to
perform this kind of analysis, and even reduce the need for a bijective
round function in some instances.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 35
Title: Blockcipher-Based Double-Length Hash Functions for Pseudorandom Oracles
Authors: Yusuke Naito
Affiliations: Mitsubishi Electric Corporation
Abstract: PRO (Pseudorandom Oracle) is an important security of hash functions because it ensures that the hash function inherits all properties of a random oracle up to 
the PRO bound (e.g., security against length extension attack, collision resistant security, preimage resistant security and so on). 
In this paper, we propose new blockcipher-based double-length hash functions, which are PROs up to $\order(2^n)$ query complexity in the ideal cipher model. 
Our hash functions use a single blockcipher, which encrypts an $n$-bit string using a $2n$-bit key, and maps an input of arbitrary length to an $n$-bit output. 
Since many blockciphers supports a $2n$-bit key (e.g. AES supports a $256$-bit key), 
the assumption to use the $2n$-bit key length blockcipher is acceptable. 
To our knowledge, this is the first time double-length hash functions based on a single (practical size) blockcipher with birthday PRO security. \\
{\bf Keywords: }Double-length hash function, pseudorandom oracle, ideal cipher model.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 38
Title: The Cryptographic Power of Random Selection
Authors: Matthias Krause and Matthias Hamann
Affiliations: University of Mannheim
Abstract: The principle of random selection and the principle of adding biased noise are new paradigms used in several recent papers for constructing lightweight RFID authentication protocols. The cryptographic power of adding biased noise can be characterized by the hardness of the intensively studied Learning Parity with Noise (LPN) Problem. In analogy to this, we identify a corresponding learning problem called RandomSelect for random selection and study its complexity. Given L secret linear functions f_1,...,f_L : {0,1}^n -> {0,1}^a, RandomSelect(L,n,a) denotes the problem of learning f_1,...,f_L from values (u,f_l(u)), where the secret indices l \in {1,...,L} and the inputs u \in {0,1}^n are randomly chosen by an oracle. We take an algebraic attack approach to design a nontrivial learning algorithm for this problem, where the running time is dominated by the time needed to solve full-rank systems of linear equations over O(n^L) unknowns. In addition to the mathematical findings relating correctness and average running time of the suggested algorithm, we also provide an experimental assessment of our results.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 42
Title: On various families of twisted Jacobi quartics
Authors: Jérôme Plût
Affiliations: Université Versailles--Saint-Quentin, France
Abstract: We provide several results on families of twisted Jacobi quartics. We
give new addition formulæ for two models of twisted Jacobi quartic
elliptic curves, which represent respectively~$1/6$ and~$2/3$ of all
elliptic curves, with respective costs $7\mathbf{M}
+ 3\mathbf{S} + \mathbf{D}_a$ and~$8 \mathbf{M} + 3 \mathbf{S} +
\mathbf{D}_a$. These formulæ allow addition and doubling of points,
except for points differing by a point of order two.
-
Furthermore, we give an intrinsic characterization of elliptic curves
represented by the classical Jacobi quartic, by the action of the
Frobenius endomorphism on the $4$-torsion subgroup. This allows us to
compute the exact proportion of elliptic curves representable by various
models (the three families of Jacobi quartics, plus Edwards and Huff
curves) from statistics on this Frobenius action.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 51
Title: Boomerang Distinguishers on MD4-Based Hash Functions: First Practical Results on Full 5-Pass HAVAL
Authors: Yu Sasaki
Affiliations: NTT Corporation
Abstract: In this paper, we study the boomerang attack on MD4-based hash functions,
and present a practical 4-sum distinguisher against the compression function of full 5-pass HAVAL.
Our attack is based on the previous work by Kim \emph{et al.}, which proposed
boomerang distinguishers on the encryption mode of MD4, MD5, and HAVAL in the related-key setting.
Firstly, we prove that the differential path for 5-pass HAVAL used in the previous boomerang distinguishers
contains a critical flaw and thus the attack cannot work.
We then search for the new differential path.
Finally, by using the new path,
we mount the distinguisher on the compression function of full 5-pass HAVAL
which generates the 4-sum quartets with a complexity of
approximately $2^{11}$ compression function computations.
As far as we know, this is the first result on the full compression function of 5-pass HAVAL
that can be computed in practice.
Our attacks are implemented on a PC and we present generated 4-sum quartets.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 53
Title: Proof of Empirical RC4 Biases and New Key Correlations
Authors: Sourav Sen Gupta and Subhamoy Maitra and Goutam Paul and Santanu Sarkar
Affiliations: Indian Statistical Institute and Jadavpur University
Abstract: In SAC 2010, Sepehrdad, Vaudenay and Vuagnoux have reported some empirical biases between the secret key, the internal state variables and the keystream bytes of RC4, by searching over a space of all linear correlations between the quantities involved. In this paper, for the first time, we give theoretical proofs for all such significant empirical biases. Our analysis not only builds a framework to justify the origin of these biases, it also brings out several new conditional biases of high order. We establish that certain conditional biases reported earlier are spurious and are actually correlated with a third event with much higher probability. This gives rise to the discovery of new keylength-dependent biases of RC4, some as high as $50/N$. The new biases in turn result in successful keylength prediction from the initial keystream bytes of the cipher.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 58
Title: Efficient Schemes for Anonymous yet Authorized and Bounded Use of Cloud Resources
Authors: Daniel Slamanig
Affiliations: Carinthia University of Applied Sciences
Abstract: In this paper we present \textit{anonymous yet authorized and bounded} cloud resource schemes. Contrary to many other approaches to security and privacy in the cloud, we aim at hiding behavioral information of users consuming their cloud resources, e.g. CPU time or storage space, from the cloud provider. More precisely, users should be able to purchase a contingent of resources from a cloud provider and be able to anonymously consume their resources till their limit is reached (in case of storage they can also reclaim these resources back anonymously). We present a definition of such schemes along with an instantiation based on Camenisch-Lysyanskaya signatures and investigate the security of our construction. Then, we extend the scheme to another scheme providing even more privacy for users (by even hiding the issued resource bound during interactions and thus providing full anonymity to users) and provide some useful extensions for both schemes. We also underpin the efficiency of our schemes by means of experimental results obtained from an implementation.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 59
Title: Conditional Differential Cryptanalysis of Trivium and KATAN
Authors: Simon Knellwolf and Willi Meier and Maria Naya-Plasencia
Affiliations: FHNW, Switzerland
Abstract: The idea of conditional differential cryptanalysis was presented at ASIACRYPT 2010. We improve the technique by using automatic tools to find and analyze the involved conditions. Using these improvements we cryptanalyze the stream cipher Trivium and the KATAN family of lightweight block ciphers.  For both ciphers we obtain new cryptanalytic results which are the best known so far. For reduced variants of Trivium we obtain a large class of weak keys that can be practically distinguished up to 961 of 1152 rounds.  For the KATAN family we focus on its security in the related-key scenario and obtain practical key-recovery attacks for 120 of 254 rounds of KATAN32, 103 rounds of KATAN48 and 90 rounds of KATAN64.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 60
Title: Very Compact Hardware Implementations of the Block Cipher CLEFIA
Authors: Toru Akishita and Harunaga Hiwatari
Affiliations: Sony Corporation
Abstract: The 128-bit block cipher CLEFIA is known to be highly efficient in hardware
implementations.
This paper proposes very compact hardware implementations of CLEFIA-128.
Our implementations are based on novel serialized architectures in the data processing block.
Three types of hardware architectures are implemented and synthesized using
a 0.13 $\mu$m standard cell library.
In the smallest implementation, the area requirements are only 2,488 GE, which
is about half of the previous smallest implementation as far as we know.
Furthermore, only additional 116 GE enable to support decryption.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 63
Title: Some Instant- and Practical-Time Related-Key Attacks on KTANTAN32/48/64
Authors: Martin Ågren
Affiliations: Lund University
Abstract: The hardware-attractive block cipher family KTANTAN was studied by Bogdanov and Rechberger who identified flaws in the key schedule and gave a match-in-the-middle attack. We revisit their result before investigating how to exploit the weakest key bits. We then develop several related-key attacks, e.g., one on KTANTAN32 which finds 28 key bits in time equivalent to $2^{3.0}$ calls to the full KTANTAN32 encryption. The main result is a related-key attack requiring $2^{28.44}$ time (half a minute on a current CPU) to recover the full 80-bit key. For KTANTAN48, we find three key bits in the time of one encryption, and give several other attacks, including full key recovery. For KTANTAN64, the attacks are only slightly more expensive, requiring $2^{10.71}$ time to find 38 key bits, and $2^{32.28}$ for the entire key. For all attacks, the requirements on related-key material are modest as in the forward and backward directions, we only need to flip a single key bit. All attacks succeed with probability one.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 69
Title: Provable Chosen-Target-Forced-Midfix Preimage Resistance
Authors: Elena Andreeva and Bart Mennink
Affiliations: KULeuven
Abstract: This paper deals with definitional aspects of the herding attack of Kelsey and Kohno, and investigates the provable security of several hash functions against herding attacks.
Firstly, we define the notion of chosen-target-forced-midfix (CTFM) as a generalization of the classical herding (chosen-target-forced-prefix) attack to the cases where the challenge message is not only a prefix but may appear at any place in the preimage. Additionally, we identify four variants of the CTFM notion in the setting where salts are explicit input parameters to the hash function. Our results show that including salts without weakening the compression function does not add up to the CTFM security of the hash function.
Our second and main technical result is a proof of CTFM security of the classical Merkle-Damgaard construction. The proof demonstrates (asymptotically) that the herding attack of Kelsey and Kohno is optimal and no attack with lower complexity exists. Our security analysis applies to a wide class of narrow-pipe Merkle-Damgaard based iterative hash functions, including enveloped Merkle-Damgaard, Merkle-Damgaard with permutation, HAIFA, zipper hash and hash-twice hash functions. To our knowledge, this is the first positive result in this field.
Finally, having excluded salts from the possible tool set for improving narrow-pipe designs' CTFM resistance, we resort to various message modification techniques. Our findings, however, result in the negative and we demonstrate CTFM attacks with complexity of the same order as the Merkle-Damgaard herding attack on a broad class of narrow-pipe schemes with specific message modifications.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 74
Title: ASC-1: An Authenticated Encryption Stream Cipher
Authors: Goce Jakimoski and Samant Khajuria
Affiliations: Stevens Institute of Technology, USA and Aalborg University, Denmark
Abstract: The goal of the modes of operation for authenticated encryption is to achieve faster encryption and message authentication by performing both the encryption and the message authentication in a single pass as opposed to the traditional encrypt-then-mac approach, which requires two passes. Unfortunately, the use of a block cipher as a building block limits the performance of the authenticated encryption schemes to at most one message block per block cipher evaluation.
-
In this paper, we propose the authenticated encryption scheme ASC-1 (Authenticating Stream Cipher One). Similarly to LEX, ASC-1 uses leak extraction from different AES rounds to compute the key material that is XOR-ed with the message to compute the ciphertext. Unlike LEX, the ASC-1 operates in a CFB fashion to compute an authentication tag over the encrypted message. We argue that ASC-1 is secure by reducing its (IND-CCA , INT-CTXT) security to the problem of distinguishing the case when the round keys are uniformly random from the case when the round keys are generated by a key scheduling algorithm.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 78
Title: Improved Three-Way Split Formulas for Binary Polynomial  Multiplication
Authors: Christophe Negre, Murat Cenk, Anwar Hasan
Affiliations: University of Waterloo, Canada
Abstract: In this paper we deal with 3-way split formulas for binary field multiplication with five recursive multiplications of smaller sizes. We first recall the formula proposed by Bernstein at CRYPTO 2009 and derive the complexity of a parallel multiplier based on this formula. We then propose a new of set of 3-way split formulas with five recursive multiplications based on field extension. We evaluate their complexities and provide a comparison.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 83
Title: Improved Analysis of ECHO-256
Authors: Jérémy Jean, María Naya-Plasencia, Martin Schläffer
Affiliations: ENS Paris, France ; FHNW Windisch, Switzerland ; IAIK TU Graz, Austria
Abstract: ECHO-256 is a second-round candidate of the SHA-3 competition. It is an
AES-based hash function that has attracted a lot of interest and
analysis. Up to now, the best known attacks were a distinguisher on the
full internal permutation and a collision on four rounds of its compression
function. The latter was the best known analysis on the compression
function as well as the one on the largest number of rounds so far. In this 
paper, we extend the compression function results to get a distinguisher on 
7 out of 8 rounds using rebound techniques. We also present the first 5-round
collision attack on the ECHO-256 hash function.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 84
Title: Faster Hashing to G_2
Authors: Laura Fuentes-Castañeda, Edward Knapp, Francisco Rodríguez-Henríquez
Affiliations: Computer Science Department CINVESTAV-IPN, University of Waterloo, Computer Science Department CINVESTAV-IPN
Abstract: An asymmetric pairing $e\colon \G_2\times \G_1\mapsto \G_T$ is considered such that $\G_1=E(\D F_p)[r]$ and $\G_2=\tilde E(\D F_{p^{k/d}})[r]$, where $r$ is a large prime, $k$ is the embedding degree of $E$, and $\tilde E$ is the degree-$d$ twist of $E$ over $\D F_{p^{k/d}}$. Hashing to $\G_1$ is considered easy, while hashing to $\G_2$ is done by selecting a random point $Q$ in $\tilde E(\D F_{p^{k/d}})$ and computing the hash value $cQ$, where $c\cdot r$ is the order of $\tilde E(\D F_{p^{k/d}})$. We show that for a large class of curves, one can hash to $\G_2$ in $\bigO(1/\gf(k)\log c)$ time, as compared with the previously best-known $\bigO(\log p)$. In the case of BN curves, we are able to double the speed of hashing to $\G_2$. For higher-embedding-degree curves, the results can be more dramatic. We also show how to reduce the cost of the final-exponentiation step in the calculation of a pairing by a fixed number of field multiplications.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 87
Title: Analysis of the Initial and Modified Versions of the Candidate 3GPP Integrity Algorithm 128-EIA3
Authors: Thomas Fuhr, Henri Gilbert, Jean-René Reinhard, Marion Videau
Affiliations: ANSSI
Abstract: In this paper we investigate the security of the two most recent
versions of the message authentication code 128-EIA3, which is
considered for adoption as a third integrity algorithm in the emerging
3GPP standard LTE. We first present an efficient existential forgery
attack against the June 2010 version of the algorithm.  This attack
allows, given any message and the associated MAC value under an
unknown integrity key and an initial vector, to predict the MAC value
of a related message under the same key and the same initial vector
with a success probability 1/2. We then briefly analyse the tweaked
version of the algorithm that was introduced in January 2011 to
circumvent this attack. We give some evidence that while this new
version offers a provable resistance against similar forgery attacks
under the assumption that (key, IV) pairs are never reused by any
legitimate sender or receiver party, some of its design features limit
its resilience against IV reuse.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Number: 98
Title: Sublinear scalar multiplication on hyperelliptic Koblitz curves
Authors: Hugo Labranda and Michael Jacobson, Jr.
Affiliations: ENS Lyon  and University of Calgary
Abstract: Recently, Dimitrov et. al. proposed a novel algorithm
for scalar multiplication of points on elliptic Koblitz curves that
requires a provably sublinear number of point additions in the size of
the scalar.  Following some ideas used by this article, most notably
double-base expansions for integers, we generalize their methods to
hyperelliptic Koblitz curves of arbitrary genus over any finite field,
obtaining a scalar multiplication algorithm requiring a sublinear
number of divisor additions.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++