<<

. 4
( 11 .)



>>

ing verifying key y) and receives information s money from her account by using a blind signa-
in return can derive from y, m, m , s only valid ture scheme and then deposit the amount into the
signatures for those messages m that observe criminal™s account.
the same structure as m. In of¬‚ine electronic Trustee based blind signature schemes have
cash this is used to encode a customer™s identity been proposed to strike a more acceptable balance
into the messages that are signed by the bank between keeping individuals accountable and pro-
such that the messages obtained by the customer tecting their identities. Stadler et al. [22] have
all have his identity encoded correctly. Impor- proposed fair blind signatures. Fair blind signa-
tant work in this direction was done by Chaum tures employ a trustee who is involved in the
and Pedersen [7], Brands [1], Ferguson [12, 13], key setup of the scheme and in an additional
Frankel et al. [14] and Radu et al. [20, 21]. A link-recovery operation between a signer and the
formal de¬nition of a special type of restrictive trustee. The trustee can revoke the “blindness”
blind signatures has been given by P¬tzmann and of certain pairs of messages and signatures upon
Sadeghi [18]. request. The link-recovery operation allows the
Blindness is a property serving the privacy in- signer or the judge to determine for each transcript
terests of honest recipients against cheating and (m, s) of the signing operation which message m
collaborating signers and veri¬ers. The highest has resulted for the recipient, or to determine for
degree of unlinkability is unconditional unlinka- a given recipient™s message m from which tran-
bility, where a dishonest signer and veri¬er, both script (m, s) it has evolved. Similar approaches
with unconditional computing power, cannot dis- have been applied to constructions of electronic
tinguish the transcripts (m, s) seen by the signer in cash [3, 21].
his interactions with the honest recipient from the Blind signatures have been employed exten-
recipient™s outputs (m , s ), which are seen by the sively in cryptographic constructions of privacy
veri¬er, even if the signer and the veri¬er collabo- oriented services such as untraceable electronic
rate. More precisely, consider an honest recipient cash, anonymous electronic voting schemes, and
who ¬rst obtains n pairs of messages and respec- unlinkable credentials.
tive valid signatures (m1 , s1 ), . . . , (mn , sn ) from a
Gerrit Bleumer
signer, then derives n pairs of blinded messages
and signatures (m1 , s1 ), . . . , (mn , sn ) from the for-
mer n pairs one by one, and later shows the latter
References
n pairs to a veri¬er in random order. Then, the
signer and the collaborating veri¬er should ¬nd
[1] Brands, Stefan (1993). “An ef¬cient off-line elec-
each bijection of the former n pairs onto the lat-
tronic cash system based on the represen-
ter n pairs to be equally likely to describe which
tation problem.” Centrum voor Wiskunde en
of the latter pairs the honest recipient has derived Informatica, Computer Science/Departement of Al-
from which of the former pairs. A weaker degree of gorithmics and Architecture, Report CS-R9323,
blindness is de¬ned as computational unlinkabil- http://www.cwi.nl/
ity, which is de¬ned just as unconditional unlinka- [2] Brands, Stefan (1994). “Untraceable off-line
bility except that the attacker is computationally cash in wallet with observers.” Advances in
Blinding techniques 39


