Click Here! |

Brief Full Advanced Search Search Tips
|  |  | To access the contents, click the chapter and section titles. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth) (Publisher: John Wiley & Sons, Inc.) Author(s): Bruce Schneier ISBN: 0471128457 Publication Date: 01/01/96 Search this book:
Previous | Table of Contents | Next
The numbers n (n is the product of two primes) and x0 must be agreed upon in advance. Then, the accumulation of y1 , y2 , and y3 would be ((x0 y1 mod n)y2 mod n)y3 mod n This computation is independent of the order of y1, y2 , and y3. ### 23.9 All-or-Nothing Disclosure of Secrets This protocol allows multiple parties (at least two are required for the protocol to work) to buy individual secrets from a single seller (see Section 4.13) [1374,1175]. First, here’s a definition. Take two bit strings, x and y. The fixed bit index (FBI) of x and y are the bits where the ith bit of x equals the ith bit of y. For example: x = 110101001011 y = 101010000110 FBI(x, y) = {1, 4, 5, 11} (We’re reading the bits from right to left, with the right-most bit as zero.) Now, here’s the protocol. Alice is the seller. Bob and Carol are buyers. Alice has k n-bit secrets: S1, S2 , ..., Sk. Bob wants to buy secret Sb; Carol wants to buy secret Sc. (1) Alice generates a public-key/private-key key pair and tells Bob (but not Carol) the public key. She generates another public-key/private-key key pair and tells Carol (but not Bob) the public key. (2) Bob generates k n-bit random numbers, B1 , B2 , ..., Bk, and tells them to Carol. Carol generates k n-bit random numbers, C1 , C2 , ..., Ck, and tells them to Bob. (3) Bob encrypts Cb (remember, Sb is the secret he wants to buy) with the public key from Alice. He computes the FBI of Cb and the result he just encrypted. He sends this FBI to Carol. Carol encrypts Bc (remember, Sc is the secret she wants to buy) with the public key from Alice. She computes the FBI of Bc and the result she just encrypted. She sends this FBI to Bob. (4) Bob takes each of the n-bit numbers B1, B2 , ..., Bk, and replaces every bit whose index is not in the FBI he received from Carol with its complement. He sends this new list of n-bit numbers, B'1, B'2, ..., B'k, to Alice. Carol takes each of the n-bit numbers C1 , C2 , ..., Ck, and replaces every bit whose index is not in the FBI she received from Bob with its complement. She sends this new list of n-bit numbers, C'1, C'2, ..., C'k, to Alice. (5) Alice decrypts all C'i with Bob’s private key, giving her k n-bit numbers: C"1, C"2, ..., C"k. She computes Si ⊕ C"i, for i = 1 to k, and sends the results to Bob. Alice decrypts all B'i with Carol’s private key, giving her k n-bit numbers: B"1, B"2, ..., B"k. She computes Si ⊕ B"i, for i = 1 to k, and sends the results to Carol. (6) Bob computes Sb by XORing Cb and the bth number he received from Alice. Carol computes Sc by XORing Bc and the cth number she received from Alice. This is complicated. An example will go a long way to help. Alice has the following eight 12-bit secrets for sale: S1 =1990, S2 =471, S3 =3860, S4 =1487, S5 =2235, S6 =3751, S7 =2546, and S8 =4043. Bob wants to buy S7. Carol wants to buy S2. (1) Alice uses the RSA algorithm. The key pair she will use with Bob is: n = 7387, e = 5145, and d = 777. The key pair she will use with Carol is: n = 2747, e = 1421, and d = 2261. She tells Bob and Carol each their public key. (2) Bob generates eight 12-bit random numbers, B1 = 743, B2 = 1988, B3 = 4001, B4 = 2942, B5 = 3421, B6 = 2210, B7 = 2306, and B8 = 222, and tells them to Carol. Carol generates eight 12-bit random numbers, C1 = 1708, C2 = 711, C3 = 1969, C4 = 3112, C5 = 4014, C6 = 2308, C7 = 2212, and C8 = 222, and tells them to Bob. (3) Bob wants to buy S7 , so he encrypts C7 with the public key that Alice gave him. 22125145 mod 7387 = 5928 Now: 2212 = 0100010100100 5928 = 1011100101000 So, the FBI of those two numbers is {0, 1, 4, 5, 6}. He sends this to Carol. Carol wants to buy S2 , so she encrypts B2 with the public key that Alice gave her and computes the FBI of B2 with the result of her encryption. She sends {0, 1, 2, 6, 9, 10} to Bob. (4) Bob takes B1 , B2 , ..., B8 , and replaces every bit whose index is not in the set {0, 1, 2, 6, 9, 10} with its complement. For example: B2 = 111111000100 = 1988 B'2 = 011001111100 = 1660 He sends B'1, B'2, ..., B'8, to Alice. Carol takes C1 , C2 , ..., C8 , and replaces every bit whose index is not in the set {0, 1, 4, 5, 6} with its complement. For example: C7 = 0100010100100 = 2212 C'7 = 1011100101000 = 5928 She sends C'1, C'2, ..., C'8, to Alice. (5) Alice decrypts all C'i with Bob’s private key and XORs the results with Si. For example, for i = 7: 5928777 mod 7387 = 2212; 2546 ⊕ 2212 = 342 She sends the results to Bob. Alice decrypts all B'i with Carol’s private key and XORs the results with Si. For example, for i = 2: 16602261 (mod 2747) = 1988; 471 ⊕ 1988 = 1555 She sends the results to Carol. (6) Bob computes S7 by XORing C7 and the seventh number he received from Alice: 2212 ⊕ 342 = 2546 Carol computes S2 by XORing B2 and the second number she received from Alice. 1988 ⊕ 1555 = 471 The protocol works for any number of buyers. If Bob, Carol, and Dave want to buy secrets, Alice gives each buyer two public keys, one for each of the others. Each buyer gets a set of numbers from each other buyer. Then, they complete the protocol with Alice for each of their sets of numbers and XOR all of their final results from Alice to get their secret. More details are in [1374,1175].
Previous | Table of Contents | Next
[an error occurred while processing this directive]

| Products | Contact Us | About Us | Privacy | Ad Info | Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.