This is an automated archive.
The original was posted on /r/cryptocurrency by /u/gigabyteIO on 2024-01-12 23:24:23+00:00.
Original Title: Did you know that Silvio Micali, Turing Award winner and founder of Algorand, is indirectly referenced multiple times in the Bitcoin whitepaper? His foundational work is used throughout modern cryptography, including Probabilistic Encryption, Zero-Knowledge Proofs, and Verifiable Random Functions.
He's also the 'M' in the hash-based signature algorithm LMS that makes use of a winternitz one time signature and merkle tree to generate a key pair. And even better the algorithm is quantum resistant (at least until a quantum algorithm is found that can break it.) For now LMS is one of the candidates to replace ECDSA signatures.
Link to paper:
If you haven't read the Bitcoin white paper I highly recommend even if you don't understand it, it's beneficial to read from the direct source and it's surprisingly short:
Reference 2 and Reference 4 both reference the 3rd:
[2] H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.
[4] D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping," In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
Bitcoin white papers third reference is:
[3] S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
link to paper: https://link.springer.com/content/pdf/10.1007%2F3-540-38424-3_32.pdf
This references Micali's work:
[2] IT. Blum and S. Xiicali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850-864, Nov. 1984.
[9] S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, 28:270-299, April 1984.
[lo] S. Goldwasser, S. Micali, and R. Rivest. A secure digital signature scheme. SIAM Journal on Computing, 17(2):281-308, 1988.
Without Micalis foundational work in Probabilistic Encryption and Interactive Proof System, Bitcoin and Ethereum may not have been a thing.
Summary of Probabilistic Encryption and Interactive Proof Systems:
Probabilistic Encryption
Shafi Goldwasser and Silvio Micali produced one of the most influential papers in computer science, “Probabilistic Encryption,” as graduate students in 1983, by introducing the question “What is a secret?” Their standards were very high: an adversary (third party) should not be able to gain any partial information about a secret. Their definition of the security of encryption as a “game” involving adversaries has become a trademark of modern cryptography. Their approach, known as the simulation paradigm, bypassed the traditional enumeration of desired properties that marked the definition of security, and led to the construction of a secure encryption scheme.
This method provided a robust defense against malicious attempts to make these schemes deviate from their prescribed functionality. They introduced two notions of encryption security – semantic security and indistinguishability of encrypted messages from each other – thus capturing the important aspects of the subject. They argued that these measures must be met for schemes to provide security across the wide range of cryptography applications. In contrast with prevailing trends in the field, they observed that to satisfy their security definition, encryption schemes must be randomized rather than deterministic, with many possible encrypted texts corresponding to each message. This development revolutionized the study of cryptography and laid the foundation for the theory of cryptographic security that was developed throughout much of the 1980s.
Interactive Proof Systems
One of the most significant contributions of Goldwasser and Micali is their 1985 paper with Charles Rackoff, titled “The Knowledge Complexity of Interactive Proof Systems.” It introduced knowledge complexity, a concept that deals with hiding information from an adversary, and is a quantifiable measure of how much “useful information” could be extracted. The paper initiated the idea of “zero-knowledge” proofs, in which interaction (the ability of provers and verifiers to send each other messages back and forth) and probabilism (the ability to toss coins to decide which messages to send) enable the establishment of a fact via a statistical argument without providing any additional information as to why it is true.
Zero-knowledge proofs were a striking new philosophical idea that provided the essential language for speaking about security of cryptographic protocols by controlling the leakage of knowledge. Subsequent works by Oded Goldreich, Micali, and Avi Wigderson and by Michael Ben-Or, Goldwasser, and Wigderson showed that every multiparty computation can be carried out securely, revealing to the players no more knowledge than prescribed by the desired outcome. These papers exhibited the power and utility of zero-knowledge protocols, and demonstrated their ubiquitous and omnipotent character.
The paper identified interactive proofs as a new method to verify correctness in the exchange of information. Going beyond cryptography, interactive proofs can be much faster to verify than classical proofs, and can be used in practice to guarantee correctness in a variety of applications.
TL;DR: Satoshi Nakamoto used Silvio Micali's fundamental early work on public-key cryptosystems, pseudorandom functions, and digital signatures to create Bitcoin.