Partial Disclosure of Secrets

A rapidly developing area with a wide range of applications consists of problems of the following type. Two or more parties are in the possession of secrets. To achieve a common goal, they want to share some information but not too much. A protocol has to be designed for this purpose.

What makes the situation different from the sharing of secrets discussed in Section 6.3 is that in the latter some of the parties wanted to disclose their secrets entirely, in order to achieve the information c. Now all of the parties cooperate but disclose their secrets only partially. (Moreover, we do not assume the existence of a central agency. However, such an agency is not needed in Section 6.3 if the moduli are publicized.)

A general setup for partial disclosure of secrets can be defined as follows. The parties A_lt. .. ,A„ t > 2, each know the definition of a function /(x_t,..., x,). Here each variable ranges over a finite initial segment of the set of natural numbers, and the values of / are natural numbers. Thus, the function / can be defined in terms of a table. Each of the parties A, knows a specific value a_; belonging to the range of x_f, but A_{ has no information in regard to the values a_} for j # i. The parties A_lt..., A, want to compute the function value /(a,,. .. ,a,) without giving away any additional information about their own values a_t. In other words, a protocol has to be designed such that, after running through the protocol, all the parties A_i know the function value /(a,,. . ., a,) but no party has given away any additional information about the value a_t. Here additional refers to any informa­tion not obtainable from the function value f(a₁,. . . ,a_t). Of course, the whole matter becomes trivial if an impartial referee is used.

For instance, consider

^ | 1 if some x, is not prime , " ²' ³ [smallest prime among the arguments, otherwise .

If a₂ = 19 and f(a_l,a₂, a₃) = 17, then A₂ knows that one of a_x and a₃ equals 17, and the other is a prime > 17. If a₂ = 4 and f(a_lta₂, a₃) = 1, then A₂ has no information whatsoever about the numbers a, and a₃.

Protocols have been designed for problems of this type. Security issues are difficult to formalize in the general case: in particular, the issue of collective cheating where some parties form a coalition to cheat the others. On the other hand, such protocols open entirely new vistas for confidential communication. For instance, new types of secret votings can be carried out. Some members of a council might have the right of veto. With the new protocols, nobody knows whether a negative decision is based on the majority, or on somebody using the veto-right, or on both!

Consider a specific example. The parties S_lt S₂, P_1;.. ., P, where t is odd, want to make a yes or no decision. All parties can vote yes or no. In addition, S, and S₂ have the possibility of using "super-votes" S-yes and S-no. It has been agreed in advance that the majority decides if no super-votes are cast. In case of a single or two equivalent super-votes, all ordinary votes are ignored. In case of two contradicting super-votes, the majority of the ordinary votes decides. Such a voting can be visualized as arising in the United Nations, with Sj and S₂ having super- votes. For instance, assume that the votes are cast according to the table

After the execution of the protocol, all parties know the result. S, does not know that the result had been the same also if they had cast a no vote. S₂ does not know that they could not change the result. The parties P_t do not know that their votes did not influence the decision. After the execution of the protocol with the votes

S, knows that S₂ cast an S-no vote and that the majority of the "ordinary powers" Pi cast a no vote.

The problem of secret voting with super-votes can be immediately formulated using the general setup for computing the value of a function, and so can the following problem for which we will also describe a protocol in detail.

A (lice) and B(ob) want to find out who is older without learning anything else about each other's age. How can they carry out a conversation satisfying this requirement?

Let us be more specific. We want to design a protocol for the following conversation. At the beginning A knows the integer i and B knows the integer j, namely, the integers indicating ,4's and B's ages in years. At the end of the conversation, both A and B know whether i > j or i < j, but A and B have obtained no further information about j and i, respectively.

The problem we are considering is often stated in the following form. Two millionaires want to know who is richer without obtaining any additional informa­tion about each other's wealth.

We assume that the ages are between one and one hundred years, that is, i and j range over the integers from 1 to 100. The following protocol is based on a public-key cryptosystem. Thus, B knows 4's encryption key E_A but not her decryption key D_A.

