<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small">On Thu, Feb 13, 2020 at 2:41 PM Jon Callas <<a href="mailto:jon@callas.org">jon@callas.org</a>> wrote:</div></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
> On Feb 12, 2020, at 5:09 PM, Ryan Carboni <<a href="mailto:ryacko@gmail.com" target="_blank">ryacko@gmail.com</a>> wrote:<br>
> <br>
> The Rabin cryptosystem is listed on wikipedia. I don't understand the<br>
> math behind it particularly well, but "the Rabin cryptosystem has the<br>
> advantage that it has been mathematically proven to be computationally<br>
> secure against a chosen-plaintext attack as long as the attacker<br>
> cannot efficiently factor integers, while there is no such proof known<br>
> for RSA."<br>
<br>
Oversimplifying slightly, Rabin is like RSA but where p == q, meaning that it's p^2 rather than p*q.<br>
<br>
All of our public-key cryptosystems have had growing pains that I'll call engineering considerations. The math hasn't changed at a math level, but at a security level, it's not quite as simple as the math. With RSA, for example, it took us years to figure out padding, and once we figured out padding, there were more years to get it right. (Look at the OAEP history.) There are DH issues with picking a generator (e.g. 2 is a great generator for encryption, but not signing). With ECC, we learned that the math done mod p is secure in a way that it done mod p^n is not. In plainer language, it would be really nice to do a "binary" curve, where we use normal binary bignums as opposed to mod some prime that's really close to some 2^n. NTRU went through lots of iterations before we thought we had it right and this grander issue pervades a lot of post-quantum work and is why cautious steps into hybrid schemes are a good idea.<br>
<br>
By the time the fiddly bits in Rabin got sorted out, RSA was dominant. Zix email encryption used Rabin at one time and might even still.<br>
<br>
        Jon<br></blockquote><div><br></div><div class="gmail_default" style="font-size:small">Indeed, provable security has proved remarkably brittle in practice. The big problem with formal systems is working out the requirements. Been there, done that, wrote my doctoral dissertation on the subject.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">The thing that held back Rabin was the RSA patent which RSA labs asserted covered Rabin's scheme.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">What worries me on post quantum is that we have this binary approach assuming that urgent planning for post quantum means it is inevitable. That is the wrong way to look at things. Given the reliance on public key crypto, we have to take very seriously a 5% risk that someone will build a quantum cryptanalysis class machine in the next 20 years.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">But then we have folk saying 'don't do anything new that isn't post quantum secure'. Well that is turning a 5% risk into a 100% certainty and the state of the physics doesn't justify that. I did particle physics experiments and that is essentially what today's quantum machines look like. Sure people can add more QBits to a supercooled computer and get press out of it. But we all know that is a dead end. The real game is trapped ions and we aren't really close to getting them to the point where we can run them at significant scale. </div></div></div>