ed. D.R. Stinson. Springer-Verlag, Berlin, 292“
Cryptology”CRYPTO™93, Lecture Notes in Com-
301.
puter Science, vol. 773, ed. D.R. Stinson. Springer-
[14] Frankel, Yair, Yiannis Tsiounis, and Moti Yung
Verlag, Berlin, 302“318.
(1996). “Indirect discourse proofs: Achiev-
[3] Brickell, Ernie, Peter Gemmell, and David Kravitz
ing ef¬cient fair off-line e-cash.” Advances in
(1995). “Trustee-based tracing extensions to
Cryptography”ASIACRYPT™96, Lecture Notes
anonymous cash and the making of anonymous
in Computer Science, vol. 1163, eds. K. Kim
change.” 6th ACM-SIAM Symposium on Discrete
and T. Matsumoto. Springer-Verlag, Berlin, 286“
Algorithms (SODA). ACM Press, New York, 457“
300.
466.
[15] Franklin, Matthew and Moti Yung (1993). “Secure
[4] Camenisch, Jan L., Jean-Marc Piveteau, and
and ef¬cient off-line digital money.” 20th Inter-
Markus A. Stadler (1994). “An ef¬cient electronic
national Colloquium on Automata, Languages
payment system protecting privacy.” ESORICS™94
and Programming (ICALP), Lecture Notes in
(Third European Symposium on Research in Com-
Computer Science, vol. 700, eds. A. Lingas, R.G.
puter Security), Brighton, Lecture Notes in Com-
Karlsson, and S. Carlsson. Springer-Verlag,
puter Science, vol. 875, ed. D. Gollman. Springer-
Heidelberg, 265“276.
Verlag, Berlin, 207“215.
[16] Goldwasser, Sha¬, Silvio Micali, and Ronald L.
[5] Camenisch, Jan L., Jean-Marc Piveteau, and
Rivest (1988). “A digital signature scheme secure
Markus A. Stadler (1995). “Blind signatures based
against adaptive chosen-message attacks.” SIAM
on the discrete logarithm problem.” Advances in
Journal on Computing, 17 (2), 281“308.
Cryptology”EUROCRYPT™94, Lecture Notes in
[17] Naccache, David and Sebastiaan von Solms (1992).
Computer Science, vol. 950, ed. A. De Santis.
“On blind signatures and perfect crimes.” Comput-
Springer-Verlag, Berlin, 428“432.
ers & Security, 11 (6), 581“583.
[6] Camenisch, Jan L., Jean-Marc Piveteau, and
[18] Birgit, P¬tzmann, and Ahmad-Reza Sadeghi
Markus A. Stadler (1996). “An ef¬cient fair pay-
(1999). “Coin-based anonymous ¬ngerprinting.”
ment system.” 3rd ACM Conference on Computer
Advances in Cryptology”EUROCRYPT™99, Lec-
and Communications Security, New Delhi, India,
ture Notes in Computer Science, vol. 1592, ed. J.
March 1996. ACM Press, New York, 88“94.
Stern. Springer-Verlag, Berlin, 150“164.
[7] Chaum, David (1983). “Blind signatures for un-
[19] Pointcheval David (1998). “Strengthened security
traceable payments.” Advances in Cryptology”
for blind signatures.” Advances in Cryptology”
CRYPTO™82, Lecture Notes in Computer Sci-
EUROCRYPT™98, Lecture Notes in Computer Sci-
ence, eds. Plenum D. Chaum, R.L. Rivest, and
ence, vol. 1403, ed. K. Nyberg. Springer-Verlag,
A.T. Sherman. Plenum Press, New York, 199“
Berlin, 391“405.
203.
[20] Radu, Christian Ren´ Govaerts, and Joos Vande-
e
[8] Chaum, David (1990). “Showing credentials with-
walle (1996). “A restrictive blind signature scheme
out identi¬cation: Transferring signatures be-
with applications to electronic cash.” Communi-
tween unconditionally unlinkable pseudonyms.”
cations and Multimedia Security II. Chapman &
Advances in Cryptology”AUSCRYPT™90, Lecture
Hall, London, 196“207.
Notes in Computer Science, vol. 453. Springer-
[21] Radu, Christian Ren´ Govaerts, and Joos
e
Verlag, Berlin, 246“264.
Vandewalle (1997). “Ef¬cient electronic cash
[9] Chaum, David (1990). “Online cash checks.” Ad-
with restricted privacy.” Financial Cryptography
vances in Cryptology”EUROCRYPT™89, Lecture
™97. Springer-Verlag, Berlin, 57“69.
Notes in Computer Science, vol. 434, eds. J.-J.
[22] Stadler, Markus, Jean-Marc Piveteau, and Jan
Quisquatere and J. Vandewalle. Springer-Verlag,
L. Camenisch (1995). “Fair blind signatures.” Ad-
Berlin, 288“293.
vances in Cryptology”EUROCRYPT™95, Lecture
[10] Chaum, David, Amos Fiat, and Moni Naor
Notes in Computer Science, vol. 921, eds. L.C.
(1990). “Untraceable electronic cash.” Advances
Guillou and J.-J. Quisquater. Springer-Verlag,
in Cryptology”CRYPTO™88, Lecture Notes in
Berlin, 209“219.
Computer Science, vol. 403, ed. S. Goldwasser.
Springer-Verlag, Berlin, 319“327.
[11] Chaum, David and Torben P. Pedersen (1993).
“Wallet databases with observers.” Advances in
BLINDING TECHNIQUES
Cryptology”CRYPTO™92, Lecture Notes in Com-
puter Science, vol. 740, ed. E.F. Brickell. Springer-
Verlag, Berlin, 89“105.
Blinding is a concept in cryptography that allows
[12] Ferguson, Niels (1994). “Single term off-line coins.”
a client to have a provider compute a mathemati-
Advances in Cryptology”EUROCRYPT™93, Lec-
cal function y = f(x), where the client provides an
ture Notes in Computer Science, vol. 765, ed. T.
input x and retrieves the corresponding output y,
Helleseth. Springer-Verlag, Berlin, 318“328.
but the provider would learn about neither x nor y.
[13] Ferguson, Niels (1994). “Extensions of single-
This concept is useful if the client cannot compute
term coins.” Advances in Cryptology”CRYPTO™93,
the mathematical function f all by himself, for
Lecture Notes in Computer Science, vol. 773,
40 Blinding techniques


