I have added the selection logic change from Trilema to this website. If you see any strange, please let me know!
Constructing Digital Signatures from One Way Function
August 19th, 2019Op. 52
Constructing Digital Signatures from One Way Function
Leslie Lamport
Computer Science Laboratory
SRI International
18 October 1979
CSL 98
333 Ravenswood Ave. Menlo Park, California 94025
(415) 3266200 Cable: SRI INTL MPK TWX: 9103731246
1. Introduction
A digital signature created by sender P for a document m is data item o_{p}(m) having the property that upon receiving m and o_{p}(m) one can determine (and if necessary prove in court of law) that P generated the document m .
A one way function is function that is easy to compute, but whose inverse is difficult to compute^{1}. More precisely one way function T is a function from set of data objects to a set of values having the following two properties:
 Given any value v , it is computationally infeasible to find a data object d such that T(d) = v .
 Given any data object d , it is computationally infeasible to find a different data object d' such that T(d') = T(d) .
If the set of data objects is larger than the set of values, then such a function is sometimes called one way hashing function.
We will describe a method for constructing digital signatures from such a one way function T . Our method is an improvement of a method devised by Rabin^{2}. Like Rabin's, it requires the sender P to deposit a piece of data o in some trusted public repository for each document he wishes to sign. This repository must have the following properties:
 o can be read by anyone who wants to verify P's signature.
 It can be proven in court of law that P was the creator of o .
Once o has been placed in the repository, P can use it to generate a signature for any single document he wishes to send.
Rabin's method has the following drawbacks not present in ours.
 The document must be sent to single recipient Q , who then requests additional information from P to validate the signature. P cannot divulge any additional validating information without compromising information that must remain private to prevent someone else from generating new document m' with valid signature o_{p}(m').
 For a court of law to determine if the signature is valid, it is necessary for P to give the court additional private information.
This has the following implications.
 P  or a trusted representative of P must be available to the court.
 P must maintain private information whose accidental disclosure would enable someone else to forge his signature on a document.
With our method, P generates a signature that is verifiable by anyone, with no further action on P's part. After generating the signature, P can destroy the private information that would enable someone else to forge his signature. The advantages of our method over Rabin's are illustrated by the following considerations when the signed document m is a check from P payable to Q .
 It is easy for Q to endorse the check payable to third party R by sending him the signed message "make m payable to R ". However, with Rabin's scheme, R cannot determine if the check m was really signed by P , so he must worry about forgery by Q as well as whether or not P can cover the check. With our method, there is no way for Q to forge the check, so the endorsed check is as good as check payable directly to R signed by P . (However, some additional mechanism must be introduced to prevent Q from cashing the original check after he has signed it over to R .)
 If P dies without leaving the executors of his estate the information he used to generate his signatures, then Rabin's method cannot prevent Q from undetectably altering the check m  for example, by changing the amount of money payable. Such posthumous forgery is impossible with our method.
 With Rabin's method, to be able to successfully challenge any attempt by Q to modify the check before cashing it, P must maintain the private information he used to generate his signature. If anyone (not just Q ) stole that information, that person could forge a check from P payable to him. Our method allows P to destroy this private information after signing the check.
2. The Algorithm
We assume a set M of possible documents, set K of possible keys^{3}, and set V of possible values. Let S denote the set of all subsets of {1, ... , 40} containing exactly 20 elements. (The numbers 40 and 20 are arbitrary, and could be replaced by 2n and n. We are using these numbers because they were used by Rabin, and we wish to make it easy for the reader to compare our method with his.)
We assume the following two functions.
 A function F : K → V with the following two properties:
 Given any value v in V , it is computationally infeasible to find a key k in K such that F(k) = v .
 For any small set of values v_{1}, ... , v_{m} , it is easy to find a key such that F(k) is not equal to any of the v_{i} .
 A function G : M → S with the property that given any document m in M , it is computationally infeasible to find document m' ≠ m such that G(m') = G(m)
