On the security of a certificateless public-key encryption.

On the Security of a Certi?cateless Public-Key

Encryption

Zhenfeng Zhang,Dengguo Feng

State Key Laboratory of Information Security,

Institute of Software,Chinese Academy of Sciences,Beijing100080,P.R.China

zfzhang@57d6d80d7cd184254b3535c1

Abstract.Certi?cateless public-key cryptosystem is a recently proposed

attractive paradigm using public key cryptosystem,which avoids the key

escrow inherent in identity-based public-key cryptosystems,and does not

need certi?cates to generate trust in public keys.Recently,Al-Riyami and

Paterson proposed a new certi?cateless public-key encryption scheme[2,

3]and proved its security in the random oracle model.This paper shows

that their scheme is vulnerable to adaptive chosen ciphertext attacks,

and presents a countermeasure to overcome such a security?aw.

1Introduction

In traditional certi?cate-based public key cryptosystems,an entity’s public-key is generated from some random information that is unrelated to his identity,and hence need to be certi?ed with a certi?cate issued by a certi?cation authority. Any participant who wants to use a public-key must?rst verify the corresponding certi?cate to check the validity of the public-key.Certi?cate-based public key cryptosystems require a large amount of storage and computing time to verify and revoke certi?cates.

The notion of identity-based cryptography(id-pkc)was introduced by Shamir [7],in which the public-key of a user can be derived from his unique identi?er information.ID-pkc eliminates the certi?cates and greatly simpli?es the key management.However,an inherent problem of id-pkc is the key escrow,i.e., the private-key of each user is known to a private key generator,who can then decrypt any ciphertext and forge signature on any messages for any user.More-over,id-pkc requires a secure channel between users and pkg to deliver private keys.Because of these problems,it seems that id-pkc should be considered to be suitable only for small private network with lower security requirements.

To alleviate the problems associated with the use of identity-based cryp-tosystems and certi?cate authorities in traditional public-key cryptosystems, Al-Riyami and Paterson[1]introduced the concept of certi?cateless public key cryptography(cl-pkc).Unlike id-pkc,user’s private-key of cl-pkc schemes is

2Z.F.Zhang etc.

not generated by a Key Generation Center(kgc)alone.Instead,it is a com-bination of kgc-produced partial-private-key and an additional user-chosen se-cret.In this way,they successfully eliminate the built-in escrow properties,since kgc could not control the user’s private-key entirely.Meanwhile,cl-pkc is not identity-based any longer,and an additional public-key must be generated from user’s randomly-chosen secret information.The complex structure of this scheme also means that a user who is encrypting a message can do it without having to verify the correctness of the public key via a public key certi?cate.

A certi?cateless scheme’s security is assessed in terms of two di?erent kinds of attackers.The?rst kind of attacker(or Type I attacker)is meant to represent a normal third party attack against the con?dentiality of the system.Here,an entity in possession of all users’public keys attempts to break the IND-CCA2 security of the scheme.Due to the uncerti?ed nature of the public-keys produced by the users,we must assume that an attacker is able to replace these entities’public keys at will.This represents the attackers’ability to fool a user into sending a con?dential message using a public key that has been supplied by the attacker.The second kind of attacker represents a malicious key generation center,who is given the key generation center’s long term secret,but may not replace entities’public keys.

In2005,Al-Riyami and Paterson proposed a new certi?cateless public key en-cryption(cl-pke)scheme[2,3],whose security is proven to rest on the hardness of the Bilinear Di?e-Hellman Problem(BDHP)in the random oracle model. The new scheme is more e?cient than the original scheme[1],and then is used to constructed an e?cient certi?cate based encryption scheme[2].In this pa-per,we analyze the security of their new cl-pke scheme and show that it is vulnerable to adaptive chosen ciphertext attacks against the Type I attacker.A countermeasure is also presented to resist such an attack.

2Certi?cateless Public-Key Encryption

A certi?cateless public-key encryption scheme is de?ned by seven probabilistic, polynomial-time algorithms[1,6]:

–Setup:This algorithm takes as input a security parameter1k and returns the master private key SK and the master public key P K.The master public key de?nes a message space M and a ciphertext space C.This algorithm is run by a KGC to initially set up a system.

–Extract-Partial-Private-Key:This algorithm takes as input the master public key P K,the master private key SK,and identi?er ID∈{0,1}?.It outputs a partial private key D ID.This algorithm is run by a KGC once for each user,and the corresponding partial private key is distributed to that user in a suitably secure manner.

