Rabin Fingerprinting is one of my favorites of his contributions. It's a "rolling hash" that allows you to quickly compute a 32-bit (or larger) hash at *every* byte offset of a file. It is used most notably to do file block matching/deduplication when those matching blocks can be at any offset. It's tragically underappreciated.
I've been meaning to write up a tutorial as part of my Galois Field series. Someday..
Thank you again!
This replaced some O(n²) searches through ASCII text, reducing search time from dozens of seconds to fractions of a second.
0 - https://github.com/ttkb-oss/mipsmatch 1 - https://github.com/ttkb-oss/mipsmatch/wiki/Identifiers
I especially like how if you end up with hash characteristics that you don't like, your can just select a different irreducible Galois polynomial and now you've got a whole new hash algorithm. It's like tuning to a different frequency.
For me it means I don't have to worry about cases where there aren't enough nearby fingerprints for the annotation to adhere to, I can just add or remove polynomials until I get a good density.
e.g., x minus x is zero, even for Euler, so therefore…
Found on Archive, https://web.archive.org/web/20210509160248/http://www.eecs.h...
Cryptography and Preventing Collusion in Second Price (Vickery) Auctions - Michael Rabin
https://www.youtube.com/watch?v=4cmCBVrVQqc
No chalkboard but more lectures
https://youtu.be/nbePExzSTQ0?si=KkTbwfwj5rMtQUhD&t=681 - פלאי תורת ההצפנות ויישומיה לתהליכים פיננסיים (The wonders of cryptography and financial applications)
https://www.youtube.com/watch?v=N_LG5Hcc8mM - Lecture 7 - Zero Knowledge Proofs and Applications Michael Rabin
For those interested in searching for more here's a Hebrew search string you can use: "פרופסור מיכאל רבין הרצאה" interesting enough Google and YT search yield results in English and Hebrew but possibly different ones than just searching in English.
EDIT: One more:
A friend of mine was one of his graduate students and a teaching assistant for the class. He pointed out to me once that Professor Rabin would state many of his points during lecture twice. Once I started listening more carefully, I found this to be true. It was both subtle and pedagogically effective.
English was not his first language, but he enjoyed his struggles with it. I remember him stumbling over the pronunciation of a word during class. Giving up with a smile, he said, "This is a word I know only from books."
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 the algorithms discovered by Merkle, Diffie, Hellman and Rabin are necessary and 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. Thus Rabin is the one who has shown how the previously proposed methods of digital signing must be used in practice. For example, the original signing algorithm proposed by RSA could trivially be broken and it became secure only in the modified form described by Rabin, i.e. with the use of a one-way hash function.
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 been included in the definition of secure hash functions.
Because this 4th 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, which do not use one-way hash functions, for instance GCM, which is today the most frequently used authentication algorithm on the Internet.
RSA were the first to provide a practical and easy to understand implementation and that had a huge impact in practice.
That's not to downplay Rabin's or others contribution. That RSA pursued a certain commercial strategy that you may or may not like is not really relevant.
He is a Turing Award winner.
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 and I believe that it is important to know who are the true authors of the things that one uses daily. Connecting to this site or to any other site with https uses digital signatures that depend on the collision-resistant hash functions defined by Rabin and Merkle.
The Wikipedia article about Michael O. Rabin lists many of his achievements, but all those that are listed there are much less important than his contribution to the definition of the one-way hash functions, which lead to secure digital signatures.
Wikipedia mentions only the Rabin signature algorithm, but that has negligible importance, because it has been used only very rarely. On the other hand all other signature algorithms are based on the work of Rabin, by using secure hash functions.
I really enjoyed reading it.