lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Thu, 13 Feb 2014 18:33:10 0800 From: "Dennis E. Hamilton" <dennis.hamilton@....org> To: <discussions@...swordhashing.net> Cc: <sneves@....uc.pt> Subject: OT: [PHC] multiplyhardening (Re: NoelKDF ready for submission) The significant amount of number theoretic lore that crops up here fascinates me too, although I am not fluent with it. I missed the "Duality in Addition Chains" in my scrutiny, though I have it [;<). The additionsubtraction business works because of the law of exponents, of course. In the 1998 (third) edition of The Art of Computer Programming, volume 2, it appears that those results and others are folded in, often in the exercises and the discussion that are part of the solutions. Pippenger's observation about the duality of direction is buried in there. The Bernstein paper is a wonderful expansion, and the page 10 "Setting the record straight" is a hoot, especially considering patenting of mathematical methods. (The mentioned patent has expired, but the problem of recognizing prior art when it is not identified the same way is telling.) Thanks for both links. I now understand who is being referred to as BJD. (I'm a newcomer here.)  Dennis Original Message From: Samuel Neves [mailto:sneves@....uc.pt] Sent: Wednesday, February 12, 2014 18:20 To: discussions@...swordhashing.net Subject: Re: [PHC] multiplyhardening (Re: NoelKDF ready for submission) This thread has gone rather offtopic by now, but this happens to be a topic that I like :) [ ... ] Additionsubtraction chains are popular with elliptic curves, where "division", i.e., subtraction, is very cheap. Similarly, multiplication by a constant can make good use of subtractions. You can see them (plus many other techniques) put to good use in, e.g., [1]. We can do much better than the binary method, at very little computational cost. Namely, by doing a small precomputation at the start and processing w bits of the exponent at a time, we can perform lg(e) + lg(e)/w + 2^w multiplications on average instead of lg(e) + lg(e)/2. There are many improvements building on this idea, of course; the survey by Dan Bernstein [2] is a good read on the subject, on top of Knuth. > I couldn't find more in any of the Knuth Collected Works papers that I have, and the early paper might be in the Discrete Mathematics volume. "Duality in Addition Chains", coauthored with Christos Papadimitriou, is reprinted in Chapter 31 of Selected Papers on the Analysis of Algorithms. It does not contain any particular improvement, but it contains an interesting observation: for each addition chain that "scans" the exponent bits lefttoright, there is another addition chain that scans righttoleft, which is its transpose (when looking at the chains as matrices). [1] http://www.hyperelliptic.org/EFD/precomp.pdf [2] http://cr.yp.to/papers/pippenger.pdf
Powered by blists  more mailing lists