Family Dynamics - The most sexist quiz ever


Take this quiz with your significant other to make sure you are on the same page where family dynamics are concerned, so that you can identify where she needs to improve so that you will be happier together.

Q. How should a woman dress while doing the housework?
A. Heels and Pearls
B. Barefoot

Q. When should a woman have dinner on the table?
A. 5:00 sharp every night
B. Whenever the man comes home at night

Q. How frequently should a couple have sex?
A. Whenever the man asks
B. Every night

Q. After the woman serves dinner, who should wash the dishes?
A. The woman
B. The kids
C. The servants

Q. When a woman has emotional troubles, who should she talk to?
A. Her mom
B. Her girl friends
C. The dog

Q. When a man has emotional troubles, he should:
A. Drink a beer
B. Work out
C. Get laid

Q. If the kids get in trouble at school, a woman should:
A. Take care of it so as not to bother the man
B. Tell the kids "Just wait till your father gets home"

Q. The man needs pants. The woman should:
A. Buy nice pants and keep them ironed for the man
B. Buy care-free pants that don't need ironing

Q. Everybody gets in the car. Who is driving?
A. The man

Q. Everybody sits in front of the TV, what should happen next?
A. The man uses the remote to select the show the man wants
B. The man uses the remote to select the show the woman wants

Post vs Article


Sometimes when people read your writings they see things you take for granted. For example, my previous article begins "In this post ..." which prompted this discusion in #trilema:

mp_en_viaje: peterl & all : would you mind terribly if you referred to your articles, on your blogs, as articles ? it's what they are, i get it, you post them, but calling them "posts" makes about as much sense as calling cars "a drived" and girls "a fucked". you don't go about bars with a "hey, fucked! wanna do shots ?", do you ?
mp_en_viaje: it's bad grammar to begin with, what desophistication is this!
spyked: mp_en_viaje, it's "post"<->"fuck" tho, innit? so "she was a good fuck" is a closer analogy
mp_en_viaje: heh, i guess that's true huh
mp_en_viaje: i dunno, it fucking grates, on the level of wow kiddos saying "rouge" for rogue and midwesterner 15yos saying "scratch" for "itch".
spyked: tbf, I can see the argument. "article" was already there, so adding the "post" slang is somewhat similar to how romanians added the new meaning for "locatie" in the lang. what's wrong with "loc" anyway
diana_coman: - technically it was "a blog post"; going for correctness there, I would even question wtf is "blog" anyway, since I get it, binary log except I don't write in binary, what.
ossabot: Logged on 2019-11-05 04:46:58 mp_en_viaje: peterl & all : would you mind terribly if you referred to your articles, on your blogs, as articles ? it's what they are, i get it, you post them, but calling them "posts" makes about as much sense as calling cars "a drived" and girls "a fucked". you don't go about bars with a "hey, fucked! wanna do shots ?", do you ?
diana_coman: so yeah, it is correct to call them articles and to call the "blog" a book I suppose.
diana_coman: or what, gazette
mp_en_viaje: what's wrong with having a blog fulla articles ?
mp_en_viaje: moreover, what we do has so little in common with what the bleaters call posts... the facebook items are properly called posts. dozen-charactger gibberish.
diana_coman: yes, but "post" there for all its similarity to "to post to the blog" is just as made up, as far as I can see; a blog post, as there is a newspaper article, dunno; and in the vein of "just as much to do with what they are doing otherwise", wouldn't that hold for articles too?
diana_coman: what, those articles they write in the new yorker or the wired or what
mp_en_viaje: seems to me article's exactly what we're doing.
mp_en_viaje: nah, article is a wider word than that. "articles of incorporation" predates the newspaper / tin alley morti di fame trying to steal it.
diana_coman: ah, in that sense; yes, that would be it indeed.
diana_coman: all right, articles it is!
mp_en_viaje: was my thinking
mp_en_viaje: article (n.)
mp_en_viaje: c. 1200, "separate parts of anything written" (such as the statements in the Apostles' Creed, the clauses of a statute or contract), from Old French article (13c.), from Latin articulus "a part, a member," also "a knuckle; the article in grammar," diminutive of artus "a joint," from PIE *ar(ə)-tu-, suffixed form of root *ar- "to fit together."
mp_en_viaje: Meaning "literary composition in a journal, etc." (independent and on a specific topic, but part of a larger work) is first recorded 1712. The older sense is preserved in Articles of War "military regulations" (1716), Articles of Confederation (U.S. history), etc. Extended meaning "piece of property, material thing, commodity" (clothing, etc.) first attested 1796, originally in rogue's cant. Grammatical sense of "word used
mp_en_viaje: attributively, to limit the application of a noun to one individual or set of individuals" is from 1530s, from this sense in Latin articulus, translating Greek arthron.
mp_en_viaje: in any case, the morphological description of the articulation of thought : a pile of articles, and the web of links tieing them together.
diana_coman: yes, that would be quite it (or it should better be it).
PeterL: The way I understand, on a blog (short for web log), a post refers to any item, which could be an article. Most posts are articles, I will try to refer to them as such in the future.
PeterL: But I wouldn't call a picture of my cat an article, even if it is a blog post.1
mircea_popescu: which is the problem : you belong on facebook.
mircea_popescu: intellectually, not yet matured enough to reach past infantile superficiality into adult interesting.
mircea_popescu: becauise i both would and do call a picture of my cat an article. and in my case, it also ~is~ an article.
PeterL: mircea_popescu: that is an article that contains a picture of a cat. My point is that you could post something other than an article.
mircea_popescu: yes, and you're cordially invited to do it on facebook. you could similarily cook using something other than a stove -- such as for instance, an open pit fire. you're cordially invited to do that with your berber brethren, rather than indoors. and so on.
BingoBoingo has thought of a blog post as being like a fence post. A structural piece holding together the larger blog as a whole. The poor labeling argument however does carry more weight than my previously private metaphor.
hanbot wonders what a writ really is, after all.
BingoBoingo: hanbot: A writ seems like something determined important enough that the order was issued to have the matter written into a writ.
mircea_popescu: traditionally, the notation behind legal proceedings.
hanbot: right, but is writ:written::post:posted ? does the act of ordering scrub 'writ' of its grating-ness? or is the seemingly obvious connection between written and writ wholly imagined?
PeterL: perhaps post (something posted) is analagous to toast (something toasted)?
mircea_popescu: i think "despatch" is more in the vein of what happened there.
BingoBoingo: English isn't a consistent enough language for me to want to save the noun "post" on blogs through comparison to other English language constructions.
BingoBoingo: If it's going to be saved by comparison, I'm inclined to favor comparison to physical posts. Fence posts, mile marker posts, "woe unto he that digs into this buried gas pipe" posts, etc
hanbot: lol, it occurs to me...should mp-wp backend change to reflect post --> article?
mircea_popescu: i thought it said "publish"
mircea_popescu: but, yes.
hanbot: left column, "posts", add new, etc.
mircea_popescu: ah, yeah. indeed it should.
hanbot: cool, that oughta cement it.
diana_coman: BingoBoingo: that "physical posts" image makes me think of a sort of haphazard hut-of-a-blog, lolz
BingoBoingo: diana_coman: The process of construction rarely focuses on the aesthetics of process regardless of how much aesthetics factor into the final product.
BingoBoingo: But that is a strong objection because... when is a blog ever finished?
BingoBoingo: Anyways, articles are the future. Noun posts need actual holes dug.
lobbes: I'm sold on 'articles', tho it dun help the cause any that the mp-wp database uses the 'posts' terminology everywhere (posts table, post_id, post_content, etc.)
mircea_popescu: indeed.
mircea_popescu: whatever, now i know i want it fixed.

So I guess the consensus is that a blog is a series of articles which are published. But if you say you posted a blog post to your blog people will understand what you meant, it just doesn't sound as formal.

  1. For example, see []

Regarding V


In this post I would like to address a few related aspects of v: why v, what is v, where does v come from, and what does v do.

The idea of v, the republican versioning system, transcends any single implementation. It is a whole new paradigm for the development and use of software. The underlying idea of v is to know completely the state of a piece of software, to be able to control all changes to it, and to ultimately know who is putting what changes into it. V allows one to confidently build code, know where it came from, and know it will not change unexpectedly1.

In the past, software development could be done by applying a series of patches to arrive at a final program state. With v, the patch is replaced with the slightly different vpatch, as described below. A collection of related of patches is referred to as a "v tree". A patch that only introduces new files is referred to as a "genesis".

One of the guiding principles behind the use of v is that each and every line should have a person to "blame", it should be obvious who wrote a line and who approved it. You can trace each line in a final document back by locating it in the corresponding vpatch and seeing who signed that vpatch. As Asciilifeform explained in a one line summary of vtronics: "every line has a sworn and cryptoauthenticated author".

The fundamental information provided in a vpatch is the state before the change, the change to the document (usually software code, but this system could be applied to any document), and the state after the change. The big change from old style patches to vpatches is that states are now given as cryptographic hashes2 of the document3 as found and as changed. Each vpatch is cryptographically signed by the author or approver4. Each time v is used it is run against a set of web-of-trust (WOT) identities (gpg keys), and only patches that have been signed by at least one of those identities will be included.

A v program is handy in that it automates a series of steps, but these steps can be done manually: 1. Each patch is verified with its corresponding signature, and the signer is verified to be within the WOT5. 2. The order of patches is determined by comparing "before" and "after" hashes for the files. 3.a. A patch is applied. 3.b. After applying the patch, the state is checked to verify that the patch applied as expected6. Repeat 3.a and 3.b until all patches have been applied.

It is not too hard to come up with a scenario that creates a diverging tree. The obvious way a tree can diverge is if two patches each alter the same file. Since v enforces changes to files based on their hash identity, if the two patches list the same hash as the starting point then only one can be used, as the other would no longer have the same hash-id'ed file to start with. A more subtle branching can also be made, where patches affect different files, and this can be non-dependent or soft-dependent. If two patches make unrelated changes in two different files then they are non-dependent on each other - the patches can be applied in either order. However, there could also be a dependency of one patch on the other. For example, a function could be defined in one file in the first patch, and the function could be called in a separate file in the second patch. In this case the program will build if the first patch is applied, but will not build if only the second patch is applied since the function would be missing its definition. This issue was addressed by adding a "manifest" file, which allows the enforcement of patch ordering over the whole set of files.

Ideally, each vpatch contains the changes of a single item - it should follow the ideal of "fits in head". The changes introduced could affect just one file or every file, but there should be some unifying theme that connects all the changes included.

Other references:
V for Victory
V-tronics 101
A collection of vpatch trees, for example, can be seen at

  1. Have you ever had a piece of software get "upgraded" and then everything which depends on it no longer works? Very frustrating. []
  2. When v was initially introduced the hash used was SHA-512, this was later changed to Keccak. []
  3. In the pre-v world, it was assumed that each person could have a different version of a file to apply a patch to, and so patch programs were made to be forgiving, and would try to find the best way to apply a patch. There are a number of ways this could go wrong. []
  4. Why would you not use the signature of the author? It is not possible to know everybody, and so the web of trust can help make decisions about who to trust. But maybe the author is too far away from you in this web, or perhaps he is not even in the web, and so you would instead rely on the signature of somebody who you did trust that read the vpatch and gives their signature of approval. In the strictest use of v the only key given to v is your own, and you only build software that you have personally read and signed. []
  5. The WOT here refers to the subset of identities which you have chosen to trust for changing this document, not the WOT as a whole. []
  6. The hash listed in the vpatch must match the hash of the file after the patch was applied. []

Meme of the day by Raelani


Camoflage, like a boss

This meme was created by my daughter Raelani, with the help of our cat, Albus. Assorted detritus were provided by my son Elliott (at least, I think that is his coat and shoes).

Back up again


After a brief downtime due to my hoster having technical difficulties, this blog is back up and running again. Hooray, rejoice and be merry!

Home Economics Likebez


I will start with a quote from the #Trilema Log1:

mircea_popescu: Let's do some practical home economics likbez:

IF the problem is that the currency is shit (which is strictly what "rising rents" means: if rents are rising, THEREFORE the currency is shit. if urine is sweet, THEREFORE diabethes, no iffs or butts about it, these are NOT separable), then owning real estate is a very poor solution: real estate follows the currency secular trend if currency is strong and stays strong, real estate goes up in value, which is how owning land in republican Rome or expansive Venice paid out. If however the currency flags, real estate forthwith moves into emergency monetization role, meaning you want to short it as part of a triple currency play. (Which is why us banks LEND you houses: it's the other part of their international trade where they borrow hard currency.)

That was part 1, as to financials.

IF you are a young man, and are producing more than consuming (if not, please follow the recipe2 for gender re-assignment, you don't belong here), you should save ~in capital goods~ specifically ~of your trade~. That's what you do with every dime you can save: you buy your own tools! to become journeyman! If you're making a living driving a car, you buy CARS. if you're making a living fixing cars, you buy forklifts and power tools. The only 20-something who can reasonably buy real estate is... a pimp. If you're not a fucking pimp, you don't buy real estate in your 20s. and if you are a pimp, you buy in fucking Baltimore, you buy in the blighted downtown of Detroit3 or Philly or whatever the shit. NOT crap in suburbia; and in any case you don't buy crap made ~for you~ by people who ~you do not know~. What the fuck, are you retarded ? if people who you don't know are making things for you, the name for the thing they're making is A TRAP. Either you buy made to order like my serb friends4, or else you buy leftover brownstone nobody else wants, etcetera. what the fuck, this is novel to someone ?! Why, because "do we still have to" read 1700s state of the art textbooks on personal conduct ?

That was part 2, as to journeyman economic conduct.

If you're a young man, YOU DO NOT BUY ILLIQUID, NON-NEGOTIABLE ANYTHING!!!! I don't mean, with money. I mean with anything. You have enough sense to keep your sexual relationships at will rather than get fucking married, fine, but the same applies throughout. Buying "a house" from "the bank" is THE EXACT EQUIVALENT of giving your savings to your dad "to hold on to them for you". what the fuck, are you twelve? Things flow the other way, your aging dad gives you the duchy of Cornwall for you to hold on to for him, what the fuck is this ? and if dad ~dun have~ a duchy of Cornwall large enough to keep you occupied, ~you leave~. and you spit on his head, too, because HE FAILED in life. Because this was his fucking job: by the time the sons he made were old enough to do something useful with his time, he was supposed to have so much fucking land and chattels as to be desperate for loyal hands, and more than happy to "go, take x, hang yourself with it, holy hell finally!" as a young orphan with potential, you keep to negotiable instruments. that's why the young men of Florence who did get to be old men and successful enough as to buy up all the young cunts for gold to all the failures' despair went into trade rather than bureaucracy! NEGOTIABLE. If whatever the fuck it is "you have" can't be ~sold~, on the ~open market~, YOU ARE NOT INTERESTED IN IT. You will be interested, of course, BUT FIVE DECADES HENCE. When you're old. Then the sort of non-negotiable commitment makes sense. Not in your fucking 20s, so spare me with all the "jobs" you can not sell (yes, this is what "working remote" IS, SELLING IT!!!), all the "college degrees" worth 0 on auction, and all the etcetera.

This was part 3, as to commercial aptitude.

There's more, and besideswhich a lot more to all of these foregoing parts, but holy hell... seriously, nobody ever thinks of things or what is the problem here !?

Back in 2005 when I was young and stupid, my wife and I were told that our apartment rent would be going up (I don't remember exactly, but it was somewhere in the 10-15% range). So we decided that we should buy a house, avoiding rising rents was one of the reasons. Another reason being that we would save up some money as equity; the price of houses in the Lansing area had been consistently rising for 20 years, and we wanted to tap in on that wave. We were college students with part-time jobs, but we didn't have any negatives on our credit report, so we somehow qualified for a mortgage. This was a 0% down mortgage, what they do is artificially inflate the price of the house and roll things like closing costs into the amount you are borrowing from the bank. Turns out we bought right at the top of the housing bubble, and five years later when we wanted to move the house was only worth a quarter of what we paid for it. At that point, we would have been much better off if we had just kept renting.

Having had our credit trashed by the housing fiasco, we rented for a while when we moved to Midland. When we bought a house again, we approached it very differently. Instead of looking at it as an investment, we tried to find the best way to maximize our return on our expense. We found a house that we will be comfortable in at least until we retire. We could have gotten a bigger house in a nicer neighborhood according to the "budget" that the real estate agent so helpfully suggested to us, but instead we chose one that fit into our own budget. And now we pay the same amount monthly for our mortgage that we did for our rental, but the house is twice as big5. My point is, in some situations it makes sense to buy a house, but not in every situation.

We also purchased some commercial real estate for my wife's business6. This would go along with Mircea's part two above. Her business involves teaching music lessons, so we have invested in the building and the instruments to make that possible. As they say, you can't get rich making money for somebody else.

  1. I have made some minor edits to change it from IRC format to paragraph format. []
  2. snsabot: Logged on 2018-01-08 12_21_33 btcvixen: Yes it does, as my government id says _Sex_ F_ []
  3. About 2011 I was looking into the real estate market in Detroit, since at that point I was working in the Detroit Suburbs and that would have been a short commute. My impression was that although the house prices were low the taxes are really high, so you don't actually end up saving money in the long run. There is also the matter of schools, Detroit schools are absolutely worthless. But then I got a job in Midland, so I never really finished that line of research. []
  4. snsabot: Logged on 2018-11-25 13:50:17 a111: Logged on 2014-09-10 15:02 mircea_popescu: well yeah. was a bunch o people, they got building permit and proceeded to built like at home. concrete pillars, brick walls etc. []
  5. We had a fourth child since moving to Midland, and now we have teen-agers, so having more space is a good thing. []
  6. Really, it is our business since we are co-owners, but I think of it as her business because she is the one doing most of the work. I give general advice on big decisions, and any light handiwork gets dumped on me, but mostly it is her thing. []

Definition: Man-Bun


Today my son and I were eating lunch, and we decided that we needed to appropriate and redefine the term "man-bun". So from this point forward, a man-bun is not some sort of fru-fru fluff ball bunched on the back of a guy's head. A man bun is a piece of bread with a pile of meat, cheese, and bacon inside.

Elliott had a man-bun for lunch today.

Signatures for FFA


I have been reading and signing the FFA series by asciilifeform. I have read the whole series as they have been published, and I have been signing them as I feel like I understand what is happening in each patch. I intended to get through the whole series before publishing this blog post, but as I have gone some time without adding any signatures I figured I should go ahead an make this post with the signatures that I already have.

These are signatures of the keccak versions of the vpatches. The patches can conveniently be viewed using the patch viewer.

Update to Selection Code


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


Op. 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) 326-6200 Cable: SRI INTL MPK TWX: 910-373-1246

1. Introduction

A digital signature created by sender P for a document m is data item op(m) having the property that upon receiving m and op(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 compute1. More precisely one way function T is a function from set of data objects to a set of values having the following two properties:

  1. Given any value v , it is computationally infeasible to find a data object d such that T(d) = v .

  2. 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 Rabin2. 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.

  1. 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 op(m').

  2. 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 .

  1. 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 .)

  2. 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.
  3. 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 keys3, 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.

  1. A function F : K → V with the following two properties:

    1. Given any value v in V , it is computationally infeasible to find a key k in K such that F(k) = v .

    2. For any small set of values v1, ... , vm , it is easy to find a key such that F(k) is not equal to any of the vi .
  2. 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 ki such that all the values F(ki) are distinct. (Our second assumption about F makes this easy to do.) He puts in public repository the data item o = (F(k1), ... , F(k40)) . Note that P does not divulge the keys ki , 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 [i1, ... , i20] of integers. The signature consists of the 20 keys ki1, ... , ki20 . More precisely, we have op(m) = (ki1, ... , ki20) , where the ij are defined by the following two requirements:

  1. G(m) = {i1, ... , i20}

  2. i1 < ... < i20

After generating the signature, P can destroy all record of the 20 keys ks with s not in G(m) .

To verify that 20-tuple (h1, ... , h20) is valid signature op(m) for the document m, one first computes G(m) to find the ij and then uses o to check that for all j , hj is the ijth key. More precisely, the signature is valid if and only if for each j with 1 ≤ j ≤ 20 : F(hj) → oij , where oi denotes the ith component of o , and the ij are defined by the above two requirements.

To demonstrate that this method correctly implements digital signatures, we prove that it has the following properties.

  1. If P does not reveal any of the keys ki , then no-one else can generate valid signature op(m) for any document m .

  2. If P does not reveal any of the keys kj except the ones that are contained in the signature op(m) , then no-one else can generate valid signature op(m') for any document m' ≠ m .

The first property is obvious, since the signature op(m) must contain 20 keys ki such that F(ki) = oi , and our first assumption about F states that it is computationally infeasible to find the keys ki just knowing the values F(ki) .

To prove the second property, note that since no-one else can obtain any of the keys ki , we must have op(m') = op(m) . Moreover, since the oi are all distinct, for the validation test to be passed by op(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 40-tuples o1, o2, ... and the document must indicate which oi 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, ... , 2n - 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, ... , 2n - 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:

  1. Divide s by 40 to obtain quotient q and a remainder r

  2. Use r to choose an element x from {1, ... , 40} (This is easy to do, since 0 ≤ r ≤ 40.)
  3. Use q to choose 19 elements from the set {1, ... , 40} - {x} as follows:
    1. 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, ... , 2n} 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, ... , 2n - 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 ith 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/10p. (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/10p.)

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, ... , 2n} .

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.

  1. Diffie, W. and Hellman, M. "New Directions in Cryptography". IEEE Trans. on Information Theory IT-22 (November 1976), 644-654. []
  2. Rabin, M. "Digitalized Signatures", in Foundations of Secure Computing, Academic Press (1978), 155-168. []
  3. 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. []