JAIST Repository

JAIST Repository

https://dspace.jaist.ac.jp/

Title

究

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

Key Distribution Systems

By Takeshi OKAMOTO

A thesis submitted to

School of Information Science,

Japan Advanced Institute of Science and Technology,

in partial fulllment of the requirements

for the degree of

Master of Information Science

Graduate Program in Information Science

Written under the direction of

Professor Eiji OKAMOTO

February 15, 1999

Copyright c 1999 byTakeshiOKAMOTO

In1984A.Shamir[3]formulatedthegeneralideaofidentity-basedcryptosystemwhich

is an asymmetric system employing users' identities instead of public keys, giving an

exampleforID-basedsignaturesystem, andconceptualmo delforanID-basedencryption

scheme. In this case, ID means information which is well-known to everyone. By using

this system, we can solve the several problems which exist in public key cryptosystems

such asmanagement orprocurement of the users' public keys.

In ID-based systems, there exit identity-based key distribution systems which are

called ID-KDS for short. These systems have some advantages because they can be

used not only for key distribution but also for authentication. In 1989, E.Okamoto and

K.Tanaka[8]proposed anewID-KDSwhichisbasedonthe Die-Hellmankeyexchange

scheme for key sharing,and whichincludes RSA-basedauthenticationagainst imperson-

ation. Besidesthis ID-KDS, there are many useful schemes [8]- [12].

These systems are ecient schemes for implementation, but they have certain draw-

backs at the stage inwhich the center revoke a user's secret information and give a new

one. That is, if a user's secret information is made public for some reasons, the center

must discard the user's ID and adopt a dierent one. When it comes to implement ID-

KDS, it is preferable that the center adopts one uniform ID such as a user's name, an

e-mail address, a so cial security number, and so on. However, usual system is needed

to make a le which contains several pieces of IDfor one user. Therefore, these systems

imposea burden on the users and losethe advantagesof ID-based systems.

To solve these problems, we propose the following concept. That is, even after the

center has revoked a user's secret information, the center generates a new one without

any change of ID.This meansthat it keepsthe one-to-onecorresp ondence between users

and ID's. Therefore,we must generate several pieces of secret information for a piece of

ID.Inthisthesis,werealizethis conceptbymo difying theOkamoto-Tanakakeyexchange

scheme [8].

In this thesiswestudy the following themes:

1. We propose a new concept of identity-based cryptosystem and call this system

\Identity-based fault-tolerant key distribution system".

2. Torealizeaboveconcept, weproposeaconcreteschemebymodifyingthe Okamoto-

Tanakakey exchange scheme.

3. We study the security of the proposed scheme by using reduction of functions.

4. We consider the applications of the proposed concept to expand it into other key

management.

First of all, I am most grateful to my supervisor, Professor Eiji Okamoto, who gave

me the opportunity to study in cryptography and supp orted me. I am grateful to thank

ProfessorTetsuo Asanoand AssociateProfessorMineoKanekofortheir muchadviceand

encouragement. I would liketothank Asso ciateProfessorAtsukoMiyajifor helpfulcom-

mentsand nice discussions with her.

I wish to express my gratitude to Associate Professor Masahiro Mambo at Tohoku

University and Professor Masahiro Kubota at Kyoto Institute of Technology for their

preciousadvice and helpful support.

I greatly thank Asso ciate MitsuruTadaand Asso ciateXunYi for their eager sugges-

tions and helpful comments. I deeply thank Dr.HisaoSakazaki and Mr.ShigekiKitazawa

for many comments and helpful teaching. They guided me into the fascinating eld of

cryptography and the basisfor this thesis lies inthe jointworkwith them.

I really appreciate to take this opportunity and thank all the people who supported

my research and gave me go o d suggestions. I would like to thank all the members in

Okamoto-Miyaji Lab oratory for their helpful comments, nice talks and much advice. In

our lab oratory,I always had a greatand relaxingatmosphere.

Finally,Isincerelythank myparents,HideoOkamoto,TomikoOkamoto,mybrothers,

TsuyoshiOkamoto,Satoshi Okamotoand my sister, MegumiOkamotofor theirsupport,

advice and encouragement.

1 Introduction 1

1.1 Preface : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1

1.2 ThesisOutline: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3

2 Public-Key Cryptosystems 4

2.1 Applications of Public-KeyCryptosystems : : : : : : : : : : : : : : : : : : 4

2.2 Requirementfor Public-Key Cryptography : : : : : : : : : : : : : : : : : : 5

2.3 Encryption Schemes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6

2.3.1 RSA Encryption Scheme : : : : : : : : : : : : : : : : : : : : : : : : 6

2.3.2 ElGamal Encryption Scheme: : : : : : : : : : : : : : : : : : : : : : 7

2.4 DigitalSignature Schemes : : : : : : : : : : : : : : : : : : : : : : : : : : : 8

2.4.1 RSA Signature Scheme : : : : : : : : : : : : : : : : : : : : : : : : : 8

2.4.2 ElGamal SignatureScheme : : : : : : : : : : : : : : : : : : : : : : 8

3 Key Establishment Protocols 10

3.1 GeneralAsp ects of KeyManagement : : : : : : : : : : : : : : : : : : : : : 10

3.2 KeyManagement Techniques : : : : : : : : : : : : : : : : : : : : : : : : : 10

3.2.1 Problemswith Symmetric KeyCryptography : : : : : : : : : : : : 10

3.2.2 Key Distribution Mo dels : : : : : : : : : : : : : : : : : : : : : : : : 11

3.3 Point-to-PointKey Management : : : : : : : : : : : : : : : : : : : : : : : : 11

3.3.1 Key Distribution for Symmetric Algorithms : : : : : : : : : : : : : 11

3.3.2 Die-HellmanKey Exchange Scheme and Its Attack : : : : : : : : 12

3.4 Centralized Key Management : : : : : : : : : : : : : : : : : : : : : : : : : 14

3.4.1 Key Agreement for Symmetric Algorithm: : : : : : : : : : : : : : : 14

3.4.2 Public-KeyCerticates : : : : : : : : : : : : : : : : : : : : : : : : : 15

3.5 Identity-Based Cryptosystem : : : : : : : : : : : : : : : : : : : : : : : : : 17

3.5.1 Basic Ideaand Analysis : : : : : : : : : : : : : : : : : : : : : : : : 17

3.5.2 Okamoto-Tanaka KeyExchange Scheme : : : : : : : : : : : : : : : 17

4 Computational Complexity Theory 20

4.1 Complexity Issuesin Cryptography : : : : : : : : : : : : : : : : : : : : : : 20

4.2 Turing Machine : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20

4.3 Complexity Classes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22

4.5 FunctionstoBreak Protocols : : : : : : : : : : : : : : : : : : : : : : : : : 25

4.6 Reducibility amongFunctions : : : : : : : : : : : : : : : : : : : : : : : : : 26

4.6.1 Diculty of BreakingKey Sharing : : : : : : : : : : : : : : : : : : 26

4.6.2 Diculty of Impersonation : : : : : : : : : : : : : : : : : : : : : : : 28

4.7 ConcludingRemarks on Reductions : : : : : : : : : : : : : : : : : : : : : : 28

5 Fault-Tolerant Key Distribution Systems 29

5.1 Concept and Analysis: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29

5.1.1 Basic Idea : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29

5.1.2 Levels of Trust : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30

5.2 Proposed Scheme : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30

5.2.1 Key SharingProtocol: : : : : : : : : : : : : : : : : : : : : : : : : : 30

5.2.2 Revo cationand Renewal Proto col : : : : : : : : : : : : : : : : : : : 32

5.2.3 New KeySharingProtocol : : : : : : : : : : : : : : : : : : : : : : : 33

5.3 Security Considerations: : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34

5.3.1 Functionsto Break Protocols : : : : : : : : : : : : : : : : : : : : : 34

