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