On the Security of a Certi?cateless Public-Key Encryption3

–Set-Secret-Value:This algorithm takes as input the master public key P K and an entity’s identi?er ID as input,and outputs a secret value x ID for that identity.This algorithm is run once by the user.

–Set-Private-Key:This algorithm takes as input the master public key P K,an entity’s partial private key D ID and an entity’s secret value x ID.It outputs the full private key sk ID for that user.This algorithm is run by the user.

–Set-Public-Key:This algorithm takes as input the master public key P K and an entity’s secret value x ID.It output a public key pk ID for that user.

This algorithm is run once by the user and the resulting public key is widely and freely distributed.

–Encrypt:This algorithm takes as input the master public key P K,a user’s identity ID and public key pk ID and a message m∈M.It outputs a ci-phertext C∈C.

–Decrypt:This algorithm takes as input the master public key P K,a user’s private key sk ID and a ciphertext C∈C.It returns m∈M or the error symbol⊥.

The security of a certi?cateless encryption scheme is expressed by two(but very similar)games.In both cases,an attacker A=(A1,A2)is trying to break the IND-CCA2security,the formal model describing con?dentiality.The game runs as follows:

1.The challenger generates(P K,SK)=Setup(1k).

2.The attacker executes A1on P K and(possibly)some extra information aux.During its execution A1may have access to certain oracles(described sub-sequently).A1terminates by outputting an identity ID?,two messages of equal length(m0,m1),and some state information state.

3.The challenger computes a public key value pk ID?for ID?(if one does not already exist)by running algorithms Set-Secret-Value and Set-Public-Key. Next it randomly chooses a bit b∈{0,1},computes and returns to the attack a ciphertext C?=Encrypt(P K,ID?,pk ID?,m b).

4.The attacker executes A2on input(C?,state).During its execution A2 may have access to the following oracles.A2terminates by outputting a guess b for b.

The attacker wins the game if b=b and its advantage is de?ned to be:

|Pr[b=b ]?1/2|.

The oracles that the attacker may have access to are de?ned as following.

–Request Public Key:The attacker provides an identity ID and the challenger responds with the public key for ID.If the identity ID has no associated public key,then the challenger generates a public key for ID by running Set-Public-Key(after running Set-Secret-Value if necessary).

4Z.F.Zhang etc.

–Replace Public Key:The attacker supplies an identity ID and a public key value pk ID,and the challenger replaces the current public key(if it exists) with pk ID.

–Extract Partial Private Key:The attacker supplies an identity ID and the challenger responds with a partial private key D ID.If the identity has no partial private key,the challenger generates a partial private key by running Extract-Partial-Private-Key on ID.

–Extract Private Key:The attacker supplies an identity ID and the challenger responds with the private key sk ID.If the identity has no associated private key,the challenger generates a private key using Set-Private-Value(after running Set-Secret-Value and Extract-Partial-Private-Key if neces-sary).The attacker may never query this oracle on any identity for which it has replaced the public key.

–Decrypt:The attacker supplies an identity ID and a ciphertext C,and the challenger responds with the decryption of C under the private key sk ID.

Note that if the attacker has replaced the public key for ID,then this ora-cle should return the correct decryption of C using the private key that is associated with the public key pk ID.

A certi?cateless scheme should resist attacks made by attackers with access to these oracles in the following ways.

De?nition1(Type I Attacker).Any probabilistic polynomial-time attacker A I=(A I1,A I2)should have negligible advantage in winning the IND-CCA2game subject to the following constraints:

–A I cannot extract the private key for the challenge identity ID?at any time,–A I cannot extract the private key of any identity for which it has replaced the public key,

–If A I1replaces the public key of ID?,then A I cannot extract the partial private key for ID?at any time after the public key was replaced,

–A I2cannot decrypt the challenge ciphertext C?for the identity ID?unless the public key pk ID?used to create the challenge ciphertext has been replaced.

Note that an attacker is allowed to make decryption queries,even for public keys which it has replaced.This means that the challenger must be able to correctly answer decryption queries even for public keys for which it does not know the corresponding secret key.This is a very strong requirement and it is unclear how realistic this restriction is.Some authors[4,6]have chosen to weaken this de?nition so that the challenger is not forced to decrypt ciphertexts for which the public key has been replaced.They presented a de?nition of Type I?security[4],which adds an additional oracle constraint given below:

–A I can only decrypt ciphertexts on identities for which it has replaced the public key with some value that is unequal to its original value if it also supplies the secret value corresponding to the new public key.

