World-leading Computer Scientists: Leslie B Lamport (Clocks, LaTeX, Byzantine Generals and Post Quantum Crypto)

Related page: https://medium.com/asecuritysite-when-bob-met-alice/clocks-latex-byzantine-generals-and-post-quantum-crypto-meet-the-amazing-leslie-b-lamport-b2ade4b590d7 Demo: https://asecuritysite.com/hashsig/lamport  Introduction I write this article in Medium and with its limited text editor, but I really would love to write it in LaTeX. Before the monopoly of Microsoft Word, there were document mark-up systems such as Lotus Manuscript, and where we had a basic editor to produce publishing-ready content. The GUI came along, and all the back-end stuff was pushed away from the user. For many, this is fine, but for those whose output is focused on sharing and dissemination of research, it is often the only way to work. In research, LaTeX is King and is a fully formed method of laying out — and sharing — research outputs. In the past few years, we have published over 100 research papers, and not one of them has been created in Microsoft Word. And for this, I thank Leslie Lamport. In fact, ask our kids about Newton, Faraday or Einstein, and they could probably tell you something about them. But ask them about Whitfield Diffie, Shafi Goldwasser, or Leslie B Lamport, and they would probably look quizzical? Their future world, though, is probably going to be built around some of the amazing minds that built the most amazing structure ever created … The Internet. To Leslie Lamport So, I am so privileged to be an academic researcher. For me, teaching, innovation and research go hand-in-hand, and where the things I research into gives me ideas for innovation, and which I can then integrate these things into my teaching. The continual probing of questions from students also pushes me to think differently about things, and so the cycle goes on. But, we are all just building on the shoulders of true giants, and there are few larger giants than Leslie Lamport — the creator of LaTeX. For me, every time I open up a LaTeX document, I think of the work he did on creating LaTeX, and which makes my research work so much more productive. If I was still stuck with Microsoft Office for research, I would spend half of my time in that horrible equation editor, or in trying to integrate the references into the required format, or in formatting Header 1 and Header 2 to have a six-point spacing underneath. So, for me, the contest between LaTeX and Microsoft Word is a knock-out in the first round. And one of the great things about Leslie is that his work is strongly academic — and which provides foundations for others to build on. For this, he did a great deal on the ordering of task synchronisation, in state theory, cryptography signatures, and fault tolerance. LaTeX I really can say enough about how much LaTeX — created in 1984 — helps my work. I am writing a few books just now, and it allows me to lay out the books in the way that I want to deliver the content. There’s no need for a further mark-up, as I work on the output that the reader will see. But the true genius of LaTeX is the way that teams can work on a paper, and where there can be async to GitHub and where version control is then embedded. Overall we use Overleaf, but we’re not tie-in to that, and can move to any editor we want. But the process is just so much better than Microsoft Word, especially when creating a thesis. Word is really just the same old package it was in the 1990s, and still hides lots away, and which makes it really difficult to create content which can easily be changed for its layout. With LaTeX, you create the content and can then apply whatever style you want. Clocks Many in the research community think that the quality measure of a paper is the impact factor of the journal that it is submitted to, or in the amount of maths that it contains. But, in the end, it is the impact of the paper, and how it changes thinking. For Leslie, in 1978, his paper on clocks changed our scientific world and is one of the most cited papers in computer science [here]: Byzantine Generals Problem In 1981, Leslie B Lamport defined the Byzantine Generals Problem [here]: And in a research world where you can have 100s of references in a paper, Leslie only used four (and which would probably not be accepted these days for having so few references): Within this paper, the generals of a Byzantine army have to agree to their battle plan, in the face of adversaries passing in order information. In the end, we aim to create a way of passing messages where if at least two out of three of the generals are honest, we will end up with the correct battle plan. So why don’t we build computer systems like this, and where we support failures in parts of the system, or where parts of the system may be taken over for malicious purposes? And the answer is … no reason, it just that we are stuck with our 1970s viewpoint of the computing world, and everything works perfectly, and security is someone else’s problem to fix. So, we need a system where we create a number of trusted nodes to perform a computation, and then an election process at the end to see if we have a consensus for a result. If we have three generals (Bob, Alice and Eve), we need two of them to be honest, which means we can cope with one of our generals turning bad: In this case, Eve could try and sway Trent by sending the wrong command, but Bob and Alice will build a better consensus, and so Trent will go with them. The work can then be defined as MPC (Multiparty Computation) and where we have multiple nodes getting involved to produce the final result. In many cases, this result could just be as simple as a Yes or No, and as to whether a Bitcoin transaction is real or fake, or whether an IoT device has a certain voltage reading. The Lamport Signature Sometime soon we perhaps need to wean ourselves of our existing public key methods and look to techniques that are more challenging for quantum computers. With the implementation of Shor’s algorithm [here] on quantum computers, we will see our RSA and Elliptic Curve methods being replaced by methods which are quantum robust. One method is the Lamport signature method and which was created by Leslie B. Lamport in 1979 [here]: At the current time, it is thought to be a quantum robust technique for signing messages. When we sign a message we take its hash and then encrypt it with our private key. The public key is then used to prove it and will prove that we signed it with our private key. The Lamport signature uses 512 random hashes for the private key, and which are split into Set A and Set B. The public key is the hash of each of these values. The size of the private key is 16KB (2×256×256 bits) and the public key size is also 16 KB (512 hashes with each of 256 bits). The basic method of creating a Lamport hash signature is: We create two data sets with 256 random 256-bit numbers (Set A and Set B). These are the private key (512 values). Next, we take the hash of each of the random numbers. This will give 512 hashes and will be the public key. We then hash the message using SHA-256, and then test each bit of the hash (0 … 255). If it is a 0, we use the ith number in Set A, else we use the ith number from Set B. The signature is then 256 random numbers (taken from either Set A or Set B) and the public key is the 512 hashes (of Set A and Set B). This process is illustrated below: We can use the Lamport method for one-time signing, but, in its core format, we would need a new public key for each signing. The major problem with Lamport is thus that we can only sign once with each public key. We can overcome this, though, by creating a hash tree which is a merger of many public keys into a single root. A sample run which just shows the first few private keys and the first public keys: ==== Private key (keep secret) =====Priv[0][0] (SetA): 6f74f11f20953dc91af94e15b7df9ae00ef0ab55eb08900db03ebdf06d59556cPriv[0][1] (SetB): 4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619Priv[1][0] (SetA): 19f0f71e913ca999a23e152edfe2ca3a94f9869ba973651a4b2cea3915e36721Priv[1][1] (SetB): 04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097ePriv[2][0] (SetA): 15ef65eda3ee872f56c150a5eeecff8abd0457408357f2126d5d97b58fc3f24ePriv[2][1] (SetB): 8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073Priv[3][0] (SetA): 1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346Priv[3][1] (SetB): e9dcbdd63d53a1cfc4c23ccd55ce008d5a71e31803ed05e78b174a0cbaf43887==== Public key (show everyone)=====Pub[0][0]: 7f2c9414db83444c586c83ceb29333c550bedfd760a4c9a22549d9b4f03e9ba9Pub[0][1]: 4bc371f8b242fa479a20f5b6b15d36c2f07f7379f788ea36111ebfaa331190a3Pub[1][0]: 663cda4de0bf16a4650d651fc9cb7680039838d0ccb59c4300411db06d2e4c20Pub[1][1]: 1a853fde7387761b4ea22fed06fd5a1446c45b4be9a9d14f26e33d845dd9005f==== Message to sign ===============Message: The quick brown fox jumps over the lazy dogSHA-256: d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592==== Signature =====================Sign[0]: 4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619Sign[1]: 04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097eSign[2]: 8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073Sign[3]: 1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346The signature test is True In this case, we take the random number and then convert it to a string. So the SHA-256 signature of “6f74f11f20953dc91af94e15…0db03ebdf06d59556c” is 7f2c9414db83444c586c…49d9b4f03e9ba9. If can be seen that the hash of the message (“The quick brown fox jumps over the lazy dog”) has a hex D value at the start, which is 1101 in binary, and we see we take from SetB [0], SetB [1], SetA [2] and SetB [3]. A demonstration is given here. Conclusions The Internet we have now built on the foundations that Leslie applied. On 18 March 2013, he received the AM Turing Award (which is like a Nobel Prize in Computer Science). At the time, Bill Gates said: Leslie has done great things not just for the field of computer science, but also in helping make the world a safer place. Countless people around the world benefit from his work without ever hearing his name. … Leslie is a fantastic example of what can happen when the world’s brightest minds are encouraged to push the boundaries of what’s possible. Basically, much of our computing world is still using the amazing foundation that was created in the 1970s and 1980s. We tip our hats to Diffie Hellman, Shafi Goldwasser, Ralph Merkle, Ron Rivest, Adi Shamir, and, of course, Leslie B Lamport. As a note, that while Leslie’s paper on Clocks is cited over 12,000 times, the Diffie Hellman paper is cited over 19,300 times: We really should be integrating computer science into our school curriculum, and show that it has equal standing to physics, biology and chemistry, and it will shape our future world as much as the others. Why not teach kids about public-key cryptography in the same way that we talk about Newton?