# Security Analysis of a Certificateless Signature from Lattices

Authors: Seunghwan Chang; Hyang-Sook Lee; Juhee Lee; Seongan Lim
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Tian and Huang proposed a lattice-based CLS scheme based on the hardness of the SIS problem and proved, in the random oracle model, that the scheme is existentially unforgeable against strong adversaries. Their security proof uses the general forking lemma under the assumption that the underlying hash functionH is a random oracle. We show that the hash function in the scheme is neither one-way nor collision-resistant in the view of a strong Type 1 adversary. We point out flaws in the security arguments and present attack algorithms that are successful in the strong Type 1 adversarial model using the weak properties of the hash function.


---

## Body

## 1. Introduction

The notion of certificateless signature (CLS) has been introduced by Al-Riyami and Paterson [1] in 2003 as a variant of identity-based signature (IBS) to eliminate the key escrow problem inherent in IBS and assuage the certificate management of regular signatures. To solve the key escrow problem, a user’s private key in a CLS scheme is not generated by the KGC alone. Instead, it is a combination of a secret from the KGC and one chosen by the user. More precisely, each user has two secrets: asecret value generated by the user and apartial private key produced by the KGC, who holds the master key. Signing requires both secrets. Since the KGC does not have access to the secret value generated by the user, the key escrow problem can be solved.Lattice-based signature schemes are an important alternative for the current number-theoretic signature schemes and are emerging as a promising candidate for postquantum cryptography on the basis of Shor’s work [2]. There are many lattice-based cryptosystems, including encryption schemes [3, 4]. There have been various attempts to construct lattice-based CLS schemes.The first lattice-based signature scheme was proposed by Gentry et al. [5] as a Hash-and-Sign signature scheme and its security is based on the hardness SIS problem on the average case. Lyubashevsky and Micciancio [6] proposed a lattice-based one-time signature scheme in 2008. Lyubashevsky [7] proposed a lattice-based signature by extending the scheme of Lyubashevsky and Micciancio [6] in the framework of Fiat-Shamir. Since then, a number of lattice-based signature schemes have been proposed in the context of PKI. Tian and Huang [8] proposed a IBS scheme following the framework of Lyubashevsky [7].In 2015, Tian and Huang [9] proposed a lattice-based CLS scheme and proved under the SIS assumption that the scheme is existentially unforgeable against strong adversaries, in the random oracle. In this paper, we discuss security flaws in the CLS scheme of Tian and Huang by scrutinizing misuses of the hash function in the security arguments. The security proof of the scheme is given in random oracle model and uses the general forking lemma under the assumption that the underlying hash function H is a random oracle. We show that the hash function is neither one-way nor collision-resistant in the view of a strong Type 1 adversary. This means that the hash function defined from H cannot be modelled as a random oracle and this indicates critical flaws in the security argument.We show that the CLS scheme is insecure against strong Type 1 adversaries by providing effective attack algorithms. The attack algorithms, which are successful in the strong Type 1 adversarial model, are based on the weak properties of the hash function that we have found.The rest of the paper is organized as follows. In Section2 we give preliminaries on CLS schemes and review the CLS scheme of Tian and Huang as well as their security proofs. In Section 3, we analyze the security arguments of Tian and Huang and point out security flaws. We show that the scheme is insecure under strong Type 1 attack. We draw our conclusion in Section 4.


## 2. Review of the Certificateless Signature Scheme of Tian and Huang

In 2015, Tian and Huang proposed a CLS scheme (from hereon in referred to simply as “Tian-Huang scheme”) and they claimed that their scheme is provably secure in the strong Type 1 adversarial model by assuming the hardness of the SIS problem [9]. In this section, we review some basics of Tian-Huang scheme and their security proof.


### 2.1. Some Basics of SIS Problem

The security of Tian-Huang scheme is based on the hardness of the SIS problem. The SIS problem can be stated as follows.Definition 1.
Given a positive integerq, a matrix A∈Zqn×m, and a positive real number γ, the (q,m,γ)-SIS problem for A is to find a nonzero vector v∈Zm such that Av=0(modq) and v≤γ.One of the related problems of the SIS problem is the Inhomogeneous-SIS (ISIS) problem that can be described as follows.Definition 2.
Given a positive integerq, a matrix A∈Zqn×m, a vector u∈Zn, and a positive real number γ′, the (q,m,γ′)-ISIS problem for (A,u) is to find a nonzero vector v∈Zm such that Av=u(mod⁡q⁡) and v≤γ′.For any polynomial-boundedm,γ and for any prime q≥γ·ω(nlog⁡n), it is known by Micciancio and Regev [10] that solving SIS on average is hard as approximating some intractable lattice problem.The polynomial-time algorithmsTrapGen and SampleMat are building blocks of Tian-Huang scheme. We skip the details of each algorithms in this paper.(i)
(A,TA)←TrapGen(q,n,m,γ) if and only if TA∈Zm×m is of full rank and each column vector of TA is a solution of (q,m,γ)-SIS problem for the matrix A∈Zqn×m.(ii)
For(A,TA)←TrapGen(q,n,m,γ), (D∈Zqn×k)←SampleMat(A,TA,γ′,u) if and only if each of the column vectors of D is a solution of (q,m,γ′)-ISIS problem for (A,u).


### 2.2. A Description of Tian-Huang Scheme [9]

