dom xU ∈ Zq as its secret key VEKU , and sets its tion.” 5th International Workshop on Practice and

public key SDKU = yU = g xU . The scheme of [1] is Theory in Public Key Cryptosystems”PKC 2002,

based on the following noninteractive key agree- February, Lecture Notes in Computer Science, vol.

2274, eds. D. Naccache and P. Paillier. Springer-

ment between users S and R. Namely, both S and R

x

x

can compute the quantity Q SR = g xRxS = ySR = yRS . Verlag, Berlin, 80“98.

[4] Bellare, Mihir and Chanathip Namprempre

They then set the key KSR = H(Q SR), where H is

(2000). “Authenticated encryption: Relations

a random oracle, and then always use KSR to per-

among notions and analysis of the generic

form symmetric-key authenticated encryption of

composition paradigm.” Advances in Cryptology”

the message m. For the latter, they can use any ASIACRYPT 2000, Kyoto, Japan, December 3“7,

secure symmetric-key scheme, like “encrypt-then- Lecture Notes in Computer Science, vol. 1976, ed.

mac” [4] or OCB [12]. The resulting signcryption T. Okamoto. Springer-Verlag, Berlin, 531“545.

scheme can be shown to be outsider-secure for both [5] Bellare, Mihir and Phillip Rogaway (1995).

privacy and authenticity, in the multi-user setting. “Optimal asymmetric encryption.” Advances in

Clearly, it is not insider-secure, since both S and Cryptology”EUROCRYPT™94, May 9“12, Lecture

Signed digit exponentiation 583

SIGNED DIGIT

Notes in Computer Science, vol. 950, ed. A. De

Santis. Springer-Verlag, Berlin, 92“111. Revised

EXPONENTIATION

version available from http://www-cse.ucsd.edu/

users/mihir/

Signed digit exponentiation is an approach for

[6] Bellare, Mihir and Phillip Rogaway (1996). “The

computing powers in any group in which the in-

exact security of digital signatures: How to sign

verse A’1 of any group element A can be computed

with RSA and Rabin.” Advances in Cryptology”

EUROCRYPT™96, May 12“16, Lecture Notes in quickly (such as the groups of points on an elliptic

Computer Science, vol. 1070, ed. U. Maurer. curve employed in elliptic curve cryptography). It

Springer-Verlag, Berlin, 399“416. Revised version is related to sliding window exponentiation: while

appears in http://www-cse.ucsd.edu/users/mihir/

in sliding window exponentiation each window

papers/crypto-papers.html

corresponds to a positive digit value, signed digit

[7] Coron, Jean-S´ bastian, Marc Joye, David

e

exponentiation additionally makes use of the cor-

Naccache, and Pascal Pailler (2002). “Universal

responding negative digit values, and the ease of

padding schemes for RSA.” Advances in Crypto-

inversion makes these extra digits available al-

logy”CRYPTO 2002, August 18“22, Lecture

most for free. This often makes signed digit expo-

Notes in Computer Science, vol. 2442, ed. M. Yung.

nentation faster when using the same amount of

Springer-Verlag, Berlin. Available from http://

eprint.iacr.org/2002/115/ memory for storing group elements, and allows it

[8] Dodis, Yevgeniy and Jee Hea An (2003). “Con- to reach approximately the same speed with less

cealment and its applications to authenticated en- memory.

cryption.” Advances in Cryptology”EUROCRYPT Let Bk = {±1, ±3, . . . , ±(2k ’ 1)} where k is a

2003, May 4“8, Lecture Notes in Computer Science,

positive integer; and let a base-two representation

vol. 2656, ed. E. Biham. Springer-Verlag, Berlin,

of an exponent e be given using the digit set {0} ∪

312“329.

Bk , i.e.

[9] Dodis, Yevgeniy, Michael J. Freedman, Stanislaw

Jarecki, and Shabsi Wal¬sh (2004). Versatile l’1

e= ei 2i , ei ∈ {0} ∪ Bk .

Padding Schemes for Joint Signature and En-

cryption. In Birgit P¬tzmann, editor, Eleventh i=0

ACM Conference on Computer and Communica-

Assuming that l is chosen such that el’1 =

tion Security pages 196“205. ACM, October 25“29,

0, the left-to-right signed digit exponentiation

2004.

method computes ge as follows where g is any

[10] Krawczyk, Hugo (2001). “The order of encryp-

tion and authentication for protecting commu- group element; cf. the left-to-right sliding window

nications (or: How secure is ssl?).” Advances in exponentiation method.

Cryptology”CRYPTO 2001, August 19“23, Lec-

G1 ← g

ture Notes in Computer Science, vol. 2139, ed. J.

Kilian. Springer-Verlag, Berlin, 310“331. A← g—¦g

[11] Rogaway, Phillip (2002). “Authenticated-

for d = 3 to 2k ’ 1 step 2 do

encryption with associated-data.” Ninth ACM

Gd ← Gd’2 —¦ A

Conference on Computer and Communication

Security, November 17“21, ed. Ravi Sandhu. ACM

if el’1 > 0 then

Press, New York, 98“107.

[12] Rogaway, Phillip, Mihir Bellare, John Black, and

A ← Gel’1

Ted Krovetz (2001). “OCB: A block-cipher mode of

else

operation for ef¬cient authenticated encryption.”

A ← G’1l’1

Eighth ACM Conference on Computer and Com-

’e

munication Security, November 5“8, ed. Pierangela

for i = l ’ 2 down to 0 do

Samarati. ACM Press, New York, 196“205.

A← A —¦ A

Full version available from http://www.cs.ucsdavis

.edu/˜rogaway if ei = 0 then

[13] Shoup, Victor (2001). “OAEP reconsidered.” Ad-

if ei > 0 then

vances in Cryptology”CRYPTO 2001, August 19“

A ← A —¦ Gei

23, Lecture Notes in Computer Science, vol. 2139,

ed. J. Kilian. Springer-Verlag, Berlin, 240“259.

else

[14] Zheng, Y. (1997). “Digital signcryption or how to

A ← A —¦ G’1i

achieve cost(signature & encryption) cost(sig- ’e

nature) + cost(encryption).” Advances in Crypto- return A

logy”CRYPTO™97, August 17“21, Lecture Notes in

The right-to-left signed digit exponentiation

Computer Science, vol. 1294, ed. B.S. Kaliski Jr.

method computes ge as follows; cf. the right-to-left

Springer-Verlag, Berlin, 65“179.

584 Simultaneous exponentiation

sliding window exponentiation method. Note that This algorithm is a variant of right-to-left scan-

the algorithm as written can be optimized simi- ning as used in sliding window exponentiation

with an effective window size of k + 1. For ef-

larly to the right-to-left 2k -ary exponentiation or

sliding window exponentiation methods to avoid ¬ciency considerations, if the cost of inverting

(at least) 2k’1 applications of the group operation. groups elements and the additional cost for ob-

taining the appropriate representation of e can

for d = 1 to 2k ’ 1 step 2 do be neglected, signed digit exponentiation dif-

Bd ← identity element fers from sliding window exponentiation with the

same parameter k in that the expected number

A← g

of nonzero digits in the representation is approxi-

mately l/(k + 2) instead of approximately l/(k + 1)

for i = 0 to l ’ 1 do

(but the maximum possible length of the signed

if ei = 0 then

digit representation is longer: while l cannot ex-

if ei > 0 then ceed the length of the binary representation of e

Bei ← Bei —¦ A for sliding window exponentiation, it can be said

length plus 1 for signed digit exponentiation).

else

B’ei ← B’ei —¦ A’1 Bodo M¨ ller

o

if i < l ’ 1 then

References