For the function F , we can use any one way function T whose domain is the set of keys. The second property of F follows easily from the second property of the one way function T . We will discuss later how the function G can be constructed from an ordinary one way function.
For convenience, we assume that P wants to generate only a single signed document. Later, we indicate how he can sign many different documents. The sender P first chooses 40 keys k_{i} such that all the values F(k_{i}) are distinct. (Our second assumption about F makes this easy to do.) He puts in public repository the data item o = (F(k_{1}), ... , F(k_{40})) . Note that P does not divulge the keys k_{i} , which by our first assumption about F cannot be computed from o .
To generate a signature for a document m , P first computes G(m) to obtain a set [i_{1}, ... , i_{20}] of integers. The signature consists of the 20 keys k_{i1}, ... , k_{i20} . More precisely, we have o_{p}(m) = (k_{i1}, ... , k_{i20}) , where the i_{j} are defined by the following two requirements:
 G(m) = {i_{1}, ... , i_{20}}
 i_{1} < ... < i_{20}
After generating the signature, P can destroy all record of the 20 keys k_{s} with s not in G(m) .
To verify that 20tuple (h_{1}, ... , h_{20}) is valid signature o_{p}(m) for the document m, one first computes G(m) to find the i_{j} and then uses o to check that for all j , h_{j} is the i_{j}^{th} key. More precisely, the signature is valid if and only if for each j with 1 ≤ j ≤ 20 : F(h_{j}) → o_{ij} , where o_{i} denotes the i^{th} component of o , and the i_{j} are defined by the above two requirements.
To demonstrate that this method correctly implements digital signatures, we prove that it has the following properties.
 If P does not reveal any of the keys k_{i} , then noone else can generate valid signature o_{p}(m) for any document m .
 If P does not reveal any of the keys k_{j} except the ones that are contained in the signature o_{p}(m) , then noone else can generate valid signature o_{p}(m') for any document m' ≠ m .
The first property is obvious, since the signature o_{p}(m) must contain 20 keys k_{i} such that F(k_{i}) = o_{i} , and our first assumption about F states that it is computationally infeasible to find the keys k_{i} just knowing the values F(k_{i}) .
To prove the second property, note that since noone else can obtain any of the keys k_{i} , we must have o_{p}(m') = o_{p}(m) . Moreover, since the o_{i} are all distinct, for the validation test to be passed by o_{p}(m') we must also have G(m') = G(m) . However, our assumption about G states that it is computationally infeasible to find such document m' . This proves the correctness of our method.
For P to send many different documents, he must use a different o for each one. This means that there must be sequence of 40tuples o_{1}, o_{2}, ... and the document must indicate which o_{i} is used to generate that document's signature. The details are simple, and will be omitted.
3. Constructing the Function G
One way functions have been proposed whose domain is the set of documents and whose range is a set of integers of the form {0, ... , 2^{n}  1} for any reasonably large value of n . (It is necessary for n to be large enough to make exhaustive searching over the range of T computationally infeasible.) Such functions are described in [1] and [2]. The obvious way to construct the required function G is to let T be such a one way function, and define G(m) to equal R(T(m)) , where R : {0, ... , 2^{n}  1} → S .
It is easy to construct function R having the required range and domain. For example, one can compute R(s) inductively as follows:
 Divide s by 40 to obtain quotient q and a remainder r
 Use r to choose an element x from {1, ... , 40} (This is easy to do, since 0 ≤ r ≤ 40.)
 Use q to choose 19 elements from the set {1, ... , 40}  {x} as follows:
 Divide q by 39 to obtain quotient ...
It requires careful analysis of the properties of the one way function T to be sure that the resulting function G has the required property. We suspect that for most one way functions T , this method would work. However, we cannot prove this.
The reason constructing G in this manner might not work is that the function R from {0, ... , 2^{n}} into S is a many to one mapping, and the resulting "collapsing" of the domain might defeat the one way nature of T . However, it is easy to show that if the function R is one to one, then property (ii) of T implies that G has the required property. To construct G we need only find an easily computable one to one function R from {0, ... , 2^{n}  1} into S , for a reasonably large value of n .
We can simplify our task by observing that the function G need not be defined on the entire set of documents. It suffices that for any document m , it is easy to modify m in a harmless way to get new document that is in the domain of G. For example, one might include a meaningless number as part of the document, and choose different values of that number until he obtains a document that is in the domain of G . This is an acceptable procedure if (i) it is easy to determine whether a document is in the domain, and (ii) the expected number of choices one must make before finding a document in the domain is small.
With this in mind, we let n = 40 and define R(s) as follows: if the binary representation of s contains exactly 20 ones, then R(s) = {i : the i^{th} bit of s equals one} , otherwise R(s) is undefined. Approximately 13% of all 40 bit numbers contain exactly 20 ones. Hence, if the one way function T is sufficiently randomizing, there is a 0.13 probability that any given document will be in the domain of G . This means that randomly choosing documents (or modifications to a document), the expected number of choices before finding one in the domain of G is approximately 8. Moreover, after 17p choices, the probability of not having found document in the domain of G is about 1/10^{p}. (If we use 60 keys instead of 40, the expected number of choices to find document in the domain becomes about 10, and 22p choices are needed to reduce the probability of not finding one to 1/10^{p}.)
If the one way function T is easy to compute, then these numbers indicate that the expected amount of effort to compute G is reasonable. However, it does seem undesirable to have to try so many documents before finding one in the domain of G . We hope that someone can find more elegant method for constructing the function G , perhaps by finding a one to one function R which is defined on a larger subset of {0, ... , 2^{n}} .
Note; We have thus far insisted that G(m) be a subset of {1, ... , 40} consisting of exactly 20 elements. It is clear that the generation and verification procedure can be applied if G(m) is any proper subset. An examination of our correctness proof shows that if we allow G(m) to have any number of elements less than 40, then our method would still have the same correctness properties if G satisfies the following property:
 For any document m , it is computationally infeasible to find a different document m' such that G(m') is a subset of G(m) .
By taking the range of G to be the collection of 20 element subsets, we insure that G(m') cannot be proper subset of G(m) . However, it may be possible to construct a function G satisfying this requirement without constraining the range of G in this way.

Editors note: Some characters in the original paper were changed to members of the Roman alphabet.
 Diffie, W. and Hellman, M. "New Directions in Cryptography". IEEE Trans. on Information Theory IT22 (November 1976), 644654. [↩]
 Rabin, M. "Digitalized Signatures", in Foundations of Secure Computing, Academic Press (1978), 155168. [↩]
 The elements of K are not keys in the usual cryptographic sense, but are arbitrary data items. We call them keys because they play the same role as the keys in Rabin's algorithm. [↩]
2020 Presidential Candidates
August 5th, 2019The United States will have its 4year presidential election next year. Here are my thoughts on the candidates running for the position.
On the Republican side, there is Donald Trump. I do not see any way that anybody else gets the nomination. Unseating a sitting president is unheard of^{1}, and the republican base seems fairly happy with Trump's performance, so we can assume that Trump will get the nomination. There are some aspects of Trump's administration that I like (like the nomination of Gorsuch to the supreme court), and he has not done as many bad things as his opponents claimed he would do when he was elected, so although he has a way of making every subject a source of drama I would not be horribly disappointed to see him win another four year term.
The Democrats seem to be using the strategy of throwing everything they can at the electorate and seeing if anything sticks. There is Obama's VP Joe Biden for the people who pine for the good old days days of the Obama administration before the racists took over our country. There are Senators Elizabeth Warren and Kirsten Gillibrand^{2} for people who really liked Hillary Clinton and like to point out by how much she won the popular vote. There are old candidates (Gravel is 89, apparently still alive and sort of running^{3} ) and young candidates (Gabbard is only 38). There are good looking candidates (Tulsi Gabbard might be the first presidential candidate anyone would want to see in a bikini) and ugly candidates (ahem, most of them, but I'm thinking of Kamala Harris here). And there are candidates from a variety of races (White, Hispanic, Black, Asian, Samoan, Indian, etc). There is even a mix of people with lots of political experience, like Bernie Sanders who has been in the Senate longer than I have been alive, down to people like Yang who have never been elected to a political office before. And the candidates are proposing free stuff in just as much diversity: free college, free healthcare, free $1000 per month to everybody, free housing, and probably more that I have forgotten.
The big problem is that the field is just too big. Democrats are struggling to get behind a candidate because there are too many of them running. And that problem is exacerbated by the media who seem to think each of these people have a chance at winning the nomination. While I like a couple proposals (which I will go into below) from some of these dark horses, at some point you just have to be honest and only list the people who have a serious chance. Looking back on recent history (post WWII), people who get elected president, or even nominated, have been one of four things: vice president from a previous administration^{4}, governor of a state^{5}, US senator^{6}, or already have nationwide name recognition^{7}. Even using these criteria, there are still Biden (VP), Bullock^{8}, Inslee^{9}, Hickenlooper^{10}, Patrick^{11} (governors), and Bennet, Booker^{12}, Gillibrand, Gravel, Harris,^{13} Klobuchar, Sanders, Warren (senators), that's still twelve eleven nine eight nine seven six people, which should be plenty to pick between.
Speaking of a couple of the longshot candidates, I like Gabbard's stance on reigning in the US military and cutting back on military spending. And I like Castro's stance on loosening immigration laws. I see immigration as a good thing. While both of these are only polling in the low single digits, they would make good vicepresidential candidates to offset an older presidential candidate.
 The last time a sitting president was not renominated by their party was Grover Cleveland in 1896 [↩]
 Update 20190829: Gillibrand just dropped out. [↩]
 Update: Looks like Gravel just dropped out. [↩]
 VP's: Truman, Johnson, Nixon, Humphery, Ford, Mondale, Bush I [↩]
 Governors: Dewey, Stevenson, Carter, Reagan, Dukakis, B Clinton, Bush II, Romney [↩]
 Senators: Kennedy, Goldwater, Dole, Kerry, McCain, Obama, H Clinton [↩]
 Had name recognition: Eisenhower  General in WWII and helped start NATO, Perot  billionaire oil tycoon, Trump  millionaire and TV personality [↩]
 Update: Bullock dropped out. [↩]
 Update: Inslee dropped out. [↩]
 Update: Hickenlooper dropped out. [↩]
 Update: Deval Patrick joined the race. [↩]
 Update 20200113: Booker Dropped out [↩]
 Update: Harris drops out. [↩]
Korihor
August 5th, 2019The teachings of Korihor^{1}:
O ye that are bound down under a foolish and a vain hope, why do ye yoke yourselves with such foolish things? Why do ye look for a Christ? No man can know of anything which is to come.
Behold, these things which ye call prophecies, which ye say are handed down by holy prophets, behold, they are foolish traditions of your fathers.
How do ye know of their surety? Behold, ye cannot know of things which ye do not see; therefore ye cannot know that there shall be a Christ.
Ye look forward and say that ye see a remission of your sins. But behold, it is the effect of a frenzied mind; and this derangement of your minds comes because of the traditions of your fathers, which lead you away into a belief of things which are not so.
There can be no atonement made for the sins of men, but every man fares in this life according to the management of the creature; therefore every man prospers according to his genius, and every man conquers according to his strength; and whatsoever a man does is no crime.
When a man is dead, that is the end thereof.
Why do I go about perverting the ways of the Lord? Why do I teach this people that there shall be no Christ, to interrupt their rejoicings? Why do I speak against all the prophecies of the holy prophets? Because I do not teach the foolish traditions of your fathers, and because I do not teach this people to bind themselves down under the foolish ordinances and performances which are laid down by ancient priests, to usurp power and authority over them, to keep them in ignorance, that they may not lift up their heads, but be brought down according to thy words.
Ye say that this people is a free people. Behold, I say they are in bondage. Ye say that those ancient prophecies are true. Behold, I say that ye do not know that they are true.
Ye say that this people is a guilty and a fallen people, because of the transgression of a parent. Behold, I say that a child is not guilty because of its parents.
And ye also say that Christ shall come. But behold, I say that ye do not know that there shall be a Christ.
And ye say also that he shall be slain for the sins of the world — And thus ye lead away this people after the foolish traditions of your fathers, and according to your own desires; and ye keep them down, even as it were in bondage, that ye may glut yourselves with the labors of their hands, that they durst not look up with boldness, and that they durst not enjoy their rights and privileges.
Yea, they durst not make use of that which is their own lest they should offend their priests, who do yoke them according to their desires, and have brought them to believe, by their traditions and their dreams and their whims and their visions and their pretended mysteries, that they should, if they did not do according to their words, offend some unknown being, who they say is God — a being who never has been seen or known, who never was nor ever will be.
 The Book of Mormon, Alma, Chapter 30. [↩]
Windows 10: Clear Clipboard
June 24th, 2019During my workflow I sometimes have to copy a series of images from a remotely accessed computer (running Windows 7) to a file on my main computer (running Windows 10). I have noticed an intermittent problem where I go to copy a second image and when I paste I still get the first image, as if the clipboard was never replaced. This can be quite frustrating if the images are similar enough that I don't notice the problem until later, and I have to go back and reprocess data to generate the image that did not copy correctly.
I don't know if this is a problem with Windows 10, or something about trying to get Windows 10 and 7 to work together, or something in the remote desktop access software. The way I have found to get around this is to clear out the clipboard on my host computer, and then copying works again.
To add a shortcut to the Windows 10 desktop that clears the clipboard, use the following procedure:
 Right click on the desktop and choose "New > Shortcut".
 A popup asks for the location of the item, enter the text:
C:\Windows\System32\cmd.exe /c echo off  clip
Then click "Next".  Give it a name, like "Clear Clipboard", then click "Finish".
 Optional  Change the icon: Right click on the shortcut and select "Properties". Click on the "Change Icon ..." button. Click on "Browse", select an icon file (look in C:\Windows\system32\SHELL32.dll for a large selection).
 Optional  Give it a keyboard shortcut: In the "Properties" window, click on the "Shortcut key" box and type a letter, the shortcut will become Control + Alt + the letter.
Alphabet
June 17th, 2019Being the father of a threeyearold whose name begins with H, I have lately been hearing this version of "The Alphabet Song":
A, B, C, D, B, F, E,
H!
Now my know my ABC, next time you sing with me.
She just wants to get to the important letter, and then she is done. And then she will sing it over and over and over again. I wish I had given her a name starting with Z, then she would know the alphabet all the way through.
A Dinner Conversation
June 10th, 2019For my first year of college I attended a large private university in Utah. For Homecoming, about ten of us went out to dinner together before the dance. We were from a variety of places across the US; I came from Michigan, my companions were from places such as California, Utah, Texas, and North Carolina.
At one point the conversation turned to the types of fast food chains found where each of us lived. There was a Carl's Jr. located across the street from our campus, and I had eaten there for the first time a couple weeks before since there are none in Michigan. We talked about Jack in the Box, and a couple other chains, and then the conversation moved on.
A couple minutes later, Andrea, from Washington, who had been pretty quiet up to this point, innocently said "Do you guys have Dick's? You know, they are like In'N'Out?"
After a few seconds of silence, she realized what she had said and turned bright red.
Jokes
June 4th, 2019I was setting a fire in the fireplace, and my 3 yo niece says to me "Be careful Uncle Peter, the fire is spicy."
The rest of these are some of my old favorites:
Q. What is bright orange and sounds like a parrot?
A. A carrot

Q. What happens when the smog lifts in Los Angeles?
A. UCLA

My uncle Joe smoked a pack a day and drank a case of beer every night, and when he died he didn't look a day over fifty. He died when he was twentynine.

Superman is flying around town when he sees Wonder Woman on a rooftop, naked, lying on her back with her legs spread out and her eyes closed. Glancing around, Superman decides nobody else can see her, so he flies down, unzips his pants, and faster than a speeding bullet gives her a good humping, then zooms away.
Wonder Woman opens her eyes and says "What just happened?"
The Invisible Man says "I don't really know, but my ass hole hurts all of a sudden!"

Joe runs an ice cream truck. Every day he stops at this park, and every day he sees this retarded kid hanging around. The kid always asks for some ice cream, but he doesn't have any money. Joe feels sorry for the kid, so he says "I'll make you a deal: if you can clap your hands three times, then I will give you an ice cream cone."
So the kid says "OK", and gives it a try: WHIFF, one hand goes over the other. And Joe says "Well, maybe you can get it tomorrow."
The next day the kid comes by, and Joe gives him the same deal. The kid smiles really big, spreads his arms out, and CLAP, WHIFF, misses it on the second time.
He tries again the next day: CLAP, CLAP, WHIFF.
The next day the kid comes by and Joe gives him one more try. He concentrates really hard, and slowly moves his arms: CLAP, CLAP, CLAP.
Joe says "Horray, you finally got it, here's your ice cream cone."
The kid takes the ice cream cone and SPLORCH, smashes it into his forehead.^{1}

Eagles may soar, but weasels don't get sucked into jet engines.

Give a man a fish and he will eat for a day.
Teach a man to fish and you will never see him again on Sundays.

After the great flood, Noah gets off the Ark and says to all the animals "Go forth, multiply, and replenish the Earth."
A little while later, he goes around to make sure everybody is doing OK. Everywhere he goes he sees baby animals, cubs, kits, foals, calves, kids, piglets, puppies, and so on, until he comes to a pair of snakes with no baby. He says to them "Why have you not reproduced as your God commanded?" And they say "We would, but we need you to cut down some trees."
Noah is a little confused, but he goes and does it anyway. He cuts down a couple trees and leaves them for the snakes.
A while later he comes back, and to his surprise there are a bunch of baby snakes. So he asks the snakes "Why did you need me to cut down a tree before you had kids?"
And they answered: "We're adders, we need logs to multiply."

Spiderman: So, can you guys give me any advice on, you know, how to last longer with the ladies?
Superman: Don't ask me, they say I'm faster than a speeding bullet.
The Flash: No idea, I'm literally the fastest man on Earth.
Vision: I have no genitals.

Teacher: Please use the word "waffle" in a sentence.
Johnny: "Come on over and my waffle make you something to eat."

At Jack's funeral, somebody asks Judy, his wife of sixty years: "I have heard that you and Jack never had an argument in your whole marriage, how did you do it?"
And she says "That's not completely true. We did have one argument, let me tell you the story:
Back when we were young we got married and we took this horse and carriage out for our honeymoon. We were going along and a fox ran by, startled the horse and made it bolt. Jack wrestled it down to a stop, then he got down, stood in front of the horse, pointed his finger and said "Don't do that. That's your first warning."
So he got back in the carriage next to me and we carried on. We were having such a pleasant ride, when an owl swooped past, startled the horse and made it bolt. Again Jack wrestled it to a stop, got down in front of the horse, pointed his finger and said "Don't do that. That's your second warning."
Well, we hadn't gone another twenty paces when a dog barked nearby, and the horse bolted again. Jack wrestled the horse to a stop, got down off the carriage, pulled out a gun and shot the horse in the head.
It took me by surprise, and I said "Jack, what did you have to shoot the horse for, it wasn't his fault!"
And he looked me in the eye, pointed his finger, and said "Don't argue with me. That's your first warning."
"And we never had another argument after that."

"Doctor, doctor, I woke up this morning and my dick is orange!"
"Hmm, were you doing anything unusual last night?"
"Well, no, I was just eating Cheetos and watching porn ..."

"Doctor, doctor, my sister thinks she's a chicken!"
"Hmm, how long has this been going on?"
"For a couple months now."
"Why haven't you said anything before?"
"We don't have a lot of money, and we could really use the eggs."

"Doctor, doctor, there is something wrong with me! It hurts every time I do this," patient pushes his finger against his head, "Ouch! Or when I do this," patient pushes his finger against his arm, "Ouch! Or when I do this," patient pushes his finger against his knee, "Ouch! What is wrong with me?"
"Hmm, your finger is broken"

John and Jane are a young couple, recently married. Jane wants to make something nice for her husband for Friday night dinner, and she remembers he always says how much he loved his mother's baked chicken dinner. So she looks up a recipe in her handmedown cookbook, spends a couple hours prepping, and has the bird on the table just as John walks in the door. After the meal, Jane asks if he liked it, and John says "It was pretty good, but it wasn't as good as my Momma always made it."
Jane is a bit disappointed, but the next week she decides to try again. She scours the internet looking for the best baked chicken recipe, spends all afternoon prepping, and has the bird on the table just as John walks in the door. After the meal, Jane asks if he liked it, and John says "It was pretty good, but it wasn't as good as my Momma always made it."
Jane is a bit worried that she will never live up to her motherinlaw, but she decides to give it one more try the next Friday. She spends the weekend getting tips and tricks from all her older girl friends, and gets a recipe book from the library with the finest cuisine from around the world. She spends all day prepping, and has the bird on the table just as John walks in the door. After the meal, she again asks if he liked it, and John says again "It was pretty good, but it wasn't as good as my Momma always made it."
Now Jane is furious that her husband does not appreciate all her hard work. So about ten minutes before John comes home on Friday she throws a frozen bird into the oven and scorches it. John comes home and she sets the blackened chicken down in front of him and lets he have a taste. After a couple bites, John says "This is amazing, it tastes just like Momma always made it!"
 This one is funner to tell facetoface so you can act out the kid's movements. [↩]