*21:17* [Pub][ePrint]
Combined Side-Channel and Fault Analysis Attack on Protected Grain Family of Stream Ciphers, by Abhishek Chakraborty and Bodhisatwa Mazumdar and Debdeep Mukhopadhay
In this paper, we first demonstrate a new Differential Power Analysis (DPA) attack technique against the Grain family of stream ciphers (Grain v1 and Grain-128) by resynchronizing the cipher multiple times with the same value of the secret \\emph{key} and randomly generated different initialization vectors (IVs). Subsequently, we develop a combined side channel and fault analysis attack strategy targeting various fault attack countermeasures for the Grain cipher family.We considered clock glitch induced faults occurring in practice for a hardware implementation of the cipher to devise our novel attack technique. Our proposed combined attack strategy works well even if the \\emph{useful} ciphertexts are not available to the adversary.

Further, the power trace classifications of a Grain cipher implementation on SASEBO G-II standard side channel evaluation board is shown in order to validate our proposed attack against the cipher.

The captured power traces were analyzed using Least Squares Support Vector Machine (LS-SVM) learning algorithm based multiclass classifiers to classify the power traces into the respective

Hamming distance (HD) classes. To extract power samples with high information about HD classes, Signal-to-noise ratio (SNR) metric

was chosen for feature selection. The experimental results of power trace classifications of test set showed a high success rate of $98\\%$ when the five largest SNR sample instants over a clock cycle were chosen as features. Our proposed attack strategy can also be extended to other stream cipher designs based on Fibonacci

configured shift registers.

*21:17* [Pub][ePrint]
Structure-Preserving Signatures from Standard Assumptions, Revisited, by Eike Kiltz and Jiaxin Pan and Hoeteck Wee
Structure-preserving signatures (SPS) are pairing-based signatureswhere all the messages, signatures and public keys are group elements, with

numerous applications in public-key cryptography. We present new,

simple and improved SPS constructions under standard assumptions via a

conceptually different approach. Our constructions significantly

narrow the gap between existing constructions from standard assumptions

and optimal schemes in the generic group model.

*21:17* [Pub][ePrint]
Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm, by Steven D. Galbraith and Ping Wang and Fangguo Zhang
The negation map can be used to speed up the computation of elliptic curve discrete logarithms using either the baby-step-giant-step algorithm (BSGS) or Pollard rho. Montgomery\'s simultaneous modular inversion can also be used to speed up Pollard rho when running many walks in parallel. We generalize these ideas and exploit the fact that for any two elliptic curve points $X$ and $Y$, we can efficiently get $X-Y$ when we compute $X+Y$. We apply these ideas to speed up the baby-step-giant-step algorithm. Compared to the previous methods, the new methods can achieve a significant speedup for computing elliptic curve discrete logarithms.Another contribution of our paper is to give an analysis of the average-case running time of Bernstein and Lange\'s ``grumpy giants and a baby\'\' algorithm, and also to consider this algorithm in the case of groups with efficient inversion.

Our conclusion is that, in the fully-optimised context, both the interleaved BSGS and grumpy-giants algorithms have superior average-case running time compared with Pollard rho.

*21:17* [Pub][ePrint]
McBits: fast constant-time code-based cryptography, by Daniel J. Bernstein and Tung Chou and Peter Schwabe
This paper presents extremely fast algorithms for code-basedpublic-key cryptography, including full protection against timing attacks. For example, at a 2^128 security level, this paper achieves a reciprocal decryption throughput of just 60493 cycles (plus cipher cost etc.) on a single Ivy Bridge core. These algorithms rely on an additive FFT for fast root computation, a transposed additive FFT for fast syndrome computation, and a sorting network to avoid cache-timing attacks.