Cryptographic Protocols Without Computers

We started this book from early cryptography, the history of secret writing. In the early days the methods were certainly developed quite independently of computers - there were none around. Early translations from plaintext to ciphertext were carried out using (hopefully!) ingenious methods. However, the methods never involved very complicated computations.

The view is different for practically all of public-key cryptography. Indeed, the whole idea of a one-way function is difficult to visualize in practice without referring to computing devices. Although we have presented in this book mostly small "toy examples" for which computers are not actually needed, this has happened only because of readability. Any real use of the presented methods of public-key cryptography is intended to take place within the environment of computers. Now in this final section of the book, we will complete the circle and come back to a setup without computers by discussing cryptographic protocols where computers are not used.

Consider a typical cryptographical task, for instance, the cryptanalysis of an RSA cryptotext when the public key is known. In principle we can factorize the modulus by trying all factors up to the square root of the modulus and, thus, everything is possible, given enough time and patience. The important thing is that this "enough" is much too much. The whole world would have during the time required changed so much that, whatever message the cryptotext originally had, it would have become completely irrelevant. The same observation can be made about cryptography in general. "Impossible tasks" are not impossible from the point of view of classical mathematics. On the contrary, in principle everything is possible, even trivial. However, solutions lose their meaning and significance if they take too long. Proper solutions in cryptography are always tied with complexity. If your method takes unreasonably long, you might as well forget it.

But you can also have in mind the seriousness of the situation and the resources of the opponent. Smaller safety measures could be adequate if the opponent has little time or resources. For most of the topics in this book, we have had a rather heavy apparatus in mind, moduli 200 digits long and so forth.

What about cryptographic protocols? Some of the situations we have de­scribed are quite "harmless", for instance, flipping a coin by telephone to settle some modest dispute. In such cases the methods suggested give the impression of killing a fly with heavy artillery - you just are not likely to do things that way. If Alice and Bob flip a coin by telephone, they certainly do not start talking about quadratic residues with respect to huge moduli! Similarly, the setup in a zero-knowledge proof becomes quite different if the Prover and/or Verifier can somehow observe the computing resources of the other. It is certainly possible to design cryptographic protocols, that is, protocols applying ideas of crypto­graphy, for situations where computing resources are limited or nonexistent. Very little work has so far been done in this direction, although the approach is also interesting from the general mathematical point of view.

This final section of the book contains some cryptographic protocols, where computers are neither used nor needed. Most of the techniques are from [NieR2]. [CrK] uses similar ideas for different purposes. Although our considerations can be viewed as initial ones in a new area, some theoretically very significant issues are involved. Of these the non-interactive zero-knowledge proofs should be especially mentioned.

There are obvious reasons for investigating cryptographic protocols, where computers are not used. Nonavailability, nonportability, unreliability, mistrust or dislike of computers are certainly among such reasons. Sometimes a protocol without computers is simply better or more natural than one with computers. For instance, assume that a relatively small group of people gathered together want to take a secret vote about some important matter. Who would in such a situation consider anything such as the balloting protocols described above - even if a network of computers were available? It is much easier and more efficient to take ballots (pieces of paper or cards) and a box. The "cryptographic element" in this protocol will be shuffling. When the ballots are shuffled, the group loses the link between the person and the ballot, although the link could perhaps be observed earlier. It is essential for secrecy that the link is broken before the votes are disclosed. This very simple protocol serves its purpose better than any other one could think of.

Let us go back to flipping a coin by telephone. Alice and Bob cannot agree about what they are going to do in the evening. Bob would like to go to the opera but Alice likes to see basketball. Alice realizes that it is not good for their relation if they go to different places. Bob would hate to sit in a crowded sports arena, thinking that he missed "Lulu", his favorite opera. So Bob tells Alice over the phone that they should flip a coin but complains that the cryptographic methods for the task are overly complicated. Neither one of them is going to compute quadratic residues or square roots with respect to a large modulus. But then Alice gets a brilliant idea. Both of them have next to the phone the same telephone directory. They can flip a coin according to the following protocol.

Step 1: Bob picks up a number in the directory (say, 7340309) and asks whether the number immediately following it in the directory is even or odd.

Step 2: Alice makes a guess (say, "odd"). It is indeed a guess because she has to react immediately and, thus, can in no way find Bob's number.