5.3.2 Diculty of BreakingKey Sharing : : : : : : : : : : : : : : : : : : 34

5.3.3 Diculty of Impersonation : : : : : : : : : : : : : : : : : : : : : : : 35

5.4 ConceptualAnalysis of the Proposed Scheme : : : : : : : : : : : : : : : : : 37

5.5 Applications toOther Key Management Schemes : : : : : : : : : : : : : : 38

5.5.1 Group Communication UsingConferenceKey : : : : : : : : : : : : 38

5.5.2 Revo cationof Specic User UsingBroadcast Communication : : : : 39

6 Conclusion 40

Bibliography 41

List of Publications 43

Introduction

1.1 Preface

Cryptography isastrategyofinformationprotectionthatdatesbackfourthousandyears.

It is anancient art that is taken onnew signicance in to day's information so ciety.

Through the ages,cryptography hasprotected communications whilethey were being

transmittedthroughhostileenvironments-usuallyinvolvingwarordiplomacy. Especially,

cryptography in World War II owed its biggest bo omto the scientic mobilization. The

world's rst digital computers were built to crack co desatthat time.

In1949thepublicationbyC.E.Shannonofthepap er,\CommunicationTheoryofSe-

cret Systems",usheredintheera of scientic secretkeycryptography. Shannon provided

a theory of secrecy systems almost ascomprehensiveas the theory of communications.

In 1977DataEncryption Standard (DES)was publishedby NationalBureau ofStan-

dards. Thewhole idea ofa \standard"incryptography iscertainlyrevolutionary. Before

the publication of DES, there apparently were no publications containing a complete

algorithm for practical cryptographic usage.

The real breakthrough of the cryptography came with the publication in 1976 by

W.Die and M.E.Hellman of their work \New Directions in Cryptography" [1]. In this

paper,they proposedtheconceptofpublickeycryptographyandshowedthatsecretcom-

municationispossiblewithout anexchangeofsecretkeyinadvance,whileusual symmet-

ric cryptosystemwasrequired for such preparations. Their splendid idea was to usetwo

dierentkeys, apublickeyforencryption andaprivate key fordecryption. Basedonthis

asymmetry, they furtherprop osedtheconceptofdigitalsignatures. Here, theprivatekey

is used tosigna messageand the publickey isused to verify asignature. However, they

didnot providerealizationsofthenewconcepts, butthey prop osedaprotocolthatallows

Theconceptofpublickeycryptographyinspired manyresearchers,anditsoonbecame

a fast-growing and fascinatingresearchtheme. In the following years, although many re-

alization of public key encryption and digital signature schemes were proposed, most

notableonewasRSAscheme. This schemewasintro duced bythreeinventors R.L.Rivest,

A.Shamir and L.Adleman who published the paper \A method for obtaining digital sig-

natures and public key cryptosystems" [2] in 1978. This scheme was the rst practical

public-key encryption and digital signature schemes. Based on these primitives, more

complex systems such asdigital paymentschemes orvoting schemes were devised.

On the other hand, there are several problems in public key cryptosystems. That is,

eachusermust haveale whichcontains users'publickeys,andifone userwantstosend

a messageto another, procurementof users' public keys isvery costly.

Tosolvethese problems, in1984A.Shamir[3]formulated thegeneralidea of identity-

based cryptosystemwhichis anasymmetric system employingusers' identities insteadof

public keys, giving an example for ID-based signature system, and conceptual model for

anID-basedencryptionscheme. Inthiscase,IDmeansinformationwhichiswell-knownto

everyone. In ID-based systems, there are identity-based key distribution systems which

are called ID-KDS for short. These systems have some advantages because they can

be used not only for key distribution but also for authentication. In 1989, E.Okamoto

and K.Tanaka [8] prop osed a new ID-KDS which is based on the Die-Hellman key

exchange scheme for key sharing, and which includes RSA-based authentication against

impersonation.

Inthesedaysasaremarkablecharacteristicofmo derncryptography,cryptographyhas

been usedfornetworksecurity. Especially Internetwhichisasort ofnetworksystem, has

enabled us to communicate with each other on networks which reach around the world.

However, it has caused some problems such as wiretapping, forgery and impersonation,

whichhavebeengettingterriblyserious. Sincetheprogressofcryptosystemisnecessaryto

realizeasecurecommunication,itispreferablethatcommunicationsystemsgiveusersless

burdenand moresecureenvironment. Thesethingscanestablishpractical infrastructures

for network communications.

Tosolve these problems, we can adopt the technique of ID-KDS. Regardingthis sys-

tem, many useful schemes [8] - [12] are proposed up to now. These systems are ecient

schemes for implementation, but they have certain drawbacks at the stage in which the

center revokesand renewsauser'ssecret information. Thatis, whenthe center revokesa

must discard the user's ID and use the dierent one. To determine the ID information,

it is preferable that the center adopts one uniform ID such as a user's name, an e-mail

address,oraso cialsecurity number. In thesesystems, the userneed tomakeale which

contains several pieces of ID for one user. Therefore, these systems impose a burden on

users and lose the advantagesof ID-based systems.

The concept of our proposal is as follows: Even after the center has revoked a user's

secretinformation, the centergeneratesanew one withoutany change ofID.This means

that it keeps the one-to-one correspondence between users and ID's. Therefore, we must

generate several pieces of secret information for a piece of ID. In this paper, we realize

this concept by mo difying the Okamoto-Tanaka keyexchange scheme [8].

1.2 Thesis Outline

Our thesis is organized asfollows.

Chapter 2summarizesthe public-keycryptosystemand showsseveral famousencryp-

tion and signature schemes.

Chapter 3 examines several asp ects of the key management. One asp ect is the im-

portance of the keys employed by secure algorithms and metho ds. Another asp ect is

authorized key managementmethods.

Chapter 4 shows the overview of Turing machine at rst, and indicates mathemati-

cally precise denitions for complexity classes, reductions and functions to break several

protocols. This chapter also shows the ordering among diculty of functions and -

nally, indicates reductionsamong functions. Each theorem inthis chapter wasprovedby

M.Mambo and H.Shizuya[17].

Chapter 5 shows a new concept of identity-based cryptosystem and proposes a new

identity-basedkeydistributionsystem. Securityconsiderationsofourproposedschemeare

studied by using reductions among functions. The conceptual structure of our proposed

scheme is alsodiscussed.

Public-Key Cryptosystems

Public-key cryptography providesa radical departure from all that hasgone before. For

one thing, public-key algorithms are based on mathematical functions rather than on

substitution and permutation. But more important, public-key cryptography is asym-

metric, involving the use oftwo separatekeys, incontrast to thesymmetric conventional

encryption, whichuses onlyone key.

The ideabehinda\public-key"system isthat itmightbepossibletondacryptosys-

tem which it is computationally infeasible to determine the decryption rule D

K

even by

using the encryption rule E

K

. If so, then the E

K

could be made public by publishing