Step 1: B chooses a large random number x and privately computes the value E_A(x) = k.

Step 2: B tells A the number k — j.

Step 3: A privately computes the numbers

y_u = D_A(k-j + u) for 1 < u < 100 .

Then A chooses a large random prime p. (The approximate size of p is somewhat smaller than the size of x. The approximate sizes of p and x have been agreed upon in advance.) A privately computes the numbers

z„ = (3'_u,modp), 1 < u < 100 .

She verifies that, for all u and all v # u,

(*) |z„ - zj > 2 and 0 < z„ < p - 1 .

If this is not the case, A chooses another prime until she succeeds.

Step 4: A tells B the sequence of numbers (in this order) (**) z,,. . . ,z,-,z_j+1 + l,z_i+2 + 1,. . . ,z₁₀₀ + l,p .

Step 5: B checks whether or not the ;-th number in the sequence is congruent to x (mod p). If it is, he concludes that i > j. If it is not, he concludes that i < j.

Step 6: B tells A the conclusion.

The conclusion in Step 5 is correct because the j-th number z) in (**) satisfies the conditions

i > j implies z'j = Zj = yj = x (mod p) and i < j implies z'j = Zj + 1 # Zj = y_} = x (mod p).

The condition (*) guarantees that no number appears twice in the sequence (**). (The addition of 1 does not matter because the positive difference of any two

z's is > 2.)

The scrambling of the numbers y_u (mod p) is necessary. If A would simply tell B the sequence

yi. • • •. j'.-.j'i+i + hy_i+2 + l,.. • ,y₁₀₀ + ¹>

then B could find i by applying E_A to this sequence, since B knows the numbers k-j + u,l<u< 100.

The only information from B to A (resp. from A to B) is given in Step 2 (resp. Step 4), and this information amounts to nothing. On the other hand, some sophisticated form of cheating is always possible and also very hard to find out, without any impartial referee or actually disclosing both i and j. For instance, there is no way of checking (without referring to birth certificates etc.) that A and B work with their proper ages while executing the protocol. For instance, B might work with j = 50 (although he actually is, say, 65) and find out whether A is younger than 50. On the other hand, any number of people can find out the order of their ages by a sequence of honest applications of the protocol.

Example 6.2. We illustrate the protocol by using the simple RSA system (n = 55, e = 7, d = 23) discussed at the beginning of Example 4.1. The values can be seen directly from the tables presented there. We assume that only the values 1, 2, 3, 4 are possible for / and j.

Suppose first that i = 2 and j = 4. If B chooses x = 39, then the value k—j told to A in Step 2 equals 15. This implies that

y_u = D_A(l5 + u), 1 < u < 4 ,

and, hence,

_yi= 26, y₂ = 18, y₃ = 2, y₄ = 39 .

Scrambling with the modulus p = 31 yields

Z[ = 26, z₂ = 18, z₃ = 2, z₄ = 8 .

(This p is not to be confused with the factor of n.) After observing that the z's satisfy (*), A tells B in Step 4 the sequence

26, 18, 3, 9, 31.

B observes that 9 ^ 39 = x (mod 31) and concludes that i < j. If the modulus 23 is used for scrambling, then

Zj =3, z₂ = 18, z₃ = 2, z₄ = 16

and, thus, (*) is not satisfied. B receives in Step 4 the sequence

3, 18, 3, 17, 23 ,

and knows that i < 3.

Suppose, secondly, that i =j = 2. If B chooses x = 48 then k — j = 25 and, consequently,

^=31, y₂ = 48, y₃ = 7, y₄ = 24. If p = 13, then B receives in Step 4 the sequence

5, 9, 8, 12, 13

and, after computing 9 = 48 = x (mod 13), concludes that i > j. □

The reader might want to consider some other public-key cryptosystem as the basis for the age protocol. It is also easy to become convinced that the protocol cannot be carried out within the framework of classical cryptography, that is, without using a one-way function. The parties have to transmit to each other some exact information in such a form that the information cannot be disclosed from the message.

Date: 2015-02-16; view: 914