Step 3: Bob tells the result of the guess (here "wrong"). At this stage they can interrupt the protocol and do whatever the result implies. (In our example they go to see "Lulu".)

Step 4: Bob proves to Alice that he was honest in telling the result. (He tells her that the number 7340309 belongs to Sebastian Mahler. Alice checks that the next number 7175914, belonging to Ibrahim Mahmud, is even. So her guess

was indeed wrong, and it was only fair that she had to suffer through the incomprehensible music!)

Observe that, in designing the above protocol, Alice made use of a function /, mapping each number in the directory to the number immediately following. This function / can be viewed as a zero-way function, at least for simple practical purposes such as the one considered above. In such a setup, computing f(x) or f~^x(x) is clearly intractable: given a number x, one can find neither the number immediately preceding it nor the number immediately following it. Also the verification of an equation f(x) = y is intractable. In all of these tasks we assume that the "commitment" (the telephone directory) is also given. Only the additional knowledge of the "trapdoor" (the inverse directory, ordered according to increasing numbers) makes these computations tractable. It should be emphasized that these observations are valid only relative to the simple setup we had in mind. For more demanding tasks the function / is not zero-way.

We consider next the computation of propositional formulas (Boolean func­tions). A propositional formula with n variables is given. Each of the partici­pating n parties knows the truth-value of a particular variable. How can they find out the truth-value of the whole formula without disclosing their own secret truth-value? We want to devise a protocol, as simple as possible and not using computers, for this task. In some cases the truth-value of the whole formula discloses the individual truth-values. For instance, if the truth-value of a dis­junction is "false", then each party learns the secret truth-value of every other party. This obvious exception must of course be granted in our considerations. We view truth-values as bits, 0 being "false" and 1 being "true".

Take first the computation of conjunction. Alice has a secret bit a and Bob has a secret bit b. They want to leam a a b without revealing their secret bits, unless necessary. This means that if a = 0 (resp. b = 0) then Alice (resp. Bob) should learn nothing. If a = 1, then Alice actually learns b.

There are numerous situations, where such a demand for learning the con­junction arises. Alice and Bob could be just at the beginning of their relationship. They want to find mutual interests. But being very shy, they refuse to show in­terest in something unless they know that also the other one is interested. If they are able to compute conjunction in the way described above, they can find out possible common interest, for instance, in the following:

- bird watching,

- classical music,

- fitness training,

- long hikes,

- watching sports,

- religious activities.

If they have a simple protocol available, they can go further after they found a common interest. Such a further exploration is necessary if they have a common interest in religious activities. But it is very helpful also in other cases. If they are both interested in classical music, they can find much more by indicating their acceptance or nonacceptance as regards the following controversial statements:

- Even-numbered Beethoven symphonies are actually better than the odd- numbered ones.

- "Parsifal" is the greatest Wagner opera.

- Glenn Gould has set an absolute standard on how to play a Bach toccata or partita.

- Mahler's Third is among the handful of greatest symphonies ever written.

- Most of Italian opera is actually operetta.

Secret computing of conjunction is needed also in more serious situations. Such a demand might arise amidst hectic negotiations between a labor union and employers' organization. Both sides are willing to bargain, but only as much as is necessarily needed to get a contract or to avoid a strike. Sometimes a neutral third party, often representing the government, takes part in the negotiations. A rather modern idea is that such a third party should not any more make an intermediate proposition but should accept as such one of the bids of the two parties. This encourages both of the parties to bargain as much as possible in their last bid, because in this way they have a better chance of getting their own bid finally accepted. This holds of course only in case both negotiating parties trust the neutral third party. Otherwise, they might test the mutual acceptance or nonacceptance of packages such as

- two-year contract, salary freeze but 10% increase in overtime bonus,

- one-year contract, terms as above,

- no specific contract period, 3% salary increase.

Thus, if one of the parties (workers or employers) does not accept a package, it does not learn the other party's eventual willingness, but if it accepts, it learns the other party's attitude.

