Title: ECDLP and Improved Baby-Step Giant-Step
| Speaker: | Randy Yee |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
The ECDLP is a classic problem whose presumed hardness is the basis for many cryptosystems. As far as general purpose ECDLP algorithms go, the most commonly used is the Pollard rho algorithm, a probabilistic algorithm with asymptotic run time \surd N where N is the size of the group in which the discrete log is being solved. While Pollard rho is the typical method of choice, an alternate, fairly naive method for solving ECDLP exists known as the Baby-Step Giant-Step algorithm.
A recent paper by Galbraith, Wang and Zhang showed that using surprisingly simple techniques, this algorithm can be sped up significantly in the context of computing ECDLPs, concluding that certain variants of BSGS have superior average case run time compared to Pollard rho.
The presentation will be based on the following paper:
https://eprint.iacr.org/2015/605.pdf
For more information about our reading group, please visit our webpage
http://www.math.uwaterloo.ca/~deolivei/reading.htm