In this subsection we give a brief description of Tian-Huang scheme; for the full details, see [9]. Major public parameters of the scheme are the following:(i)
n: security parameter.(ii)
q: prime number.(iii)
M: a positive real number.(iv)
m,m1,m2,b,k,λ,s,σ: positive integers with m=m1+m2,m1>2nlog⁡q,m2>64+nlog⁡q/2b+1 and s=Ω(nlog⁡q),σ=12sλm. The scheme consists of the following seven algorithms: (i)
Setup(n∈Z): on input the security parameter n, the KGC
(a)
computes(A,TA)←TrapGen(q,n,m1),(b)
chooses a random matrixB∈Zqn×m2,(c)
chooses two secure hash functions(1)F:0,1∗⟶Zqn×k,H:Zq2n×0,1∗⟶v∈-1,0,1k:v1≤λ,(d)
outputs the master secretmsk=TA and the public parameters params={A,B,F,H}.(ii)
PartialPrivateKeyExtract(id,msk,params): on input (id,msk=TA,params), the KGC obtains Did∈Zm1×k←SampleMat(A,TA,s,F(id)) and sends it to the user with id. Upon receiving Did, the user with id checks the correctness of Did by verifying if ADid=F(id) and Did≤sm1. If so, the user sets his partial private key as pskid=Did.(iii)
SetSecretValue(id,params): on input (id,params), the user with id selects a random matrix Sid∈Zm2×k satisfying Sid∞≤b and outputs his secret value xid=Sid.(iv)
SetPrivateKey(id,xid,pskid,params): on input (id,xid=Sid,pskid=Did,params), the user with id outputs his full private key SKid=(pskid,xid)=(Did,Sid)∈Zm1×k×Zm2×k.(v)
SetPublicKey(id,SKid,params): on input (id,SKid=(Did,Sid),params), the user with id outputs his public key PKid=BSid.(vi)
CLSign(id,SKid,m,params): on input (id,SKid=Did,Sid,m,params), the user with id
(a)
selectsy1←Dσm1 and y2←Dσm2 and sets y=y1y2∈Zm.(b)
setsh=HAy1By2,m∈{-1,0,1}k and c=DidSidh∈Zm.(c)
computesz=c+y∈Zm.(d)
outputs the signaturesig=(h,z) on m with probability min⁡1,Dσmz/MDσ,cmz. If nothing is outputted, repeat this algorithm.(vii)
CLVfy(id,PKid,σ,m,params): on input (id,PKid=BSid,sig=h,z,m,params), the algorithm outputs 1 only if z≤2σm,h=HAz1Bz2-FidPKidh,m, where z=z1z2.Correctness. The correctness of Tian-Huang scheme is clear from the fact that the following holds for any correctly computed key pairs and a signature (h,z) on m. (2)Az1Bz2-FidPKidh=A00Bz-A00BDidSidh=A00Bz-c=Ay1By2.


### 2.3. Security Model for CLS Schemes

The most general security notion of regular signature is the existential unforgeability under an adaptively chosen message attack. It is extended to IBS, namely, existential unforgeability under an adaptively chosen message and an adaptively chosen-ID attack, where an adversary can choose its messages and its identities adaptively. The security notion of CLS is similar to that of IBS, but it is more complicated from the following facts:(i)
The KGC should be considered as an adversary because it is not a trusted party.(ii)
There is no way to authenticate the public keyPKid of the user id because no certificate of PKid is given. Therefore, replacing the public key PKid of the user id is allowed. Such issues necessitate considering two types of adversaries in CLS, namely, Type 1 and Type 2 adversaries. The Type 1 adversary models outside attacker which is allowed to replace any user’s public key. The Type 2 adversary models a malicious KGC which is allowed to obtain the master secret msk. For each type, the adversary is also given access to the signing oracle for any messages for any identities of its chosen. However, none of Type 1 and Type 2 adversaries are allowed to replace PKid and obtain msk at the same time.In 2007, Hu et al. [11] defined formal security models and Huang et al. [12, 13] also defined formal security models in which the adversaries can be categorized into normal, strong, super adversaries (ordered based on their attack powers), which are accessed different sign oracles. Because our focus in this paper is the Type 1 security of Tian-Huang scheme against strong adversary, we describe the Type 1 security model of CLS against strong adversary, only. The Type 1 security of a CLS against strong adversary is formalized by using the following security game, CL-EUF game between the challenger C and a Type 1 adversary A.[CL-EUF-Game 1][Initialization] the challenger runs(msk,mpk,params)← setup(k) and sends (params,mpk) to A.[Queries]A can request the following queries adaptively to the challenger C.
CreateUser Query. For the requested identity id∈{0,1}∗, if id has already been created, nothing is to be carried out. Otherwise, the oracle runs the algorithms PartialPrivateKeyExtract(id,params,msk), SetSecretValue(id,params), SetPrivateKey(id,xid,pskid,params), and SetPublicKey(id,xid,params) to generate pskid, xid, SKid, and PKid. In both cases, PKid is returned.RevealSecretValue Query. For the requested identity id∈{0,1}∗, the oracle returns the corresponding secret value xid.ReplacePublicKey Query. For the requested (id,PKid′), the oracle replaces the public key PKid of the original user with PKid′ and returns the replaced (id,PKid′). The replacement will be recorded.RevealPartialPrivateKey Query. For the requested id∈{0,1}∗, the challenger C returns the corresponding partial private key pskid.StrongSign Query. For the requested (id,xid,mi), C returns the signature σi such that (3)CLVfyid,PKid,sigi,mi,params=1.[Forgery] finally,A outputs sig∗ on a message m∗ for an identity id∗. We say that the adversary A wins the [CL-EUF-Game 1] if
(1)
id∗ has never been requested to theRevealPartialPrivateKey oracle,(2)
the pair(id∗,xid∗,m∗) has never been requested to theStrongSign oracle, where xid∗ is the corresponding secret of PKid∗,(3)
CLVfy(id∗,PKid∗,sig∗,m∗,params)=1.The security of CLS against strong Type 1 adversaries is defined as follows.Definition 3.
For any polynomial-time strong Type I adversary, if the probability of the adversary win CL-EUF-Game 1 is negligible, then we say the CLS scheme is existentially unforgeable against strong Type 1 adversaries under adaptive chosen message and chosen identity attacks.Note that, for the security of CLS, one should consider both of Type 1 and Type 2 adversaries. However, we believe that the description of Type 1 security of CLS is enough to read the ideas of this paper and we omit the description of Type 2 security of CLS in this paper.


### 2.4. Summary of the Security Proof of Tian-Huang Scheme in [9]