Having discussed in length the background of the problem of computing conjunctions secretly, we now describe a simple protocol where a deck of five cards will be used. This "five-card trick" is due to [Bo]. The cryptographic element in this and other protocols described below will be a random cut of the deck. As usual, a cut of the deck means that some number of topmost cards is moved, without changing their order, to the bottom. An important observation is that the effect of several cuts, made after each other, can always be achieved by one cut. If so many cuts are made in succession that every participant in the protocol has lost the possibility of keeping track of the cutting position, we speak of a random cut. Thus, a random cut is a sequence of cuts, viewed as one cut. The unchanged deck constitutes also a cut, being one possibility for a random cut. Our overall cryptographic assumption will be that it is possible to make a random cut. The assumption will be made for any number > 1 of participants in the protocol and any number > 2 of cards in the deck.

There are two kinds of cards, white and black. Cards of the same color are indistinguishable. As usual, the back side of each card is identical. White cards are denoted by the bit 0 and black cards by the bit 1. A deck of cards can be represented in this way as a word over the alphabet {0, 1}, using the convention that the leftmost letter represents the topmost card. Thus, the word 01011 stands for a deck with two white and three black cards, where the topmost and third cards are white. We will also have to make a distinction whether the cards are face (white or black) down or face up.

A commitment to the bit 0 (resp. 1) is the deck 10 (resp. 01), cards face down. Thus, a commitment is made using one card of each color, the bottom card telling the bit committed to. It will become apparent below why it is better to use two cards for a commitment, rather then simply a card 0 or 1. We speak also of negations of bits, ~ 0 = 1 and ~ 1 = 0.

We are now ready to define the protocol.

Setup: Alice and Bob have both a white card and a black card. An additional black card is put on the table, face down.

Step 1: Alice makes a commitment to her secret bit. Bob makes a commitment to the negation of his secret bit.

Step 2: Alice's commitment is put on top of the card on the table, Bob's com­mitment below it. After this there is a deck of five cards on the table, all cards face down.

Step 3: A random cut is made on the deck.

Step 4: The cards are shown. The conjunction has the value "true" exactly in case the two white cards are next to each other, where also the top and bottom cards are considered being next to each other. (Thus, we view the deck cyclically, every card having two neighbors. We could require equivalently that the three black cards are next to each other.)

Let us now analyze the validity of the protocol, namely, that the outcome is the correct one and that the secrecy requirement will be satisfied. This happens conveniently in terms of a case analysis:

The correctness of the conclusion in Step 4 is immediate. If both A and B have the secret bit 1, then all cuts have two adjacent Os, whereas none of the cuts in any other case has this property. Each of the three other cases leads to the same total set of cuts. Thus, it is impossible to tell the initial conditions from a random cut. If one of the parties is committed to the bit 1, then the black card in the commitment will be placed next to the black card on the table. So if there are no three adjacent black cards in the final cut, the other party must have placed a white card next to the black card on the table. The first party knows that 0 is the secret bit of the other party. However, a party committed to 0 leams nothing, because we are then dealing with two of the three indistinguishable sets of cuts.

Clearly, disjunction can be computed in a very similar way. Now a party committed to 1 learns nothing. However, we want to take one step further. We want to compute conjunctions in such a way that the outcome remains in encrypted form. More specifically, we are given two bits x and y, in the form of commitments as described above. We want to compute the bit z — x a y, also as a commitment. Thus, to start with we have four cards faces down, two of them being a commitment for x, the other two for y. We want to devise a protocol, which now will be a game of solitaire, producing two cards faces down representing a commitment for z. Possibly some auxiliary cards will be needed in the protocol. But the player of the solitaire does not know or leam later the original bits x and y, and also not the resulting bit r! The idea is that z can be used as an input for other protocols.

Note that such a solitaire is obvious for negation. Given a commitment for the bit x, we get a commitment for ~ x just by switching the order of cards. (Of course, we should not look at the cards!) This would perhaps not at all be possible if we had defined a commitment to be one card, face down. Another reason for defining a commitment in terms of two cards is that one is then able to copy a commitment without learning the bit. Such a capability is very useful in many protocols. The following protocol and the subsequent protocol for conjunction follows [NieR2], The protocol is presented in the form of a game of solitaire. The only participant is called Verifier, Vera, V. This reflects our final aim of presenting a non-interactive zero-knowledge proof. The Verifier is of course not supposed to cheat. In particular, we assume that she (i) makes true random cuts when the protocol so requires and (ii) displays cards only if the protocol allows her to do so.

