Variants of the Signed Fractional Window Representation. In our per-

formance estimates in Section 4, we optimistically assumed that besides ROM and fast

read/write memory, there is another kind of memory that we can use for the cache.

This is an assumption that we made for simplicity, but which is not necessary. In fact

we may use some of the fast read/write memory for a small cache without completely

losing this memory for precomputed powers of g1 .

This can be achieved by observing that we may modify the parameter m for the

left-to-right signed fractional window representation while performing the conversion.

Thus, in the algorithm from Section 3.1, provided that m ≥ 2s ’ 1, we may initially use

some maximum-size digit set B ± (m) = {±1, ±3, . . ., ±m, 0} for signed digits b1, down

(b1, ,...,b1,L +···+L )2

1 s’1

to b1,L1 +···+Ls’1 , then cache the current group element g1 in the

m ±

memory space that so far held g1 , and then use the smaller digit set B (m ’ 2) for

¡

subsequent digits b1,L1 +···+Ls’1 ’1 down to b1,L1 +···+Ls’2 . Continuing in this fashion,

we eventually give up digits ±m, ±(m ’ 2), . . ., ± m ’ 2(s ’ 1) .

C Performance Comparison

This appendix demonstrates the merits of our new technique for multi-exponentiation

with caching in one particular situation where very little memory is available for use as

a cache. We show that our method is of advantage even under this severe restriction.

We make the following assumptions:

Faster Multi-exponentiation through Caching 55

e e

“ We look at two-fold multi-exponentiation, g11 g22 . Base element g2 is ¬xed; base el-

ement g1 is variable such that the current value will repeat in the directly following

multi-exponentiation with probability Pold = 1 . 2

“ The exponents e1 and e2 are uniformly random integers up to = 256 bits.

“ Storage is available for 128 ¬xed precomputed elements in read-only memory (de-

rived from the ¬xed base g2 ), and for only 2 precomputed elements in read/write

memory. The latter includes input value g1 . In addition to this, we have space for

variable A in the algorithm from Section 2.1, and the memory holding the expo-

nents. (Note that typically the memory needed for the exponents is less than the

memory needed for a single group element: for elliptic curve cryptography using

projective coordinates over a 256-bit ¬eld, one group element takes 768 bits.)

“ Di¬erent from the assumptions as used in Section 4, we have no additional cache

memory. That is, a group element to be cached has to be kept in one of the two

read/write storage units for precomputed elements.

“ We use rough estimates S = 0.7 and M = 1 for the amount of time spent on

each group squaring (e.g., elliptic curve point doubling) and on each group multi-

plication (e.g., elliptic curve point addition). (For example, when using Jacobian

projective coordinates for elliptic curves over prime ¬elds, a point doubling takes

10 or 8 ¬eld multiplications depending on the curve, and a general point addi-

tion requires 16 ¬eld multiplications [10], or 11 ¬eld multiplications in the case

of “mixed coordinates” [7]. Mixed coordinates require a one-time conversion step

to one of the inputs to convert it into a¬ne coordinates, which is reasonable for

precomputed values. Accordingly, 11 ≈ 0.73 is one way to justify our estimate

8

S

≈ 0.7, although in the following we neglect the cost of the conversion.)

M

If (instead of applying our new caching strategy) we directly use interleaved multi-

exponentiation in this situation, employing signed-digit representation as explained in

Section 2.1, we can keep precomputed values g2 , g2 , g2 , . . ., g2 in read-only memory,

3 5 255

and use read/write memory for g1 and g1 , thus achieving an exponentiation cost of

3

approximately

256 256

M + 255S ≈ 268.1

+

4 10

(or 89.5M +254S ≈ 267.3 according to experimental simulation results) plus 1M +1S =

1.7 to precompute g1 from g1 when g1 has changed from the previous computation. By

3

assumption, this happens with probability 1 , resulting in a total estimate of 268.1 +

2

≈ 269.0 (for the simulation: 268.2).

1.7

2

Our method initially performs worse than this, namely, in the case with a new base

(Section 3.1). Here, the read-only memory will contain g2 , g2 , g2 , . . ., g2 , plus similar

3 5 127

128

powers of g2 . The read/write memory initially is ¬lled with precomputed elements g1

2

and g1 . To perform the multi-exponentiation as described in Section 3.1, we use radix-2

3

exponent splitting for exponent e2 to obtain partial exponent representations no longer

than 129 digits. For exponent e1 , we use a signed fractional window representation

variant as sketched in Appendix B, i.e., where digit set parameter m is modi¬ed within

the conversion: the more signi¬cant digits can use digits set {±1, ±3, 0}, whereas the

less signi¬cant digits (digits b1,127 , . . ., b1,0 ) are restricted to digit set {±1, 0}. This

is because we no longer keep g1 in memory when the method from Section 3.1 has

3

determined a group element to be cached, thus freeing a memory location for use as

cache space. The performance estimate for this multi-exponentiation is

128 128 256

M + 255S ≈ 281.6

+ +

4 3 9

56 B. M¨ller and A. Rupp

o

(simulation: 102.7M + 253.8S ≈ 280.4) plus 1M + 1S ≈ 1.7 to precompute g1 from 3

g1 . We bene¬t from the extra e¬ort put into this computation whenever the same g1

reappears in the following multi-exponentiation. In this case, the multi-exponentiation

will only take approximate e¬ort

128 128 256

M + 127S ≈ 202.7

+ +

3 3 9

(simulation: 113.9M +128.2S ≈ 203.6). The average cost given Pold = 1 comes to 242.1

2

(simulation: 242.0). Thus, our method provides an average 10 percent performance

improvement in this speci¬c scenario.

Privacy Preserving Data Mining within

Anonymous Credential Systems

Aggelos Kiayias1, , Shouhuai Xu2, , and Moti Yung3

1

Computer Science and Engineering, University of Connecticut

Storrs, CT, USA

aggelos@cse.uconn.edu

2

University of Texas, San Antonio, TX, USA

shxu@cs.utsa.edu

3

Google Inc. and Computer Science, Columbia University

New York, NY, USA

moti@cs.columbia.edu

Abstract. Regular (non-private) data mining can be applied to manage

and utilize accumulated transaction data. For example, the accumulated

relative service time per user per month can be calculated given indi-

vidual transaction data from which the user compliance with a service

agreement can be determined and possibly billing can be processed. Nev-

ertheless, due to user privacy concerns, cryptographic research developed

transactions based on unlinkable anonymous credentials. Given the na-

ture of anonymous credentials the ease of managing accumulated data

(e.g., per user) is lost. To restore the possibility of management and accu-

mulation of data it seems that a suitable form of privacy preserving data