The security proof of Tian-Huang scheme in [9] is given in random oracle model where the hash functions F and H are viewed as random oracles and controlled by the challenger C.Suppose there is a polynomial-time strong Type 1 adversaryA that requests CreateUser, RevealPartialPrivateKey, RevealSecretValue, ReplacePublicKey, StrongSign, and F and H queries and outputs a forged signature for Tian-Huang scheme with nonnegligible probability. Tian and Huang proved that the challenger C can solve the (q,m1,4σm+2sλm1)-SIS problem with nonnegligible probability using A. Now, we give a brief review of how the challenger C solves a given SIS problem by using the successful strong Type 1 adversary; for the full details, see [9]. Suppose that a specific (q,m1,4σm+2sλm1)-SIS problem with matrix A is given to C.First, the challengerC simulates the security game with the adversary A for params={A,B,F,H} with a randomly chosen B∈Zqn×m2 and two secure hash functions H and F. Even though the challenger C does not know the corresponding trapdoor TA, C can respond to Create-User-Oracle query or Extract-Partial-Private-Key-Oracle query correctly by using the hash function F as a random oracle which is controlled and recorded by C. The challenger C also records the list LH={(vi,μi,hi)} corresponding to idi of H-oracle query as a random oracle. Finally, A outputs a signature forgery sig∗=(h∗,z∗) on a message m∗ for an identity id∗ and Pid∗ with nonnegligible probability.To solve the given SIS problem for the matrixA, the challenger C reruns the adversary A with the same random tape but different outputting sequence of H-oracle. The general forking lemma assures that A will output a new forgery sig′∗ on a message m∗ for an identity id∗ and Pid∗ such that h∗≠h′ and (4)Az1∗Bz2∗-Fid∗Pid∗h∗=Az1′Bz2′-Fid∗Pid∗h′,where z∗=z1∗z2∗ and z′=z1′z2′.In particular, we see thatAz1∗-F(id∗)h∗=Az1′-Fid∗h′. By inserting F(id∗)=ADid∗, we have(5)Az1∗-z1′+Did∗h′-h∗=0.Since z1∗,z1′≤2σm and Did∗h′,Did∗h∗≤sλm1 with overwhelming probability, we can see that(6)z1∗-z1′+Did∗h′-Did∗h∗≤4σm+2sλm1.The fact h∗≠h′ and the nonuniqueness of the solution of ISIS problem for A,Fid∗ yields(7)z1∗-z1′+Did∗h′-Did∗h∗≠0with probability at least 1/2. Therefore, x=z1∗-z1′+Did∗h′-Did∗h∗ is a solution of the given SIS problem to C.Remark 4.
The security proof above is based on the forking lemma assuming the underlying hash functionH can be modelled as a random oracle. However, as we will see in the next section, for the strong Type I adversary, the specific hash function in the scheme, which is related but has a different property from the given H, is neither one-way nor collision-resistant. This means that the hash function defined from H cannot be modelled as a random oracle. Therefore, we see that there is a critical flaw in their security proof. In fact, we present successful strong Type 1 adversarial algorithms on the scheme in the next section.


## 2.1. Some Basics of SIS Problem

The security of Tian-Huang scheme is based on the hardness of the SIS problem. The SIS problem can be stated as follows.Definition 1.
Given a positive integerq, a matrix A∈Zqn×m, and a positive real number γ, the (q,m,γ)-SIS problem for A is to find a nonzero vector v∈Zm such that Av=0(modq) and v≤γ.One of the related problems of the SIS problem is the Inhomogeneous-SIS (ISIS) problem that can be described as follows.Definition 2.
Given a positive integerq, a matrix A∈Zqn×m, a vector u∈Zn, and a positive real number γ′, the (q,m,γ′)-ISIS problem for (A,u) is to find a nonzero vector v∈Zm such that Av=u(mod⁡q⁡) and v≤γ′.For any polynomial-boundedm,γ and for any prime q≥γ·ω(nlog⁡n), it is known by Micciancio and Regev [10] that solving SIS on average is hard as approximating some intractable lattice problem.The polynomial-time algorithmsTrapGen and SampleMat are building blocks of Tian-Huang scheme. We skip the details of each algorithms in this paper.(i)
(A,TA)←TrapGen(q,n,m,γ) if and only if TA∈Zm×m is of full rank and each column vector of TA is a solution of (q,m,γ)-SIS problem for the matrix A∈Zqn×m.(ii)
For(A,TA)←TrapGen(q,n,m,γ), (D∈Zqn×k)←SampleMat(A,TA,γ′,u) if and only if each of the column vectors of D is a solution of (q,m,γ′)-ISIS problem for (A,u).


## 2.2. A Description of Tian-Huang Scheme [9]

In this subsection we give a brief description of Tian-Huang scheme; for the full details, see [9]. Major public parameters of the scheme are the following:(i)
n: security parameter.(ii)
q: prime number.(iii)
M: a positive real number.(iv)
m,m1,m2,b,k,λ,s,σ: positive integers with m=m1+m2,m1>2nlog⁡q,m2>64+nlog⁡q/2b+1 and s=Ω(nlog⁡q),σ=12sλm. The scheme consists of the following seven algorithms: (i)
Setup(n∈Z): on input the security parameter n, the KGC
(a)
computes(A,TA)←TrapGen(q,n,m1),(b)
chooses a random matrixB∈Zqn×m2,(c)
chooses two secure hash functions(1)F:0,1∗⟶Zqn×k,H:Zq2n×0,1∗⟶v∈-1,0,1k:v1≤λ,(d)
outputs the master secretmsk=TA and the public parameters params={A,B,F,H}.(ii)
PartialPrivateKeyExtract(id,msk,params): on input (id,msk=TA,params), the KGC obtains Did∈Zm1×k←SampleMat(A,TA,s,F(id)) and sends it to the user with id. Upon receiving Did, the user with id checks the correctness of Did by verifying if ADid=F(id) and Did≤sm1. If so, the user sets his partial private key as pskid=Did.(iii)
SetSecretValue(id,params): on input (id,params), the user with id selects a random matrix Sid∈Zm2×k satisfying Sid∞≤b and outputs his secret value xid=Sid.(iv)
SetPrivateKey(id,xid,pskid,params): on input (id,xid=Sid,pskid=Did,params), the user with id outputs his full private key SKid=(pskid,xid)=(Did,Sid)∈Zm1×k×Zm2×k.(v)
SetPublicKey(id,SKid,params): on input (id,SKid=(Did,Sid),params), the user with id outputs his public key PKid=BSid.(vi)
CLSign(id,SKid,m,params): on input (id,SKid=Did,Sid,m,params), the user with id
(a)
selectsy1←Dσm1 and y2←Dσm2 and sets y=y1y2∈Zm.(b)
setsh=HAy1By2,m∈{-1,0,1}k and c=DidSidh∈Zm.(c)
computesz=c+y∈Zm.(d)
outputs the signaturesig=(h,z) on m with probability min⁡1,Dσmz/MDσ,cmz. If nothing is outputted, repeat this algorithm.(vii)
CLVfy(id,PKid,σ,m,params): on input (id,PKid=BSid,sig=h,z,m,params), the algorithm outputs 1 only if z≤2σm,h=HAz1Bz2-FidPKidh,m, where z=z1z2.Correctness. The correctness of Tian-Huang scheme is clear from the fact that the following holds for any correctly computed key pairs and a signature (h,z) on m. (2)Az1Bz2-FidPKidh=A00Bz-A00BDidSidh=A00Bz-c=Ay1By2.