Setup: Vera is given two cards face down, defining a commitment ~xx. (Thus, the deck equals 01 or 10. Vera knows that one of these alternatives holds but does not know which one.) In addition, she is given a deck (01)*^+l of 2k + 2 cards, for some k > 2. Also these cards are face down but she may check that they form indeed the deck (01)*⁺¹.

Step 1: Vera makes a random cut of the deck (Ol)^'. She is not any more allowed to look at any card of the resulting deck, but she knows that the deck is of the form (~;y.y)*⁺¹, where y — 0 or y = 1.

Step 2: Vera takes two topmost cards of the deck (~ yy)^k+x. She joins these cards to the commitment ~xx, getting the deck ~ xx ~ yy = X,. She still has also the deck (~~yy)^k = Y_2k.

Step 3: Vera makes a random cut of the deck after which she looks at the four cards. If they are 0101 or 1010, then she outputs Y_2k (face down). If they are 0011, 0110, 1100 or 1001, then she outputs (y~~y)^k, obtained from Y_2k by moving the topmost card to the bottom (without looking at it).

Step 4: Vera concludes that her output equals (~ xx)* and, thus, consists of k copies of the original commitment.

It is easy to get convinced about the correctness of the conclusion in Step 4. If x = y, then Y₄ = 0101 or 7₄ = 1010. If jc = ~ y, then Y₄ = 0110 or y₄ = 1001, and there are the two further possibilities 0011 and 1100 for random cuts. In both cases Vera's output, formed according to Step 3, will be (~xx)*. On the other hand, Vera learns something only in Step 3. But she learns only whether or not x = y and this will tell her nothing because y is completely random. Vera gets k copies of the original commitment by taking pairs of cards (preserving the order and not looking at the cards) from her output deck of 2k cards.

We are now ready to describe a protocol for computing conjunctions in such a way that the outcome remains in encrypted form. Copying of commitments is needed in this protocol. So is a certain modification of making random cuts, where we force the topmost card to be the one we want. The protocol below can be viewed as a "doubling variant" of the five-card trick presented before: the deck in Step 2 below is obtained by doubling the deck constructed in Step 2 of the protocol for the five-card trick.

Setup: Vera is given two decks of cards, faces down, defining two commitments ~xx and ~yy. (Thus, both of the decks contain a white and a black card. Vera knows this but nothing more about the decks. The decks may or may not be identical.) In addition, Vera is given openly four white and four black cards. (They are needed in copying commitments.)

Step 1: Vera makes two copies of the commitment ~xx and two copies of the commitment ~ yy. (Her white and black cards suffice for making the copies according to the preceding protocol. She needs first three cards of both colors to make two copies of ~ xx. But in this construction four cards become free, so Vera has again the six cards needed for making two copies of ~ yy. This copying leaves her again four displayed cards, two of them white and two black, for possible use later.)

Step 2: Vera builds the deck of ten cards, face down, ^10= ~xxly

out of the cards she has from Step 1. The two decks y ~ y are obtained from the two decks ~ yy by changing the order of cards. Vera is not allowed to look at any of the face-down cards. (Thus, Vera knows the third and eighth card of the deck y_t0 but none of the other cards explicitly. She has some implicit information based on her overall knowledge of K_l0, for instance, that the two topmost cards are of different colors but the fifth card is of the same color as the bottom card. Besides the deck K₁₀, Vera has still also two displayed white cards.)

Step 3: Vera makes a random cut of the deck y₁₀ and looks at the topmost card of the resulting deck. If it is black, she puts it back, face down, to the topmost position, takes another random cut and looks at the topmost card. She continues in this way until the topmost card is white. Then she removes the topmost card from the deck, which leaves her a deck of nine cards

Y₉ = yiyiyAysyeyiy^yto- (Thus, r;₀ = 0Y₉ is a cut of Fi₀.)

Step 4: Vera makes a random cut of the deck y₂yi and looks at the cards. If they are both black, she outputs the deck y\₀y9, without looking at the cards. If one of them is white and the other black, she outputs (face down) the deck yny%. (The cards y₂ and y3 cannot both be white because there are no three consecutive 0s in the original deck K_i0.)