On the Security of a Certi?cateless Public-Key Encryption5

The security de?nition against a Type II attacker states that the key genera-tion center should not be able to break the con?dentiality of the scheme.In this case,an attacker A II has access to the oracles as a Type I attacker,subject to the oracle constraints that A II cannot extract the private key for the challenge identity ID?at any time,cannot replace public keys at any point in time,and cannot decrypt the challenge ciphertext C?for the identity ID?.We refer to [1-3]for detail.

3Al-Riyami and Paterson’s cl-pke Scheme

In this section,we describe Al-Riyami and Paterson’s new certi?cateless public-key encryption scheme[2,3].

Setup:1.On input a security parameter k,this algorithm output G1,G2,e ?rst,where(G1,+)and(G2,·)are groups of prime order q,e:G1×G1→G2is

a bilinear pairing[5].

2.Choose an arbitrary generator P∈G1.

3.Select a master-key s∈Z?q randomly and set P0=sP.

4.Choose cryptographic hash functions H1:{0,1}?→G?1,H2:G2→{0,1}n,H3:{0,1}n×{0,1}n→Z?q,H4:{0,1}n→{0,1}n and H5:G1→{0,1}n,where n is the bit-length of messages.The master public key is params= G1,G2,e,n,P,P0,H1,H2,H3,H4,H5 .

Partial-Private-Key-Extract:This algorithm takes as input ID A∈{0,1}?, computes Q A=H1(ID A)and outputs D A=sQ A as a partial private-key for entity A.

Set-Secret-Value:This algorithm takes as inputs params and an entity A’s identi?er ID A as inputs.It selects x A∈Z?q at random and outputs x A as A’s secret value.

Set-Private-Key:This algorithm takes as inputs params,an entity A’s partial private-key D A and A’s secret value x A∈Z?q.The output of the algorithm is the pair S A=(D A,x A).So the private key for A is just the pair consisting of the partial private key and the secret value.

Set-Public-Key:This algorithm takes params and entity A’s secret value x A∈Z?q as inputs and constructs A’s public-key as P A=x A P.

Encrypt:To encrypt M∈M for entity A with identi?er ID A and public-key P A,perform the following steps:

1.Check that P A is in G?1,if not output⊥and abort.

57d6d80d7cd184254b3535c1pute Q A=H1(ID A)∈G?1.

3.Choose a random valueσ∈{0,1}n.

3.Set r=H3(σ,M).

6Z.F.Zhang etc.

57d6d80d7cd184254b3535c1pute and output the ciphertext:

C = rP,σ⊕H 2(e (Q A ,P 0)r )⊕H 5(rP A ),M ⊕H 4(σ) .

Decrypt:Suppose C = U,V,W ∈C .To decrypt this ciphertext using private-key S A =(D A ,x A ):

57d6d80d7cd184254b3535c1pute V ⊕H 2(e (D A ,U ))⊕H 5(x A U )=σ .

57d6d80d7cd184254b3535c1pute W ⊕H 4(σ )=M .

3.Set r =H 3(σ ,M )and test if U =r P .If not,output ⊥and reject the ciphertext.Otherwise,output M .

Al-Riyami and Paterson have shown that the proposed cl-pke scheme is provable secure in the random oracle model.

Theorem 1([2,3]).Let H i (1≤i ≤5)be random oracles.Suppose that there is no polynomially bounded algorithm can solve the bilinear Di?e-Hellman problem with non-negligible advantage.Then the cl-pke scheme is IND-CCA2secure.

4A Type I Attacker’s CCA2Attack

In this section we consider the security model against a Type I attacker and show that the cl-pke scheme is insecure against a Type I attacker under adaptive

chosen ciphertext attacks.A Type I attacker A I =(A I 1,A I 2)can break the IND-

CCA2security of their cl-pke scheme in the following manner.

The challenger ?rst executes Setup (1k )to generate a master private key s ,P 0=sP ,and other parameters params .

The attacker executes A I 1on params .During its execution A I 1chooses t ∈Z ?q

at random,and then has access to the oracles to replace the public key of an entity with identity ID ?with P ID ?=rP .Then A I 1terminates by outputting

the identity ID ?,and two messages (m 0,m 1)of equal length.

The challenger randomly chooses b ∈{0,1},and computes

C ?=Encrypt (params ,I

D ?,P ID ?,m b )

as following:Compute Q ID ?=H 1(ID ?)∈G ?1,choose a random value σ∈