## 2.3. Security Model for CLS Schemes

The most general security notion of regular signature is the existential unforgeability under an adaptively chosen message attack. It is extended to IBS, namely, existential unforgeability under an adaptively chosen message and an adaptively chosen-ID attack, where an adversary can choose its messages and its identities adaptively. The security notion of CLS is similar to that of IBS, but it is more complicated from the following facts:(i)
The KGC should be considered as an adversary because it is not a trusted party.(ii)
There is no way to authenticate the public keyPKid of the user id because no certificate of PKid is given. Therefore, replacing the public key PKid of the user id is allowed. Such issues necessitate considering two types of adversaries in CLS, namely, Type 1 and Type 2 adversaries. The Type 1 adversary models outside attacker which is allowed to replace any user’s public key. The Type 2 adversary models a malicious KGC which is allowed to obtain the master secret msk. For each type, the adversary is also given access to the signing oracle for any messages for any identities of its chosen. However, none of Type 1 and Type 2 adversaries are allowed to replace PKid and obtain msk at the same time.In 2007, Hu et al. [11] defined formal security models and Huang et al. [12, 13] also defined formal security models in which the adversaries can be categorized into normal, strong, super adversaries (ordered based on their attack powers), which are accessed different sign oracles. Because our focus in this paper is the Type 1 security of Tian-Huang scheme against strong adversary, we describe the Type 1 security model of CLS against strong adversary, only. The Type 1 security of a CLS against strong adversary is formalized by using the following security game, CL-EUF game between the challenger C and a Type 1 adversary A.[CL-EUF-Game 1][Initialization] the challenger runs(msk,mpk,params)← setup(k) and sends (params,mpk) to A.[Queries]A can request the following queries adaptively to the challenger C.
CreateUser Query. For the requested identity id∈{0,1}∗, if id has already been created, nothing is to be carried out. Otherwise, the oracle runs the algorithms PartialPrivateKeyExtract(id,params,msk), SetSecretValue(id,params), SetPrivateKey(id,xid,pskid,params), and SetPublicKey(id,xid,params) to generate pskid, xid, SKid, and PKid. In both cases, PKid is returned.RevealSecretValue Query. For the requested identity id∈{0,1}∗, the oracle returns the corresponding secret value xid.ReplacePublicKey Query. For the requested (id,PKid′), the oracle replaces the public key PKid of the original user with PKid′ and returns the replaced (id,PKid′). The replacement will be recorded.RevealPartialPrivateKey Query. For the requested id∈{0,1}∗, the challenger C returns the corresponding partial private key pskid.StrongSign Query. For the requested (id,xid,mi), C returns the signature σi such that (3)CLVfyid,PKid,sigi,mi,params=1.[Forgery] finally,A outputs sig∗ on a message m∗ for an identity id∗. We say that the adversary A wins the [CL-EUF-Game 1] if
(1)
id∗ has never been requested to theRevealPartialPrivateKey oracle,(2)
the pair(id∗,xid∗,m∗) has never been requested to theStrongSign oracle, where xid∗ is the corresponding secret of PKid∗,(3)
CLVfy(id∗,PKid∗,sig∗,m∗,params)=1.The security of CLS against strong Type 1 adversaries is defined as follows.Definition 3.
For any polynomial-time strong Type I adversary, if the probability of the adversary win CL-EUF-Game 1 is negligible, then we say the CLS scheme is existentially unforgeable against strong Type 1 adversaries under adaptive chosen message and chosen identity attacks.Note that, for the security of CLS, one should consider both of Type 1 and Type 2 adversaries. However, we believe that the description of Type 1 security of CLS is enough to read the ideas of this paper and we omit the description of Type 2 security of CLS in this paper.


## 2.4. Summary of the Security Proof of Tian-Huang Scheme in [9]

The security proof of Tian-Huang scheme in [9] is given in random oracle model where the hash functions F and H are viewed as random oracles and controlled by the challenger C.Suppose there is a polynomial-time strong Type 1 adversaryA that requests CreateUser, RevealPartialPrivateKey, RevealSecretValue, ReplacePublicKey, StrongSign, and F and H queries and outputs a forged signature for Tian-Huang scheme with nonnegligible probability. Tian and Huang proved that the challenger C can solve the (q,m1,4σm+2sλm1)-SIS problem with nonnegligible probability using A. Now, we give a brief review of how the challenger C solves a given SIS problem by using the successful strong Type 1 adversary; for the full details, see [9]. Suppose that a specific (q,m1,4σm+2sλm1)-SIS problem with matrix A is given to C.First, the challengerC simulates the security game with the adversary A for params={A,B,F,H} with a randomly chosen B∈Zqn×m2 and two secure hash functions H and F. Even though the challenger C does not know the corresponding trapdoor TA, C can respond to Create-User-Oracle query or Extract-Partial-Private-Key-Oracle query correctly by using the hash function F as a random oracle which is controlled and recorded by C. The challenger C also records the list LH={(vi,μi,hi)} corresponding to idi of H-oracle query as a random oracle. Finally, A outputs a signature forgery sig∗=(h∗,z∗) on a message m∗ for an identity id∗ and Pid∗ with nonnegligible probability.To solve the given SIS problem for the matrixA, the challenger C reruns the adversary A with the same random tape but different outputting sequence of H-oracle. The general forking lemma assures that A will output a new forgery sig′∗ on a message m∗ for an identity id∗ and Pid∗ such that h∗≠h′ and (4)Az1∗Bz2∗-Fid∗Pid∗h∗=Az1′Bz2′-Fid∗Pid∗h′,where z∗=z1∗z2∗ and z′=z1′z2′.In particular, we see thatAz1∗-F(id∗)h∗=Az1′-Fid∗h′. By inserting F(id∗)=ADid∗, we have(5)Az1∗-z1′+Did∗h′-h∗=0.Since z1∗,z1′≤2σm and Did∗h′,Did∗h∗≤sλm1 with overwhelming probability, we can see that(6)z1∗-z1′+Did∗h′-Did∗h∗≤4σm+2sλm1.The fact h∗≠h′ and the nonuniqueness of the solution of ISIS problem for A,Fid∗ yields(7)z1∗-z1′+Did∗h′-Did∗h∗≠0with probability at least 1/2. Therefore, x=z1∗-z1′+Did∗h′-Did∗h∗ is a solution of the given SIS problem to C.Remark 4.
The security proof above is based on the forking lemma assuming the underlying hash functionH can be modelled as a random oracle. However, as we will see in the next section, for the strong Type I adversary, the specific hash function in the scheme, which is related but has a different property from the given H, is neither one-way nor collision-resistant. This means that the hash function defined from H cannot be modelled as a random oracle. Therefore, we see that there is a critical flaw in their security proof. In fact, we present successful strong Type 1 adversarial algorithms on the scheme in the next section.