Step 5: Vera concludes that her output is a commitment for the conjunction (that is, the output equals ~ (x a y)(x a y)).

Since the outputs in Step 4 may sound a bit mystical, let us have a closer look at the protocol. In regard to the five-card trick, some kind of doubling of the deck is needed: Vera has to get some information in order to output the correct commitment but, on the other hand, she must learn nothing about x, y or the output. This means that some cards must be shown to her (recall that white and black cards are associated to the bits 0 and 1, respectively) but enough cards must remain under cover to determine the output correctly.

If the protocol above is used as a subprotocol in some more comprehensive task, then the following requirement is essential. Vera gets initially 12 cards but her output requires only 2 cards. Thus, 10 cards are "saved". Of these 10 cards 3 white ones are disclosed to Vera, whereas the remaining 7 remain secret: Vera is not allowed to look at the y_t -cards left over. (She knows something about them, for instance, that exactly 2 of them are white and that the y, -deck contains no adjacent white cards.) The 10 cards might be needed at some later stages of the comprehensive task. (We might have an unlimited supply of cards available but, on the other hand, the number of cards needed is a good complexity measure for such protocols.) An essential requirement is that the secret left-over cards are shuffled before any further use.

Perhaps the clearest way of proving the validity of the above protocol (that is, the correctness of the conclusion and the secrecy of the hidden bits) is by case analysis. Depending on the values of x and y, we have the following four alternatives for the deck Fi₀:

The conjunction should assume the value 1 (that is, have the commitment xy with y = 1) only if we are dealing with the alternative A^

We now investigate all possible cuts of A\, where the topmost card is 0. There will be four cases, depending on the position of this 0 in A_{. However, the four cases can be joined into two pairs, because the first and second halves of A i are identical. (This holds true for A₂-A₄ as well.) The items important in the protocol are given in the following table:

The corresponding tables for the alternatives A₂-A₄ are, accordingly:

These tables tell immediately that Vera's conclusion in Step 5 is always cor­rect. We have shown before that she leams nothing in copying the commitments. She also learns nothing in making the special random cut in Step 3. Although she sees some cards, she only learns that the deck contains white and black cards, which she knows anyway. Vera also learns the unordered pair (_V;, y₃). (Observe that making a random cut renders an ordered pair unordered!) But she still leams nothing because all truth-value combinations are present for both of the outcomes "black-white" and "both black", as is immediately seen from the tables. It is also seen from the tables that it is necessary to make a random cut before looking at y₂ and y₃: if she could distinguish between 01 and 10, Vera would also know the difference between "true" and "false" in the final commitment!

Thus, the validity of the protocol follows. Vera learns nothing if she does not cheat. But it is very easy for her to cheat - she can look at any commitment she wants to! The possibility for cheating lies in the nature of every solitaire.

We are now ready for the final step. We can present a simple non-interactive zero-knowledge prooffor the satisfiability of propositional formulas. (See Ap­pendix A for a discussion about the universality of this problem.)

A propositional formula F with variables ... ,x_n is given. Since every propositional connective can be expressed in terms of conjunction and negation, we assume that these two are the only connectives occurring in F. The Prover, Peter, knows an assignment for the variables making F true. He wants to con­vince the Verifier, Vera, of his knowledge without revealing to her any details of the assignment. The protocol will be simply the following.

Peter gives Vera his assignment in the form of n commitments, 2n cards, as described above. In addition, Vera is given a sufficient supply of auxiliary cards, needed in copying the commitments. (Estimates, based on F, for the number of auxiliary cards needed can be given.) Vera now plays the solitaire, applying the protocols for conjunction and negation. She looks at the final outcome, the commitment for the whole formula F, and accepts iff the commitment is 01. Only one round is needed in this non-interactive protocol. Vera's eventual cheating can be prevented if Peter or a person trusted by him stands by, watching Vera's play. One could also imagine a technical device that would have the same effects as card play and would report any wrongdoings of the operator. Finally, the only way for Peter to cheat is to give pairs 00 or 11 in place of some commitments. But he would be caught immediately because cards assigned to a variable will be disclosed as an unordered pair whenever the variable takes part in a conjunction. If she gets two cards of the same color when the colors should be different, Vera will stop the game.

Fig. 6.5

Date: 2015-02-16; view: 779