Thank you Michael Rabin for your excellent work. Rest in Peace.
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..
I recently found his fingerprint algorithm and wrote a utility that uses it to find duplicate MIPS code for decompilation[0] and build unique identifiers that can be used to find duplicates without sharing any potentially copyrighted data[1].
This replaced some O(n²) searches through ASCII text, reducing search time from dozens of seconds to fractions of a second.
I wrote a Rabin—Karp implementation in ~2006 as part of the spam and threat scanning stack for the MX Logic mail service. It was incredibly performant, letting us test {n} bytes against an essentially unlimited number of string signatures in O(n) time.
Important to note that FastCDC is about an order of magnitude for block deduplication and is generally considered the state of art for such an approach (speed of computing the hash is more important than absolutely optimal distribution of hashes).
I'm working on a data annotation system based around Rabin fingerprints. They're a really neat idea.
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.
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.
I took his Computability class in the Hebrew University. He got angry that students were often late to class, and said that this never happened in Harvard...
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.
I took a course from him as a graduate student. I was not (and am still not) a theoretician. But I enjoyed the class and Professor Rabin's lectures.
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."
I had the incredible good fortune to take one of his classes in college, and I loved it so much I took another just to learn from him again. A tremendous intellect AND an incredibly engaging and talented instructor. It would be an exaggeration to say that I knew him, but nevertheless he had a great impact on my education and my life. He will be missed.
Amazing man, with many important contributions over a very long career. The Rabin Cryptosystem (like RSA, but with public exponent 2) is notable for two reasons. First, unlike RSA, it is provably as hard as "factorization" (as he would call it), and second, unlike RSA, it wasn't protected by patent.
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 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.
I think you're vastly underplaying the importance of RSA to cryptography. Personally it was the first time I was exposed to the concept of public key cryptography (in the 1980's). "would have been delayed by some years" is very dismissive. The same thing can be said of many inventions. Yet someone is/was the inventor.
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.
They didn't really found a successful business. They founded a middling business that didn't do much but license a patent until Security Dynamics, a smart card company, bought them and took over the name.
The story that I remember going around is that they each made some millions of dollars. That was a lot of money at the time for academics. I audited a cryptography course given by Adi Shamir in the early 90's and you couldn't tell he was rich though.
"As a young boy, he was very interested in mathematics and his father sent him to the best high school in Haifa, where he studied under mathematician Elisha Netanyahu, who was then a high school teacher."
Interesting. Some people are lucky enough to find their vocation quite early in life.
Sad that the only thing that shows up nowadays in searches tends to be Wikipedia. I miss the democratic internet with lots of quirky sites you could find with ease.
> Benzion Netanyahu ... A scholar of Judaic history, he was also an activist in the Revisionist Zionism movement, who lobbied in the United States to support the creation of the Jewish state.
Thank you! I’m a casual user of Wikipedia but after this thread I went through the history of edits on the article and...oh my.
I have a greater appreciation for folks like you and the other editors who seem to be constantly removing this type of stuf. Some truly horrendous slurs there.
I used to regularly donate to the wikimedia foundation every year. I stopped doing that as I find the whole project is now a political tool and cannot be relied on. Even ignoring vandalism like here, sometimtes the same articles get different meanings depending on the language you view them in.
Different language editions of Wikipedia are completely different projects, with distinct user bases. You're never looking at the "same" article across languages.
In that case, Wikipedia should not link to them (and even distance themselves from the edition) if they purposefully change the content of the article to suit a political agenda. The whole thing became a death match arena of factions as mature as 12 year old kids playing an actual death match arena game... This example here just demonstrates my point.
Wikipedia has demonstrably been ravaged by anti-semitism. Feel free to ignore any of the notes here about Israel / anti-Israeli sentiment which I understand is not clear cut. There's demonstrably antisemitic coalitions editing wikipedia en-masse.
The ADL labels all opponents of Israel as anti-semitic. They don't speak for Jewish people. Their smears help Israel by hurting Jews, so that Zionists can point to Israel as their only refuge. Helping Israel in turn hurts countless other people who are not Jewish, which Zionists mostly don't care about because Zionists are mostly ethno-centric, full of self-pity, regurgitate predictable lies about Israel's history without doing any critical investigation of their own, and have absolutely no principles. You are amplifying this.
I know this because I've grown up around them. I used to be on their side until I found out that they lied to me about certain events - and to such a degree that they swapped around victim and perpetrator. They told me that the Gazans blew up greenhouses when the Israeli settlers left, because of their insane hatred of Jews. Then I found out that the only people who blew up any greenhouses were the Israeli settlers - and that there was even a website set up solely to rebut the claim that the Gazans did it. Then I found out that Zionists didn't care, because of a long litany of grievances that had nothing to do with Palestinians. Then most of them voted for a government that put Ben Gvir in charge of the police force and prisons. Then they passed on a chance to use diplomatic pressure to get Hamas to step down after the 07/10 attack, without launching a vengeful massacre in Gaza.
"@dang" doesn't do anything last I heard (though at this point it's used often enough that maybe the HN folks should consider it). If you want to reach the mods you can contact hn@ycombinator.com I believe.
63 comments:
Thank you Michael Rabin for your excellent work. Rest in Peace.
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!
I recently found his fingerprint algorithm and wrote a utility that uses it to find duplicate MIPS code for decompilation[0] and build unique identifiers that can be used to find duplicates without sharing any potentially copyrighted data[1].
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
That's where I knew the name from. Thank you!
I wrote a Rabin—Karp implementation in ~2006 as part of the spam and threat scanning stack for the MX Logic mail service. It was incredibly performant, letting us test {n} bytes against an essentially unlimited number of string signatures in O(n) time.
Important to note that FastCDC is about an order of magnitude for block deduplication and is generally considered the state of art for such an approach (speed of computing the hash is more important than absolutely optimal distribution of hashes).
I'm working on a data annotation system based around Rabin fingerprints. They're a really neat idea.
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.
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.
Hugely engaging, the margins of my notebook had many of his quips… there was an archive online somewhere.
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...
I know him from Harvard and came here to say pretty much the same thing. RIP.
I took his Computability class in the Hebrew University. He got angry that students were often late to class, and said that this never happened in Harvard...
Any of his "chalkboard" lectures (preferably in English) in open archives of these universities? YouTube searches only bring up Prof Rabin's lectures aided by slides and presentation (ex: https://www.youtube.com/watch?v=thK_qJqx5mo at Tel Aviv Uni / https://www.youtube.com/watch?v=QCX0Ut0hcWw at Harvard).
There's a chalkboard here (used ~44:50):
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:
https://www.youtube.com/watch?v=30wkb46BE1k
I took a course from him as a graduate student. I was not (and am still not) a theoretician. But I enjoyed the class and Professor Rabin's lectures.
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."
I had the incredible good fortune to take one of his classes in college, and I loved it so much I took another just to learn from him again. A tremendous intellect AND an incredibly engaging and talented instructor. It would be an exaggeration to say that I knew him, but nevertheless he had a great impact on my education and my life. He will be missed.
Amazing man, with many important contributions over a very long career. The Rabin Cryptosystem (like RSA, but with public exponent 2) is notable for two reasons. First, unlike RSA, it is provably as hard as "factorization" (as he would call it), and second, unlike RSA, it wasn't protected by patent.
Michael Rabin, 1976 ACM Turing Award Recipient
https://youtu.be/L3FZzGU3n14
Michael Rabin: "godfather of Israeli computer science", https://www.ynetnews.com/health_science/article/byohxvw611l
That sly remark at 22:40 on the telephone ringing :)
It's hard to imagine how a single person managed to accomplish so much. RIP to the great soul :|
Seriously. After reading, I scrolled through his Known For section and thought, “Alright already, leave something for everybody else to work on.”
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 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.
I think you're vastly underplaying the importance of RSA to cryptography. Personally it was the first time I was exposed to the concept of public key cryptography (in the 1980's). "would have been delayed by some years" is very dismissive. The same thing can be said of many inventions. Yet someone is/was the inventor.
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.
They didn't really found a successful business. They founded a middling business that didn't do much but license a patent until Security Dynamics, a smart card company, bought them and took over the name.
The story that I remember going around is that they each made some millions of dollars. That was a lot of money at the time for academics. I audited a cryptography course given by Adi Shamir in the early 90's and you couldn't tell he was rich though.
I mean, I'm sure it turned out great for them, but their reputation definitely isn't rooted in their business acumen.
Nobody has hidden the history of contributions of Rabin to cryptography or computer science.
He is a Turing Award winner.
I would argue that nondeterministic finite automata are both more significant and more practical.
Doctoral advisor - Alonzo Church
TIL. Also just realized that Alan Turing was also one of Church’s doctoral students. We stand on the shoulders of these giants.
May his memory be a blessing.
I loved implementing the Rabin-Karp algoritm, such a fun and celever solution.
A founding father of computer science has passed away. Thank you for building the foundations that made modern AI possible.
"As a young boy, he was very interested in mathematics and his father sent him to the best high school in Haifa, where he studied under mathematician Elisha Netanyahu, who was then a high school teacher."
Interesting. Some people are lucky enough to find their vocation quite early in life.
That's Benjamin Netanyahu's brother apparently.
Sad that the only thing that shows up nowadays in searches tends to be Wikipedia. I miss the democratic internet with lots of quirky sites you could find with ease.
actually his uncle.
Wow hadn't heard of him https://en.wikipedia.org/wiki/Elisha_Netanyahu
Yeah.
Everything is intertwined at some level.
Interesting.
What a small world. But the entire extended family are professors. Too bad one became a politician.
Benzion?
> Benzion Netanyahu ... A scholar of Judaic history, he was also an activist in the Revisionist Zionism movement, who lobbied in the United States to support the creation of the Jewish state.
Benzion’s son (and Elisha’s nephew) Benjamin Netanyahu is the Israeli prime minister.
Then there are at least two.
First sentence starts with horrible antisemitism. Can someone fix it? (on my phone with kids so not in a position to)
It's been fixed.
Thank you! I’m a casual user of Wikipedia but after this thread I went through the history of edits on the article and...oh my.
I have a greater appreciation for folks like you and the other editors who seem to be constantly removing this type of stuf. Some truly horrendous slurs there.
Still up. Looks like this is going to be another game of hit the hedgehog.
People keep adding different slurs. Awful and disgraceful.
Anti-Jew rhetoric is at a level unseen since WW2. It’s the new normal. It’s horrible.
Yeah, I come into contact with some form of Jewish hate on a literal daily basis now. It’s been this way for months.
*It’s the old normal :(
The article has now been been semi-protected to prevent vandalism by anonymous users.
I had a look at the history of todays edits and it is appalling.
Indeed I just figured out how to view them. Wow. https://en.wikipedia.org/w/index.php?title=Michael_O._Rabin&...
An admin has now semi-protected the article.
I used to regularly donate to the wikimedia foundation every year. I stopped doing that as I find the whole project is now a political tool and cannot be relied on. Even ignoring vandalism like here, sometimtes the same articles get different meanings depending on the language you view them in.
Different language editions of Wikipedia are completely different projects, with distinct user bases. You're never looking at the "same" article across languages.
In that case, Wikipedia should not link to them (and even distance themselves from the edition) if they purposefully change the content of the article to suit a political agenda. The whole thing became a death match arena of factions as mature as 12 year old kids playing an actual death match arena game... This example here just demonstrates my point.
Wikipedia has demonstrably been ravaged by anti-semitism. Feel free to ignore any of the notes here about Israel / anti-Israeli sentiment which I understand is not clear cut. There's demonstrably antisemitic coalitions editing wikipedia en-masse.
https://www.adl.org/resources/report/editing-hate-how-anti-i...
The ADL labels all opponents of Israel as anti-semitic. They don't speak for Jewish people. Their smears help Israel by hurting Jews, so that Zionists can point to Israel as their only refuge. Helping Israel in turn hurts countless other people who are not Jewish, which Zionists mostly don't care about because Zionists are mostly ethno-centric, full of self-pity, regurgitate predictable lies about Israel's history without doing any critical investigation of their own, and have absolutely no principles. You are amplifying this.
I know this because I've grown up around them. I used to be on their side until I found out that they lied to me about certain events - and to such a degree that they swapped around victim and perpetrator. They told me that the Gazans blew up greenhouses when the Israeli settlers left, because of their insane hatred of Jews. Then I found out that the only people who blew up any greenhouses were the Israeli settlers - and that there was even a website set up solely to rebut the claim that the Gazans did it. Then I found out that Zionists didn't care, because of a long litany of grievances that had nothing to do with Palestinians. Then most of them voted for a government that put Ben Gvir in charge of the police force and prisons. Then they passed on a chance to use diplomatic pressure to get Hamas to step down after the 07/10 attack, without launching a vengeful massacre in Gaza.
@dang this deserves a black ribbon
"@dang" doesn't do anything last I heard (though at this point it's used often enough that maybe the HN folks should consider it). If you want to reach the mods you can contact hn@ycombinator.com I believe.
I did.
What is a black ribbon?
Probably meant black HN top bar.
An HN website tweak as a sign of respect on the passing of notable contributors to the tech world:
<https://blog.willmeye.rs/whos-received-a-black-bar/>