Discussion

Michael O. Rabin

adrian_b: Michael O. Rabin had important contributions in many domains, but from a practical point of view the most important are his contributions to cryptography.After Ralph Merkle, Whitfield Diffie and Martin Hellman, Michael O. Rabin is the most important of the creators of public-key cryptography.The RSA team (Ron Rivest, Adi Shamir and Leonard Adleman) is better known than Michael O. Rabin, but that is entirely due to marketing and advertising, because they founded a successful business.In reality the RSA algorithm is superfluous and suboptimal. If the RSA team had never discovered this algorithm, that would have had a null impact on the practice of cryptography. Public-key cryptography would have been developed equally well, because only the algorithms discovered by Merkle, Diffie, Hellman and Rabin are sufficient.On the other hand, while without the publications of RSA, cryptography would have evolved pretty much in the same way, without the publications of Michael O. Rabin from the late seventies the development of public-key cryptography would have been delayed by some years, until someone else would have made the same discoveries.Together with Ralph Merkle, Michael O. Rabin was the one who discovered the need for secure cryptographic hash functions, i.e. one-way hash functions, which are now critical for many applications, including digital signatures.Originally, Merkle defined 2 conditions for one-way hash functions, of resistance to first preimage attacks and second preimage attacks, while Rabin defined 1 condition, of resistance to collision attacks. Soon after that it was realized that all 3 conditions are mandatory, so the 2 definitions, of Merkle and of Rabin, have been merged into the modern definition of such hash functions.Unfortunately, both Merkle and Rabin have overlooked a 4th condition, of resistance to length extension attacks. This should have always be included in the definition of secure hash function.Because this condition was omitted, the US Secure Hash Algorithm Standards defined algorithms that lack this property, which has forced many applications to use workarounds, like the HMAC algorithm, which for many years have wasted time and energy wherever encrypted communications were used, until more efficient authentication methods have been standardized, like GCM, which is the most frequently used algorithm today.

thraxil: I took his Introduction to Cryptography class when he was a visiting professor at Columbia. Absolute master of an old-school chalkboard lecturer. They don't make them like that any more.

opem: It's hard to imagine how a single person managed to accomplish so much. RIP to the great soul :|

snitty: May his memory be a blessing.

puttycat: @dang this deserves a black ribbon

XCSme: I loved implementing the Rabin-Karp algoritm, such a fun and celever solution.

AlecBG: First sentence starts with horrible antisemitism. Can someone fix it? (on my phone with kids so not in a position to)

codingrightnow: It's been fixed.

blondie9x: Can this non genuine AI slop comment be flagged?

fakedang: Still up. Looks like this is going to be another game of hit the hedgehog.

metmac: People keep adding different slurs. Awful and disgraceful.

Findecanor: I don't think that is AI slop. adrian_b often post long posts because he thinks he has a lot to say, but you can often tell that they contain his personal views and points that he thinks are important related to the discussions whereas actual AI slop tends to be bland and generic.

adrian_b: This is no AI slop.On the contrary, you cannot find frequently descriptions about the role of Michael O. Rabin in the creation of public-key cryptography, so few people are aware of it and I bet that no AI model can generate any text even remotely resembling this, because this information cannot be found in any single place in the possible training texts.You can find definitions of secure hash functions everywhere, but pretty much nowhere you will find who are the authors of the conditions that are used in the modern definition and who have introduced the use of one-way hash functions.I did not find this information anywhere, before reading the original publications of Rabin and Merkle from 1978/1979 and some later follow-up papers written by them.You will not find this historical information in Wikipedia.