. 1
( 2)



>>

Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




CHAPTER 23 ................................................ 526
Special Algorithms for Protocols ........... 526
MULTIPLE-KEY PUBLIC-KEY .................. 526
SECRET-SHARING ALGORITHMS ......... 527
LaGrange Interpolating Polynomial ................ 527
Vector Scheme .............................................. 528
Asmuth-Bloom ............................................... 528
Karnin-Greene-Hellman ................................ 529
Advanced Threshold Schemes ..................... 529
Sharing a Secret with Cheaters .................... 530
SUBLIMINAL CHANNEL ........................... 530
Ong-Schnorr-Shamir ..................................... 530
ElGamal ........................................................ 531
ESZGN .......................................................... 532
DSA ............................................................... 533
Foiling the DSA Subliminal Channel ............. 535
Other Schemes ............................................. 535
UNDENIABLE DIGITAL SIGNATURES .... 535
Conoertible Undeniable Signatures .............. 537
DESIGNATED CONFIRMER SIGNATU ... 538
COMPUTING WITH ENCRYPTED ........... 539
The Discrete Logarithm Problem .................. 539
FAIR COIN FLIPS ..................................... 540
Coin Flipping Using Square Roots ................ 540
Coin Flipping Using Exponentiation ............... 541
Coin Flipping Using Blum Integers ................ 542
ONE-WAY ACCUMULATORS .................. 542
ALL-OR-NOTHING DISCLOSURE OF ..... 542
FAIR AND FAILSAFE CRYPTOSYSTE .... 545
Fair Diffie-Hellman ......................................... 545
Failsafe Diffie-Hellman .................................. 546
ZERO-KNOWLEDGE PROOFS OF .......... 547
Zero-Knowledge Proof a Discrete .................. 547
Zero-Knowledge Proof of the Ability to ........... 547
Zero-Knowledge Proof that n Is a Blwm ......... 548
BLIND SIGNATURES ............................... 548
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter



OBLIVIOUS TRANSFER .......................... 549
SECURE MULTIPARTY COMPUTATIO... 550
Example of the Protocol ................................. 551
PROBABILISTIC ENCRYPTION ............... 551
QUANTUM CRYPTOGRAPHY ................. 553
Page 526
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




23
CHAPTER


Special Algorithms
for Protocols

23.1 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY
This is a generalization of RSA (see Section 19.3) [217,212]. The modulus, n, is the
product of two primes, p and q. However, instead of choosing e and d such that ed
E 1 mod ((p - l)(q - l)), choose t keys, Ki, such that
K1 * K2 . . . * Kt = 1 mod ((p - l)(q - 1))
l



Since


this is a multiple-key scheme as described in Section 3.5.
If, for example, there are five keys, a message encrypted with K3 and K5 can be
decrypted with K1, K,, and K4:
C=MK3™K5modn
M=CKl*K2*K4modn
One use for this is multisignatures. Imagine a situation where both Alice and Bob
have to sign a document for it to be valid. Use three keys: K1, K,, and K3. The first
two are issued one each to Alice and Bob, and the third is made public.

(1) First Alice signs M and sends it to Bob.
M™=MK1modn
(2) Bob can recover M from M™.
M=MK2 +K3modn
(3) He can also add his signature.
M”=M™K2modn
Page 527
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

Special Algorithms for Protocols
CHAPTER 23


(4) Anyone can verify the signature with K3, the public key.
M = M”K3 mod n

Note that a trusted party is needed to set this system up and distribute the keys
to Alice and Bob. Another scheme with the same problem is [484]. Yet a third
scheme is [695,830,700], but the effort in verification is proportional to the number
of signers. Newer schemes [220,1200] based on zero-knowledge identification
schemes solve both shortcomings of the previous systems.