{0,1}n ,set r =H 3(σ,M ),and compute the ciphertext

C ?=(U,V,W )= rP,σ⊕H 2(e (Q I

D ?,P 0)r )⊕H 5(rP ID ?),m b ⊕H 4(σ) .

and returns C ?to the attacker.

Upon receipt of C ?,the attacker executes A I 2to determine the value of b .During its execution A I 2may have access to the oracles under the constraints described in De?nition 1.Particularly,A I 2accesses to the Replace Public Key

On the Security of a Certi?cateless Public-Key Encryption7

=x P ID?,where x ∈Z?q is oracle,and replace the public P ID?with P

ID?

randomly chosen by A I2.

Then A I2compute V =V⊕H5(tU)⊕H5(x tU)and set C??=(U,V ,W).

). Now A I2can access the Decrypt oracle and request decrypting C??for(ID?,P

ID?

=x P ID?=x tP and then x tU= Note that rP ID?=r·tP=t·U,P

ID?

.Thus we have

x t·rP=rP

ID?

V =σ⊕H2(e(Q ID?,P0)r)⊕H5(rP ID?)⊕H5(tU)⊕H5(x tU)

=σ⊕H2(e(Q ID?,P0)r)⊕H5(rP ID?).

That is,C??=(U,V ,W)is a valid ciphertext of m b for the entity with identity ID?and public key P

.

ID?

So the challenger will return m b to A I2as the answer,from which the attacker can determine a correct value for b,and thus break the IND-CCA2security of cl-pke scheme.

Note that,the above attack also works for the Type I?attacker,as A I2can supply the secret value x t corresponding to the public key P

to the challenger

ID?

for decrypting C??.

The reason that the above attack works is that A I can generate a valid ciphertext of m b after receiving C?,with only the secret value corresponding to P ID?.As a countermeasure to overcome such a?aw,we can let H2:G2×G1→{0,1}n,and encrypt a message M by randomly choosingσ∈{0,1}n,setting r=H3(σ,m)and then computing

C= rP,σ⊕H2(e(Q A,P0)r,rP A),M⊕H4(σ) .

The decryption can be done in a similar way.

Now one needs both the partial private-key D A=sQ A and the secret value corresponding to P A to compute the masking factor H2(e(Q A,P0)r,rP A)from a given ciphertext C.Therefore the above attack can be thwarted.

5Conclusion

Certi?cateless public-key encryption has recently been proposed as an attrac-tive alternative to certi?cate-based and identity-based encryption schemes.Al-Riyami and Paterson proposed a new certi?cateless public key encryption scheme [2,3],which is more e?cient than their original one[1].This paper shows that their new cl-pke scheme is vulnerable to adaptive chosen ciphertext attacks against a Type I attacker.A countermeasure is also presented to resist such attacks.

8Z.F.Zhang etc.

References

1.S.Al-Riyami and K.Paterson,“Certi?cateless public key cryptography”,Advances

in Cryptology-Asiacrypt’03,Lecture Notes in Computer Science,vol.2894,pp.452-473,Springer-Verlag,2003.

2.S.Al-Riyami and K.Paterson,“CBE from CL-PKE:A generic construction and

e?cient schemes”,Public Key Cryptography-PKC’05,Lecture Notes in Computer Science,vol.3386,pp.398-415,Springer-Verlag,2005.

3.S.Al-Riyami,Cryptographic schemes based on elliptic curve pairings.PhD thesis,

Royal Holloway,University of London,2004.

4.K.Bentahar,P.Farshim,J.Malone-Lee,and N.P.Smart.“Generic constructions

of identity-based and certi?cateless KEMs”.Cryptology ePrint Archive:Report 2005/058,Available from 57d6d80d7cd184254b3535c1/2005/058,2005.

5. D.Boneh and F.Franklin,“Identity-based encryption from the Weil pairing”,

SIAM Journal on Computing,32,586-615,2003.

6.Alexander W.Dent and Caroline Kudla,“On Proofs of Security for Certi?cate-

less Cryptosystems”.Cryptology ePrint Archive:Report2005/348,Available from 57d6d80d7cd184254b3535c1/2005/348,2005.

7. A.Shamir,“Identity based cryptosystems and signature schemes”,Advances in

Cryptology-Crypto’84,Lecture Notes in Computer Science,vol.196,pp.47-53, Springer-Verlag,1984.

本文来源：https://www.bwwdw.com/article/un2l.html