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.
Postdoc, Cryptographic Algorithms Group, CISPA, Saarland University, Germany
The Cryptographic Algorithms Group is offering a 2-year post-doc position. We are part of the Center for IT-Security and Privacy (short: CISPA). The CISPA was founded in October 2011 as a competence center for IT security at Saarland University. It is a joint endeavor of Saarland University (UdS) and its on-site partner institutions: the Max Planck Institute for Informatics (MPI-INF), the Max Planck Institute for Software Systems (MPI-SWS), and the German Research Center for Artificial Intelligence (DFKI).
Requirements: A PhD in cryptography and related areas, excellence in research proven for example by publications in IACR conferences and workshops or venues like IEEE S&P, ACM CCS, NDSS, USENIX Security,…
Applicants interested in the positions should provide the following information in pdf format with the application:
- Research Statement
- List of publications, mark your top 2
- 2 reference letters
Expected starting date is Nov, 1st.
Cryptographic Algorithms Group: www.ca.cs.uni-saarland.de