## 3. Main Results

In this section, we discuss the flaws that we have found in the arguments of their security proof against a strong Type 1 adversary. Then we give two successful strong Type 1 attack algorithms.


### 3.1. Analysis of Cryptographic Usage of Hash Functions in the Tian-Huang Scheme

The Tian-Huang scheme uses a collision-resistant hash functionH:Zq2n×{0,1}∗→{-1,0,1}k in an essential way in the security proof. In this section, we discuss the usage of the hash function and analyze how the security arguments utilize its cryptographic properties incorrectly.Lemma 5.
LetPid=BSid and ADid=F(id). Consider a signature sig=(h,z) on a message m, where h=HAy1By2,m. Then sig is valid under (id,Pid) if the following holds:(1)
z≤2σm.(2)
z=DidSidh+y1y2.Proof.
By (2) we have(8)Az1Bz2=A00Bz1z2=A00BDidSidh+y1y2=ADid00BSidh+Ay1By2=FidPidh+Ay1By2,and so(9)h=HAy1By2,m=HAz1Bz2-FidPidh,m.The converse is true with overwhelming probability if the hash functionH is collision-resistant:Lemma 6.
LetPid=BSid and ADid=F(id). If a signature sig=(h,z) on a message m is valid under (id,Pid) where h=HAy1By2,m, then with overwhelming probability we have (10)z=DidSidh+y1y2.By Lemmas5 and 6, we see that the validity of a signature (z,h) on the message m under (id,Pid) for Pid=BSid and ADid=F(id) is (computationally) equivalent to the following:(1)
z≤2σm,(2)
z=DidSidh+y1y2 for h=HAy1By2,m.Now we analyze some cryptographic properties concerning(11)h=HAy1By2,m=HAz1Bz2-FidPh,m,where H:Zq2n×{0,1}∗→{-1,0,1}k is a collision-resistant hash function.Theorem 7.
Suppose that we have functionsH:Zq2n×{0,1}∗→{-1,0,1}k,H′:Zm1×Zm2×{0,1}∗→{-1,0,1}k,such that (12)H′y1,y2,m=HAy1By2,m.For any given y1,m,h=H′y1,y2,m, one can efficiently compute y2 if the following data are known: (13)Sid,z=DidSidh+y1y2.Proof.
Givenh=H′y1,y2,m together with Sid,z=DidSidh+y1y2, one can recover y2 by computing and taking the second component of(14)z-0Sidh=Didh+y1y2.Theorem7 can be interpreted as asserting that the function H′ cannot acquire one-wayness in the presence of the (additional) data Sid,z=DidSidh+y1y2 for h=H′(y1,∗,m), even though H′ is closely related to a secure hash function H. We note that this additional data is always available to any strong Type 1 adversary against the Tian-Huang scheme by requesting ReplacePublicKey queries and a StrongSign query. In fact, we will use this to design a successful strong Type 1 attack on the Tian-Huang scheme in Section 3.2.1.Theorem 8.
Suppose we have functionsH:Zq2n×{0,1}∗→{-1,0,1}k,H′′:Zqm1×Zqm2×Zqn×k×{0,1}∗→{-1,0,1}k,such that (15)H′′z1,z2,P,id,m=HAz1Bz2-FidPh,m.For any given preimage (z1,z2,P,id,m) of h=H′′(∗), one can efficiently compute a second preimage of h.Proof.
Suppose we are givenz1,z2,P,id,m such that H′′z1,z2,P,id,m=h. Choose a S′∈Zm2×k such that S′h≠0 and BS′≠0. Compute z2′≔z2+S′h and P′≔P+BS′. Then(16)H′′z1,z2′,P′,id,m=HAz1Bz2′-FidP′h,m=HAz1Bz2+S′h-FidP+BS′h,m=HAz1Bz2-FidPh,m=h.By Theorem8, the function H′′ cannot be collision-resistant even if H is. In Section 3.2.2 we show how to utilize a second preimage of h to design a successful strong Type 1 attack on the Tian-Huang scheme.Theorems7 and 8 show that the functions h=HAy1By2,m and h=HAz1Bz2-FidPh,m cannot be a secure hash function even if the underlying function H is a one-way and collision-resistant if some additional data is known. Moreover we see that such additional information is always available to any strong Type 1 adversaries against the Tian-Huang scheme. In other words, none of the functions H′ and H′′ is a secure hash function in the view of strong Type 1 adversaries against the Tian-Huang scheme. Tian and Huang claimed that their CLS scheme is provably secure against strong Type 1 adversaries. The arguments of the proof are based on the fact that H′ and H′′ are cryptographically secure hash functions and they can be modelled as a random oracle, which are assumed by the authors from the secure choice of H. By Theorems 7 and 8, however, we see that this is not correct under the strong Type 1 adversarial model and so are their security proofs. In fact, we present two successful strong Type 1 attacks in the sections that follow.


### 3.2. Strong Type 1 Attacks on the Tian-Huang Scheme

