Another look at non-uniformity

Neal Koblitz and Alfred Menezes
Groups Complexity Cryptology, 5 (2013), 117-140.

Abstract: We argue that it is unnatural and undesirable to use the non-uniform model of complexity for practice-oriented security reductions in cryptography.

Journal paper       Eprint paper

Related material:
  • Another look at provable security, invited presentation by Alfred Menezes at Eurocrypt 2012 (April 18, 2012).
  • Non-uniform cracks in the concrete: the power of free precompuation, article by Dan Bernstein and Tanja Lange (June 4, 2012; updated on March 6 2013). Slides from recent lectures are available here and here.
    Read the negative reports from EUROCRYPT 2013 and ASIACRYPT 2012 and CRYPTO 2013 (and here) referees and responses by Bernstein and Lange. In our opinion, the treatment of the Bernstein-Lange paper by these program committees is an example of the "complacency, arrogance and efforts to suppress alternative viewpoints [which are] antithetical to the scientific spirit" that we speak about on the main page of this web site.
  • Slides from a lecture entitled "Non-uniformity" by Neal Koblitz given at ECC 2012 (October 30, 2012).
  • Slides from a lecture entitled "NIST P-256 has a cube-root ECDL algorithm" by Dan Bernstein given at ECC 2012 (October 30, 2012).