23.2 SECRET-SHARING ALGORITHMS
Back in Section 3.7 I discussed the idea behind secret-sharing schemes. The four dif-
ferent algorithms that follow are all particular cases of a general theoretical frame-
work [883].
LaGrange Interpolating Polynomial Scheme
Adi Shamir uses polynomial equations in a finite field to construct a threshold
scheme [ 14141. Choose a prime, p, which is both larger than the number of possible
shadows and larger than the largest possible secret. To share a secret, generate an
arbitrary polynomial of degree m - 1. For example, if you want to create a (3,n)-
threshold scheme (three shadows are necessary to reconstruct M), generate a
quadratic polynomial
(ax” + bx + M) mod p
where p is a random prime larger than any of the coefficients. The coefficients a and
b are chosen randomly; they are kept secret and discarded after the shadows are
handed out. M is the message. The prime must be made public.
The shadows are obtained by evaluating the polynomial at n different points:
k, = F(xi)
In other words, the first shadow could be the polynomial evaluated at x = 1, the sec-
ond shadow could be the polynomial evaluated at x = 2, and so forth.
Since the quadratic polynomial has three unknown coefficients, a, b, and M, any
three shadows can be used to create three equations. Two shadows cannot. One
shadow cannot. Four or five shadows are redundant.
For example, let M be 11. To construct a (3, 5)-threshold scheme, where any three
of five people can reconstruct M, first generate a quadratic equation (7 and 8 were
chosen randomly):
F(x)=(7x2+8x+11)mod13
The five shadows are:
k,=F(1)=7+8+11 =O(mod13)
k,=F(2)=28+16+11 =3(mod13)
k3=F(3)=63+24+11=7(mod13)
Page 528
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




k4= F(4)= 112+32+ 11 = 12 (mod 13)
k,=F(5)=175+40+11=5(mod13)
To reconstruct M from three of the shadows, for example kp, k3, and kg, solve the
set of linear equations:
a*22+b*2+M=3(mod13)
a*3™+b*3+M=7(mod13)
a*52+b*5+M=5(mod13)
The solution will be a = 7, b = 8, and M = 11. So M is recovered.
This sharing scheme can be easily implemented for larger numbers. If you want to
divide the message into 30 equal parts such that any six can get together and repro-
duce the message, give each of the 30 people the evaluation of a polynomial of
degree 6.
F(x)=(ax6+bX5+cP+&˜+ex2+fx+M)modp
Six people can solve for the six unknowns (including M); five people cannot learn
anything about M.
The most mind-boggling aspect of secret sharing is that if the coefficients are
picked randomly, five people with infinite computing power can™t learn anything
more than the length of the message (which each of them knows anyway). This is as
secure as a one-time pad; an attempt at exhaustive search (that is, trying all possible
sixth shadows) will reveal that any conceivable message could be the secret. This is
true for all the secret-sharing schemes presented here.
Vector Scheme
George Blakley invented a scheme using points in space [ 182). The message is
defined as a point in m-dimensional space. Each shadow is the equation of an
(m - 1)-dimensional hyperplane that includes the point. The intersection of any m
of the hyperplanes exactly determines the point.
For example, if three shadows are required to reconstruct the message, then it is a
point in three-dimensional space. Each shadow is a different plane. With one shadow,
you know the point is somewhere on the plane. With two shadows, you know the
point is somewhere on the line formed where the two planes intersect. With three
shadows, you can determine the point exactly: the intersection of the three planes.
Asmuth-Bloom
This scheme uses prime numbers [65]. For an (m, n)-threshold scheme, choose a
large prime, p, greater than M. Then choose n numbers less than p, dl, dL, . . . , d,,
such that:

1. The d values are in increasing order; di < di + 1
2. Each d, is relatively prime to every other d,
3. d, d2 * . . . * d,>p dn-m+2 d,-,+3 . . . * d,
l l l l
Page 529
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 23 Special Algorithms for Protocols


To distribute the shadows, first choose a random value r and compute
M™=M+rp
The shadows, ki, are
k,=hJ™moddi
Any m shadows can get together and reconstruct M using the Chinese remainder
theorem, but any m - 1 cannot. See [65] for details.
Karnin-Greene-Hellman
This scheme uses matrix multiplication [818]. Choose n + 1 m-dimensional vec-
tors, V,, VI, . . . , V,, such that any possible m * m matrix formed out of those vec-
tors has rank m. The vector U is a row vector of dimension m + 1.
M is the matrix product U.V,. The shadows are the products U.V,, where i is a
number from 1 to n.
Any m shadows can be used to solve the m * m system of linear equations, where
the unknowns are the coefficients of U. UV, can be computed from U. Any m - 1
shadows cannot solve the system of linear equations and therefore cannot recover
the secret.
Advanced Threshold Schemes
The previous examples illustrate only the simplest threshold schemes: Divide a
secret into n shadows such that any m can be used to recover the secret. These algo-
rithms can be used to create far more complicated schemes. The following examples
will use Shamir™s algorithm, although any of the others will work.
To create a scheme in which one person is more important than another, give
that person more shadows. If it takes five shadows to recreate a secret and one per-
son has three shadows while everyone else has only one, then that person and two
other people can recreate the secret. Without that person, it takes five to recreate
the secret.
Two or more people could get multiple shadows. Each person could have a differ-
ent number of shadows. No matter how the shadows are distributed, any m of them
can be used to reconstruct the secret. Someone with m - 1 shadows, be it one per-
son or a roomful of people, cannot do it.
In other types of schemes, imagine a scenario with two hostile delegations. You
can share the secret so that two people from the 7 in Delegation A and 3 people from
the 12 in Delegation B are required to reconstruct the secret. Make a polynomial of
degree 3 that is the product of a linear expression and a quadratic expression. Give
everyone from Delegation A a shadow that is the result of an evaluation of the lin-
ear equation; give everyone from Delegation B a shadow that is the evaluation of the
quadratic equation.
Any two shadows from Delegation A can be used to reconstruct the linear equa-
tion, but no matter how many other shadows the group has, they cannot get any
information about the secret. The same is true for Delegation B: They can get three
shadows together to reconstruct the quadratic equation, but they cannot get any
Page 530
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23.3 Subliminal Channel


more information necessary to reconstruct the secret. Only when the two delega-
tions share their equations can they be multiplied to reconstruct the secret.
In general, any type of sharing scheme that can be imagined can be implemented.
All you have to do is to envision a system of equations that corresponds to the par-
ticular scheme. Some excellent papers on generalized secret-sharing schemes are
[1462,1463,1464].

Sharing a Secret with Cheaters
This algorithm modifies the standard (m, n)-threshold scheme to detect cheaters
[1529]. I demonstrate this using the LaGrange scheme, although it works with the
others as well.
Choose a prime, p, that is both larger than n and larger than
(s-l)(m-l)/e+m
where s is the largest possible secret and e is the probability of successful cheating.
You can make e as small as you want; it just makes the computation more complex.
Construct your shadows as before, except instead of using 1, 2, 3, . . . , n for Xi,
choose random numbers between 1 and p - 1 for xi.
Now, when Mallory sneaks into the secret reconstruction meeting with his false
share, his share has a high probability of not being possible. An impossible secret is,
of course, a fake secret. See [ 15291for the math.
Unfortunately, while Mallory is exposed as a cheater, he still learns the secret
(assuming that there are m other valid shares). Another protocol, from [1529,975],
prevents that. The basic idea is to have a series of k secrets, such that none of the
participants knows beforehand which is correct. Each secret is larger than the one
before, except for the real secret. The participants combine their shadows to gener-
ate one secret after the other, until they create a secret that is less than the previous
secret. That™s the correct one.
This scheme will expose cheaters early, before the secret is generated. There are
complications when the participants deliver their shadows one at a time; refer to the
papers for details. Other papers on the detection and prevention of cheaters in
threshold schemes are [355,114,270].


23.3 SUBLIMINAL CHANNEL
Ong-Schnorr-Shamir
This subliminal channel (see Section 4.2), designed by Gustavus Simmons
[ 1458,1459,1460], uses the Ong-Schnorr-Shamir identification scheme (see Section
20.5). As in the original scheme, the sender (Alice) chooses a public modulus, n, and
a private key, k, such that n and k are relatively prime. Unlike the original scheme,
k is shared between Alice and Bob, the recipient of the subliminal message.
The public key is calculated:
h=-k2modn
Page 531
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

CHAPTER 23 Special Algorithms for Protocols


If Alice wants to send the subliminal message M by means of the innocuous mes-
sage M™, she first confirms that M™ and n are relatively prime, and that M and n are
relatively prime.
Alice calculates
S1= l/2 ((M™/M + M)) mod n
l


ST= k/2 * ((M™/M - M)) mod n
Together, the pair, S1 and Sz, is the signature under the traditional Ong-Schnorr-
Shamir scheme and the carrier of the subliminal message.
Walter the warden (remember him?) can authenticate the message as described by
the Ong-Schnorr-Shamir signature scheme, but Bob can do better. He can authenti-
cate the message (it is always possible that Walter can make his own messages). He
confirms that
S12 Szz/k2= M™ (mod n)
-
If the message is authentic, the receiver can recover the subliminal message using
this formula:
M = M™/( S1+ &k-l) mod n
This works, but remember that the basic Ong-Schnorr-Shamir has been broken.
ElGamal
Simmons™s second subliminal channel [1459], described in [1407,1473], is based
on the ElGamal signature scheme (see Section 19.6).
Key generation is the same as the basic ElGamal signature scheme. First choose a
prime, p, and two random numbers, g and r, such that both g and r are less than p.
Then calculate
K=g™modp
The public key is K, g, and p. The private key is 2: Besides Alice, Bob also knows
r; it is the key that is used to send and read the subliminal message in addition to
being the key used to sign the innocuous message.
To send a subliminal message M using the innocuous message M™, M and p must
be all relatively prime to each other, and M and p - 1 must be relatively prime. Alice
calculates
X=gMmodp
and solves the following equation for Y (using the extended Euclidean algorithm):
M™=rX+MYmod(p- 1)
As in the basic ElGamal scheme, the signature is the pair: X and Y
Walter can verify the ElGamal signature. He confirms that
KxXy = g”™ (mod p)
Bob can recover the subliminal message. First he confirms that
(g™)xXy = 9”™ (mod p)
Page 532
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23.3 Subliminal Channel


If it does, he accepts the message as genuine (not from Walter).
Then, to recover M, he computes
M=(Y-˜(&I-rX))mod(p-1)
For example, let p = 11 and g = 2. The private key, r, is chosen to be 8. This
means the public key, which Walter can use to verify the signature, is g™ mod p =
28 mod 11 = 3.
To send the subliminal message M = 9, using innocuous message M™ = 5, Alice con-
firms that 9 and 11 are relatively prime and that 5 and 11 are relatively prime. She
also confirms that 9 and 11 - 1 = 10 are relatively prime. They are, so she calculates
X=gMmodp=29mod11=6
Then, she solves the following equation for Y:
5=8*6+9*YmodlO
Y = 3, so the signature is the pair, X and Y: 6 and 3.
Bob confirms that
(g™)“X™ = 9” (mod p)
(28)663 2” (mod 11)
=
It does (do the math yourself if you don™t trust me), so he then recovers the sublim-
inal message by calculating
M = (Y-™ (M™ - rX)) mod (p - 1) = 3-˜(5 - 8 * 6) mod 10 = 7(7) mod 10 =
@modlO=
ESZGN
A subliminal channel can be added to ESIGN [ 1460) (see Section 20.6).
In ESIGN, the secret key is a pair of large prime numbers, p and 4, and the public
key is n = p2q. With a subliminal channel, the private key is three primes, p, 4, and
r, and the public key is n, such that
n = p2qr
The variable, r, is the extra piece of information that Bob needs to read the sublimi-
nal message.
To sign a normal message, Alice first picks a random number, x, such that x is less
than pqr and computes:
w, the least integer that is larger than (H(m) - xk mod n)/pqr)
s = x + ((w/kxk - I) mod p)pqr
H(m) is the hash of the message; k is a security parameter. The value s is the signature.
To verify the signature, Bob computes sk mod n. He also computes a, which is the
least integer larger than the number of bits of n divided by 3. If H(m) is less than or
equal to sk mod n, and if sk mod n is less than H(m) + 2”, then the signature is con-
sidered valid.
To send a subliminal message, M, using the innocuous message, M™, Alice calcu-
Page 533
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 23 Special Algorithms for Protocols


lates s using M in place of H(m). This means that the message must be smaller than
p2qr. She then chooses a random value, u, and calculates
i=M™+ur
Then, use this x™ value as the “random number” x to sign M™. This second s value
is sent as a signature.
Walter can verify that s (the second s) is a valid signature of M™.
Bob can also authenticate the message in the same way. But, since he also knows
r, he can calculate
s=x™+ypqr=M+ur+ypqr=M(modr)
This implementation of a subliminal channel is far better than the previous two.
In the Ong-Schnorr-Shamir and ElGamal implementations, Bob has Alice™s private
key. Besides being able to read subliminal messages from Alice, Bob can imperson-
ate Alice and sign normal documents. Alice can do nothing about this; she must
trust Bob to set up this subliminal channel.
The ESIGN scheme doesn™t suffer from this problem. Alice™s private key is the set
of three primes: p, 4, and 1: Bob™s secret key is just 1: He knows n = p™qr, but to
recover p and q he has to factor that number. If the primes are large enough, Bob has
just as much trouble impersonating Alice as would Walter or anyone else.

DSA
There is also a subliminal channel in DSA (see Section 20.1) [ 1468,1469,1473]. In
fact, there are several. The simplest subliminal channel involves the choice of k. It
is supposed to be a 160-bit random number. However, if Alice chooses a particular
k, then Bob, who also knows Alice™s private key, can recover it. Alice can send Bob
a 160-bit subliminal message in each DSA signature; everyone else simply verifies
Alice™s signature. Another complication: Since k should be random, Alice and Bob
need to share a one-time pad and encrypt the subliminal message with the one-time
pad to generate a k.
DSA has subliminal channels that do not require Bob to know Alice™s private key.
These also involve choosing particular values of k, but cannot be used to send 160
bits of information. This scheme, presented in [ 1468,1469], allows Alice and Bob to
exchange one bit of subliminal information per signed message.

( 1) Alice and Bob agree on a random prime, P (different from the parameter p in
the signature scheme). This is their secret key for the subliminal channel.
(2) Alice signs an innocuous message, M. If she wants to send Bob the sublim-
inal bit, 1, she makes sure the r parameter of the signature is a quadratic
residue modulo l? If she wants to send him a 0, she makes sure the r param-
eter is a quadratic nonresidue modulo P She does this by signing the mes-
sage with random k values until she gets a signature with an r with the
requisite property. Since quadratic residues and quadratic nonresidues are
equally likely, this shouldn™t be too difficult.
(3) Alice sends the signed message to Bob.
Page 534
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23.3 Subliminal Channel


(4) Bob verifies the signature to make sure the message is authentic. Then he
checks whether r is a quadratic residue or a quadratic nonresidue modulo
P and recovers the subliminal bit.

Sending multiple bits via this method involves making r either a quadratic
residue or a quadratic nonresidue modulo a variety of parameters. See [ 1468,1469]
for details.
This scheme can be easily extended to send multiple subliminal bits per signa-
ture. If Alice and Bob agree on two random primes, P and Q, Alice can send two bits
by choosing a random k such that r is either a quadratic residue mod P or a
quadratic nonresidue mod P, and either a quadratic residue mod Q or a quadratic
nonresidue mod Q. A random value of k has a 25 percent chance of producing an r
of the correct form.
Here™s how Mallory, an unscrupulous implementer of DSA, can have the algo-
rithm leak 10 bits of Alice™s private key every time she signs a document.

(1) Mallory puts his implementation of DSA in a tamperproof VLSI chip, so
that no one can examine its inner workings. He creates a 14-bit subliminal
channel in his implementation of DSA. That is, he chooses 14 random
primes, and has the chip choose a value of k such that r is either a quadratic
residue or a quadratic nonresidue modulo each of those 14 primes, depend-
ing on the subliminal message.
(2) Mallory distributes the chips to Alice, Bob, and everyone else who wants
them.
(3) Alice signs a message normally, using her 160-bit private key, x.
(4) The chip randomly chooses a lo-bit block of x: the first 10 bits, the second
10 bits, and so on. Since there are 16 possible lo-bit blocks, a 4bit number
can identify which block it is. This 4-bit identifier, plus the 10 bits of the
key, is the 14-bit subliminal message.
(5) The chip tries random values of k until it finds one that has the correct
quadratic residue properties to send the subliminal message. The odds of a
random k being of the correct form are 1 in 16,384. Assuming the chip can
test 10,000 values of k per second, it will find one in less than two seconds.
This computation does not involve the message and can be performed off-
line, before Alice wants to sign a message.
(6) The chip signs the message normally, using the value of k chosen in step (5).
(7) Alice sends the digital signature to Bob, or publishes it on the network, or
whatever.
(8) Mallory recovers r and, because he knows the 14 primes, decrypts the sub-
liminal message.

It™s scary that even if Alice knows what is happening, she cannot prove it. As long
as those 14 secret primes stay secret, Mallory is safe.
Page 535
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 23 Special Algorithms for Protocols


Foiling the DSA Subliminal Channel
The subliminal channel relies on the fact that Alice can choose k to transmit
subliminal information. To foil the subliminal channel, Alice cannot be allowed to
choose k. However, neither can anyone else; if someone else were allowed to
choose k, it would allow that person to forge Alice™s signature. The only solution is
for Alice to jointly generate k with another party, call him Bob, in such a way that
Alice cannot control a single bit of k and Bob cannot know a single bit of k. At the
end of the protocol, Bob should be able to verify that Alice used the k that they
jointly generated.
Here™s the protocol [ 1470,1472,1473]:

(1) Alice chooses k™ and sends Bob
u=fmodp
(2) Bob chooses k” and sends it to Alice.
(3) Alice calculates k = k™k” mod (p - 1). She uses k to sign her message, M,
with the DSA and sends Bob the signature: r and s.
(4) Bob verifies that
((uk” mod p) mod q) = r

If it does, he knows that k was used to sign M.
After step (4), Bob knows that no subliminal information can be embedded in r. If
he is a trusted party, he can certify that Alice™s signature is subliminal-free. Others
will have to trust his certification; Bob cannot prove this fact to a third party with a
transcript of the protocol.
A surprising result is that if Bob wants to, he can use this protocol to create his
own subliminal channel. Bob can embed a subliminal message in one of Alice™s sig-
natures by choosing k” with certain characteristics. When Simmons discovered this,
he dubbed it the “Cuckoo™s Channel.” Details on how the Cuckoo™s Channel works,
and a three-pass protocol for generating k that prevents it, are discussed in
[ 1471,1473].

Other Schemes
Any signature scheme can be converted into a subliminal channel [1458,1460,
14061. A protocol for embedding a subliminal channel in the Fiat-Shamir and Feige-
Fiat-Shamir protocols, as well as possible abuses of the subliminal channel, can be
found in [485].


23.4 UNDENIABLE SIGNATURES
DIGITAL

This undeniable signature algorithm (see Section 4.3) is by David Chaum [343,327].
First, a large prime, p, and a primitive element, g, are made public, and used by a
group of signers. Alice has a private key, x, and a public key, g” mod p.
Page 536
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23.4 Undeniable Digital Signatures


To sign a message, Alice computes z = mx mod p. That™s all she has to do.
Verification is a little more complicated.

(1) Bob chooses two random numbers, a and b, both less than p, and sends
Alice:
c = I™m mod p
(2) Alice computes t=x-i mod (p - l), and sends Bob:
d =cfmodp
(3) Bob confirms that
d = magb (mod p)

If it is, he accepts the signature as genuine.
Imagine that Alice and Bob went through this protocol, and Bob is now convinced
that Alice signed the message. Bob wants to convince Carol, so he shows her a tran-
script of the protocol. Dave, however, wants to convince Carol that some other per-
son signed the document. He creates a fake transcript of the protocol. First he
generates the message in step (1). Then in step (3) he generates d and the fake trans-
mission from this other person in step (2). Finally, he creates the message in step (2).
To Carol, both Bob™s and Dave™s transcripts are identical. She cannot be convinced
of the signature™s validity unless she goes through the protocol herself.
Of course, if she were watching over Bob™s shoulder as he completed the protocol,
she would be convinced. Carol has to see the steps done in order, just as Bob does.
There may be a problem with this signature scheme, but I know of no details.
Please pay attention to the literature before you use it.
Another protocol not only has a confirmation protocol-Alice can convince Bob
that her signature is valid-but it also has a disavowal protocol; Alice can use a zero-
knowledge interactive protocol to convince him that the signature is not valid, if it
is not [329].
Like the previous protocol, a group of signers use a shared public large prime, p,
and a primitive element, g. Alice has a unique private key, x, and a public key,
9™ mod p. To sign a message, Alice computes z = mx mod p.
To verify a signature:

( 1) Bob chooses two random numbers, a and b, both less thanp, and sends Alice:
c = mngb mod p
(2) Alice chooses a random number, q, less than p, and computes and sends
to Bob:
s1= cgq mod p, s2 = (cg4)xmod p
(3) Bob sends Alice a and b, so that Alice can confirm that Bob did not cheat
in step (1).
Page 537
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

CHAPTER 23 Special Algorithms for Protocols


(4) Alice sends Bob q, so that Bob can use mx and reconstruct s1 and s2. If
s1 = cgq (mod p)
s2 = (f)b + qz™ (mod p)
then the signature is valid.

Alice can also disavow a signature, z, for a message, m. See [329] for details.
Additional protocols for undeniable signatures can be found in [584,344]. Lein
Harn and Shoubao Yang proposed a group undeniable signature scheme [7001.

Conoertible Undeniable Signatures
An algorithm for a convertible undeniable signature, which can be verified, dis-
avowed, and also converted to a conventional digital signature is given in [213]. It™s
based on the ElGamal digital signature algorithm.
Like ElGamal, first choose two primes, p and q, such that q divides p - 1. Now you
have to create a number, g, less than q. First choose a random number, h, between 2
and p - 1. Calculate
g = h[p - 1)/qmod p
If g equals the 1, choose another random h. If it doesn™t, stick with the g you have.
The private keys are two different random numbers, x and z, both less than q. The
public keys are p, q, g, y, and u, where
y=g”modp
u=gmodp
To compute the convertible undeniable signature of message m (which is actually
the hash of a message), first choose a random number, t, between 1 and q - 1. Then
compute
T=g™modp
and
m™ = Ttzm mod q.
Now, compute the standard ElGamal signature on m™. Choose a random number,
R, such that R is less than and relatively prime to p - 1. Then compute r = gRmod p,
and use the extended Euclidean algorithm to compute s, such that
m™ = rx + Rs (mod q)
The signature is the ElGamal signature (r, s), and T.
Here™s how Alice verifies her signature to Bob:

(1) Bob generates two random numbers, a and b. He computes c = Trm”gbmod
p and sends that to Alice.
(2) Alice generates a random number, k, and computes h, = cg” mod p, and h2
= hl™ mod p, and sends both of those numbers to Bob.
Page 538
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23.5 Designated Confirmer Signatures


(3) Bob sends Alice a and b.
(4) Alice verifies that c = TTm”gbmod p. She sends k to Bob.
(5) Bob verifies that h, = TT”“gb +k mod p, and that h2 = yrYaub +k mod p.

Alice can convert all of her undeniable signatures to normal signatures by pub-
lishing z. Now, anyone can verify her signature without her help.
Undeniable signature schemes can be combined with secret-sharing schemes to
create distributed convertible undeniable signatures [1235]. Someone can sign a
message, then distribute the ability to confirm that the signature is valid. He might,
for example, require three out of five people to participate in the protocol in order to
convince Bob that the signature is valid. Improvements on this notion deleted the
requirement for a trusted dealer [700,1369].

23.5 DESIGNATED CONFIRMER SIGNATURES
Here™s how Alice can sign a message and Bob can verify it, such that Carol can ver-
ify Alice™s signature at some later time to Dave (see Section 4.4) [333].
First, a large prime, p, and a primitive element, g, are made public and used by a
group of users. The product of two primes, n, is also public. Carol has a private key,
z, and a public key is h = 9” mod p.
In this protocol Alice can sign m such that Bob is convinced that the signature is
valid, but cannot convince a third party.

(1) Alice chooses a random x and computes
a=gmodp
b=h”modp
She computes the hash of m, H(m), and the hash of a and b concatenated,
H(a,b). She then computes
j = (H(m) 0 H(a, b))˜i3 mod n
and sends a, b, and j to Bob.
(2) Bob chooses two random numbers, s and t, both less than p, and sends Alice
c=g”h™modp
(3) Alice chooses a random q less than p, and sends Bob
d =gqmodp
e = (cd)” mod p
(4) Bob sends Alice s and t.
(5) Alice confirms that
g™hf = c (modp)
Then she sends Bob q.
Page 539
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 23 Special Algorithms for Protocols


(6) Bob confirms
d = gq (mod p)
e/a4 = ash™ (mod p)
H(m) 0 H(a, b) = j”3 mod n
If they all check out, he accepts the signature as genuine.

Bob cannot use a transcript of this proof to convince Dave that the signature is
genuine, but Dave can conduct a protocol with Alice™s designated confirmer, Carol.
Here™s how Carol convinces Dave that a and b constitute a valid signature.

(1) Dave chooses a random u and v, both less than p, and sends Carol
k = g”av mod p
(2) Carol chooses a random w, less than p, and sends Dave
1 =g”modp
y = (kl)™ mod p
(3) Dave sends Carol u and v.
(4) Carol confirms that
g”av = k (mod p)
Then she sends Dave w.
(5) Dave confirms that
g” = 1 (mod p)
y/h” = hub” (mod p)
If they both check out, he accepts the signature as genuine.

In another protocol Carol can convert the designated-confirmer protocol into a
conventional digital signature. See [333] for details.


23.6 COMPUTING WITH ENCRYPTED DATA
The Discrete Logarithm Problem
There is a large prime, p, and a generator, g. Alice has a particular value for x, and
wants to know e, such that
g” = x (mod p)
This is a hard problem, and Alice lacks the computational power to compute the
result. Bob has the power to solve the problem-he represents the government, or a
large computing organization, or whatever. Here™s how Bob can do it without Alice
revealing x [547,4]:
Page 540
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




(1) Alice chooses a random number, r, less than p.
(2) Alice computes
x™=xgmodp
(3) Alice asks Bob to solve
g” = x™ (mod p)
(5) Bob computes e™ and sends it to Alice.
(6) Alice recovers e by computing
e=(e™-r)mod(p-1)

Similar protocols for the quadratic residuosity problem and for the primitive root
problem are in [3,4]. (See also Section 4.8.)


23.7 FAIR COIN FLIPS
The following protocols allow Alice and Bob to flip a fair coin over a data network
(see Section 4.9) [194]. Th™1s is an example of flipping a coin into a well (see Section
4.10). At first, only Bob knows the result of the coin toss and tells it to Alice. Later,
Alice may check to make sure that Bob told her the correct outcome of the toss.

Coin Flipping Using Square Roots
Coin-flip subprotocol:

(1) Alice chooses two large primes, p and q, and sends their product, n to Bob.
(2) Bob chooses a random positive integer, r, such that r is less than n/2. Bob
computes
z=?modn
and sends z to Alice.
(3) Alice computes the four square roots of z (mod n). She can do this because
she knows the factorization of n. Let™s call them +x, -x, +y, and -y. Call x™
the smaller of these two numbers:
xmodn
-x mod n
Similarly, call y™ the smaller of these two numbers:
ymodn
-y mod n
Note that r is equal either to x™ or y™.
(4) Alice guesses whether r = x™ or r = y™, and sends her guess to Bob.
Page 541
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 23 Special Algorithms for Protocols


(5) If Alice™s guess is correct, the result of the coin flip is heads. If Alice™s guess
is incorrect, the result of the coin flip is tails. Bob announces the result of
the coin flip.

Verification subprotocol:

(6) Alice sends p and q to Bob.
(7) Bob computes x™ and y™ and sends them to Alice.
(8) Alice calculates r.

Alice has no way of knowing r, so her guess is real. She only tells Bob one bit of
her guess in step (4) to prevent Bob from getting both x™ and y™. If Bob has both of
those numbers, he can change r after step (4).
Coin Flipping Using Exponentiation Modulo p
Exponentiation modulo a prime number, p, is used as a one-way function in this
protocol [ 13061:
Coin-flip subprotocol:

(1) Alice chooses a prime number, p, in such a way that the factorization of p
- 1 is known and contains at least one large prime.
(2) Bob selects two primitive elements, h and t, in GF(p). He sends them to
Alice.
(3) Alice checks that h and t are primitive and then chooses a random integer
x, relatively prime to p - 1. She then computes one of the two values:
y=h”modp, ory=t”modp
She sends y to Bob.
(4) Bob guesses whether Alice calculated y as a function of h or t, and sends his
guess to Alice.
(5) If Bob™s guess is correct, the result of the coin flip is heads. If Bob™s guess is
incorrect, the result of the coin flip is tails. Alice announces the result of
the coin flip.

Verification subprotocol:

(6) Alice reveals x to Bob. Bob computes h” mod p and tX mod p, to confirm
that Alice has played fairly and to verify the result of the toss. He also
checks that x and p - 1 are relatively prime.

For Alice to cheat, she has to know two integers, x and i, such that h” =
t™ (mod p). If she knew those values, she would be able to calculate:
log,h = x™x -™ mod p - 1 and log,h = x-lx™ mod p - 1
These are hard problems.
Page 542
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23.9 All-or-Nothing Disclosure of Secrets


Alice would be able to do this if she knew log,h, but Bob chooses h and t in step
(2). Alice has no other recourse except to try to compute the discrete logarithm.
Alice could also attempt to cheat by choosing an x that is not relatively prime to p
- 1, but Bob will detect that in step (6).
Bob can cheat if h and t are not primitive in GF(p), but Alice can easily check that
after step (2) because she knows the prime factorization of p - 1.
One nice thing about this protocol is that if Alice and Bob want to flip multiple
coins, they can use the same values for p, h, and t. Alice just generates a new x, and
the protocol continues from step (3).
Coin Flipping Using Blum Integers
Blum integers can be used in a coin-flipping protocol.

(1) Alice generates a Blum integer, n, a random x relatively prime to n, x0 =
x2 mod n, and x1 = xo2 mod n. She sends n and x1 to Bob.
(2) Bob guesses whether x0 is even or odd.
(3) Alice sends x to Bob.
(4) Bob checks that n is a Blum integer (Alice would have to give Bob the fac-
tors of n and proofs of their primality, or execute some zero-knowledge
protocol to convince him that n is a Blum integer), and he verifies that x0 =
x2 mod n and x1 = x0™ mod n. If all this checks out, Bob wins the flip if he
guessed correctly.

It is crucial that n be a Blum integer. Otherwise, Alice may be able to find an x™.
such that x™02 mod n = x0™ mod n = x1, where x™. is also a quadratic residue. If x0 were
even and x™. were odd (or vice versa), Alice could freely cheat.


23.8 ONE-WAY ACCUMULATORS
There is a simple one-way accumulator function [116] (see Section 4.12):
A(x,, y) = xi - 1Ymod n
The numbers n (n is the product of two primes) and x0 must be agreed upon in
advance. Then, the accumulation of yi, yz, and y3 would be
((xoyl mod n)yz mod n)y3 mod n
This computation is independent of the order of yl, yz, and y30


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.
Page 543
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

CHAPTER 23 Special Algorithms for Protocols


For example:
x=110101001011
y=101010000110
FBI(x, y) = 11, 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, SZ, . . . , Sk. Bob wants to buy secret Sbi Carol wants to buy
secret S,.

(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, &, . . . , Bk, and tells them to
Carol. Carol generates k n-bit random numbers, C1, Cz, . . . , Ck, and tells
them to Bob.
(3) Bob encrypts Cb (remember, Sbis the secret he wants to buy) with the pub-
lic key from Alice. He computes the FBI of Cb and the result he just
encrypted. He sends this FBI to Carol.
Carol encrypts B, (remember, S, is the secret she wants to buy) with the
public key from Alice. She computes the FBI of B, and the result she just
encrypted. She sends this FBI to Bob.
(4) Bob takes each of the n-bit numbers B1, Bz, . . . , 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™i, B™2, . . . , B™k, to Alice.
Carol takes each of the n-bit numbers Ci, CZ, . . . , Ck, and replaces every
bit whose index is not in the FBI she received from Bob with its comple-
ment. She sends this new list of n-bit numbers, cI1, C2, . . . , C™k, to Alice.
(5) Alice decrypts all C™i with Bob™s private key, giving her k n-bit numbers:
CNl, C112, . . ) C”,. She computes Si 0 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 num-
bers: B™ll, BN2,. . . , B”k. She computes Si 0 B”,, 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 S, by XORing B, 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: Si = 1990, SZ= 471, S3= 3860,
S, = 1487, Ss= 2235, S6= 3751, S, = 2546, and Ss= 4043. Bob wants to buy S,. Carol
wants to buy &.
Page 544
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23.9 All-or-Nothing Disclosure of Secrets


(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, Bi = 743, Bz = 1988, B3 = 4001,
B4 = 2942, Bs = 3421, B6 = 2210, B, = 2306, and Bs = 222, and tells them to
Carol. Carol generates eight 1%bit random numbers, C1 = 1708, C2 = 711,
C3= 1969, Cq=3112, &=4014, &=2308, C,=2212, and&=222, andtells
them to Bob.
(3) Bob wants to buy S,, so he encrypts C, 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 [O, 1, 4, 5, 61. He sends this to Carol.
Carol wants to buy Sz, so she encrypts Bz with the public key that Alice
gave her and computes the FBI of Bz with the result of her encryption, She
sends (0, 1, 2, 6, 9, 10) to Bob.
(4) Bob takes B1, Bz, . . . , Bs, and replaces every bit whose index is not in the
set [O, 1, 2, 6, 9, 10) with its complement. For example:
Bz=111111000100=1988
B™,=011001111100= 1660
He sends B™l, B$, . . . , B™8, to Alice.
Carol takes C1, C2, . . . , Cs, 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™,=1011100101000=5928
She sends C™i, C2, . . . , C™8, to Alice.
(5) Alice decrypts all C™i with Bob™s private key and XORs the results with S,.
For example, for i = 7:
5928777mod 7387 = 2212; 2546 0 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 0 1988 = 1555
She sends the results to Carol.
(6) Bob computes S, by XORing C, and the seventh number he received
from Alice:
Page 545
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 23 Special Algorithms for Protocols


2212 0 342 = 2546
Carol computes SZby XORing Bz and the second number she received from
Alice.
1988 0 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 proto-
col 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].
Unfortunately, a pair of dishonest parties can cheat. Alice and Carol, working
together, can easily find out what secret Bob is getting: If they know the FBI of Cb
and Bob™s encryption algorithm, they can find b such that Cb has the right FBI. And
Bob and Carol, working together, can easily get all the secrets from Alice.
If you assume honest parties, there™s an easier protocol [389].

(1) Alice encrypts all of the secrets with RSA and sends them to Bob:
Ci=SFmodn
(2) Bob chooses his secret Cb, picks a random r, and sends C™ to Alice.
C™=C&modn
(3) Alice sends Bob P™.
P™=C™dmodn
(4) Bob calculates &.
Sb= P™r-™ mod n

If the parties may be dishonest, Bob can prove in zero-knowledge that he knows
some r such that C™ = C& mod n and keep b secret until Alice gives him P™ in step
(3) 12461.


23.10 FAIR AND FAILSAFE CRYPTOSYSTEMS
Fair Diffie-Hellman
Fair cryptosystems are a way to do key escrowing in software (see Section 4.14).
This example is from Silvio Micali [ 1084,1085]. It is patented [ 1086,1087].
In the basic Diffie-Hellman scheme, a group of users share a prime, p, and a gen-
erator, g. Alice™s private key is s, and her public key is t = g™ mod p.
Here™s how to make Diffie-Hellman fair (this example uses five trustees).

(1) Alice chooses five integers, sl, s2, s3, s4, and s5, each less than p - 1. Alice™s
private key is
Page 546
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

23.10 Fair and Failsafe Cryptosystems


s = (sl + sz + s3+ s4 + s5)mod p - 1
and her public key is
t =g”modp
Alice also computes
ti = g™i mod p, for i = 1 to 5
Alice™s public shares are ti, and her private shares are s,.
(2) Alice sends a private piece and corresponding public piece to each trustee.
For example, she sends s1 and tl to trustee 1. She sends t to the KDC.
(3) Each trustee verifies that
ti=gS™ modp
If it does, the trustee signs ti and sends it to the KDC. The trustee stores Si
in a secure place.
(4) After receiving all five public pieces, the KDC verifies that
t = (tl * tz * t3 * t4 * ts) mod p
If it does, the KDC approves the public key.

At this point, the KDC knows that the trustees each have a valid piece, and that
they can reconstruct the private key if required. However, neither the KDC nor any
four of the trustees working together can reconstruct Alice™s private key.
Micah™s papers [ 1084,1085] also contain a procedure for making RSA fair and for
combining a threshold scheme with the fair cryptosystem, so that m out of n
trustees can reconstruct the private key.
Failsafe Diffie-Hellman
Like the previous protocol, a group of users share a prime, p, and a generator, g.
Alice™s private key is s, and her public key is t = g” mod p.

(1) The KDC chooses a random number, B, between 0 and p - 2, and commits
to B using a bit-commitment protocol (see Section 4.9).
(2) Alice chooses a random number, A, between 0 and p - 2. She sends g” mod
p to the KDC.
(3) The user “shares” A with each trustee using a verifiable secret-sharing
scheme (see Section 3.7).
(4) The KDC reveals B to Alice.
(5) Alice verifies the commitment from step (1). Then she sets her public key as
t = (gA)gBmod p
She sets her private key as
s = (A + B) mod (p - 1)
Page 547
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

CHAPTER 23 Special Algorithms for Protocols


The trustees can reconstruct A. Since the KDC knows B, this is enough to recon-
struct s. And Alice cannot make use of any subliminal channels to send unautho-
rized information. This protocol, discussed in [946,833] is being patented.


23.11 ZERO-KNOWLEDGE PROOFS KNOWLEDGE
OF

Zero-Knowledge Proof of a Discrete Logarithm
Peggy wants to prove to Victor that she knows an x that satisfies
A” = B (mod p)
where p is a prime, and x is a random number relatively prime to p - 1. The num-
bers A, B, and p are public, and x is secret. Here™s how Peggy can prove she knows x
without revealing it (see Section 5.1) [338,337].

(1) Peggy generates t random numbers, rl, rz, . . . , rt, where all r, are less than
p- 1.
(2) Peggy computes hi = A™i mod p, for all values of i, and sends them to Victor.
(3) Peggy and Victor engage in a coin-flipping protocol to generate t bits: bi,
b2, . . . , b,.
(4) For all t bits, Peggy does one of the following:
a) If bi = 0, she sends Victor ri
b) If bi = 1, she sends Victor si = (ri - ri) mod (p - l), where j is the lowest
value for which bj = 1
(5) For all t bits, Victor confirms one of the following:
a) If b, = 0, that A™i = hi (mod p)
b) If b, = 1, that ASi E hih,-l (mod p)
(6) Peggy sends Victor Z, where
Z = (x - rl) mod (p - 1)
(7) Victor confirms that
AZ = Bhyl (mod p)

Peggy™s probability of successfully cheating is 2-t.

Zero-Knowledge Proof of the Ability to Break RSA
Alice knows Carol™s private key. Maybe she has broken RSA; maybe she has bro-
ken into Carol™s house and stolen the key. Alice wants to convince Bob that she
knows Carol™s key. However, she doesn™t want to tell Bob the key or even decrypt
one of Carol™s messages for Bob. Here™s a zero-knowledge protocol by which Alice
convinces Bob that she knows Carol™s private key [888].
Carol™s public key is e, her private key is d, and the RSA modulus is n.
Page 548
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




(1) Alice and Bob agree on a random k and an m such that
km = e (mod n)
They should choose the numbers randomly, using a coin-flip protocol to
generate k and then computing m. If both k and m are greater than 3, the
protocol continues. Otherwise, they choose again.
(2) Alice and Bob generate a random ciphertext, C. Again, they should use a
coin-flip protocol.
(3) Alice, using Carol™s private key, computes
M= Cdmodn
She then computes
X=Mkmodn
and sends X to Bob.
(4) Bob confirms that X” mod n = C. If it does, he believes Alice.

A similar protocol can be used to demonstrate the ability to break a discrete loga-
rithm problem [888].

Zero-Knowledge Proof that n Is a Blwm Znteger
There are no known truly practical zero-knowledge proofs that n = pq, where p and
q are primes congruent to 3 modulo 4. However, if you allow n to be of the form p™@,
where r and s are odd, then the properties which make Blum integers useful in cryp-
tography still hold. And there exists a zero-knowledge proof that n is of that form.
Assume Alice knows the factorization of the Blum integer n, where n is of the form
previously discussed. Here™s how she can prove to Bob that n is of that form [660].

(1) Alice sends Bob a number u which has a Jacobi symbol -1 modulo n.
(2) Alice and Bob jointly agree on random bits: bl, b2, . . . , bk.
(3) Alice and Bob jointly agree on random numbers: x1, x1, . . . , xk.
(4) For each i = 1, 2, . . . , k, Alice sends Bob a square root modulo n, of one of
the four numbers: xi, -xi, ux,, -uxi. The square root must have the Jacobi
symbol bi.

The odds of Alice successfully cheating are one in 2k.


23.12 BLIND SIGNATURES
The notion of blind signatures (see Section 5.3) was invented by David Chaum
[317,323], who also invented their first implementation [318]. It uses the RSA
algorithm.
Page 549
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

23 Special Algorithms for Protocols
CHAPTER



Bob has a public key, e, a private key, d, and a public modulus, n. Alice wants Bob
to sign message m blindly.

Alice chooses a random value, k, between 1 and n. Then she blinds m by
(1)
computing
t=mkemodn
(2) Bob signs t
td = (mk”)d mod n
(3) Alice unblinds td by computing
s = td/k mod n
(4) And the result is
s=mdmodn
This can easily be shown
td = (mk”)d = mdk (mod n), so td/k = mdk/k = md (mod n).

Chaum invented a family of more complicated blind signature algorithms in
[320,324], called blind unanticipated signatures. These signatures are more complex
in construction, but more flexible.

23.13 OBLIVIOUS TRANSFER
In this protocol by Michael Rabin [1286], Alice has a 50 percent chance of sending
Bob two primes, p, and q. Alice will not know whether the transfer is successful.
(See Section 5.5.) (This protocol can be used to send Bob any message with a 50 per-
cent success rate if p and q reveal an RSA private key.)

(1) Alice sends Bob the product of the two primes: n = pq.
(2) Bob chooses a random x less than n, such that x is relatively prime to n. He
sends Alice:
a=x™modn
(3) Alice, knowing p and q, computes the four roots of a: x, n - x, y, and n - y.
She chooses one of these roots at random and sends it to Bob.
(4) If Bob receives y or n - y, he can compute the greatest common divisor of x
+ y and n, which is either p or q. Then, of course, n/p = q.
If Bob receives x or n - x, he can™t compute anything.

This protocol may have a weakness: It might be the case that Bob can compute
a number a such that given the square root of a you can calculate a factor of n all
the time.
Page 550
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23.14 Secure Multiparty Computation


23.14 SECURE MULTIPARTY COMPUTATION
This protocol is from [ 13731.Alice knows the integer i; Bob knows the integer j. Alice
and Bob together wish to know whether i I j or if i > j, but neither Alice nor Bob wish
to reveal the integer each knows. This special case of secure multiparty computation
(see Section 6.2) is sometimes known as Yao™s millionaire problem [ 16271.
For this example, assume that i and j range from 1 to 100. Bob has a public key and
a private key.

(1) Alice chooses a large random number, x, and encrypts it in Bob™s public key.
c = EB(X)
(2) Alice computes c - i and sends the result to Bob.
(3) Bob computes the following 100 numbers:
yu = DB(c - i + u), for 1 I u I 100
DB is the decryption algorithm with Bob™s private key.
He chooses a large random prime, p. (The size of p should be somewhat
smaller than x. Bob doesn™t know x, but Alice could easily tell him the size
of x.) He then computes the following 100 numbers:
z, = (yUmodp), for 1 I u I 100
He then verifies that, for all u f v
lz, - z,I 2 2
and that for all u
o<z,<p-1
If this is not true, Bob chooses another prime and tries again.
(4) Bob sends Alice this sequence of numbers in this exact order:
p
Zl, 22, . . . > q, z, + 1 + 1, q + 2 + 1, . . . I ZlOO + 1,

(5) Alice checks whether the ith number in the sequence is congruent to
x mod p. If it is, she concludes that i 5 j. If it is not, she concludes that i > j.
(6) Alice tells Bob the conclusion.

All the verification that Bob goes through in step (3) is to guarantee that no num-
ber appears twice in the sequence generated in step (4). Otherwise, if z, = zb, Alice
knows that a < j < b.
The one drawback to this protocol is that Alice learns the result of the compu-
tation before Bob does. Nothing stops her from completing the protocol up to step
(5) and then refusing to tell Bob the results in step (6). She could even lie to Bob in
step (6).
Page 551
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23 Special Algorithms for Protocols
CHAPTER



Example of the Protocol
Assume they™re using RSA. Bob™s public key is 7 and his private key is 23; n = 55.
Alice™s secret value, i, is 4; Bob™s secret value, j, is 2. (Assume that only the values 1,
2, 3, and 4 are possible for i and j.)

(1) Alice chooses x = 39, and c = E,(39) = 19.
(2) Alice computes c-i = 19 - 4 = 15. She sends 15 to Bob.
(3) Bob computes the following 4 numbers:
yl=D,(15+1)=26
y,=D,(15+2)= 18
y,=D,(15+3)=2
y4=&(15+4)=39
He chooses p = 3 1 and calculates:
zl=(26mod31)=26
zz=(l8mod31)=18
z3=(2mod31)=2
z4=(39mod31)=8
He does all the verifications and confirms that the sequence is fine.
(4) Bob sends Alice this sequence of numbers in this exact order:
26, 18, 2 + 1, 8 + 1, 31 = 26, 18, 3, 9, 31
(5) Alice checks whether the 4th number in the sequence is congruent to
x mod p. Since 9 f 39 (mod 3 l), then i > j.
(6) Alice tells Bob.

This protocol can be used to create far more complicated protocols. A group of
people can conduct a secret auction over a computer network. They arrange them-
selves in a logical circle, and through individual pairwise comparisons, determine
which is offering the highest price. In order to prevent people from changing their
bids in mid-auction, some sort of bit-commitment protocol could also be used. If the
auction is a Dutch auction, then the highest bidder gets the item for his highest
price. If it is an English auction, then he gets the item for the second-highest price.
(This can be determined by a second round of pairwise comparisons.) Similar ideas
have applications in bargaining, negotiations, and arbitration.

23.15 ENCRYPTION
PROBABILISTIC
The notion of probabilistic encryption was invented by Shafi Goldwasser and Silvio
Micali [624]. Although its theory makes it the most secure cryptosystem invented,
its early implementation was impractical [625]. More recent implementations have
changed that.
Page 552
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter



The point behind probabilistic encryption is to eliminate any information leaked
with public-key cryptography. Because a cryptanalyst can always encrypt random
messages with a public key, he can get some information. Assuming he has cipher-
text C = E,(M) and is trying to recover plaintext message M, he can pick a random
message M™ and encrypt it: C™ = EK(M™). If C™ = C, then he guessed the correct plain-
text. If it™s wrong, he just guesses again.
Also, no partial information is leaked about the original message. With public-key
cryptography, sometimes a cryptanalyst can learn things about the bits: The XOR of
bits 5, 17, and 39 is 1, and so on. With probabilistic encryption, even this type of
information remains hidden.
Not a whole lot of information is to be gained here, but there are potential prob-
lems with allowing a cryptanalyst to encrypt random messages with your public
key. Some information is being leaked to the cryptanalyst every time he encrypts a
message. No one really knows how much.
Probabilistic encryption tries to eliminate that leakage. The goal is that no com-
putation on the ciphertext, or on any other trial plaintexts, can give the cryptanalyst
any information about the corresponding plaintext.
In probabilistic encryption, the encrypting algorithm is probabilistic rather than
deterministic. In other words, a large number of ciphertexts will decrypt to a given
plaintext, and the particular ciphertext used in any given encryption is randomly
chosen.
Cl =EK(M), Cz =E&M), C3 =E,(M), . . .t Ci=E,(M)
M = DK(Cl) = DK(C2) = DK(C,) = . . . = DK(Ci)
With probabilistic encryption, a cryptanalyst can no longer encrypt random plain-
texts looking for the correct ciphertext. To illustrate, assume the cryptanalyst has
ciphertext Ci = E,(M). Even if he guesses M correctly, when he encrypts E,(M), the
result will be a completely different C: C,. He cannot compare C, and Ci, and so can-
not know that he has guessed the message correctly.
This is amazingly cool stuff. Even if a cryptanalyst has the public encryption key,
the plaintext, and the ciphertext, he cannot prove that the ciphertext is the encryp-
tion of the plaintext without the private decryption key. Even if he tries exhaustive
search, he can only prove that every conceivable plaintext is a possible plaintext.
Under this scheme, the ciphertext will always be larger than the plaintext. You
can™t get around this; it™s a result of the fact that many ciphertexts decrypt to the
same plaintexts. The first probabilistic encryption scheme [625] resulted in a cipher-
text so much larger than the plaintext that it was unusable.
However, Manual Blum and Goldwasser have an efficient implementation of
probabilistic encryption using the Blum Blum Shub (BBS) random-bit generator
described in Section 17.9 [ 1991.
The BBS generator is based on the theory of quadratic residues. In English, there
are two primes, p and q, that are congruent to 3 modulo 4. That™s the private key.
Their product, pq = n, is the public key. (Mind your ps and qs; the security of this
scheme rests in the difficulty of factoring n.)
To encrypt a message, M, first choose some random x, relatively prime to n. Then
compute
Page 553
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

23 Special Algorithms for Protocols
CHAPTER



x,,=x™modn
Use x0 as the seed of the BBS pseudo-random-bit generator and use the output of
the generator as a stream cipher. XOR M, one bit at a time, with the output of the
generator. The generator spits out bits bi (the least-significant bit of x,, where x, =
x, - 12 mod n), so

M=M,,M,,M, ,..., M,
C = Ml 0 bl, M2 0 bz, M3 0 ba, . . . , M, 0 b,
where t is the length of the plaintext
Append the last computed value, x0 to the end of the message and you™re done.
The only way to decrypt this message is to recover x0 and then set up the same
BBS generator to XOR with the ciphertext. Because the BBS generator is secure to
the left, the value xt is of no use to the cryptanalyst. Only someone who knows p
and 4 can decrypt the message.
In C, the algorithm to recover x0 from xt is:

. 1
( 2)



>>