We present two attack algorithms on the Tian-Huang scheme. The first attack is successful by considering the hash function in the scheme as(17)h=H′y1,y2,m=HAy1By2,m.The second attack is successful by considering the hash function in the scheme as(18)h=H′′z1,z2,P,id,m=HAz1Bz2-FidPh,m.


#### 3.2.1. Attack Algorithm 1

The idea of the attack is that a strong Type 1 adversary, by requesting ReplacePublicKey queries and a StrongSign query, is always able to obtain the data needed to compute the preimage ofh=H′(y1,y2,m) as in Theorem 7.A strong Type 1 adversaryA proceeds as follows.Step 1.
A choose any Sid′∈Zm2×k, to be used as a new secret value for id, and sets Pid′≔BSid′.Step 2.
A submits a query ReplacePublicKey(id,Pid′), so that the public key corresponding to id is now Pid′=BSid′.Step 3.
A submits a query StrongSign(m,id,Sid′) to obtain a signature(19)sig=z,h=c+y,HAy1By2,m,where (i)
y=y1y2; we may assume that y2≠0; that is, there is 1≤l≤m2 such that the lth component y2l of y2 is nonzero. (So there is ε∈{1,-1} such that (20)εel+y2≤y2,whereel is a standard unit vector, with all components zero except for the lth, which is one.)(ii)
h∈{-1,0,1}k; we may assume that h≠0; that is, hs≠0 for some 1≤s≤k.(iii)
z=DidSid′h+y1y2.Step 4.
A computes t≔t1t2←z-0Sid′h; note that t=Didh+y1y2=z1y2.Step 5.
A chooses Sid∗∈Zm2×k so that Sid∗h=εel∈Zm2; for instance, one can simply let Sid∗ to be the matrix whose entries are all zero except for the (l,s)-entry, which is set to be εhs (recall that hs≠0 from Step 3). A computes Pid∗=BSid∗ and submits a query ReplacePublicKey(id,Pid∗).Step 6.
A forges a signature sig∗=(h∗,z∗) by computing(i)
h∗←h;(ii)
z∗←t1Sid∗h+t2.Validity of the Forged Signature. The validity of sig∗ as a signature on m under (id,Pid∗) can be checked using Lemma 5:(i)
Notingh∗=h=HAy1By2,m, we have(21)z∗=t1Sid∗h+t2=Didh+y1Sid∗h+y2=DidSid∗h∗+y1y2.(ii)
Sincez∗=z1Sid∗h+y2=z1εel+y2, we have(22)z∗2=z12+εel+y22≤z12+y22=z2≤2σm.


#### 3.2.2. Attack Algorithm 2

The idea of the attack is that a preimage ofh=H′′(z1,z2,P,id,m) can be obtained from any (eavesdropped) valid signature and one can compute a second preimage of h as in Theorem 8. The adversary only eavesdrops and makes one ReplacePublicKey query. A strong Type 1 adversary A proceeds as follows.Step 1.
A starts with a(n eavesdropped) valid signature sig=(h,z) on a message m under the public key Pid=BSid, where (i)
h=(h1,…,hk)=HAy1By2,m;(ii)
z=z1z2=z11⋮z1m1z21⋮z2m2=c+y;(iii)
c=DidSidh.We may assume that z2≠0; that is, there is 1≤l≤m2 such that z2l is nonzero. So there is ε∈{1,-1} such that (23)εel+z2≤z2,where el is a unit vector, with all zero components except for the lth, which is one. The adversary A sets z2′=εel+z2. We may also assume that h≠0, say hs≠0 for some 1≤s≤k.Step 2.
A sets Sid′∈Zm2×k to be the matrix whose entries are all zeros except for the (l,s)-entry, which is εhs. A computes (i)
Pid∗←Pid+BSid′;(ii)
z∗=z1∗z2∗←z1z2′.Note that z∗=0Sid′h+z≠z and Pid=BSid with Sid unknown to A.Step 3.
A submits a query ReplacePublicKey(id,Pid∗); note that A does not know the secret value Sid∗=Sid+Sid′ corresponding to Pid∗.Step 4.
A returns forged sig∗=(h,z∗) as a signature on m under (id,Pid∗).Validity of the Forged Signature. The validity of sig∗ as a signature on m under (id,Pid∗) can be checked using Lemma 5:(i)
Noting thath=HAy1By2,m, we have(24)z∗=0Sid′h+z=0Sid′h+c+y=DidSid′+Sidh+y1y2=DidSid∗h+y1y2.(ii)
Sincez∗=z1Sid′h+z2=z1εel+z2, we have(25)z∗2=z12+εel+z22≤z12+z22=z2≤2σm.


## 3.1. Analysis of Cryptographic Usage of Hash Functions in the Tian-Huang Scheme

