Structure-Preserving Signatures from Standard Assumptions, Revisited, by Eike Kiltz and Jiaxin Pan and Hoeteck Wee
Structure-preserving signatures (SPS) are pairing-based signatures
where 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.
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.
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-based
public-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.
Two PhD Positions in Cryptography, University of Bristol
We are looking for PhD applicants in the areas of practical Multi-Party Computation and in Multi-Linear Maps and associated techniques. The positions include a tax free stipend as well as payment of your tuition fees. The projects are with partners in the USA and so travel to the USA will be a major component of the projects.
Please contact Nigel Smart, as soon as possible, to informally discuss the positions.