it in a directory (hence we call this \public-key" system). the advantage of a public-key

system isthat Alice(or anyone else) can send anencrypted messagetoBob(without the

prior communication of a secret key) by using the public encryption rule E

K

. Bob will

be the only person that can decrypt the ciphertext, using his secret decryption rule D

K .

2.1 Applications of Public-Key Cryptosystems

In broadterms, wecan classifythe useof public-keycryptosystemsintothreecategories:

1. Encryption/Decryption : The senderencrypts amessagewith the recipient's public

key.

2. Digital Signature : The sender \signs" a message with its private key. Signing is

achieved by a cryptographic algorithm applied to the message or to a small block

of data that is bound insome way tothe message.

3. Keyexchange: Twosidesco operatetoexchangeasessionkey. Severalquitedierent

approachesare p ossible,involving the private key(s) of one or both parties.

Some algorithms are suitable for all three applications, whereas others can only be used

for one ortwo of these applications.

We show algorithms which public-key cryptography must fulll:

1. It is computationally easy for Bob to generate a pair (PK

B

;SK

B

), where PK

B is

a publickey and SK

B

isa secret key.

2. Itiscomputationallyeasy forasenderAlicewhoknowthe publickeyPK

B

andthe

message M whichis encrypted by Aliceto generatethe corresp onding ciphertext

C =E

PK

B ( M):

3. It is computationally easy for the receiver Bob to decrypt the resulting ciphertext

C using the private key torecoverthe original message

M =D

SKB

(C)=D

SKB [E

PKB (M)] :

4. It is computationally infeasible for an opp onent who know the public key PK

B to

determinatethe secret key SK

B .

5. Itis computationallyinfeasiblefor anopponentwho knowthe publickeyPK

B and

a ciphertext C torecover the original messageM.

We can add asixth requirement that, although useful, is not necessaryfor all public-

key applications:

6. The encryption and decryption functionscan be appliedineither order

M =E

PK

B [D

SK

B (M)] :

There are formidable requirements, as evidenced by the fact that only one of such

algorithmhasreceivedwidespreadacceptanceinoveraquarter-century sincethe concept

of public-keycryptography was proposed.

Beforeelab orating onwhythe requirementsare soformidable,letusrstrecastthem.

The requirements boil down to the need for a trapdo or one-way function. \one-way

function" is one that maps a domain into a range such that every function value is easy

whereasthe calculationof the inverse is infeasible:

Y =f(X) easy:

X =f 01

(Y) infeasible:

Generally,\easy"isdenedtomean aproblem thatcan be solvedinpolynomialtime

asafunctionofinputsize. Thus,ifthe lengthofthe inputisnbits, then thetimecostto

compute the function is prop ortional to n a

, where a is a xed constant. Next, the term

\infeasible" isamuchfuzzierconcept. Ingeneral,wecansayaproblemisinfeasibleifthe

eorttosolveitgrowsfasterthanpolynomialtimeasafunctionofinputsize. Forexample,

to 2 n

,it is considered infeasible. Unfortunately,it is dicult todetermine if aparticular

algorithm exhibits this complexity. Furthermore, traditional notions of computational

complexity fo cus on the worst-case of average-case complexity of an algorithm. These

measures are worthless for cryptography, which requires that it be infeasible to invert a

function for virtually allinputs, not for the worst caseorevenaverage case.

We now turn to the denition of a \trapdoor one way function", which, likethe one-

wayfunction, is easytocalculate in one direction and infeasibleto calculate inthe other

directionunlesscertainadditionalinformationisknown. Withtheadditionalinformation,

the inverse can be calculated in polynomial time. We can summarize as follows: A

trapdo orone-way function isa family of invertiblefunctions f

K

, suchthat,

Y =f

K

(X) easy, if K and X are known.

X =f 01

K

(Y) easy, if K and Y are known.

X =f 01

K

(Y) infeasible,if Y is known but K is not known.

Thus,thedevelopmentofapracticalpublic-keyschemedependsondiscoveryofasuitable

trapdo orone-way function.

2.3 Encryption Schemes

We show two famous encryption schemes, such as the RSA and ElGamal encryption

schemes. Forpreparation, we assume:

1. Alicegenerates several keys.

2. Bob encryptsa message m and makes acipher text cfor Alice.

3. Alicedecrypts the cipher text cand get the messagem.

Let h bea collision-residenthash function such as

h:f0;1g 3

7!f0;1g t01

;

where t isthe security parameter.

2.3.1 RSA Encryption Scheme

Key generation

Alice picks two large primes p and q, and computes n, (n), where n = pq and

(n) = lcm(p01;q01). Alice selects e 2 Z 3

( n)

and computes d satises ed = 1

(mo d (n)). In this case, Alice's publickey is (n;e) and secret key is ( p;q;d).

Encryption

c=m e

(modn)

and sends c toAlice.

Decryption

Alicecomputes

m=c d

(mod n):

She can get the messagem since

c d

=(m e

) d

=m ed

=m (mod n):

2.3.2 ElGamal Encryption Scheme

Key generation

Alicepicks a large prime p and agenerator g of Z 3

p

. Aliceselects a randominteger

x2Z 3

p01

andcomputes y=g x

(mod p). In this case,Alice's publickey is(p;g;y)

and secret key isx.

Encryption

Bob picks arandom integer k2Z

p01

computes

c

1

=g k

(modp);

c

2

=m1y k

(modp);

and sends (c

1

;c

2

) toAlice.

Decryption

Alicecomputes

m= c

2

c x

1

(mod p):

She getsthe message m since

c

2

c x

1

= m1y

k

(g k

) x

= m1 (g

x

) k

g kx

=m (modp):

Weshowtwofamoussignatureschemes,suchastheRSAandElGamalSignatureschemes.

For preparation,we assume:

1. Alicegenerates several keys.

2. Alicesignsa message m and makes asignature s.

3. Bob veries the signature s.

Let h bea collision-residenthash function such as

h:f0;1g 3

7!f0;1g t01

;

where t isthe security parameter.

2.4.1 RSA Signature Scheme

Key generation

Alice picks two large primes p and q, and computes n, (n), where n = pq and

(n) = lcm(p01;q01). Alice selects e 2 Z 3

( n)

and computes d satises ed = 1

(mo d (n)). Alice publishes ( n;e) and keeps (p;q;d) secret. In this case, Alice's

signature key is (p;q;d) and certication key is (n;e).

Signature generation

Alicecomputes

s=h (m) d

(modn) ;

and sends (m;s) to Bob.

Signature verication

Bob conrmswhether the following vericationholds:

h (m)

?

=s e

(mod n):

If itis true, Bobaccepts the signature. Otherwise, Bob rejects it.

2.4.2 ElGamal Signature Scheme

Key generation

Alicepicks alarge primep, and agenerator g of Z 3

p

. Aliceselects arandominteger

x 2 Z 3

p01

and computes y = g x

(modp). In this case, Alice's signature key is

(p;g;y) and certication key isx.

Alicepicks an integer k2Z 3

p01

,computes

r =g k

(mod p);

s =k 01

( h(m)0xr) (mod p01);

and sends (m;r;s) to Bob.

Signature verication

Bob conrmswhether the following vericationholds:

g h (m)

?

=y r

r s

(mod n) :

If itis true, Bobaccepts the signature. Otherwise, Bob rejects it.

Key Establishment Protocols

3.1 General Aspects of Key Management

Since the security of many cryptographic algorithms and metho ds depends to a large

extent on the secrecy of the key, the key must be kept secret, no matter how ingenious

and safe the algorithm may be. Who ever has access to the key, can also access the

information, assume someone else's identity, etc. This applies not only to symmetrical

systems,whichrequireunconditionalsecrecyofallkeys,butalsotoasymmetricalsystems,

whichare based on both public and secret keys.

These problems are considered in \key management". In general,a key management

system must not only prevent intruders from obtaining a key, but in addition, it must

avoidunauthorizeduseofkeys,deliberatemodicationandotherformsofmanipulationof

keys,etc. It isdesirable tobeabletodetectanysituationinwhichthisoccurs. Naturally,

once the reliability of a keyis impaired, its usemust be terminatedimmediately.

3.2 Key Management Techniques

3.2.1 Problems with Symmetric Key Cryptography

We assume the system which n users involve symmetric-key techniques. If each pair of

usersmay potentially needtocommunicatesecurely,then eachpairmust share adistinct

secret key. In this case, each party must have n01 secret keys; the overall number of

keys in the system, which may need to be centrally backed up, is then n(n01)=2, or

approximately n 2

. As the size of a system increases,this number becomes unacceptably

large.

For systems based on symmetric-key techniques, the solution is to use centralized

key servers with a trusted third party at the center or hub of communications. These

methods diminish the n 2

key distribution problem, at the cost of the requirement of an

on-linetrustedserver, andadditionalcommunicationswithit. Public-keytechniquesgive

analternate solution.

Point-to-pointcommunicationsand\centralizedkeymanagement",areexamplesofsimple

keydistribution(communications)models. Asanexampleofthecentralizedkeymanage-

ment mo dels, we indicate \key distribution center" model. These models are described

below, whereK

XY

denotes a key shared by X and Y.

1. point-to-point mechanisms: These involvetwoparties communicatingdirectly.

2. key distribution centers (KDCs): KDCs are used to distribute keys between users

which share distinct keys with the KDC, but not with each other. A basic KDC

proto cols asfollows. Upon request fromAlice to share a key with Bob, the Center

generatesorotherwiseacquiresakeyK,thensendsitencryptedunderK

AC

toAlice,

alongwith acopy of K (forBob)encrypted under K

BC

. Alternatively, Center may

communicate K (secured under K

BC

)to Bob directly.

Note that centralized key management involving third parties (KDCs in this case)

oerstheadvantageofkey-storageeciency: eachpartyneedmaintainonlyonelong-term

secretkeywiththetrustedthirdparty(ratherthanoneforeachp otentialcommunications

partner). Potential disadvantage include: vulnerability toloss of overall system security

if the central node is compromised (providing an attractive target to adversaries); a

performance bottleneck if the central node becomes overloaded; loss of service if the

central node fails (a critical reliability point); and the requirement of an on-line trusted

server.

3.3 Point-to-Point Key Management

3.3.1 Key Distribution for Symmetric Algorithms

The use of a key distribution center imposes the requirement that the KDC be trusted

and be protected fromsubversion. This requirementcan be avoided if key distribution is

fully decentralized. Although full decentralization is not practical for larger networks, it

may be usefulwith in alo cal context.

A decentralizedapproach requires that eachend system be able tocommunicateina

securemannerwithallpotentialpartner endsystems forpurposesofsessionkeydistribu-

tion. Therefore,there need tobeas many as n(n01)=2 master keys for a conguration

with nend systems.

A session key may b e established with the following sequence of steps;

1. Alice issues a request to be for a session key. The message includes the identity

of Alice and Bob and a unique identier N

1

for this transaction, which we refer to

as a \nonce". The nonce may be a timestamp, a counter, or a random number;

the minimum requirement is that it dier with each request. Also, to prevent

masquerade, itis desirable for ittobedicult for anopp onentto guess the nonce.

Thus,a randomnumberis ago o d choice fora nonce.

resp onse includes the session key selected by Bob, an identier of Bob, the value

f(N

1

), and anothernonce, N

2 .

3. Usingthe new sessionkey,Alice returnsf( N

2

) toBob.

Although each mode must maintain at most (n01)master keys, as many session

keys as required may be generated and used. Since the message transferred using

the masterkeyare short,cryptanalysisisdierent. As before,sessionkeysare used

for onlya limited time to protectthem.

$OLFH

,QLWLDWRU

5HVSRQGHU %RE

>__5HTXHVW____I__@ 1

. 6

( . ₆ ,' _%

1

5HTXHVW__ 1

>I@ 1 . 6

(

Figure 3.1: Point-to-p oint key management.

3.3.2 Die-Hellman Key Exchange Scheme and Its Attack

Die-Hellmankey exchangescheme provide the rst practical solution tothe keydistri-

butionproblemallowingtwoparties,neverhavingmetinadvanceorsharedkeymaterial,

to establish a shared secret key by exchanging messages over an open channel. Though

this schemehave several kinds of mo dels, we showthe basic one.

Proto col

Preparation phase

An appropriate a large prime p, and a generator g of Z 3

p

are select and published. Here,

(p;g)servesas the users' publickey.

Common key generation phase

Aliceselects a randominteger a 2Z 3

p01

,computes

y

A

=g a

(modp);

and sends y

A

toBob. Similarly, Bob selects arandom integer b2Z

p01

, computes

y

B

=g b

(modp);

and sends y

A

toAlice. Next, Alice computes

K

A

=y a

B

(mo d p) :

Similarly Bob computes

K

B

=y b

A

(mo d p) :

K

A

and K

B

serve as acommonkey since

K

A

=y b

A

=(g a

) b

=g ab

=K

B

(mod p)

Attack Strategy

Unfortunately, the basic type of the Die-Hellman scheme is vulnerable to an active

adversary who uses an \intruder-in-the-middle" attack. We show the example by using

this attack.

Weassume Aliceand Bob haveprivate keys a and b,respectively and Carol createsa 0

andb 0

. CarolinterceptsAlice'sexponentialandreplacesitbyg a

0

. Similarly,sheintercepts

Bob's exponential and replaces it by g b

0

. Alice forms session key K

A

= g ab

0

, while Bob

forms session key K

B

=g a

0

b

. Carol is able toboth these keys. When Alicesubsequently

sends a messageto Bob encrypted under K

A

, Carol deciphers it, re-enciphers under K

B ,

andforwardsittoB. SimilarlyCaroldeciphersmessageencrypted byBobforAliceunder

K

B

and re-enciphers themunder K

A

. Aliceand Bobbelieve they communicatesecurely,

while Carol reads alltrac.

$OLFH &DURO %RE

J D J ^D J E E

J

Figure 3.2: Intruder-in-the-middle attack.

To prevent this attack, it is essential for Alice and Bob to make sure that they are

exchanging messages with each other and not with Carol. Before exchangingkeys, Alice

andBobmightcarryoutaseparateproto coltoestablisheachother'sidentity,forexample

middleattackifCarolsimply remainsinactiveuntil afterAliceandBobhaveprovedtheir

identitiestoeachother. Hence, the key agreement protocolshoulditselfauthenticatethe

participants' identities at the same time as the key is b eing established. Such aprotocol

will be called \authenticated key agreement".

3.4 Centralized Key Management

3.4.1 Key Agreement for Symmetric Algorithm

We show a typical symmetric model illustrated in Figure 3.3. This model assumes that

eachuser shares aunique master key withthe key distributioncenter(KDC).

Let us assume that user Alicewishes to establish a logical connection with Bob and

require aone-time sessionkeytoprotect the datatransmittedover connection. Alicehas

asecret key K

A

known onlyfor itselfand the KDC;similarly, Bob sharesthe masterkey

K

B

with the KDC. Thefollowing steps o ccur:

1. Alice issues a request to the KDC for a session key to protecta logical connection

toBob. The messageincludes the identity both Aliceand Bob, and a nonceN

1

2. The KDC responds with a messageencrypted by using K

A

. Therefore,Aliceis the

onlyonewhocansuccessfullyreceivethemessage,andAliceknowsthatitoriginated

atthe KDC.The message includestwoitems instead for Alice:

{ The one-time session key K

s

which is used for the session;

{ The original request message, including the nonce, to enable Alice to match

this response with the appropriate request.

Therefore,Alicecanverifythat itsoriginalrequestwas notalteredbeforereception

be the KDC, and because of the nonce, that this is not a replay of some previous

request. In addition, the message includestwo items intended for Bob:

{ The one-time session key K

s

which is used for the session;

{ Anidentier of Alice:ID

A .

These lasttwoitems are encrypted with the masterkey that the KDCshares with

Bob. They are to be sent to Bob to establish the connection and prove Alice's

identity.

3. Alicestores thesessionkeyforuseinthe upcomingsessionand forwardstoBobthe

information that originated at the KDC for Bob, namely, E

K

B [ K

s jj ID

A

]. Because

thisinformationisencryptedwithK

B

,itisprotectedfromeavesdropping. Bobnow

knows the session key (K

s

), knows that the other party is Alice (from ID

A ), and

that the information originated at the KDC(becauseit is encrypted using E

K

B ).

$OLFH

,QLWLDWRU

%RE

5HVSRQGHU

.H\'LVWULEXWLRQ

&HQWHU.'&

5HTXHVW__ 1

>__5HTXHVW____í@ ( . _$ . ₆ 1

. %

( . ₆ ,' _$

,' $

>__@ ( ^. _% . ₆

>@ 1 . 6

(

>I@ 1 . 6

(

.H\GLVWULEXWLRQVWHSV

$XWKHQWLFDWLRQVWHSV

Figure 3.3: Authenticated key distribution system.

At this point, a session key has been securely delivered to Alice and Bob, and they may

begin their protected exchange. However, two additional steps are desirable:

4. Usingthe newlymintedsessionkey forencryption, Bobsendsanonce,N

2

,toAlice.

5. AlsousingK

s

,Alicerespondswithf( N

2

),whereitisafunctionthatperformssome

transformation onN

2 .

These steps assure Bob that the originalmessage itreceived (step 3)hasnot areplay.

Note that actual key distribution involves only step 1 through 3but that step 4 and

5,as well as3, perform anauthenticationfunction.

3.4.2 Public-Key Certicates

Public-key certicates are a vehicle by which public keys may be stored, distributed or

forwarded overunsecured media without danger of undetectable manipulation. The ob-

jectiveistomakeone entity'spublickeyavailabletootherssuchthatitsauthenticity(i.e.,

its statusas the true public key of that entity) and validity are veriable.

The \Certication Authority"(CA) is a trusted third party whose signature on the

certicatevouchesforthe publickeyboundtothe subjectentity. Thesignicance ofthis

binding(e.g.,what the key maybe usedfor)must be providedby additionalmeans, such

as an attribute certicate or p olicy statement. Within the certicate, the string which

identies the subject entity must be a unique name within the system (distinguished

name), which the CA typically associates with a real-world entity. The CA requires its

own signature keypair, the authentic publickeyof whichismade availabletoeachparty

upon registering as an authorized system user. This CA public key allows any system

user, though certicate acquisition and verication, to transitively acquire trust in the

authenticity of the public key inany certicate signed by that CA.

Before creating a public-key certicate for Alice, the certication authority should take

appropriatemeasures(relativetothesecuritylevelrequired), typically non-cryptographic

innature,toverifytheclaimedidentityofAliceandthefactthatpublickeytobecertied

is actually that of Alice. Twocasesmay bedistinguished:

1. trusted party creates key pair . The trusted party creates a public-key pair, assign

it to a specic entity, and includes the public key and the identity of that entity

in the certicate. The entity obtains a copy of the corresponding private key over

a secure (authenticate and private) channelafter providing its identity. All parties

subsequentlyusing thiscerticateessentiallydelegatetrusttothisprior verication

of identity by the trusted party.

2. entitycreatesown keypair . The entitycreatesitsown public-keypair, andsecurely

transfersthepublickeytothetrustedpartyinamannerwhichpreservesauthentic-

ity(e.g., over atrustedchannel,orinperson). Uponvericationof the authenticity

(source) of the public key, the trusted party creates the public-key certicate as

ab ove.

Use and Verication of public-key certicates

The overall process whereby Bob uses a public-key certicate to obtain the authentic

public key ofAlice may be summarizedas follows:

1. (One time) acquirethe authentic public-key of the certication authority.

2. Obtainan identifyingstring whichuniquely identies the intendedparty Alice.

3. Acquire over some unsecured channel (e.g. from a central public database of cer-

ticates, or from Alice directly), a public-key certicate corresp onding to subject

entity Alice and agreeingwith the previous identifyingstring.

4. (a) Verify the current date and time against the validity perio d (id any) in the

certicate,relying onalo cal trustedtime/day-clo ck;

(b) Verify the currentvalidity of the CA'spublic key itself;

(c) Verify the signature onAlice's certicate, using the CA's publickey;

(d) Verify that the certicate has not been revoked.

5. Ifallcheckssucceed,acceptthe publickeyinthecerticateasAlice's authentickey.

3.5.1 Basic Idea and Analysis

Anidentity-basedcryptographicsystem,whichwasproposedbyA.Shamir[3], isanasym-

metric system wherein an entity's public identication information (unique name) plays

the role of itspublickey. This system is used asinput by atrusted center T to compute

the entity's corresp onding private key.

In usualpublic-keycryptosystems, everyuserhasakey-pair (s;P),wheres isasecret

key,onlyknowntothisuserandP isapublickeywhichanybo dymayknow. Bydenition,

public keys need not beprotected for condentiality; on the contrary,they haveto be as

madeaspublicaspossible. Butthis\publicity"becomesdrawbacktowardactiveattacks,

such as the substitution of a \false"public key to a\true" one ina directory. Therefore

besideskey-pair(s;P),wemust includehisidenticationstringIand \guarantee"Gthat

P isreally the publickey of user I, and not the one of animposerI.

WhenweadopttheIdentity-basedsystems,thepublickeyisequivalenttotheidentity.

i.e. P =I. Andguarantee isequivalentto the secretkey itself. i.e. G=s. Since there is

nocerticate to store and tocheck, this system hasgo o d properties.

After computing the entity's private key, T transfers the entity's private key to the

entity over a secure (authentic and private) cannel. This private key is computed from

not onlythe entity's identity information, butmust alsobea functionof some privileged

information known only toT ( T's private key). This is necessary topreventforgery and

impersonation-itisessentialthatonlyT beabletocreatevalidprivatekeyscorresponding

to give identication information. Corresp onding (authentic) publicly available system

data must beincorporatedinthe cryptographictransformations of the ID-basedsystem,

analogousto the certicationauthority public key incerticate-based systems.

3.5.2 Okamoto-Tanaka Key Exchange Scheme

ThissectionsummarizestheID-KDSwhichwasproposedbyE.OkamotoandK.Tanaka[8].

This scheme consists of the following three phases.

Preparation phase

A trustedcenter picks two primesp and q, and makesn, g and e public,wheren=pq ,g

isageneratorofboth Z 3

p

and Z 3

q

,ande2Z 3

(n)

. TheCarmichaelfunctionof nisgivenby

(n) =lcm(p01;q01). Let d2 Z 3

(n)

be the secret key of the center satisfying ed =1

(mod(n)).

&HQWHU

8VHU

$OLFH

8VHU

%RE

U $

$

$ V J

[ = ⋅ [ _% = V _% ⋅ J ^{U %}

U $

% H

%

$% ,' [

:. = ⋅ :. _%$ = ,' _$ ⋅ [ _$ ^{H U %}

$ G

$ ,'

V = ⁻ V _% = ,' _% ^{− G}

Figure 3.4: Okamoto-Tanaka key exchange scheme.

User's participation phase

Let ID

i

be the user i's (i=A;B;C ;...) identity information. Let s

i

be the secretkey of

the user i satisfying

s

i

=ID 0d

i

(modn) :

The center then publishes ( e;n;g;ID

i

) and delivers s

i

to each user i through a secure

channel orby using anIC card.

Common key generation phase

We assume here that two users Alice and Bob want to share acommon-key. First, Alice

generatesa randomnumberr

A

, computes

x

A

=s

A 1g

r

A

(modn);

and sends it toBob. Similarly, Bob generatesarandom number r

B

,computes

x

B

=s

B 1g

r

B

(mod n) ;

and sends it toAlice. Next, Alice computes

WK

AB

=(ID

B 1x

e

B )

r

A

(mod n):

Similarly, Bob computes

WK

BA

=( ID

A 1x

e

A )

r

B

(modn) :

AB BA

WK

AB

=(ID

B 1x

e

B )

r

A

=(ID

B 1( s

B 1g

r

B

) e

) r

A

=(ID

B 1( ID

0d

B )

e

1g r

B e

) r

A

=g er

A r

B

=WK

BA

(modn) :

Computational Complexity Theory

4.1 Complexity Issues in Cryptography

One very important observation is that a public-key cryptosystem can never provide

unconditionalsecurity. Consequently,itisimportanttostudy thecomputational security

of public-keysystems.

Certainlyaminimalexpectationofapublic-keycryptoystemisthatthissystemcannot

be cracked inpolynomial time. Ifthis condition is satised,then every polynomialtime-

boundedalgorithmthereexitsinnitelymanymessageswhosecodesthealgorithm,cannot

crack. This leaves op en possibility that there existssome algorithm, and innitely many

messages whose codes this algorithm can crack in polynomial time. For a public-key

cryptoystemtobesecure,itmustbethecasethatciphertextscannotbecrackedformost

messages.

4.2 Turing Machine

We show a simple, yet powerful computing device called \Turing machine", which was

invited by A.Turing. A Turing machine consists of two major components, a tape and a

control unit. The \Tape"isa sequenceofcells that extendstoinnityinbothdirections.

Eachcellcontainsasymbolfromanitealphab et. Thereisatap eheadthatreadsfroma

cell and writesintothe same cell. The\control unit"contains anite setof instructions,

and it executes these instructions as follows: Each instruction causes the tape head to

read the symb ol fromacell, towritea symbolintothe same cell, and either tomovethe

tapehead toanadjacent cell orto leave it atthe same cell.

Eachinstructionof aTuringmachinecan berepresented asa5-tupleconsistingofthe

following veparts:

1. The Turing machine state.

2. A tapesymbol readfrom the currenttape cell.

&RQWURO

XQLW ([HFXWHVDILQLWHVHWRILQVWUXFWLRQV 7DSHKHDG

7DSH

Figure 4.1: Overview of Turing machine.

3. A tapesymbol towrite intothe current tapecell.

4. A direction for the tape head tomove.

5. The next machine state.

We'll agree to let the letters L, S and R mean \move left one cell,", \stay at the

current cell" and \move right one cell," respectively. For example, supp ose we have the

following instruction:

<i;a;b;L;j >:

The instruction is interpreted asfollows:

Ifthe currentstate of the machine is i,and if the symbolinthe currenttapecell is

a, then write binto current tapecell, move leftone cell, and goto state j.

The tape is used much like the memory ina mo dern computer,to store the input, to

store data neededduring execution, weneed to make afew more assumptions:

1. An input string is represented on the tape by placing the letters of the string in

contiguoustape cells. All other cells of the tapecontain the blank symbol.

2. The tape head is positionedat the leftmost cell of the input string unless specied

otherwise.

3. Thereis one \start state".

4. Thereis one \halt state".

The execution of a Turing machine stops when it enters the Halt state or when it

enters a tate for which there is no valid move. For example, if a Turing machine enters

statej andreadsainthe currentcell,but thereisnoinstructionof theform<i;a;...>,

then the machine in statei.

the Haltstate. Otherwise, the inputstring is\rejected". Thereare twoways toreject an

inputstring: Eitherthe machine stopsby enteringa stateother thanthe Haltstate from

whichthereisnomove,orthemachine runsforever. The Turing machineisthe setof all

input strings accepted by the machine.

It's easy to see that Turing machines can solve all the problem that \Pushdown au-

tomatons" which mean a nite automaton with a stack, can solve because a stack can

be maintained onsome portion ofthe tape. In fact, a Turing machine can maintain any

number of stacks onthe tape by allo cating some space onthe tape for eachstack.

4.3 Complexity Classes

We rst dene the followingdenition.

Denition 4.3.1 [Polynomial-TimeAlgorithm] Analgorithmwhoseworst-caserun-

ning time function is of the form O(n k

), wheren is the input sizeand k is a constant, is

called anpolynomial-time algorithm .

Roughly speaking, polynomial-time algorithms can be equipped with \good" or \ef-

cient" algorithms. When considering polynomial-time complexity, the degree of the

polynomial is signicant. For example, even though an algorithm with a running time

of O ( n lnlnn

), n b eing the input size, is asymptotically slower that an algorithm with a

running time ofO(n 100

), the former algorithmmay be fasterinpractice forsmaller value

of n, especially if the contains hidden by the big-O notion are smaller. Furthermore, in

cryptography, average-case complexity is more important than worst-case complexity {

a necessary condition for an encryption scheme to be considered secure is that the cor-

responding cryptanalysis problem is dicult on average (or better yet, always dicult),

and not just for some isolatedcases.

With resp ect tothe complexity class, we showthe followingdenition:

Denition 4.3.2 [Complexity Class P] The set of all decision problems that are

solvable inpolynomialtime is called the complexity class P.

The computational tasks that need to get solved in practice are not all of the kind

that take a \yes" or \no" answer. For example, we say need to nd a satisfying truth

assignmentof a Bo olean expression,not justto tell whether the expressionis satisable;

in the traveling salesman problem we want the optimal tour, not just whether a tour

withinagivenbudgetexists;and soon. Wecall suchproblems requiringananswermore

elab oratethan \yes"or \no", \functionproblems". Wecan showthe following denition

whichis asso ciatedwith this problems.

Denition 4.3.3 [Complexity Class FP] The class of all function problems in P is

called the complexity class FP.

Weshowthemethodsofreductionsamongfunctionsatrst. Thesereductionsaredened

in the same way as the reductions among languagesoversome nite alphab et.

We dene the function Q

1

to solve the program P

1

, and the function q

2

to solve the

programP

2

,respectively. If one adopt P

1

as asubroutine, and can construct polynomial

time computable programP

2

, then we say \Q

2

reduces to Q

1

".

We showthe instruction in graphical asfollows:

RXWSXW

LQSXW 370

3 3

Figure 4.2: Querying anoracle.

In Figure 4.2, PTM means \Polynomial-time Turing Machine". With respect to re-

ductions, there exist some classications. At rst, we dene \polynomial-time many-one

reducibility" asfollows:

Denition 4.4.1 [Polynomial-Time Many-One Reducibility] ForfunctionsF and

G,ifthereexistsapairofpolynomial-timecomputablefunction(h

1

;h

2

)suchthatF( x)=

h

1 (G( h

2

( x))), thenwe say\F reduces to G with respectto the polynomial-time many-one

reducibility", and write as F FP

m

G. If the converse reduction also holds, we say \F is

equivalent to G with respect to the polynomial-time many-one reducibility", and write as

F FP

m G.

In short, Denition 4.4.1 means that PTM is allowedto ask (only) one question toa

oracle G, and on input the answer (G (h

2

(x)) which the oracle G generate, outputs the

value h

1 (G( h

2

( x))) byusingthe functionh

2

. Forsimplicity,weshowthegureasfollows:

Proposition 4.4.2 Binary relationF FP

m

G is reexive and transitive. That is:

(1) F FP

m F.

(2) If F FP

m

Gand G FP

m

H, then F FP

m H.

Proof.

(1) It isobvious.

(2) Because of F

m

G and G

m

H, there exists two p olynomial-time computable

function f and g, and

x2F ,f(x) 2G,and x2G,g(x) 2H

Therefore,x2A,g(f( x))2C. This meansF FP

m H.

Since Relation F FP

m

G isreexive,symmetric and transitive, this relation is equiv-

alence.

Inthecaseofmany-onereducibility,thisreductionrestrictsthequestiontowardoracle

for onlyone time.

RXWSXW 370

RUDFOH

*

( ) ( ^{K [} )

*

( ) ^[

K

( )

( )

( ^{* K [} )

K

LQSXW [

Figure 4.3: Many-onereducibility.

Next, we showthe following two denition whichwas diminished this restriction.

Denition 4.4.3 [Polynomial-TimeTuringReducibility] ForfunctionsF andG ,if

onecanconstructapolynomial-timeoracleTuringmachinewithaccesstovalueofg,which

computesf,wesay\F reduces toGwithrespecttothepolynomial-timeTuringreducibility

", and write as F FP

T

G. Regarding the complexity of such an algorithm, we suppose

thatthecostofonecallingtheoracleisjustonestep. Iftheconversereductionalsoholds,

wesay \F is equivalentto Gwith respectto thepolynomial-time Turing reducibility",and

write asF FP

T G.

Denition 4.4.4 [Expected Polynomial-TimeTuringReducibility] Forfunctions

F and G, if anexpected polynomial-timeoracle Turingmachine with access to values of

g, can compute f, we say \ F reduces to G with respect to the expected polynomial-time

Turing reducibility",and writeasF EFP

T

G. Herewe say thata machineM isexpected

polynomial-time if there exists an e > 0 such that, for all x 2 f0;1g, the expectation,

taken overthe innite bit sequences r,of (t

M ( x;r))

e

is boundedab ove by j xj, i:e:,

E(( t

M (x;r))

e

)j xj:

As seen in the denitions, if F FP

m

G or F FP

T

G holds, and if the polynomial-

time algorithm for computing Gis discovered, then so is that for computing F. Fortwo

functions F and G,F FP

m

G implies F FP

T

G,and that F FP

T

G implies F EFP

T G.

We rst dene functions relatedwith the several problems.

Denition 4.5.1 [Discrete Logarithm Problem] DLP (n;g;y) is a function that on

input n2N

>1

, g 2Z 3

n

, y2Z 3

n

,outputs w suchthat y=g w

(modn) and 0w <n, if

such anw exists.

Denition 4.5.2 [Factoring Problem] Factoring ( n)is afunction that oninput n2

N

>1

, outputsa such that 1<a <n and a jn,if such ana exists.

Now it is not known whether complexity class FP contains the discrete logarithm

problem or not. the same statementalso holds forthe factoringproblem.

Notethatthe oraclehasnoresp onsibilitieswhenthe inputisinappropriate. However,

we will assumethat oncorrect inputsthe oraclewill return ananswerwithin somepoly-

nomial time bound. For example, suppose B is an oracle for the function DLP. When

n=pq is not the product of twoprime, org is not a generator of Z 3

n :

1. A mayreturn asyntacticallyincorrect answer; inwhichcasewe knowthat eitherp

org is a inappropriate.

2. A may failto give ananswerwithin agivenpolynomialtime bound, and again we

conclude that either norg is inappropriate. (Here we assumethat the time bound

can be computed inpolynomialtime.)

3. Amay returnasyntacticallycorrectanswer. Theanswercan becheckedtoseeif it

satises the appropriateequivalence, but we cannotconclude that n isthe product

of two primes pand q org is agenerator.

Next,wedenefunctionstobreaktheseveral proto colswhichareallbasedondiscrete

logarithm problem. We assume that the base g is in Z 3

n

. This assumption includes the

caseof g being a primitive ro ot mo dulo both p and q.

Denition 4.5.3 [Die-Hellman Key ExchangeScheme] DH(n;g;y

A

;y

B

)isafunc-

tionthat oninputn2N

>1

,g 2Z 3

n ,y

A 2Z

3

n ,y

B 2Z

3

n

, outputsK 2Z 3

n

suchthatK =g ab

(modn), wherey

A

=g a

(mod n) and y

B

=g b

(mod n), if sucha K exists.

Denition 4.5.4 [Okamoto-Tanaka Key Exchange Scheme] OT(n;e;g;ID

A

;ID

B

;

x

A

; x

B

) is a function that on input n 2 N

>1

, e 2 Z 3

(n)

, g 2 Z 3

n

;ID

A 2 Z

3

n , ID

B 2 Z

3

n ,

x

A 2Z

3

n ,x

B 2Z

3

n

,outputsWK2Z 3

n

suchthatWK =(ID

B 1x

e

B )

r

A

=(ID

A 1x

e

A )

r

B

=g er

A r

B

(modn), where x

A

= g r

A

1(ID

A )

0e 01

(mod n), x

B

= g r

B

1( ID

B )

0e 01

(mod n) and

ee 01

=e 01

e=1 (mod ( n)), if such aWK exists.

Other functions based onseveral problems are dened asfollows:

on inputn2N

>1

, e2Z 3

( n)

, y2Z 3

n

, outputs x2Z 3

n

such that y=x e

(modn), if such

anx exists.

Denition 4.5.6 [ElGamal Public-Key Cryptosystem] EG (n;g;y;C

1

;C

2

)isafunc-

tion that on input n 2 N

>1

, g 2 Z 3

n

, y 2 Z 3

n , C

1 2 Z

3

n , C

2 2 Z

3

n

, outputs m 2 Z 3

n such

that m=C

2

=C x

1

(mo d n), wherey =g x

(modn), if suchan m exists.

4.6 Reducibility among Functions

4.6.1 Diculty of Breaking Key Sharing

WithrespecttothekeysharingoftheOkamoto-Tanakascheme,weindicatethefollowing

theorem.

Theorem 4.6.1 OT FP

m DH .

Proof.

1. OT FP

m DH:

OT (n;e;g;ID

A

;ID

B

;x

A

;x

B

)=DH(n;e;g e

;ID

A x

e

A

;ID

B x

e

B ):

2. DH FP

m OT:

DH(n;g;y

A

;y

B

)=OT(n;1;g;1;1;y

A

;y

B ):

In Theorem 4.6.1, note that as follows:

1. This reduction holds whenever g is in Z 3

n

. Therefore, there is no need for us to

assume that g is a primitive ro ot modulo both p and q. Note that the order of a

subgroupgeneratedbyacommonprimitiverootislcm( p01;q01)'(n)=2, where

'is the Euler totientfunction.

2. In the proof of DH FP

m

OT, we put e =12Z 3

'(n)

and ID

A

=ID

B

=12 Z 3

n

. If ID

A

and ID

B

must bedierentfromeachother, one may pick any twodistinctID

A and

ID

B

from Z 3

n

, and generate a query to be (n;1;g;ID

A

;ID

B

;y

A

=ID

A

;y

B

=ID

B ) so

that OT returns WK=g ab

(mod n). Moreover, if for e such that e=1 or e2= Z 3

n ,

OT returns ?, then the reduction algorithm b ecomes something else. The following

is aprobabilistic polynomial-time algorithmthat reducesDH to OT.

One may pick any o dd e from Z 3

n

nf1g, choose s

A

and s

B

from Z 3

n

, and generate

a query to be (n;e;g;s e

A y

A

;s e

B

;s 01

A g;s

01

B y

B

). If e is in fact in Z 3

'( n)

nf 1g, then OT

returnsacorrectWK=g ab +eb

. Thisisbecauses e

A A(s

A g)

e

=y

A g

e

=y

A g

e

=g a+e

=

g ee

01

(a+e)

,s e

B ( s

01

B y

B )=y

e

B

=g eb

, and soWK=g ee

01

(a+e) b

=g ( ab+eb)

. Therefore,

DH (n;g;y

A

;y

B

)=OT (n;e;g;s e

A y

A

;s e

B

;s 01

A g;s

01

A y

B )=y

e

B

(modn);

if e is inZ 3

'( n)

nf1g. On the other hand, if e=1 ornot in Z 3

'( n)

, OT returns?.

The probability that e picked insuch a way is inZ 3

'(n)

is estimated as

=

'('(n))

'(n)0 n01

2 01

2'('(n))

'( n)

2ln(2)'( n)

'(n)l n(2'(n))

2ln(2)

ln(2n)

;

where we used an inequality that '(n) ln(2)1n=ln(2) for a positive integer n.

Thus if e is picked repeatedly for ln(2n)=(2)ln(2)times, one may expect that there

isatleastone correctanswerotherthan?amongthevaluesreturned fromOT. The

expected numberof repetitionis b ounded ab ove by apolynomialin j nj. Therefore

the reduction algorithm runs in expected polynomial time.

Specically, if the mo dulus n is chosen such that n= pq, p= 2p 0

+1, q = 2q 0

+1

with p,q, p 0

,q 0

prime, then

2'('( n))

'(n)

=10 1

p 0

0 1

p 0

q 0

:

Thismeansthat thereductionalgorithmworksinadeterministic matterwithover-

whelming probability.

Next weshow that EG is equivalent toDH asfollows:

Theorem 4.6.2 EG p

m DH.

Proof.

1. DH FP

m EG:

DH (n;g;y

A

;y

B

)=EG (n;g;y 01

A

;B;1);

wherey 01

A

isthe inverse of y

A

(mod n). Notethat

EG (n;g;y 01

A

;y

B

;1)=EG( n;g;g 0a

;g b

;g ab 0ba

):

2. EG FP

m DH:

EG( n;g;y;C

1

;C

2 )=C

2

=DH (n;g;y;C

1

) (mod n) :

Besidesthis reductions,itis known atpresentthat DH FP

m

DLP , RSA FP

m

Factoring,

and Factoring EFP

m

DLP in[22] and [23].

We showthe security with resp ect tothe impersonationof the Okamoto-Tanakascheme.

ThisschemeusetheRSAschemeforidenticationchecking. Therefore,itisnaturalforus

toexpectthatthesecuritywoulddependontheRSA.However, Theorem4.6.1showsthat

breaking the function OT is equivalent to breaking the function DH. This means nothing

ab out relationship between OT and RSA .

In fact if RSA were apolynomial-timecomputable function, anyone could break iden-

tication, that is, one could compute s

A

= ID 0e

01

A

(mo d n) by RSA (n;e;1=ID

A ), and

impersonate Alice or Bob. Therefore, computing s

A or s

B

from ( n;e;ID

A

;ID

B

) reduces

to computing RSA with respect to polynomial-time many-one reducibility. This indicate

the security againstimpersonation dependson thediculty of computing RSA. However,

we indicate that even RSA reduces to DH. This implies that impersonation is easier than

breaking.

Theorem 4.6.3 RSA FP

m DH .

Proof.

RSA (n;e;y)=DH (n;y e

;y;y):

Notethat

DH( n;y e

;y;y) = DH(n;y e

;y ed

;y ed

) =y ed

2

=y d

=x (mod n);

whereed =de=1 (mod'(n)) :

4.7 Concluding Remarks on Reductions

As aconsequence, wecan summarize the reductions relatedwith DLP asfollows:

1. RSA FP

m

OT FP

m

DH FP

m

EG FP

m DLP .

2. RSA FP

m

Factoring FP

T DLP.

ItisnotknownatpresenttoholdthatDHreducestoRSA ,DLPreducestoDH ,orFactoring

reduces to DH, with respect to some p olynomial-time reducibility. These remain as op en

questions.

Fault-Tolerant Key Distribution

Systems

5.1 Concept and Analysis

5.1.1 Basic Idea

In ID-KDS, many useful schemes [8] - [12] are proposed up to now. These schemes are

ecient for implementation, but they have certain drawbacks at the stage in which the

centerrevokeandrenewauserssecretinformation. Thatis,whenuser'ssecretinformation

ismadepublicforsomereason,the usermustaskforthecentertorevokeitandget anew

one. When we implement ID-KDS on networks, it is preferable that the center adopts

one uniform ID such as a user's name, an e-mail address, a so cial security number, and

soon, andneverchangethat IDforany reason. Butunfortunately, theseschemes cannot

satisfy abovecondition. Tosolvethese problems, we show the following denition.

Denition 5.1.1 [Fault-Tolerant Key Distribution System] A system which sat-

isfy the following conditions 1-3is calledFault-Tolerant Key Distribution System.

1. This system is a centralized key management system which exists a certication

authority (CA).

2. This system can generate plural signatures for a message and each signature is

dierent from anotherone.

3. Iftwoor moreusers whichtakepart inthis system want toshare the commonkey,

eachuser can usethe signature as authentication.

By using this system, even after a center revoke the user's secret information, the

center can generatea newone without any changeof ID.This meansthere isnoneedfor

the user to make a le which contains several pieces of ID for one user. Therefore, this

system can diminish the burden of the user inthis sense.

In1991, M.Giraut[20]classiedthelevelsoftrustfor centralizedkeymanagement. With

respect to the fault-tolerant key distribution system, we can reconstruct this level as

follows:

1. Theauthorityknows(orcaneasilycompute)user'sallsecretinformation. Therefore,

the authority can impersonateany user atany time without detected.

2. The authority does not know(or cannot easily compute) user's secret information.

Nevertheless, the authoritycan still impersonatea user by generatingfalse guaran-

tees.

3. Even after the authority generates the false guarantees, the impersonation of the

authority can be detective.

Ideally, the level 3 is the most desirable one. However in this case, we need another

authority which guarantee a user's secret information. Therefore, when it comes to im-

plement the centralizedkey management system, we must considerthis problem.

5.2 Proposed Scheme

This section shows our proposed scheme. There are three kinds of protocols, and each

protocolhasone or several phase(s) inthis scheme.

5.2.1 Key Sharing Proto col

In this section, we discuss the key sharing protocol by which two users can agree on a

commonkey. This proto col consists of the following three phases.

Preparation phase

A trustedcenter picks two primesp and q, and makesn, g and e public,wheren=pq ,g

isageneratorofboth Z 3

p

and Z 3

q

,ande2Z 3

(n)

. TheCarmichaelfunctionof nisgivenby

(n) =lcm(p01;q01). Let d2 Z 3

(n)

be the secret key of the center satisfying ed =1

(mod(n)).

User's participation phase

Let ID

i

be the user i's (i = A;B;C ;...) identity information. Let f be a one-way hash

function which maps from ID

i

to the following m-dimensional vector(ID-vector) v

i ,as

v

i

=f(ID

i )=(v

i0

;v

i1

;v

i2

;...;v

i(m01) );

where v

ij 6=v

ij

0 if j 6=j 0

for all j,and v

ij 2Z

n

, (0j m01).

&HQWHU

8VHU

$OLFH

8VHU

%RE

( PRG Q )

( ( ) − )

= _{% % % % P}

% [ [ [ [

[

&

U %

% J V

[ = ^% ⋅

( ( ) − )

= _{$ $ $ $ P}

$ [ [ [ [

[

&

U $

$ J V

[ = ^$ ⋅ ( PRG Q ) ( ) ^{%W Y $ U $}

P W

HY

% %W

%

%

$% ,' K [

:.

 

  ⋅ ⋅

= ∏ ₌ ⁻ ( PRG Q ) ^{$ P} ( ) ^{$W Y % U %}

W

$ HY

$ Y

$

%$ ,' K [

:.

 

  ⋅ ⋅

= ∏ ⁻

= W ( PRG Q )

( V $ χ ^& $ ) ( V % χ ^& % )

Figure 5.1: Proposed scheme.

The center generatesmrandomnumbersk

i0

; k

i1

;k

i2

;... ; k

i( m01)

(Let k

i be(k

i0

;k

i1

;

k

i2

;... ; k

i(m01)

)), and then computes

i ,

i

, and

i

as follows:

i

=k

i 1v

i

= m01

X

t=0 k

it v

it

(mod(n)) ;

i

i

=1 (mo d (n)); and

i

=( x

i1

;x

i2

;x

i3

;...;x

i( m01) ) ;

where

x

ij

=ID 0d

i k

ij

i

(mo d n) ;

for eachj; (1j m01).

Leth beaone-way hashfunction whichcomputesh

i

and thecenter computes s

i0 , i.e.

h

i

=h (x

i1

;x

i2

;x

i3

;...;x

i(m01)

); and

s

i0

=(h

i 1ID

i k

i0

i )

0d

:

The center then publishes (e;n;g;ID

i

;f;h) and delivers ( s

i0

;

i

) to each user i. With

respect to s

i0

, it must be delivered through a secure channel orby using anIC card.

Common key generation phase

We assume here that two users Alice and Bob want to share acommon-key. First, Alice

generatesa randomnumberr

A

and computes

x

A0

=g r

A

1s

A0

(mo d n):