The Tian-Huang scheme uses a collision-resistant hash functionH:Zq2n×{0,1}∗→{-1,0,1}k in an essential way in the security proof. In this section, we discuss the usage of the hash function and analyze how the security arguments utilize its cryptographic properties incorrectly.Lemma 5.
LetPid=BSid and ADid=F(id). Consider a signature sig=(h,z) on a message m, where h=HAy1By2,m. Then sig is valid under (id,Pid) if the following holds:(1)
z≤2σm.(2)
z=DidSidh+y1y2.Proof.
By (2) we have(8)Az1Bz2=A00Bz1z2=A00BDidSidh+y1y2=ADid00BSidh+Ay1By2=FidPidh+Ay1By2,and so(9)h=HAy1By2,m=HAz1Bz2-FidPidh,m.The converse is true with overwhelming probability if the hash functionH is collision-resistant:Lemma 6.
LetPid=BSid and ADid=F(id). If a signature sig=(h,z) on a message m is valid under (id,Pid) where h=HAy1By2,m, then with overwhelming probability we have (10)z=DidSidh+y1y2.By Lemmas5 and 6, we see that the validity of a signature (z,h) on the message m under (id,Pid) for Pid=BSid and ADid=F(id) is (computationally) equivalent to the following:(1)
z≤2σm,(2)
z=DidSidh+y1y2 for h=HAy1By2,m.Now we analyze some cryptographic properties concerning(11)h=HAy1By2,m=HAz1Bz2-FidPh,m,where H:Zq2n×{0,1}∗→{-1,0,1}k is a collision-resistant hash function.Theorem 7.
Suppose that we have functionsH:Zq2n×{0,1}∗→{-1,0,1}k,H′:Zm1×Zm2×{0,1}∗→{-1,0,1}k,such that (12)H′y1,y2,m=HAy1By2,m.For any given y1,m,h=H′y1,y2,m, one can efficiently compute y2 if the following data are known: (13)Sid,z=DidSidh+y1y2.Proof.
Givenh=H′y1,y2,m together with Sid,z=DidSidh+y1y2, one can recover y2 by computing and taking the second component of(14)z-0Sidh=Didh+y1y2.Theorem7 can be interpreted as asserting that the function H′ cannot acquire one-wayness in the presence of the (additional) data Sid,z=DidSidh+y1y2 for h=H′(y1,∗,m), even though H′ is closely related to a secure hash function H. We note that this additional data is always available to any strong Type 1 adversary against the Tian-Huang scheme by requesting ReplacePublicKey queries and a StrongSign query. In fact, we will use this to design a successful strong Type 1 attack on the Tian-Huang scheme in Section 3.2.1.Theorem 8.
Suppose we have functionsH:Zq2n×{0,1}∗→{-1,0,1}k,H′′:Zqm1×Zqm2×Zqn×k×{0,1}∗→{-1,0,1}k,such that (15)H′′z1,z2,P,id,m=HAz1Bz2-FidPh,m.For any given preimage (z1,z2,P,id,m) of h=H′′(∗), one can efficiently compute a second preimage of h.Proof.
Suppose we are givenz1,z2,P,id,m such that H′′z1,z2,P,id,m=h. Choose a S′∈Zm2×k such that S′h≠0 and BS′≠0. Compute z2′≔z2+S′h and P′≔P+BS′. Then(16)H′′z1,z2′,P′,id,m=HAz1Bz2′-FidP′h,m=HAz1Bz2+S′h-FidP+BS′h,m=HAz1Bz2-FidPh,m=h.By Theorem8, the function H′′ cannot be collision-resistant even if H is. In Section 3.2.2 we show how to utilize a second preimage of h to design a successful strong Type 1 attack on the Tian-Huang scheme.Theorems7 and 8 show that the functions h=HAy1By2,m and h=HAz1Bz2-FidPh,m cannot be a secure hash function even if the underlying function H is a one-way and collision-resistant if some additional data is known. Moreover we see that such additional information is always available to any strong Type 1 adversaries against the Tian-Huang scheme. In other words, none of the functions H′ and H′′ is a secure hash function in the view of strong Type 1 adversaries against the Tian-Huang scheme. Tian and Huang claimed that their CLS scheme is provably secure against strong Type 1 adversaries. The arguments of the proof are based on the fact that H′ and H′′ are cryptographically secure hash functions and they can be modelled as a random oracle, which are assumed by the authors from the secure choice of H. By Theorems 7 and 8, however, we see that this is not correct under the strong Type 1 adversarial model and so are their security proofs. In fact, we present two successful strong Type 1 attacks in the sections that follow.


## 3.2. Strong Type 1 Attacks on the Tian-Huang Scheme

We present two attack algorithms on the Tian-Huang scheme. The first attack is successful by considering the hash function in the scheme as(17)h=H′y1,y2,m=HAy1By2,m.The second attack is successful by considering the hash function in the scheme as(18)h=H′′z1,z2,P,id,m=HAz1Bz2-FidPh,m.


### 3.2.1. Attack Algorithm 1

The idea of the attack is that a strong Type 1 adversary, by requesting ReplacePublicKey queries and a StrongSign query, is always able to obtain the data needed to compute the preimage ofh=H′(y1,y2,m) as in Theorem 7.A strong Type 1 adversaryA proceeds as follows.Step 1.
A choose any Sid′∈Zm2×k, to be used as a new secret value for id, and sets Pid′≔BSid′.Step 2.
A submits a query ReplacePublicKey(id,Pid′), so that the public key corresponding to id is now Pid′=BSid′.Step 3.
A submits a query StrongSign(m,id,Sid′) to obtain a signature(19)sig=z,h=c+y,HAy1By2,m,where (i)
y=y1y2; we may assume that y2≠0; that is, there is 1≤l≤m2 such that the lth component y2l of y2 is nonzero. (So there is ε∈{1,-1} such that (20)εel+y2≤y2,whereel is a standard unit vector, with all components zero except for the lth, which is one.)(ii)
h∈{-1,0,1}k; we may assume that h≠0; that is, hs≠0 for some 1≤s≤k.(iii)
z=DidSid′h+y1y2.Step 4.
A computes t≔t1t2←z-0Sid′h; note that t=Didh+y1y2=z1y2.Step 5.
A chooses Sid∗∈Zm2×k so that Sid∗h=εel∈Zm2; for instance, one can simply let Sid∗ to be the matrix whose entries are all zero except for the (l,s)-entry, which is set to be εhs (recall that hs≠0 from Step 3). A computes Pid∗=BSid∗ and submits a query ReplacePublicKey(id,Pid∗).Step 6.
A forges a signature sig∗=(h∗,z∗) by computing(i)
h∗←h;(ii)
z∗←t1Sid∗h+t2.Validity of the Forged Signature. The validity of sig∗ as a signature on m under (id,Pid∗) can be checked using Lemma 5:(i)
Notingh∗=h=HAy1By2,m, we have(21)z∗=t1Sid∗h+t2=Didh+y1Sid∗h+y2=DidSid∗h∗+y1y2.(ii)
Sincez∗=z1Sid∗h+y2=z1εel+y2, we have(22)z∗2=z12+εel+y22≤z12+y22=z2≤2σm.


### 3.2.2. Attack Algorithm 2