example, because the provider uses an additional 2. The client chooses an input m, generates a
blinding factor a ∈ A at random, and trans-
private input in order to compute f ef¬ciently.
forms m into m = φ y,a (m).
Blinding techniques can be used on the client
side of client-server architectures in order to en- 3. The client sends m to the provider and receives
z = fx (m ) from the provider in return.
hance the privacy of users in online transactions.
4. The client computes z = ¦’1 (z ).
This is the most effective way of dealing with y,a
server(s) that are not fully trusted. If both m and m are equally meaningful or mean-
Blinding techniques are also the most effective ingless to the provider, then he has no way of dis-
countermeasure against remote timing analysis of tinguishing a client who sends the plain argument
Web servers [4] and against power analysis and/or m from a client who sends a blinded argument m
timing analysis of hardware security modules (see in step 3.
side-channel attacks and side-channel analysis). The ¬rst blinding technique was proposed by
In a typical setting, a provider offers to com- Chaum as part of the Chaum Blind Signature
pute a function fx (m) using some private key x [5,6]. It is based on a homomorphic property of the
and some input m chosen by a client. A client RSA signing function (see RSA digital signature
can send an input m, have the provider compute scheme).
the corresponding result z = fx (m), and retrieve z Let n = pq be the product of two large
from the provider afterward. With a blinding tech- safe primes, (x, y) being a pair of private and pub-
nique, a client would send a transformed input m lic RSA keys such that x is chosen randomly from
Z —p’1)(q’1) and y = x ’1 (mod ( p ’ 1)(q ’ 1)) and
to the provider, and would retrieve the correspond- Z(
M = Z — be the domain of multiplicative inverses
ing result z in return. From this result, the client Zn
could then derive the result z = fx (m ) that corre- of the residues modulo n. The functions fx (m) =
mx (mod n) are the RSA signing functions. The
sponds to the input m in which the client was inter-
families φ, ¦ of auxiliary functions are chosen as
ested in the ¬rst place. Some blinding techniques
guarantee that the provider learns no information follows:
about the client™s input m and the corresponding
φ y,a (m) = ma y (mod n)
output z.
¦’1 (z ) = z a ’1 (mod n).
More precisely, blinding works as follows: con- y,a
sider a key generating algorithm gen that outputs Other blinding techniques have been used in a
pairs (x, y) of private and public keys (see public- variety of interactive protocols such as divert-
key cryptography), two domains M, Z of messages, ible proofs of knowledge [1, 7, 8], privacy-oriented
and a domain A of blinding factors. Assume a electronic cash [2, 3] and unlinkable credentials
family of functions z = fx (m), where each mem- [6], and in anonymous electronic voting schemes.
ber is indexed by a private key x, takes as in-
put a value m ∈ M, and produces an output z ∈ Z. Gerrit Bleumer
Let φ y,a : M ’ M and ¦ y,a : Z ’ Z be two fami-
References
lies of auxiliary functions, where each member is
indexed by a public key y and a blinding factor
[1] Blaze, Matt, Gerrit Bleumer, and Martin
a, such that the following two conditions hold for
Strauss (1998). “Divertible protocols and atomic
each key pair (x, y) that can be generated by gen,
proxy cryptography.” Advances in Cryptology”
each blinding factor a ∈ A and each input m ∈ M: EUROCRYPT™98, Lecture Notes in Computer
“ the functions φ y,a and ¦’1 are computable in Science, vol. 1403, ed. K. Nyberg. Springer-Verlag,
y,a
polynomial time, Berlin, 127“144.
“ ¦’1 ( fx (φ y,a (m))) = f (m) (as shown in the follow- [2] Brands, Stefan (1994). “Untraceable off-line cash in
x
y,a
ing diagram). wallet with observers.” Advances in Cryptology”
CRYPTO™93, Lecture Notes in Computer Science,
fx (m)
M ’’ Z vol. 773, ed. D.R. Stinson. Springer-Verlag, Berlin,
¦
¦ ¦ ’1 302“318.
φ y,a (m) ¦¦ y,a (z ) [3] Brickell, Ernie, Peter Gemmell, and David Kravitz
(1995). “Trustee-based tracing extensions to anony-
fx (m )
M ’’ Z mous cash and the making of anonymous change.”
6th ACM-SIAM Symposium on Discrete Algorithms
In order to blind the computation of fx by the (SODA). ACM Press, New York, 457“466.
provider, a client can use the auxiliary functions [4] Brumley, David and Dan Boneh (2003). “Re-
φ, ¦ in a two-pass interactive protocol as follows: mote timing attacks are practical.” 12th Usenix
1. The provider generates a pair (x, y) of a private Security Symposium 2003. http://www.usenix.org/
key and a public key and publishes y. publications/library/proceedings/sec03/
Block ciphers 41


Diffusion: “each digit of the plaintext and each
[5] Chaum, David (1993). “Blind signatures for un-
traceable payments.” Advances in Cryptology” digit of the secret key should in¬‚uence many
CRYPTO™82, Lecture Notes in Computer Science, digits of the ciphertext” [29].
eds. Plenum D. Chaum, R.L. Rivest, and A.T. These two design principles are very general and
Sherman. Plenum Press, New York, 199“203. informal.
[6] Chaum, David (1990). “Showing credentials with-
Shannon also discusses two other more speci¬c
out identi¬cation: Transferring signatures between
design principles. The ¬rst is to make the secu-
unconditionally unlinkable pseudonyms.” Advances
rity of the system reducible to some known dif¬-
in Cryptology”AUSCRYPT™90, Sydney, Australia,
cult problem. This principle has been used widely
January 1990, Lecture Notes in Computer Science,
in the design of public-key systems, but not in
vol. 453. Springer-Verlag, Berlin, 246“264.
secret-key ciphers. Shannon™s second principle is
[7] Chaum, David and Torben P. Pedersen (1993).
to make the system secure against all known at-
“Wallet databases with observers.” Advances in

<<

. 4
( 11 .)



>>