ńňđ. 1 
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 23 ................................................ 526
Special Algorithms for Protocols ........... 526
MULTIPLEKEY PUBLICKEY .................. 526
SECRETSHARING ALGORITHMS ......... 527
LaGrange Interpolating Polynomial ................ 527
Vector Scheme .............................................. 528
AsmuthBloom ............................................... 528
KarninGreeneHellman ................................ 529
Advanced Threshold Schemes ..................... 529
Sharing a Secret with Cheaters .................... 530
SUBLIMINAL CHANNEL ........................... 530
OngSchnorrShamir ..................................... 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
ONEWAY ACCUMULATORS .................. 542
ALLORNOTHING DISCLOSURE OF ..... 542
FAIR AND FAILSAFE CRYPTOSYSTE .... 545
Fair DiffieHellman ......................................... 545
Failsafe DiffieHellman .................................. 546
ZEROKNOWLEDGE PROOFS OF .......... 547
ZeroKnowledge Proof a Discrete .................. 547
ZeroKnowledge Proof of the Ability to ........... 547
ZeroKnowledge 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 MULTIPLEKEY PUBLICKEY 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 multiplekey 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 zeroknowledge identification
schemes solve both shortcomings of the previous systems.
23.2 SECRETSHARING ALGORITHMS
Back in Section 3.7 I discussed the idea behind secretsharing 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 mindboggling 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 onetime 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 secretsharing schemes presented here.
Vector Scheme
George Blakley invented a scheme using points in space [ 182). The message is
defined as a point in mdimensional 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 threedimensional 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.
AsmuthBloom
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 dnm+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.
KarninGreeneHellman
This scheme uses matrix multiplication [818]. Choose n + 1 mdimensional 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 secretsharing 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
(sl)(ml)/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
OngSchnorrShamir
This subliminal channel (see Section 4.2), designed by Gustavus Simmons
[ 1458,1459,1460], uses the OngSchnorrShamir 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 OngSchnorr
Shamir scheme and the carrier of the subliminal message.
Walter the warden (remember him?) can authenticate the message as described by
the OngSchnorrShamir 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+ &kl) mod n
This works, but remember that the basic OngSchnorrShamir 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â€˜(&IrX))mod(p1)
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 OngSchnorrShamir 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 160bit 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 160bit 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 onetime pad and encrypt the subliminal message with the onetime
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 14bit 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 160bit private key, x.
(4) The chip randomly chooses a lobit block of x: the first 10 bits, the second
10 bits, and so on. Since there are 16 possible lobit blocks, a 4bit number
can identify which block it is. This 4bit identifier, plus the 10 bits of the
key, is the 14bit 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 subliminalfree. 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 threepass 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 FiatShamir and Feige
FiatShamir 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=xi 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 protocolAlice can convince Bob
that her signature is validbut 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 secretsharing 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 designatedconfirmer 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 problemhe 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(p1)
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
Coinflip 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 oneway function in this
protocol [ 13061:
Coinflip 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 = xlxâ€™ mod p  1
These are hard problems.
Page 542
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23.9 AllorNothing 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 coinflipping 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 zeroknowledge
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 ONEWAY ACCUMULATORS
There is a simple oneway 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 ALLORNOTHING 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 rightmost bit as
zero.)
Now, hereâ€™s the protocol. Alice is the seller. Bob and Carol are buyers. Alice has
k nbit secrets: S1, SZ, . . . , Sk. Bob wants to buy secret Sbi Carol wants to buy
secret S,.
(1) Alice generates a publickey/privatekey key pair and tells Bob (but not
Carol) the public key. She generates another publickey/privatekey key
pair and tells Carol (but not Bob) the public key.
(2) Bob generates k nbit random numbers, B1, &, . . . , Bk, and tells them to
Carol. Carol generates k nbit 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 nbit 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 nbit numbers, Bâ€™i, Bâ€™2, . . . , Bâ€™k, to Alice.
Carol takes each of the nbit 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 nbit numbers, cI1, C2, . . . , Câ€™k, to Alice.
(5) Alice decrypts all Câ€™i with Bobâ€™s private key, giving her k nbit 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 nbit 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 12bit 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 AllorNothing 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 12bit 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 zeroknowledge 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 DiffieHellman
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 DiffieHellman 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 DiffieHellman 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 DiffieHellman
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 bitcommitment 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 secretsharing
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 ZEROKNOWLEDGE PROOFS KNOWLEDGE
OF
ZeroKnowledge 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 coinflipping 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 2t.
ZeroKnowledge 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 zeroknowledge 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 coinflip 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
coinflip 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].
ZeroKnowledge Proof that n Is a Blwm Znteger
There are no known truly practical zeroknowledge 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 zeroknowledge 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,<p1
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 ci = 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 midauction, some sort of bitcommitment 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 secondhighest 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 publickey 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 publickey
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) randombit 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 pseudorandombit 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 leastsignificant 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 