The idea of the attack is that a preimage ofh=H′′(z1,z2,P,id,m) can be obtained from any (eavesdropped) valid signature and one can compute a second preimage of h as in Theorem 8. The adversary only eavesdrops and makes one ReplacePublicKey query. A strong Type 1 adversary A proceeds as follows.Step 1.
A starts with a(n eavesdropped) valid signature sig=(h,z) on a message m under the public key Pid=BSid, where (i)
h=(h1,…,hk)=HAy1By2,m;(ii)
z=z1z2=z11⋮z1m1z21⋮z2m2=c+y;(iii)
c=DidSidh.We may assume that z2≠0; that is, there is 1≤l≤m2 such that z2l is nonzero. So there is ε∈{1,-1} such that (23)εel+z2≤z2,where el is a unit vector, with all zero components except for the lth, which is one. The adversary A sets z2′=εel+z2. We may also assume that h≠0, say hs≠0 for some 1≤s≤k.Step 2.
A sets Sid′∈Zm2×k to be the matrix whose entries are all zeros except for the (l,s)-entry, which is εhs. A computes (i)
Pid∗←Pid+BSid′;(ii)
z∗=z1∗z2∗←z1z2′.Note that z∗=0Sid′h+z≠z and Pid=BSid with Sid unknown to A.Step 3.
A submits a query ReplacePublicKey(id,Pid∗); note that A does not know the secret value Sid∗=Sid+Sid′ corresponding to Pid∗.Step 4.
A returns forged sig∗=(h,z∗) as a signature on m under (id,Pid∗).Validity of the Forged Signature. The validity of sig∗ as a signature on m under (id,Pid∗) can be checked using Lemma 5:(i)
Noting thath=HAy1By2,m, we have(24)z∗=0Sid′h+z=0Sid′h+c+y=DidSid′+Sidh+y1y2=DidSid∗h+y1y2.(ii)
Sincez∗=z1Sid′h+z2=z1εel+z2, we have(25)z∗2=z12+εel+z22≤z12+z22=z2≤2σm.


## 3.2.1. Attack Algorithm 1

The idea of the attack is that a strong Type 1 adversary, by requesting ReplacePublicKey queries and a StrongSign query, is always able to obtain the data needed to compute the preimage ofh=H′(y1,y2,m) as in Theorem 7.A strong Type 1 adversaryA proceeds as follows.Step 1.
A choose any Sid′∈Zm2×k, to be used as a new secret value for id, and sets Pid′≔BSid′.Step 2.
A submits a query ReplacePublicKey(id,Pid′), so that the public key corresponding to id is now Pid′=BSid′.Step 3.
A submits a query StrongSign(m,id,Sid′) to obtain a signature(19)sig=z,h=c+y,HAy1By2,m,where (i)
y=y1y2; we may assume that y2≠0; that is, there is 1≤l≤m2 such that the lth component y2l of y2 is nonzero. (So there is ε∈{1,-1} such that (20)εel+y2≤y2,whereel is a standard unit vector, with all components zero except for the lth, which is one.)(ii)
h∈{-1,0,1}k; we may assume that h≠0; that is, hs≠0 for some 1≤s≤k.(iii)
z=DidSid′h+y1y2.Step 4.
A computes t≔t1t2←z-0Sid′h; note that t=Didh+y1y2=z1y2.Step 5.
A chooses Sid∗∈Zm2×k so that Sid∗h=εel∈Zm2; for instance, one can simply let Sid∗ to be the matrix whose entries are all zero except for the (l,s)-entry, which is set to be εhs (recall that hs≠0 from Step 3). A computes Pid∗=BSid∗ and submits a query ReplacePublicKey(id,Pid∗).Step 6.
A forges a signature sig∗=(h∗,z∗) by computing(i)
h∗←h;(ii)
z∗←t1Sid∗h+t2.Validity of the Forged Signature. The validity of sig∗ as a signature on m under (id,Pid∗) can be checked using Lemma 5:(i)
Notingh∗=h=HAy1By2,m, we have(21)z∗=t1Sid∗h+t2=Didh+y1Sid∗h+y2=DidSid∗h∗+y1y2.(ii)
Sincez∗=z1Sid∗h+y2=z1εel+y2, we have(22)z∗2=z12+εel+y22≤z12+y22=z2≤2σm.


## 3.2.2. Attack Algorithm 2

The idea of the attack is that a preimage ofh=H′′(z1,z2,P,id,m) can be obtained from any (eavesdropped) valid signature and one can compute a second preimage of h as in Theorem 8. The adversary only eavesdrops and makes one ReplacePublicKey query. A strong Type 1 adversary A proceeds as follows.Step 1.
A starts with a(n eavesdropped) valid signature sig=(h,z) on a message m under the public key Pid=BSid, where (i)
h=(h1,…,hk)=HAy1By2,m;(ii)
z=z1z2=z11⋮z1m1z21⋮z2m2=c+y;(iii)
c=DidSidh.We may assume that z2≠0; that is, there is 1≤l≤m2 such that z2l is nonzero. So there is ε∈{1,-1} such that (23)εel+z2≤z2,where el is a unit vector, with all zero components except for the lth, which is one. The adversary A sets z2′=εel+z2. We may also assume that h≠0, say hs≠0 for some 1≤s≤k.Step 2.
A sets Sid′∈Zm2×k to be the matrix whose entries are all zeros except for the (l,s)-entry, which is εhs. A computes (i)
Pid∗←Pid+BSid′;(ii)
z∗=z1∗z2∗←z1z2′.Note that z∗=0Sid′h+z≠z and Pid=BSid with Sid unknown to A.Step 3.
A submits a query ReplacePublicKey(id,Pid∗); note that A does not know the secret value Sid∗=Sid+Sid′ corresponding to Pid∗.Step 4.
A returns forged sig∗=(h,z∗) as a signature on m under (id,Pid∗).Validity of the Forged Signature. The validity of sig∗ as a signature on m under (id,Pid∗) can be checked using Lemma 5:(i)
Noting thath=HAy1By2,m, we have(24)z∗=0Sid′h+z=0Sid′h+c+y=DidSid′+Sidh+y1y2=DidSid∗h+y1y2.(ii)
Sincez∗=z1Sid′h+z2=z1εel+z2, we have(25)z∗2=z12+εel+z22≤z12+z22=z2≤2σm.


## 4. Conclusion

In this paper, we showed that the hash function used in Tian-Huang’s scheme is not a secure hash function in the presence of a strong Type 1 adversary even though the function is defined from a cryptographically secure hash function. Such weakness of the hash function admits successful strong Type 1 attacks on their scheme. The security proof of the Tian-Huang scheme was done under the assumption that the hash function is a random oracle, which requires cryptographically security properties. It seems that to improve security argument one needs to make more careful use of the hash function in the simulation of the security game.



---

*Source: 3413567-2017-01-26.xml*