# Key Substitution Attacks on Lattice Signature Schemes Based on SIS Problem

Authors: Youngjoo An; Hyang-Sook Lee; Juhee Lee; Seongan Lim
Journal: Security and Communication Networks
 (2018)

---

## Abstract

The notion of key substitution security on digital signatures in the multiuser setting has been proposed by Menezes and Smart in 2004. Along with the unforgeability of signature, the key substitution security is very important since it is a critical requirement for the nonrepudiation and the authentication of the signature. Lattice-based signature is a promising candidate for post-quantum cryptography, and the unforgeability of each scheme has been relatively well studied. In this paper, we present key substitution attacks on BLISS, Lyubashevsky’s signature scheme, and GPV and thus show that these signature schemes do not provide nonrepudiation. We also suggest how to avoid key substitution attack on these schemes.


---

## Body

## 1. Introduction

The classical cryptography based on factoring or discrete-logarithm problem is vulnerable to cryptanalysis by quantum computers. To prepare for a security plan after the emergence of quantum computing, NIST [1] and ETSI [2] currently try to standardize public key algorithms of three categories, namely, digital signature, public key encryption, and key exchange protocol. Among them, digital signatures are commonly used for authenticated key exchange protocol, software distribution, financial transactions, and contract management software and in other cases where it is important to detect forgery or tampering.The established security notion for digital signature schemes isexistentially unforgeable against adaptive chosen-message attacks introduced by Goldwasser, Micali, and Rivest [3]. Although a signature scheme secure in this scenario offers rather strong security guarantees, further requirements can be crucial in certain applications. For example, Koblitz, Menezes, and Smart [4, 5] indicate that the GMR security is not sufficient in a multiuser setting by proposing a new type of attack on digital signature scheme, which is called a key substitution attack. In the key substitution attack, an adversary is given a public key pk and a signature sig on a message m under pk, and then he tries to produce a new public key pk′ different from pk, which validates the same signature sig on the same message m under the new public key pk′.A serious practical danger of key substitution attacks is that they not only undermine nonrepudiation but are disable to authenticate the signer who signed the message. These are core functionalities the digital signature can offer. Nonrepudiation refers to the ability to ensure that a sender who signed a message or document cannot later deny having sign it. The US government standard for digital signatures states that nonrepudiation and authentication are main characteristics of a signature scheme [6]. In the key substitution attack, a successful attacker obtains a new public key pk′, which validates a given signature signed by the signer. As a result, one signature is valid under two different public keys which affects these functionalities of the signature scheme. In other words, the threat of the key substitution attack is that there are two (or more) different valid public keys for the same given signature.A typical scenario where the key substitution attack has damaging consequences is the following. Suppose that Bob has signed an important contract with Alice. When the contract was nullified by Bob, he cannot claim that he did not sign the contract with Alice if the nonrepudiation property of the digital signature scheme works properly, because Alice presents the contract signed by Bob’s signature corresponding to his public keypkBob as an evidence of his lying. However, if the signature scheme is attacked by the key substitution attack, the scheme loses its function of nonrepudiation. Then Bob insists that he has not signed the contract with Alice and the signature on the contract presented by Alice is not what he has signed. As a proof of his claim, he mounts a key substitution attack to obtain a new public key pk′ different from pkBob and shows that the contract signed by the same signature can be validated by using the public key pk′. It means that it is hard to prove that Bob has signed a contract with Alice by using pkBob. It is serious issue to weaken the usability of the digital signature scheme in the real world. Therefore, it is crucial for the digital signature scheme to prevent the key substitution attack. It is noteworthy that the legal signer, Bob, could be a potential attacker in the key substitution attacks. For more real-world impact of the key substitution attack, we refer to [4].In this paper, we present key substitution attacks on the lattice signature schemes based on SIS problem such as GPV signature scheme [7], Lyubashevsky’s signature scheme [8], and BLISS [9]. Note that lattice-based cryptography is a most promising candidate for post-quantum cryptography, and BLISS (Bimodal Lattice Signature Scheme) is currently one of the most compact and efficient lattice-based signature schemes that is provably secure under lattice assumptions.We present two kinds of key substitution attacks. The first one is weak key substitution attack in which the adversary who may be a legal signer wants to ruin the properties of the digital signature schemes by obtaining new public and private key pairs. This type of attack is considered in [10, 11], and e-coupon and e-lottery were presented as concrete examples of these attacks. For instance, an electronic coupon (e-coupon) system works as follows. When issuing the e-coupon for a customer, in order to prevent illegal use of the e-coupon, it requires the customer to sign the e-coupon. Then the e-coupon is signed by the issuer and it will be issued to the customer as a legitimate buyer. Before he redeems the e-coupon at the store, he needs to show the ownership of the e-coupon by zero-knowledge proof of his secret key. Assume that a successful weak key substitution attacker Alice has a valid e-coupon and duplicates the e-coupon with the same signature under pk′ and sk′. Then she can use the e-coupon multiple times to buy the goods because she is able to prove that she owns the e-coupons by using sk′. Moreover, if Alice sells the copies of e-coupon with pk′ and sk′ to unauthorized users, she gets the financial benefits from it and illegal users obtain the goods using the e-coupon with sk′ at the shop.The other is strong key substitution attack in which an adversary, not necessary to be a signer, wants to compute a new public key validating a given signature. In this case the attacker may interfere with the communication between a signer and a verifier in order to achieve his malicious goal, like the unknown key share attack proposed in [12].In our attacks on these signature schemes, we solve linear equations for a valid new public keypk′ to pass the verification algorithm. One of the important requirements is to check if a hash value for given sig and pk′ is correct. On SIS-based signature schemes mentioned above, we succeed in substituting a new public key pk′ using algebraic structures depending on each signature scheme without finding the collision of hash function on the same message.This paper is organized as follows. In Section2, we introduce some necessary cryptographic and mathematical backgrounds, including the definitions of SIS problem and key substitution attack. In Section 3, we recall three lattice-based signature schemes, namely, GPV signature [7], Lyubashevsky’s signature [8], and BLISS [9], and present key substitution attacks on these schemes. In Section 4, we examine the effectiveness of the proposed attacks and explain how to avoid key substitution attacks on these schemes. In Section 5, we conclude our paper.


## 2. Preliminaries

### 2.1. Notations

We assume that all vectors are column vectors and vectors will be written in bold lower case letters. Matrices will be written in upper case letters. For vectorsb1,…,bm, let [b1,…,bm] denote a matrix whose i-th column is bi.Thelp norm of a vector v is denoted by vp and we will usually avoid writing the p for the l2 norm. For a distribution D, we use the notation x←D to mean that x is chosen according to the distribution D. If S is a set, then x←$S means that x is chosen uniformly at random from S. For integers a≥b, let [a,b] denote the set of integers {a,a+1,…,b}.


### 2.2. Some Basics on Lattices

LetB={b1,…,bn}⊆Rm consist of n linearly independent vectors. The n-dimensional lattice L generated by the basis B is L={∑1≤i≤ncibi:ci∈Z}. A lattice L⊆Rm is a discrete additive subgroup of Rm. If n=m, we say that L is full-rank.The minimum distanceλ1(L) of a lattice L is the length of its shortest nonzero vector in the l2 norm: λ1(L)=minx∈L∖{0}x. We write λ1∞(L) to denote the minimum distance of a lattice L in the l∞ norm. More generally, the k-th minimum λk(L) for k≤n is defined as the smallest r such that L contains ≥k linearly independent vectors of norm ≤r. If B=[b1,…,bn] is a basis matrix of L, the fundamental parallelepiped of B is the set P(B)={∑1≤i≤ncibi:ci∈[0,1)}. The volume det⁡(BTB) of P(B) is an invariant of the lattice L which is denoted by det(L). Minkowski’s theorem states that λ1(L)≤ndet⁡(L)1/n. The dual lattice of L, denoted by L∗, is defined as L∗=x∈Rn:∀v∈L,x,v∈Z.The following background results are borrowed from [13, Section 2]. Let n a power of 2, Φ(x)=xn+1, and R=Z[x]/Φ(x). An ideal I of R is a subset of R which is closed under addition and multiplication by arbitrary elements of R. By mapping polynomials to the vectors of their coefficients, we can see that an ideal I≠0 corresponds to a full-rank sublattice of Zn. An ideal lattice for Φ(x) is a sublattice of Zn that corresponds to a nonzero ideal I of R. The algebraic norm N(I) is the cardinality of R/I and it is equal to det(I) where I is regarded as a lattice. Any nonzero ideal I of R satisfies λn(I)=λ1(I).For an integerq, the elements in Zq are represented by integers in the range [-(q-1)/2,(q-1)/2). Let A∈Zqn×m for some positive integers n,m,q. We consider two kinds of full-rank m-dimensional integer lattices defined by A. The first consists of those integer vectors that are orthogonal (modulo q) to the rows of A, and it is defined as L⊥(A)={e∈Zm:Ae≡0mod⁡q}. The second lattice is generated by the transposed rows of A, and it is defined as L(A)={y∈Zm:y≡ATsmod⁡q for some s∈Zn}. In terminology of coding theory, A is the parity check matrix for the linear code {e∈Zm:Ae≡0mod⁡q} over Zq, and AT is the generator matrix for the lattice {y∈Zqm:y≡ATsmod⁡q} over Zq. When A is clear in the context, we can omit it and just write L and L⊥.Micciancio and Regev [14] introduced a lattice quantity called the smoothing parameter.Definition 1 (see [14]).
For anyn-dimensional lattice L and positive real ϵ>0, the smoothing parameter ηϵ(L) is the smallest real s>0 such that ρ1/s(L∗∖{0})≤ϵ.The following lemma shows that a Gaussian sample overL is distributed almost-uniformly modulo a sublattice L′, if s≥ηϵ(L′).Lemma 2 (see [14]).
LetL, L′ be n-dimensional lattices, with L′⊆L. Then for any ϵ∈(0,1/2), any s≥ηϵ(L′), and any c∈Rn, the distribution of (DΛ,s,cmod⁡L′) is within statistical distance at most 2ϵ of uniform over (Lmod⁡L′).The following lemma also shows that the smoothing parameter of a lattice is related to the minimum distance of its dual lattice in thel∞ norm or to the n-th minimum of the lattice.Lemma 3 (see [15]).
For anyn-dimensional lattice L and real ϵ>0, we have (1)ηϵL≤ln⁡2n1+1/ϵ/πλ1∞L∗.Lemma 4 (see [14]).
For anyn-dimensional lattice L and real ϵ>0, we have (2)ηϵL≤ln⁡2n1+1/ϵπ·λnL.


### 2.3. SIS Problems on Lattices

We recall the definition of the generalized Short Integer Solution (SIS) problem. This average case problem proposed by Ajtai [16] is to find a short nonzero integer solution e∈Zm to the homogeneous linear system Ae≡0mod⁡q for uniformly random A∈Zqn×m. This is syntactically equivalent to finding an approximately short nonzero vector in L⊥(A). The problem was formalized as follows in [14].Definition 5 (l2-SISq,n,m,β problem).
The small integer solution problem SIS (in thel2 norm) is defined as follows: given an integer q, a random matrix A←$Zqn×m, and a positive real number β, find a nonzero vector e∈Zm such that Ae≡0mod⁡q and e≤β.By the pigeonhole principle, ifβ≥mqn/m, then the SIS instances are guaranteed to have a solution. We now recall a variant problem, which is to find a short solution to a random inhomogeneous system, specifically, Ae≡umod⁡q (where both A and u are uniformly random).Definition 6 (l2-ISISq,n,m,β problem).
The inhomogeneous small integer solution problem ISIS (in thel2 norm) is as follows: given an integer q, a matrix A←$Zqn×m, a syndrome u∈Zqn, and a real β, find an integer vector e∈Zm such that Ae≡umod⁡q and e≤β.


### 2.4. Probability Distributions

The continuous normal distribution overRm centered at v with standard deviation σ is defined by the function ρv,σm(x)=(1/2πσ2)mexp⁡(-x-v2/2σ2). When v=0, we write ρσm(x). The discrete normal distribution over an m-dimensional lattice L centered at some v∈L with standard deviation σ is defined as DL,v,σm(x)=ρv,σm(x)/ρσm(L) where the quantity ρσm(L)=∑z∈Lρσm(z) is just a scaling quantity needed to make the function into a probability distribution. When L=Zm, we write DL,v,σm as Dv,σm, and Dσm denotes Dv=0,σm. When m=1, we write Dσ1 as Dσ.The following lemma shows the equivalence of two distributions which is used in the construction of Lyubashevsky’s signature scheme [8] and BLISS [9].Lemma 7 (rejection sampling [9]).
LetV be an arbitrary set, and let h:V→R and f:Zm→R be probability distributions. If gv:Zm→R is a family of probability distributions indexed by v∈V with property that there exists a M∈R such that ∀v∈V, ∀z∈Zm, M·gv(z)≥f(z), then the output distributions of the following two algorithms are identical:(1)
v←h, z←gv, output (z,v) with probability f(z)/(M·gv(z)).(2)
v←h, z←f, output (z,v) with probability 1/M.


### 2.5. Signatures and Key Substitution Attack

In this section we recall the definition of digital signature schemes and introduce the key substitution attack against it.Definition 8 (signature scheme [11]).
A signature schemeS is a triple of algorithms (KeyGen,Sign,Verify), where, for security parameter κ,(i)
KeyGen(1κ), the key pair generation algorithm, is a probabilistic polynomial-time algorithm which outputs a private/public key pair (sk,pk) on input of domain parameters pp which is an output of the setup algorithm taking a security parameter κ as an input;(ii)
Sign(pp,sk,μ), the signature generation algorithm, is a probabilistic polynomial-time algorithm which on input of message μ and a private key sk associated with domain parameters pp outputs a digital signature sig;(iii)
Verify(pp,pk,μ,sig), the signature verification algorithm, is a deterministic algorithm which on input of a message μ, signature sig, valid domain parameters pp, and a public key pk outputs 1 (= valid) or 0 (= invalid).A digital signature scheme issecure if it iscorrect andexistentially unforgeable under adaptive chosen-message attack (EUF-CMA). These properties are defined below. For simplicity, we omit the input pp in Sign and Verify and just write it as Sign(sk,μ) and Verify(pk,μ,sig).Definition 9 (correctness).
A digital signature scheme(KeyGen,Sign,Verify) is correct if for all κ∈N, all key pairs (sk,pk)∈KeyGen(1κ), and all messages μ we have(3)PrVerifypk,μ,Signsk,μ=1=1.Definition 10 (EUF-CMA).
A digital signature scheme(KeyGen,Sign,Verify) is existentially unforgeable under adaptive chosen-message attacks if for all probabilistic polynomial-time algorithms A with access to a signing oracle Sign(sk,·) there is a negligible function ϵ(·) such that(4)Prsk,pk←KeyGen1κμ∗,sig∗←ASignsk,·pk:μ∗∉Q∧Verifypk,μ∗,sig∗=1≤ϵκ,where Q is the set of queries which A has accessed to the signing oracle.We consider an additional checking algorithmCheck to check the validity of a public key pk. Given the domain parameters pp and a candidate public key pk, the checking algorithm Check(pp,pk) returns 1 if and only if the pk is valid under the domain parameters pp.Definition 11 (key substitution attack [11]).
Given a signature schemeS, a key substitution attack (with malicious signer) is a probabilistic polynomial-time algorithm A which on input of valid domain parameters pp outputs two valid public keys pk and pk′ (passing the tests for KeyGen(pp,pk) and Check(pp,pk′)) and a message/signature pair (μ,sig) where Verify(pp,pk,μ,sig)=1 and Verify(pp,pk′,μ,sig)=1. When taking into account certificates, key substitution attack has access to a certification oracle.A key substitution attack is calledweak if an adversary also needs to output private keys sk and sk′ corresponding to pk and pk′, respectively; otherwise key substitution attack is calledstrong. A digital signature scheme isstrong (resp.,weak) key substitution secure if it is secure againststrong (resp.,weak) key substitution attacks.Remark 12.
When considering the nonrepudiation property of signature schemes, it is important to note that the legal signers can be considered as attackers since the repudiation of a signature is a malicious goal of legal signers.Remark 13.
A more general version of key substitution attack, which is calledmessage and key substitution (MKS) attack by Menezes and Smart [5], states that the adversary has generated a valid public key pk′≠pk and a message m′≠m such that the same signature sig is valid under public key pk′ for given valid signature sig on a message m under the public key pk. In [5], Menezes and Smart regarded MKS as an attack with little meaning, since signatures by themselves have no meaning and so they cannot envision a realistic scenario where this ability can have damaging consequence.


## 2.1. Notations

We assume that all vectors are column vectors and vectors will be written in bold lower case letters. Matrices will be written in upper case letters. For vectorsb1,…,bm, let [b1,…,bm] denote a matrix whose i-th column is bi.Thelp norm of a vector v is denoted by vp and we will usually avoid writing the p for the l2 norm. For a distribution D, we use the notation x←D to mean that x is chosen according to the distribution D. If S is a set, then x←$S means that x is chosen uniformly at random from S. For integers a≥b, let [a,b] denote the set of integers {a,a+1,…,b}.


## 2.2. Some Basics on Lattices

LetB={b1,…,bn}⊆Rm consist of n linearly independent vectors. The n-dimensional lattice L generated by the basis B is L={∑1≤i≤ncibi:ci∈Z}. A lattice L⊆Rm is a discrete additive subgroup of Rm. If n=m, we say that L is full-rank.The minimum distanceλ1(L) of a lattice L is the length of its shortest nonzero vector in the l2 norm: λ1(L)=minx∈L∖{0}x. We write λ1∞(L) to denote the minimum distance of a lattice L in the l∞ norm. More generally, the k-th minimum λk(L) for k≤n is defined as the smallest r such that L contains ≥k linearly independent vectors of norm ≤r. If B=[b1,…,bn] is a basis matrix of L, the fundamental parallelepiped of B is the set P(B)={∑1≤i≤ncibi:ci∈[0,1)}. The volume det⁡(BTB) of P(B) is an invariant of the lattice L which is denoted by det(L). Minkowski’s theorem states that λ1(L)≤ndet⁡(L)1/n. The dual lattice of L, denoted by L∗, is defined as L∗=x∈Rn:∀v∈L,x,v∈Z.The following background results are borrowed from [13, Section 2]. Let n a power of 2, Φ(x)=xn+1, and R=Z[x]/Φ(x). An ideal I of R is a subset of R which is closed under addition and multiplication by arbitrary elements of R. By mapping polynomials to the vectors of their coefficients, we can see that an ideal I≠0 corresponds to a full-rank sublattice of Zn. An ideal lattice for Φ(x) is a sublattice of Zn that corresponds to a nonzero ideal I of R. The algebraic norm N(I) is the cardinality of R/I and it is equal to det(I) where I is regarded as a lattice. Any nonzero ideal I of R satisfies λn(I)=λ1(I).For an integerq, the elements in Zq are represented by integers in the range [-(q-1)/2,(q-1)/2). Let A∈Zqn×m for some positive integers n,m,q. We consider two kinds of full-rank m-dimensional integer lattices defined by A. The first consists of those integer vectors that are orthogonal (modulo q) to the rows of A, and it is defined as L⊥(A)={e∈Zm:Ae≡0mod⁡q}. The second lattice is generated by the transposed rows of A, and it is defined as L(A)={y∈Zm:y≡ATsmod⁡q for some s∈Zn}. In terminology of coding theory, A is the parity check matrix for the linear code {e∈Zm:Ae≡0mod⁡q} over Zq, and AT is the generator matrix for the lattice {y∈Zqm:y≡ATsmod⁡q} over Zq. When A is clear in the context, we can omit it and just write L and L⊥.Micciancio and Regev [14] introduced a lattice quantity called the smoothing parameter.Definition 1 (see [14]).
For anyn-dimensional lattice L and positive real ϵ>0, the smoothing parameter ηϵ(L) is the smallest real s>0 such that ρ1/s(L∗∖{0})≤ϵ.The following lemma shows that a Gaussian sample overL is distributed almost-uniformly modulo a sublattice L′, if s≥ηϵ(L′).Lemma 2 (see [14]).
LetL, L′ be n-dimensional lattices, with L′⊆L. Then for any ϵ∈(0,1/2), any s≥ηϵ(L′), and any c∈Rn, the distribution of (DΛ,s,cmod⁡L′) is within statistical distance at most 2ϵ of uniform over (Lmod⁡L′).The following lemma also shows that the smoothing parameter of a lattice is related to the minimum distance of its dual lattice in thel∞ norm or to the n-th minimum of the lattice.Lemma 3 (see [15]).
For anyn-dimensional lattice L and real ϵ>0, we have (1)ηϵL≤ln⁡2n1+1/ϵ/πλ1∞L∗.Lemma 4 (see [14]).
For anyn-dimensional lattice L and real ϵ>0, we have (2)ηϵL≤ln⁡2n1+1/ϵπ·λnL.


## 2.3. SIS Problems on Lattices

We recall the definition of the generalized Short Integer Solution (SIS) problem. This average case problem proposed by Ajtai [16] is to find a short nonzero integer solution e∈Zm to the homogeneous linear system Ae≡0mod⁡q for uniformly random A∈Zqn×m. This is syntactically equivalent to finding an approximately short nonzero vector in L⊥(A). The problem was formalized as follows in [14].Definition 5 (l2-SISq,n,m,β problem).
The small integer solution problem SIS (in thel2 norm) is defined as follows: given an integer q, a random matrix A←$Zqn×m, and a positive real number β, find a nonzero vector e∈Zm such that Ae≡0mod⁡q and e≤β.By the pigeonhole principle, ifβ≥mqn/m, then the SIS instances are guaranteed to have a solution. We now recall a variant problem, which is to find a short solution to a random inhomogeneous system, specifically, Ae≡umod⁡q (where both A and u are uniformly random).Definition 6 (l2-ISISq,n,m,β problem).
The inhomogeneous small integer solution problem ISIS (in thel2 norm) is as follows: given an integer q, a matrix A←$Zqn×m, a syndrome u∈Zqn, and a real β, find an integer vector e∈Zm such that Ae≡umod⁡q and e≤β.


## 2.4. Probability Distributions

The continuous normal distribution overRm centered at v with standard deviation σ is defined by the function ρv,σm(x)=(1/2πσ2)mexp⁡(-x-v2/2σ2). When v=0, we write ρσm(x). The discrete normal distribution over an m-dimensional lattice L centered at some v∈L with standard deviation σ is defined as DL,v,σm(x)=ρv,σm(x)/ρσm(L) where the quantity ρσm(L)=∑z∈Lρσm(z) is just a scaling quantity needed to make the function into a probability distribution. When L=Zm, we write DL,v,σm as Dv,σm, and Dσm denotes Dv=0,σm. When m=1, we write Dσ1 as Dσ.The following lemma shows the equivalence of two distributions which is used in the construction of Lyubashevsky’s signature scheme [8] and BLISS [9].Lemma 7 (rejection sampling [9]).
LetV be an arbitrary set, and let h:V→R and f:Zm→R be probability distributions. If gv:Zm→R is a family of probability distributions indexed by v∈V with property that there exists a M∈R such that ∀v∈V, ∀z∈Zm, M·gv(z)≥f(z), then the output distributions of the following two algorithms are identical:(1)
v←h, z←gv, output (z,v) with probability f(z)/(M·gv(z)).(2)
v←h, z←f, output (z,v) with probability 1/M.


## 2.5. Signatures and Key Substitution Attack

In this section we recall the definition of digital signature schemes and introduce the key substitution attack against it.Definition 8 (signature scheme [11]).
A signature schemeS is a triple of algorithms (KeyGen,Sign,Verify), where, for security parameter κ,(i)
KeyGen(1κ), the key pair generation algorithm, is a probabilistic polynomial-time algorithm which outputs a private/public key pair (sk,pk) on input of domain parameters pp which is an output of the setup algorithm taking a security parameter κ as an input;(ii)
Sign(pp,sk,μ), the signature generation algorithm, is a probabilistic polynomial-time algorithm which on input of message μ and a private key sk associated with domain parameters pp outputs a digital signature sig;(iii)
Verify(pp,pk,μ,sig), the signature verification algorithm, is a deterministic algorithm which on input of a message μ, signature sig, valid domain parameters pp, and a public key pk outputs 1 (= valid) or 0 (= invalid).A digital signature scheme issecure if it iscorrect andexistentially unforgeable under adaptive chosen-message attack (EUF-CMA). These properties are defined below. For simplicity, we omit the input pp in Sign and Verify and just write it as Sign(sk,μ) and Verify(pk,μ,sig).Definition 9 (correctness).
A digital signature scheme(KeyGen,Sign,Verify) is correct if for all κ∈N, all key pairs (sk,pk)∈KeyGen(1κ), and all messages μ we have(3)PrVerifypk,μ,Signsk,μ=1=1.Definition 10 (EUF-CMA).
A digital signature scheme(KeyGen,Sign,Verify) is existentially unforgeable under adaptive chosen-message attacks if for all probabilistic polynomial-time algorithms A with access to a signing oracle Sign(sk,·) there is a negligible function ϵ(·) such that(4)Prsk,pk←KeyGen1κμ∗,sig∗←ASignsk,·pk:μ∗∉Q∧Verifypk,μ∗,sig∗=1≤ϵκ,where Q is the set of queries which A has accessed to the signing oracle.We consider an additional checking algorithmCheck to check the validity of a public key pk. Given the domain parameters pp and a candidate public key pk, the checking algorithm Check(pp,pk) returns 1 if and only if the pk is valid under the domain parameters pp.Definition 11 (key substitution attack [11]).
Given a signature schemeS, a key substitution attack (with malicious signer) is a probabilistic polynomial-time algorithm A which on input of valid domain parameters pp outputs two valid public keys pk and pk′ (passing the tests for KeyGen(pp,pk) and Check(pp,pk′)) and a message/signature pair (μ,sig) where Verify(pp,pk,μ,sig)=1 and Verify(pp,pk′,μ,sig)=1. When taking into account certificates, key substitution attack has access to a certification oracle.A key substitution attack is calledweak if an adversary also needs to output private keys sk and sk′ corresponding to pk and pk′, respectively; otherwise key substitution attack is calledstrong. A digital signature scheme isstrong (resp.,weak) key substitution secure if it is secure againststrong (resp.,weak) key substitution attacks.Remark 12.
When considering the nonrepudiation property of signature schemes, it is important to note that the legal signers can be considered as attackers since the repudiation of a signature is a malicious goal of legal signers.Remark 13.
A more general version of key substitution attack, which is calledmessage and key substitution (MKS) attack by Menezes and Smart [5], states that the adversary has generated a valid public key pk′≠pk and a message m′≠m such that the same signature sig is valid under public key pk′ for given valid signature sig on a message m under the public key pk. In [5], Menezes and Smart regarded MKS as an attack with little meaning, since signatures by themselves have no meaning and so they cannot envision a realistic scenario where this ability can have damaging consequence.


## 3. Key Substitution Attacks on SIS-Based Signature Schemes

In this section, we describe three SIS-based signature schemes: GPV signature scheme [7], Lyubashevsky’s signature scheme [8], and BLISS [9]. We present strong key substitution attacks on these schemes. We also provide weak key substitution attacks on these schemes where a legal signer acts as an attacker, and this implies that these signature schemes have a problem in providing nonrepudiation property, even if the certificate authority requires users to prove possession of user’s private key before issuing certificates. We note that even though our weak key substitution attack is not successful when the attacker is not the original signer, at least it can be said that there may be a problem in providing nonrepudiation with these signature schemes.


### 3.1. Attacks on GPV Signature Scheme

Description of GPV Signature Scheme. First, we present key substitution attacks on GPV signature scheme designed by Gentry, Peikert, and Vaikuntanathan [7]. Before continuing, we briefly describe the key generation algorithm KeyGen.GPV, signature generation algorithm Sign.GPV, and signature verification algorithm Verify.GPV of the GPV signature scheme.KeyGen.GPV(1κ): On the given input 1κ, the algorithm samples a pair of matrices (A,T), where A∈Zqn×m is a matrix of rank n over Zq and T∈Zm×m is a matrix of rank m over R satisfying AT≡0mod⁡q, and max1≤i≤mti≤β, where ti denotes i-th column vector of T. The key generation algorithm also sets a collision resistant function H:0,1∗→Zqn and outputs public parameters pp=H and a pair of public key and private key (pk=A,sk=T).Sign.GPV(pp,sk,μ∈0,1∗): On the given inputs pp,sk, and a message μ, the algorithm computes y=H(μ)∈Zqn and finds c∈Zm such that Ac≡ymod⁡q. The signing algorithm also samples z←DLA⊥,β,-c satisfying Az≡0mod⁡q and z+c≤mβ, using the short basis of LA⊥ induced from sk=T. The signing algorithm finally outputs sigμ=z+c∈Zm as a signature of the message μ.Verify.GPV(pk,pp,μ,sigμ): On the given inputs pk,pp,μ,sigμ, the algorithm outputs 1 (= valid) if and only if(5)sigμ≤mβandA·sigμ≡Hμmod⁡q.Strong Key Substitution Attack. We present a strong key substitution attacks on the GPV signature scheme.Suppose that a valid signaturesigμ∈Zm on a message μ∈0,1∗ under the public key pk=A∈Zqn×m is given. One proceeds as follows to obtain a new public key pk′ where sigμ is a valid signature on the message μ under this new public key pk′.(1)
Compute a matrixB∈Zqn×m such that B·sigμ≡0mod⁡q and the rank of the matrix A+B is n.
(a)
Letsigμ=(s1,…,sm)T. In the construction of B, the vector {b2,…,bm} can be chosen arbitrarily such that s2b2+⋯+smbm≠0. In particular, we select n column vectors of A which are linearly independent over Zq, namely, ai1,…,ain(we may assume that i1>1). And we set bij=0 for j=1,…,n and choose other bi’s so that s2b2+⋯+smbm≠0. Then A+B has n linearly independent column vectors over Zq, which means the rank(A+B)=n.(2)
SetA′≡(A+B)mod⁡q.(3)
Outputpk′=A′ and sigμ as a signature on μ under the public key pk′.The validity ofsigμ as a signature on the message μ under the new public key pk′ follows from the facts below:(i)
sigμ<mβ since sigμ is a valid signature.(ii)
A′·sigμ≡Hμmod⁡q since we have(6)A′·sigμ≡A+B·sigμ≡A·sigμ≡Hμmod⁡q.Weak Key Substitution Attack. We now present a weak key substitution attack on the GPV signature scheme. In the proposed attack, we assume that the signer acts as an attacker to undermine the nonrepudiation property of the signature scheme and so the attacker knows sk=T.Suppose that a valid signaturesigμ∈Zm on a message μ∈{0,1}∗ under the public key pk=A∈Zqn×m is given. The attacker proceeds as follows to obtain a new public key pk′ and the corresponding private key sk′ such that sigμ is a valid signature on the message μ under this new public key pk′.(1)
Compute a matrixM∈Zqn×n such that H(μ)∈Zqn is an eigenvector of M with eigenvalue 1; that is, M·H(μ)≡H(μ)mod⁡q.
(a)
M is chosen as an invertible matrix over Zq with eigenvector H(μ) and eigenvalue 1 so that MA has rank n. More precisely, one can construct M=(δi,j) as follows. We may assume that H(μ)=(h1,…,hn)t≠0 and h1,h2≠0. For any α∈Zq∖{0,1}, we set the following.(7)δ1,1=αδ1,2=β=1-αh1h2-1mod⁡qδi,i=1fori∈2,…,nδi,j=0fori,j∉i,i:i=1,…,n∪1,2ThenM is invertible, M·H(μ)≡Hμmod⁡q, and the rank of MA(≠A) is n.(2)
SetA′≡M·Amod⁡q.(3)
Outputpk′=A′ and sigμ as a signature on the message μ under the public key pk′, and output T as a private key of pk′.Noting that the private keysk=T corresponding to the public key pk=A satisfies A′·T≡M·A·T≡0mod⁡q, we know that T is also a private key of the new public key pk′=A′. Thus, the attacker who knows sk also knows the private key sk′ of pk′.The validity ofsigμ as a signature on the message μ under the new public key pk′ follows from the facts below:(i)
sigμ<mβ since sigμ is a valid signature.(ii)
A′·sigμ≡Hμmod⁡q since we have(8)A′·sigμ≡M·A·sigμ≡M·Hμ≡Hμmod⁡q.Therefore, the attacker, who was the original signer, has succeeded in a weak strong key substitution attack on the GPV signature scheme.


### 3.2. Attacks on Lyubashevsky’s Signature Scheme

Description of Lyubashevsky’s Signature Scheme. We describe Lyubashevsky’s signature scheme based on SIS problem [8].KeyGen.LYU(1κ): On the given input 1κ, the algorithm samples two matrices (A,S), where A∈Zqn×m is a matrix of rank n and S∈[-d,d]m×k. The algorithm computes T∈Zqn×k satisfying T≡ASmod⁡q. The algorithm sets an integer γ such that 2γkγ≥2κ and sets η∈R so that Prz←Dσm[z≤ηmσ]≤1-2κ. The key generation algorithm also sets a hash function H:{0,1}∗→{v:v∈{-1,0,1}k,v1≤γ} and outputs public parameters pp=(A,H,B2:=ησm) and a pair of public key and private key (pk=T,sk=S).Sign.LYU(pp,sk,μ∈0,1∗): On the given inputs pp,sk, and a message μ, the algorithm samples an m-dimensional vector y from Dσm, then computes c=H(Ay,μ), and finally obtains z≡Sc+ymod⁡q by applying the rejection sampling algorithm. The signature algorithm only outputs (z,c) as a signature with probability min{Dσm/MDSc,σm,1}. If nothing is printed, run the algorithm again until some signature is outputted.Verify.LYU(pp,pk,μ,sig=(z,c)): On the given inputs pp,sk,μ,sigμ, the algorithm outputs 1 if and only if (9)z≤B2andc=HAz-Tcmod⁡q,μ.Strong Key Substitution Attack. Suppose that a valid signature sigμ=(z,c)∈Zqm×Zqk on a message μ∈{0,1}∗ under the public key pk=T∈Zqn×k is given. One proceeds as follows to obtain a new public key pk′ such that sigμ is a valid signature on the message μ under the new public key pk′.(1)
Compute a matrixB∈Zqn×k such that B·c≡0mod⁡q. It is easy to compute B in a similar way that is described in the strong key substitution attack on the GPV signature scheme.(2)
SetT′≡T+Bmod⁡q.(3)
Outputpk′=T′ and sigμ as a signature on the message μ under the public key pk′.The validity ofsigμ=(z,c)∈Zqm×Zqk as a signature on the message μ under the new public key pk′ follows from the facts below:(i)
z≤ησm since sigμ=(z,c) is a valid signature.(ii)
H(Az-T′cmod⁡q,μ)=c since we have(10)Az-T′c≡Az-T+Bc≡Az-Tcmod⁡q,c=HAz-Tcmod⁡q,μ.Weak Key Substitution Attack. We now present a weak key substitution attack on Lyubashevsky’s signature scheme. Suppose that a valid signature sigμ=(z,c)∈Zqm×Zqk on a message μ∈{0,1}∗ under the public key pk=T∈Zqn×k is given. As we have commented before, the signer is an attacker and it is assumed that the attacker knows sk=S such that AS≡Tmod⁡q. The attacker proceeds as follows to obtain a new public key pk′ such that sigμ is a valid signature on the message μ under the new public key pk′.(1)
Compute a matrixS′∈[-d,d]m×k satisfying S′·c≡0mod⁡q.
(i)
With high probability, we may assume thatc=(c1,…,ck)t∈{-1,0,1}k has at least two nonzero components, say c1 and c2. Let S=(s1,…,sk) and sj=(s1j,…,smj)t with sij∈[-d,d]. We also assume(11)s11,s12∉d,d,-d,-d,-d,d,d,-d,which occurs with overwhelming probability. Letϵ∈{1,-1} which will be determined later. We set S′=(s1′,…,sk′) as follows.(12)s1′=ϵc2,0,…,0ts2′=-ϵc1,0,…,0tsl′=0,…,0tforl≠1,2Then, it satisfies thatS′·c≡s1′c1+s2′c2≡0mod⁡q.LetS′′=S+S′∈[-d,d]m×k. The only terms of S′′ differing from S are s11′′=s11+ϵc2 and s12′′=s12-ϵc1. If s11,s12<d, then one can choose any ϵ∈{-1,1}. If s11=±d and s12<d, then set ϵ so that ϵc2=∓1. If s12=±d and s11<d, then set ϵ so that ϵc1=±1.(2)
SetT′≡T+A·S′mod⁡q.(3)
Outputpk′=T′ and sigμ as a signature on μ under the public key pk′.Note thatsk′=S+S′ is a valid private key corresponding to pk′=T′ since T′≡(T+A·S′)≡A·S+S′mod⁡q and S+S′∈[-d,d]m×k. Therefore, the attacker, who knows sk=S such that T≡ASmod⁡q also knows the private key sk′=S+S′ of pk′.The validity ofsigμ=(z,c)∈Zqm×Zqk as a signature on the message μ under the new public key pk′ follows from the facts below:(i)
z≤ησm since sigμ=(z,c) is a valid signature.(ii)
H(Az-T′cmod⁡q,μ)=c since we have(13)Az-T′c≡Az-T+A·S′c≡Az-Tcmod⁡q,c=HAz-Tcmod⁡q,μ.Therefore, the attacker, who was the original signer, has succeeded in a weak key substitution attack on Lyubashevsky’s signature scheme.


### 3.3. Attacks on BLISS Signature Scheme

BLISS [9] is possibly one of the most efficient lattice-based signature schemes. It has been implemented in both software and hardware and boasts implementation efficiency comparable to classical factoring and discrete-logarithm-based schemes. BLISS can be seen as a ring-based optimization of the earlier lattice-based scheme of Lyubashevsky, sharing the same “Fiat-Shamir with aborts” structure.The security of the BLISS signature scheme is based on the hardness of theR-SISq,n,m,β problem which is the ring variant of the SIS problem. We first describe the matrix version of BLISS signature scheme and then explain its ring version. For more detailed descriptions and definition of the R-SISq,n,m,β problem, we refer to [9]. The scheme construction and proof work for matrix version are equally well for ring version, when instantiated with polynomials.In this subsection, we will assume thatq is a prime such that q≡1(mod⁡2n) and n is a power of 2. For any integer q, we define the quotient ring Rq=Zq[x]/(xn+1) and R2q=Z2q[x]/(xn+1).LetB={0,1} and T={-1,0,1} be the set of binary and ternary integers, respectively. We define Bωn (resp., Tωn ), the set of binary vectors (resp., ternary vectors) of length n and Hamming weight ω (i.e., vectors with exactly ω out of n nonzero entries). Depending on the context, we consider Bωn and Tωn as a subset of Z2qn or R2q and regard bold lower case letters as vectors or polynomials. For every integer x in the range -q,q and any positive integer d, x can be uniquely written x=xd·2d+[xmod⁡2d], where [xmod⁡2d]∈-2d-1,2d-1. For every integer vector x=(xi)1≤i≤n, xd denotes xid1≤i≤n. Let v1∣v2 denote the concatenation of two vectors v1 and v2.


#### 3.3.1. Matrix Version of BLISS

Description of the Matrix Version of BLISS. We describe the key generation algorithm KeyGen.mBLISS, signature generation algorithm Sign.mBLISS, and verification algorithm Verify.mBLISS of the matrix version of the BLISS signature scheme.KeyGen.mBLISS(1κ): On the given input 1κ, the algorithm outputs the key pair (pk=A,sk=S) such that S∈Zm×n2q has a small norm, A∈Z2qn×m, and AS≡qInmod⁡2q. The algorithm set η∈R so that Prz←Dσm[z≤ηmσ]≤1-2κ. Let H denote a hash function H:{0,1}∗→Bωn. The algorithm also outputs public parameter pp=(H,σ,B2:=ηmσ).Sign.mBLISS(pp,sk,pk,μ∈0,1∗): On the given inputs pp, sk, pk, and a message μ, the algorithm computes a signature sigμ=(z,c) of the message μ as follows:
(1)
y←Dσm.(2)
c←H(Aymod⁡2q,μ).(3)
Choose a random bitb∈{0,1}.(4)
z←y+(-1)bSc.(5)
Output(z,c) with probability 1/(Mexp⁡-Sc2/2σ2coshz,Sc/σ2); otherwiserestart.Verify.mBLISS(pp,pk,μ,sigμ): On the given inputs pp,pk,μ, and a signature sigμ=(z,c), the algorithm accepts or rejects the signature according to the following steps:
(1)
Ifz>B2, then output 0.(2)
Ifz∞≥q/4, then output 0.(3)
Output 1 if and only ifc=H(Az+qcmod⁡2q,μ).Note that the signer outputs the signature(z,c) where z is distributed according to Dσm. It can be seen from Lemma 7 by taking gv=(1/2)DSc,σm+(1/2)D-Sc,σm and f=Dσm where v=Sc.Strong Key Substitution Attack. We present a strong key substitution attack on the matrix version of BLISS signature scheme.Suppose that a valid signaturesigμ=(z,c)∈Z2qm×Z2qm on a message μ∈{0,1}∗ under the public key pk=A∈Z2qn×m is given. One proceeds as follows to obtain a new public key pk′ such that the signature sigμ=(z,c) is a valid signature on the message μ under the new public key pk′.To succeed in strong key substitution attack, it is enough to find a new matrixA′∈Z2qn×m such that c=H(A′z+qcmod⁡2q,μ), which holds when A′z≡Azmod⁡2q. In the following we show how to find such a matrix A′.(1)
We may assume that there existsj∈{1,…,m} such that zj is invertible modulo 2q.(2)
Lett=(t1,…,tn)T=Azmod⁡2q and z=(z1,…,zm)T. For each i∈{1,…,n}, choose ai,1′,…,ai,j-1′,ai,j+1′,…,ai,m′ uniformly at random from Z2q, and then compute ai,j′≡zj-1ti-∑1≤k≠j≤mai,k′zkmod⁡2q.(3)
Defining a matrixA′=(ai,j′)∈Z2qn×m, we have A′z≡tmod⁡2q because of step (2).(4)
Outputpk′=A′ and sigμ=(z,c) as a signature on the message μ under the public key pk′.We note that the validity ofsigμ=(z,c) as a signature on the message μ under pk′=A′ can be checked as follows:(i)
z2≤B2 and z∞<q/4 since sigμ is a valid signature.(ii)
The equationA′z+qc≡Az+qcmod⁡2q implies that c=H(Az+qcmod⁡2q,μ)=H(A′z+qcmod⁡2q,μ).The described attack succeeds unless there is noj∈{1,…,m} such that zj is invertible in Z2q. Note that the signer outputs the signature (z,c) where z is distributed according to Dσm by Lemma 7. Therefore it is enough to estimate the success probability of our attack for z←Dσm. Let f(x)=e-x2/(2σ2) and a be a positive real number. Since f is a nonincreasing function in [0,∞), ∑x=0∞f(x)≥∫0∞f(x)dx and ∑x=1∞f(ax)≤(1/a)∫0∞f(x)dx. We thus have f(Z)=∑x∈Zf(x)≥∫-∞∞f(x)dx-f(0)=2πσ-1 and f(aZ)=∑x∈Zf(ax)≤1+1/a∫-∞∞f(x)dx=1+2πσ/a. We also note that Prz←Dσmz=a=∏1≤i≤mPrzi←Dσm[zi=ai] for any a∈Zm. Then (14)Prz←Dσmzjis  non-invertible  modulo2q=Przj←Dσ⁡zjis  non-invertible  modulo2q≤∑zj≡0mod⁡2ρσzj+∑zj≡0mod⁡qρσzj∑zj∈Zρσzj=ρσ2Z+ρσqZρσZ≤12+1q+ϵ, where ϵ=(5q+2)/2q(2πσ-1)<0.013 for parameters proposed in BLISS (σ≥100). This implies that the probability that all of z1,…,zm are noninvertible modulo 2q is at most (1/2+1/q+ϵ)m. Thus, the success probability of our attack is at least 1-(1/2+1/q+ϵ)m which is very high.Weak Key Substitution Attack. We now present a weak key substitution attack on the matrix version of BLISS signature scheme.Suppose that a valid signaturesigμ=(z,c)∈Z2qm×Z2qm on a message μ∈{0,1}∗ under the public key pk=A∈Z2qn×m is given. The signer, who owns pk=A and sk=S such that AS≡qInmod⁡2q, proceeds as follows to obtain a new public key pk′=A′ and the corresponding private key sk′=S′ such that the signature sigμ=(z,c) is a valid signature on the message μ under the new public key pk′. To succeed in weak key substitution attack, it is sufficient to find matrices A′ and S′ such that A′z≡Azmod⁡2q and A′S′≡qInmod⁡2q. In the following we show how to find such matrices A′ and S′.(1)
Compute a matrixM∈Z2qn×n such that M≡Inmod⁡2 and MAz≡Azmod⁡q, which imply that MAz≡Azmod⁡2q.
(a)
Computing such a matrix,M is easy if Az≢0mod⁡q. We first compute a matrix Y∈Zqn×n such that Y·Az≡0mod⁡q. We then set M=2Y+Inmod⁡2q. It is clear to see that M≡Inmod⁡2 and MAz≡Azmod⁡q.(2)
We setpk′=A′=MAmod⁡2q.Sincepk=A and sk=S satisfy AS≡qInmod⁡2q, we have AS≡0mod⁡q and AS≡Inmod⁡2. From the construction of M, we also have MAS≡0mod⁡q and MAS≡Inmod⁡2, which imply A′S≡qInmod⁡2q. Thus, the signer obtains a valid key pair pk′=A′ and sk′=S.The validity ofsigμ=(z,c) as a signature on the message μ under the public key pk′=A′ can be checked as follows:(i)
z2≤B2 and z∞≤q/4 since sigμ is a valid signature.(ii)
c=H(A′z+qcmod⁡2q,μ) from the following equations: (15)c=HAz+qcmod⁡2q,μandAz≡MAz≡A′zmod⁡2q.Therefore, the signer of the signaturesigμ=(z,c) succeeds in a weak key substitution attack on the matrix version of BLISS signature scheme.


#### 3.3.2. Ring Version of BLISS

Description of the Ring Version of BLISS. We describe the key generation algorithm KeyGen.BLISS, signature generation algorithm Sign.BLISS, and verification algorithm Verify.BLISS of the ring version of the BLISS signature scheme. Let us define p=⌊2q/2d⌋ where d is the number of dropped bits, and ζ such that ζ·(q-2)≡1mod⁡2q.The notationf(x)←Dσn means that f(x)=∑0≤i<nfixi and (f0,…,fn-1) are sampled from the distribution Dσn.ForS=(s1,s2)T∈R2q and an integer τ≤n, define (16)NτS=maxI⊂1,…,n#I=τ∑i∈ImaxJ⊂1,…,n#J=τ⁡∑j∈JTi,j,where T=(Ti,j)=S^TS^∈Rn×n and S^=(S^1,S^2)T is a matrix in R2n×n such that j-th column of S^i∈Rn×n is the coefficient vector of polynomial sixj-1mod⁡xn+1 for i=1,2 and j=1,…,n.KeyGen.BLISS(1κ): On the given input 1κ, the algorithm outputs the key pair (pk=A,sk=S) generated as follows. We note that a key pair (A,S) satisfies AS≡qmod⁡2q. The algorithm sets η∈R so that Prz←Dσ2n[z≤η2nσ]≤1-2κ. The algorithm also sets a positive integer τ≤n and a constant C so that 25% of the keys are accepted. Let H denote a hash function H:{0,1}∗→Bωn. The algorithm also outputs public parameter pp=(H,σ,B2:=ηnσ,B∞) where 2B∞+(2d+1)<q/2.
(1)
Choosef,g as uniform polynomials of degree less than n with exactly d1=⌈δ1n⌉ entries in {±1}, d2=⌈δ2n⌉ entries in {±2}, and other entries in {0} where 0≤δ1<1 and 0≤δ2<1 are given densities.(2)
S=(s1,s2)T←(f,2g+1)T.(3)
IfNτ(S)≥C2·5·(⌈δ1n⌉+4⌈δ2n⌉)·τ, thenrestart.(4)
aq←(2g+1)/fmod⁡q (restart if f is not invertible).(5)
A=(a1,q-2)←(2aq,q-2)mod⁡2q.Sign.BLISS(pp,sk,pk,μ∈{0,1}∗): On the given inputs pp, sk, pk, and a message μ, the algorithm computes a signature sigμ=(z1,z2†,c) of the message μ as follows:
(1)
y1,y2←Dσn.(2)
u←ζ·a1·y1+y2mod⁡2q.(3)
c←H(⌊udmod⁡p,μ).(4)
Choose a random bitb.(5)
z1←y1+(-1)bs1c.(6)
z2←y2+(-1)bs2c.(7)
Continue with probability 1/(Mexp⁡-Sc2/2σ2cosh⁡z,Sc/σ2); otherwiserestart.(8)
z2†←ud-u-z2dmod⁡p.(9)
Output(z1,z2†,c).Verify.BLISS(pp,pk,μ,sigμ): On the given inputs pp,pk,μ,sigμ=(z1,z2†,c), the algorithm accepts or rejects the signature according to the following steps:
(1)
z←z1∣(2d·z2†).(2)
Ifz2>B2, then output 0.(3)
Ifz∞>B∞, then output 0.(4)
Output 1 if and only ifc=H(ζ·a1·z1+ζ·q·cd+z2†mod⁡p,μ).As in the matrix version of BLISS, the signer outputs the signature(z1,z2†,c) where z1 is sampled from Dσn by Lemma 7.Strong Key Substitution Attack. Suppose that a valid signature sigμ=(z1,z2†,c)∈R2q×R2q×R2q on a message μ∈0,1∗ under the public key A=(a1,q-2)∈R2q×R2q is given. One proceeds as follows to obtain a new public key pk′ where the signature sigμ is a valid signature on the message μ under the new public key pk′.Since we want to findA′=(a1′,q-2) satisfying the equation (17)Hζ·a1′·z1+ζ·q·cd+z2†mod⁡p,μ=Hζ·a1·z1+ζ·q·cd+z2†mod⁡p,μ,where ζ(q-2)≡1mod⁡2q, it suffices to find a1′∈R2q such that a1′z1≡a1z1mod⁡2q. To find such a polynomial a1′, we consider the greatest common divisor of two polynomials z1 and xn+1. Let gq(x) be the gcd of z1 and xn+1 modulo q, and let g2(x) be the gcd of z1 and xn+1 modulo 2. Since q≡1mod⁡2n, the polynomial xn+1 is completely factorized as a product of distinct linear polynomials modulo q; that is, xn+1≡∏i=1n(x-αi)mod⁡q,αi∈Zq. Since n is a power of two, we also have xn+1≡(x+1)nmod⁡2.Case 1.
Ifgq(x)≠1, there exists i∈{1,…,n} such that z1≡(x-αi)zˇ1mod⁡q for some zˇ1∈Rq. We set h(x)≡(xn+1)/(x-αi)mod⁡q and define a1′≡a1+2hmod⁡(2q,xn+1). In this case, we output A′=(a1′,q-2) as a new public key pk′ and sigμ=(z1,z2†,c) as a signature on the message μ under the public key pk′.Case 2.
Ifg2(x)≠1, we set h(x)≡(xn+1)/(x+1)≡(x+1)n-1mod⁡2 and define a1′≡a1+qhmod⁡2q,xn+1. In this case, we output A′=(a1′,q-2) as a new public key pk′ and sigμ=(z1,z2†,c) as a signature on the message μ under the public key pk′.In both cases, the validity ofsigμ=(z1,z2†,c) as a signature on the message μ under the public key pk′ can be checked as follows:(i)
z1∣(2d·z2†)≤B2 and z1∣(2d·z2†)∞≤B∞ since sigμ is a valid signature.(ii)
In both casesgq≠1 and g2≠1, we have a1z1≡a1′z1mod(2q,xn+1), which implies (18)ζ·a1′·z1+ζ·q·cd+z2†mod⁡p=ζ·a1·z1+ζ·q·cd+z2†mod⁡p.Thus, we havec=H(ζ·a1′·z1+ζ·q·cd+z2†mod⁡p,μ).As described, our attack succeeds whenz1 is noninvertible in R2 or z1 is noninvertible in Rq. Note that the signer outputs the signature (z1,z2†,c) where z1 is distributed according to Dσn by Lemma 7. Therefore it is enough to estimate the success probability of our attack for z1←Dσn. To compute success probability of our attack, we first consider the case that z1 is noninvertible in R2. Recall that, by Lemma 2, if σ≥ηϵ(2Zn), the distribution of (Dσnmod⁡2Zn) is within statistical distance at most 2ϵ of uniform over (Znmod⁡2Zn). Noting that (2Zn)∗=1/2Zn and λ1∞(2Zn)∗=1/2, by Lemma 3, we have (19)ηϵ2Zn≤1λ1∞2Zn∗ln⁡2n/1+1/ϵπ=2ln⁡2n/1+1/ϵπ.Therefore, if σ≥2ln(2n/(1+1/ϵ))/π, then the distribution of (Dσnmod⁡2Zn) is uniform over Zn/2Zn≅Z2n within statistical distance at most 2ϵ. Hence, for z1(x)←Dσn, the probability that z1(x) is not invertible in R2 is greater than or equal to 1/2-2ϵ. This is summarized in the following theorem.Theorem 14.
Ifσ≥2ln(2n/(1+1/ϵ))/π, (20)Prfx←Dσnfxis  non-invertible  inR2≥12-2ϵ.Takingϵ=2-n, we have ηϵ(2Zn)<2ln(n). For the proposed parameter sets for BLISS, we have σ≥100 and n≥256, which imply σ≥2ln(n)≥ηϵ(2Zn). Thus, the probability that z1(x) is noninvertible in R2 is greater than or equal to 1/2-2-n+1.We now consider the case thatz1(x) is noninvertible in Rq. Before continuing we first show that the following theorem holds. Note that this is essentially from [13, Lemma 11].Theorem 15.
Letn≥8 be a power of 2 such that Φ(x)=xn+1 splits into n linear factors modulo prime q≥5 as Φ(x)≡∏i=1n(x-αi)mod⁡q,αi∈Zq. Let ϵ∈(0,1/2) be an arbitrary real number. For i≠j∈{1,…,n}, we have the following. (i)
Ifσ≥nln⁡(2n(1+1/ϵ))/π·q1/n, (21)Prfx←Dσnfαi≡0mod⁡q≥1q-2ϵ.(ii)
Ifσ≥nln⁡(2n(1+1/ϵ))/π·q2/n, (22)Prfx←Dσnfαi≡0mod⁡q∧fαj≡0mod⁡q≤1q2+2ϵ.Proof.
LetI=〈q,x-αi〉 be an ideal of R=Z[x]/Φ(x). From R/I≅Zq[x]/(x-αi)≅Zq, we have N(I)=q and so λ1(I)≤nq1/n by Minkowski’s theorem. Since I is an ideal of R, we have λn(I)=λ1(I), and Lemma 4 gives ηϵ(I)≤ln⁡(2n(1+1/ϵ))/π·λn(I)≤nln⁡(2n(1+1/ϵ))/π·q1/n. Thus, if σ≥nln⁡(2n(1+1/ϵ))/π·q1/n, by Lemma 2, (fmod⁡I) is within statistical distance ≤2ϵ to the uniform distribution on R/I. As a result, we have Prf(x)←Dσn[f(x)≡0mod⁡I]=Prf(x)←Dσn[f(αi)≡0mod⁡q]≥1/q-2ϵ.
LetJ=〈q,(x-αi)(x-αj)〉 be an ideal of R. We then have N(J)=q2 and λ1(J)≤nq2/n, because R/J≅Zq[x]/(x-αi)(x-αj). Lemmas 4 and 2 then show that (fmod⁡J) is within statistical distance ≤2ϵ to the uniform distribution on R/J when σ≥nln⁡(2n(1+1/ϵ))/π·q2/n. On the other hand, since f(x)≡Ax+Bmod⁡J for A=(αi-αj)-1(f(αi)-f(αj))mod⁡q, B=f(αi)-Aαimod⁡q, f(x)≡0mod⁡J is equivalent to f(αi)≡0mod⁡q and f(αj)≡0mod⁡q. Thus, by combining these results, we have Prf(x)←Dσn[f(x)≡0mod⁡J]=Prf(x)←Dσn[f(αi)≡0mod⁡q∧f(αj)≡0mod⁡q]≤1/q2+2ϵ.Ifσ≥nln⁡(2n(1+1/ϵ))/π·q2/n, we have (23)Prz1x←Dσnz1is  non-invertible  inRq=Prz1x←Dσn⋁1≤i≤nz1αi≡0mod⁡q≥∑1≤i≤nPrz1x←Dσn⁡z1αi≡0mod⁡q-∑1≤i≠j≤nPrz1x←Dσn⁡z1αi≡0mod⁡q∧z1αj≡0mod⁡q≥n1q-2ϵ-n21q2+2ϵ=nq-nn-12q2-nn+1ϵ.Takingϵ=q-3, if σ≥nln⁡(2n(1+q3))/π·q2/n, the probability that z1←DZn,σ is noninvertible in Rq is at least n/q-n(n-1)/2q2-n(n+1)/q3, which is nonnegligible in n since in general q is polynomial in n. For the proposed parameter sets of BLISS having at least 128-bit security, we have n=512 and q=12289 and σ>100 always satisfies σ≥nln⁡2n1+q3/π·q2/n; thus the success probability is at least 0.04.Weak Key Substitution Attack. We present a weak key substitution attack on the ring version of the BLISS signature scheme. In this case, our attack is successful only in a very limited case.Suppose that a valid signaturesigμ=(z1,z2†,c) on a message μ∈0,1∗ under the public key pk=(a1,q-2) is given. In weak key substitution attacks the signer who owns the key pair pk=(a1,q-2),sk=(f,2g+1)T wants to obtain a new public key pk′=(a1′,q-2) and the corresponding private key sk′=(s1′,s2′)T so that the signature sigμ is a valid signature on the message μ under the new public key pk′.Similar to the strong key substitution attack on BLISS, it suffices to finda1′∈R2q and (f′,2g′+1) such that a1′z1≡a1z1mod⁡2q and a1′≡(2g′+1)/f′mod⁡q. In the following we show how to find such polynomials.(1)
Compute a polynomialb∈R2q such that bz1=0 in R2q by using a similar method in the strong key substitution attack. This implies that (2b/f)z1=0 in R2q.(2)
We setaq′=aq+(2b)/f in R2q.Sinceaq≡(2g+1)/fmod⁡q, we have aq′≡(2(g+b)+1)/fmod⁡q. However, we cannot guarantee that g′=(g+b) is small enough. Therefore, the signer obtains a valid key pair pk′=(a1′,q-2)=(2aq′,q-2) and sk′=(f′,2g′+1) only if one can make g′ small. One way to get a smaller g′ is to apply a lattice reduction algorithm on the ideal lattice generated by bmod⁡q. However, it does not guarantee that g′ is small enough to be a valid private key.The validity ofsigμ=(z,c) as a signature on the message μ under pk′=A′ can be checked as follows:(i)
z2≤B2 and z∞≤B∞ since sigμ is a valid signature.(ii)
c=H(ζ·a1′·z1+ζ·q·cd+z2†mod⁡p,μ) from the following equalities: c=H(ζ·a1·z1+ζ·q·cd+z2†mod⁡p,μ)anda1·z1≡a1′·z1mod⁡2q.Therefore, the signer ofsigμ=(z,c) succeeds in a weak key substitution attack on BLISS of ring version as long as g′ is small enough for a valid private key.


## 3.1. Attacks on GPV Signature Scheme

Description of GPV Signature Scheme. First, we present key substitution attacks on GPV signature scheme designed by Gentry, Peikert, and Vaikuntanathan [7]. Before continuing, we briefly describe the key generation algorithm KeyGen.GPV, signature generation algorithm Sign.GPV, and signature verification algorithm Verify.GPV of the GPV signature scheme.KeyGen.GPV(1κ): On the given input 1κ, the algorithm samples a pair of matrices (A,T), where A∈Zqn×m is a matrix of rank n over Zq and T∈Zm×m is a matrix of rank m over R satisfying AT≡0mod⁡q, and max1≤i≤mti≤β, where ti denotes i-th column vector of T. The key generation algorithm also sets a collision resistant function H:0,1∗→Zqn and outputs public parameters pp=H and a pair of public key and private key (pk=A,sk=T).Sign.GPV(pp,sk,μ∈0,1∗): On the given inputs pp,sk, and a message μ, the algorithm computes y=H(μ)∈Zqn and finds c∈Zm such that Ac≡ymod⁡q. The signing algorithm also samples z←DLA⊥,β,-c satisfying Az≡0mod⁡q and z+c≤mβ, using the short basis of LA⊥ induced from sk=T. The signing algorithm finally outputs sigμ=z+c∈Zm as a signature of the message μ.Verify.GPV(pk,pp,μ,sigμ): On the given inputs pk,pp,μ,sigμ, the algorithm outputs 1 (= valid) if and only if(5)sigμ≤mβandA·sigμ≡Hμmod⁡q.Strong Key Substitution Attack. We present a strong key substitution attacks on the GPV signature scheme.Suppose that a valid signaturesigμ∈Zm on a message μ∈0,1∗ under the public key pk=A∈Zqn×m is given. One proceeds as follows to obtain a new public key pk′ where sigμ is a valid signature on the message μ under this new public key pk′.(1)
Compute a matrixB∈Zqn×m such that B·sigμ≡0mod⁡q and the rank of the matrix A+B is n.
(a)
Letsigμ=(s1,…,sm)T. In the construction of B, the vector {b2,…,bm} can be chosen arbitrarily such that s2b2+⋯+smbm≠0. In particular, we select n column vectors of A which are linearly independent over Zq, namely, ai1,…,ain(we may assume that i1>1). And we set bij=0 for j=1,…,n and choose other bi’s so that s2b2+⋯+smbm≠0. Then A+B has n linearly independent column vectors over Zq, which means the rank(A+B)=n.(2)
SetA′≡(A+B)mod⁡q.(3)
Outputpk′=A′ and sigμ as a signature on μ under the public key pk′.The validity ofsigμ as a signature on the message μ under the new public key pk′ follows from the facts below:(i)
sigμ<mβ since sigμ is a valid signature.(ii)
A′·sigμ≡Hμmod⁡q since we have(6)A′·sigμ≡A+B·sigμ≡A·sigμ≡Hμmod⁡q.Weak Key Substitution Attack. We now present a weak key substitution attack on the GPV signature scheme. In the proposed attack, we assume that the signer acts as an attacker to undermine the nonrepudiation property of the signature scheme and so the attacker knows sk=T.Suppose that a valid signaturesigμ∈Zm on a message μ∈{0,1}∗ under the public key pk=A∈Zqn×m is given. The attacker proceeds as follows to obtain a new public key pk′ and the corresponding private key sk′ such that sigμ is a valid signature on the message μ under this new public key pk′.(1)
Compute a matrixM∈Zqn×n such that H(μ)∈Zqn is an eigenvector of M with eigenvalue 1; that is, M·H(μ)≡H(μ)mod⁡q.
(a)
M is chosen as an invertible matrix over Zq with eigenvector H(μ) and eigenvalue 1 so that MA has rank n. More precisely, one can construct M=(δi,j) as follows. We may assume that H(μ)=(h1,…,hn)t≠0 and h1,h2≠0. For any α∈Zq∖{0,1}, we set the following.(7)δ1,1=αδ1,2=β=1-αh1h2-1mod⁡qδi,i=1fori∈2,…,nδi,j=0fori,j∉i,i:i=1,…,n∪1,2ThenM is invertible, M·H(μ)≡Hμmod⁡q, and the rank of MA(≠A) is n.(2)
SetA′≡M·Amod⁡q.(3)
Outputpk′=A′ and sigμ as a signature on the message μ under the public key pk′, and output T as a private key of pk′.Noting that the private keysk=T corresponding to the public key pk=A satisfies A′·T≡M·A·T≡0mod⁡q, we know that T is also a private key of the new public key pk′=A′. Thus, the attacker who knows sk also knows the private key sk′ of pk′.The validity ofsigμ as a signature on the message μ under the new public key pk′ follows from the facts below:(i)
sigμ<mβ since sigμ is a valid signature.(ii)
A′·sigμ≡Hμmod⁡q since we have(8)A′·sigμ≡M·A·sigμ≡M·Hμ≡Hμmod⁡q.Therefore, the attacker, who was the original signer, has succeeded in a weak strong key substitution attack on the GPV signature scheme.


## 3.2. Attacks on Lyubashevsky’s Signature Scheme

Description of Lyubashevsky’s Signature Scheme. We describe Lyubashevsky’s signature scheme based on SIS problem [8].KeyGen.LYU(1κ): On the given input 1κ, the algorithm samples two matrices (A,S), where A∈Zqn×m is a matrix of rank n and S∈[-d,d]m×k. The algorithm computes T∈Zqn×k satisfying T≡ASmod⁡q. The algorithm sets an integer γ such that 2γkγ≥2κ and sets η∈R so that Prz←Dσm[z≤ηmσ]≤1-2κ. The key generation algorithm also sets a hash function H:{0,1}∗→{v:v∈{-1,0,1}k,v1≤γ} and outputs public parameters pp=(A,H,B2:=ησm) and a pair of public key and private key (pk=T,sk=S).Sign.LYU(pp,sk,μ∈0,1∗): On the given inputs pp,sk, and a message μ, the algorithm samples an m-dimensional vector y from Dσm, then computes c=H(Ay,μ), and finally obtains z≡Sc+ymod⁡q by applying the rejection sampling algorithm. The signature algorithm only outputs (z,c) as a signature with probability min{Dσm/MDSc,σm,1}. If nothing is printed, run the algorithm again until some signature is outputted.Verify.LYU(pp,pk,μ,sig=(z,c)): On the given inputs pp,sk,μ,sigμ, the algorithm outputs 1 if and only if (9)z≤B2andc=HAz-Tcmod⁡q,μ.Strong Key Substitution Attack. Suppose that a valid signature sigμ=(z,c)∈Zqm×Zqk on a message μ∈{0,1}∗ under the public key pk=T∈Zqn×k is given. One proceeds as follows to obtain a new public key pk′ such that sigμ is a valid signature on the message μ under the new public key pk′.(1)
Compute a matrixB∈Zqn×k such that B·c≡0mod⁡q. It is easy to compute B in a similar way that is described in the strong key substitution attack on the GPV signature scheme.(2)
SetT′≡T+Bmod⁡q.(3)
Outputpk′=T′ and sigμ as a signature on the message μ under the public key pk′.The validity ofsigμ=(z,c)∈Zqm×Zqk as a signature on the message μ under the new public key pk′ follows from the facts below:(i)
z≤ησm since sigμ=(z,c) is a valid signature.(ii)
H(Az-T′cmod⁡q,μ)=c since we have(10)Az-T′c≡Az-T+Bc≡Az-Tcmod⁡q,c=HAz-Tcmod⁡q,μ.Weak Key Substitution Attack. We now present a weak key substitution attack on Lyubashevsky’s signature scheme. Suppose that a valid signature sigμ=(z,c)∈Zqm×Zqk on a message μ∈{0,1}∗ under the public key pk=T∈Zqn×k is given. As we have commented before, the signer is an attacker and it is assumed that the attacker knows sk=S such that AS≡Tmod⁡q. The attacker proceeds as follows to obtain a new public key pk′ such that sigμ is a valid signature on the message μ under the new public key pk′.(1)
Compute a matrixS′∈[-d,d]m×k satisfying S′·c≡0mod⁡q.
(i)
With high probability, we may assume thatc=(c1,…,ck)t∈{-1,0,1}k has at least two nonzero components, say c1 and c2. Let S=(s1,…,sk) and sj=(s1j,…,smj)t with sij∈[-d,d]. We also assume(11)s11,s12∉d,d,-d,-d,-d,d,d,-d,which occurs with overwhelming probability. Letϵ∈{1,-1} which will be determined later. We set S′=(s1′,…,sk′) as follows.(12)s1′=ϵc2,0,…,0ts2′=-ϵc1,0,…,0tsl′=0,…,0tforl≠1,2Then, it satisfies thatS′·c≡s1′c1+s2′c2≡0mod⁡q.LetS′′=S+S′∈[-d,d]m×k. The only terms of S′′ differing from S are s11′′=s11+ϵc2 and s12′′=s12-ϵc1. If s11,s12<d, then one can choose any ϵ∈{-1,1}. If s11=±d and s12<d, then set ϵ so that ϵc2=∓1. If s12=±d and s11<d, then set ϵ so that ϵc1=±1.(2)
SetT′≡T+A·S′mod⁡q.(3)
Outputpk′=T′ and sigμ as a signature on μ under the public key pk′.Note thatsk′=S+S′ is a valid private key corresponding to pk′=T′ since T′≡(T+A·S′)≡A·S+S′mod⁡q and S+S′∈[-d,d]m×k. Therefore, the attacker, who knows sk=S such that T≡ASmod⁡q also knows the private key sk′=S+S′ of pk′.The validity ofsigμ=(z,c)∈Zqm×Zqk as a signature on the message μ under the new public key pk′ follows from the facts below:(i)
z≤ησm since sigμ=(z,c) is a valid signature.(ii)
H(Az-T′cmod⁡q,μ)=c since we have(13)Az-T′c≡Az-T+A·S′c≡Az-Tcmod⁡q,c=HAz-Tcmod⁡q,μ.Therefore, the attacker, who was the original signer, has succeeded in a weak key substitution attack on Lyubashevsky’s signature scheme.


## 3.3. Attacks on BLISS Signature Scheme

BLISS [9] is possibly one of the most efficient lattice-based signature schemes. It has been implemented in both software and hardware and boasts implementation efficiency comparable to classical factoring and discrete-logarithm-based schemes. BLISS can be seen as a ring-based optimization of the earlier lattice-based scheme of Lyubashevsky, sharing the same “Fiat-Shamir with aborts” structure.The security of the BLISS signature scheme is based on the hardness of theR-SISq,n,m,β problem which is the ring variant of the SIS problem. We first describe the matrix version of BLISS signature scheme and then explain its ring version. For more detailed descriptions and definition of the R-SISq,n,m,β problem, we refer to [9]. The scheme construction and proof work for matrix version are equally well for ring version, when instantiated with polynomials.In this subsection, we will assume thatq is a prime such that q≡1(mod⁡2n) and n is a power of 2. For any integer q, we define the quotient ring Rq=Zq[x]/(xn+1) and R2q=Z2q[x]/(xn+1).LetB={0,1} and T={-1,0,1} be the set of binary and ternary integers, respectively. We define Bωn (resp., Tωn ), the set of binary vectors (resp., ternary vectors) of length n and Hamming weight ω (i.e., vectors with exactly ω out of n nonzero entries). Depending on the context, we consider Bωn and Tωn as a subset of Z2qn or R2q and regard bold lower case letters as vectors or polynomials. For every integer x in the range -q,q and any positive integer d, x can be uniquely written x=xd·2d+[xmod⁡2d], where [xmod⁡2d]∈-2d-1,2d-1. For every integer vector x=(xi)1≤i≤n, xd denotes xid1≤i≤n. Let v1∣v2 denote the concatenation of two vectors v1 and v2.


### 3.3.1. Matrix Version of BLISS

Description of the Matrix Version of BLISS. We describe the key generation algorithm KeyGen.mBLISS, signature generation algorithm Sign.mBLISS, and verification algorithm Verify.mBLISS of the matrix version of the BLISS signature scheme.KeyGen.mBLISS(1κ): On the given input 1κ, the algorithm outputs the key pair (pk=A,sk=S) such that S∈Zm×n2q has a small norm, A∈Z2qn×m, and AS≡qInmod⁡2q. The algorithm set η∈R so that Prz←Dσm[z≤ηmσ]≤1-2κ. Let H denote a hash function H:{0,1}∗→Bωn. The algorithm also outputs public parameter pp=(H,σ,B2:=ηmσ).Sign.mBLISS(pp,sk,pk,μ∈0,1∗): On the given inputs pp, sk, pk, and a message μ, the algorithm computes a signature sigμ=(z,c) of the message μ as follows:
(1)
y←Dσm.(2)
c←H(Aymod⁡2q,μ).(3)
Choose a random bitb∈{0,1}.(4)
z←y+(-1)bSc.(5)
Output(z,c) with probability 1/(Mexp⁡-Sc2/2σ2coshz,Sc/σ2); otherwiserestart.Verify.mBLISS(pp,pk,μ,sigμ): On the given inputs pp,pk,μ, and a signature sigμ=(z,c), the algorithm accepts or rejects the signature according to the following steps:
(1)
Ifz>B2, then output 0.(2)
Ifz∞≥q/4, then output 0.(3)
Output 1 if and only ifc=H(Az+qcmod⁡2q,μ).Note that the signer outputs the signature(z,c) where z is distributed according to Dσm. It can be seen from Lemma 7 by taking gv=(1/2)DSc,σm+(1/2)D-Sc,σm and f=Dσm where v=Sc.Strong Key Substitution Attack. We present a strong key substitution attack on the matrix version of BLISS signature scheme.Suppose that a valid signaturesigμ=(z,c)∈Z2qm×Z2qm on a message μ∈{0,1}∗ under the public key pk=A∈Z2qn×m is given. One proceeds as follows to obtain a new public key pk′ such that the signature sigμ=(z,c) is a valid signature on the message μ under the new public key pk′.To succeed in strong key substitution attack, it is enough to find a new matrixA′∈Z2qn×m such that c=H(A′z+qcmod⁡2q,μ), which holds when A′z≡Azmod⁡2q. In the following we show how to find such a matrix A′.(1)
We may assume that there existsj∈{1,…,m} such that zj is invertible modulo 2q.(2)
Lett=(t1,…,tn)T=Azmod⁡2q and z=(z1,…,zm)T. For each i∈{1,…,n}, choose ai,1′,…,ai,j-1′,ai,j+1′,…,ai,m′ uniformly at random from Z2q, and then compute ai,j′≡zj-1ti-∑1≤k≠j≤mai,k′zkmod⁡2q.(3)
Defining a matrixA′=(ai,j′)∈Z2qn×m, we have A′z≡tmod⁡2q because of step (2).(4)
Outputpk′=A′ and sigμ=(z,c) as a signature on the message μ under the public key pk′.We note that the validity ofsigμ=(z,c) as a signature on the message μ under pk′=A′ can be checked as follows:(i)
z2≤B2 and z∞<q/4 since sigμ is a valid signature.(ii)
The equationA′z+qc≡Az+qcmod⁡2q implies that c=H(Az+qcmod⁡2q,μ)=H(A′z+qcmod⁡2q,μ).The described attack succeeds unless there is noj∈{1,…,m} such that zj is invertible in Z2q. Note that the signer outputs the signature (z,c) where z is distributed according to Dσm by Lemma 7. Therefore it is enough to estimate the success probability of our attack for z←Dσm. Let f(x)=e-x2/(2σ2) and a be a positive real number. Since f is a nonincreasing function in [0,∞), ∑x=0∞f(x)≥∫0∞f(x)dx and ∑x=1∞f(ax)≤(1/a)∫0∞f(x)dx. We thus have f(Z)=∑x∈Zf(x)≥∫-∞∞f(x)dx-f(0)=2πσ-1 and f(aZ)=∑x∈Zf(ax)≤1+1/a∫-∞∞f(x)dx=1+2πσ/a. We also note that Prz←Dσmz=a=∏1≤i≤mPrzi←Dσm[zi=ai] for any a∈Zm. Then (14)Prz←Dσmzjis  non-invertible  modulo2q=Przj←Dσ⁡zjis  non-invertible  modulo2q≤∑zj≡0mod⁡2ρσzj+∑zj≡0mod⁡qρσzj∑zj∈Zρσzj=ρσ2Z+ρσqZρσZ≤12+1q+ϵ, where ϵ=(5q+2)/2q(2πσ-1)<0.013 for parameters proposed in BLISS (σ≥100). This implies that the probability that all of z1,…,zm are noninvertible modulo 2q is at most (1/2+1/q+ϵ)m. Thus, the success probability of our attack is at least 1-(1/2+1/q+ϵ)m which is very high.Weak Key Substitution Attack. We now present a weak key substitution attack on the matrix version of BLISS signature scheme.Suppose that a valid signaturesigμ=(z,c)∈Z2qm×Z2qm on a message μ∈{0,1}∗ under the public key pk=A∈Z2qn×m is given. The signer, who owns pk=A and sk=S such that AS≡qInmod⁡2q, proceeds as follows to obtain a new public key pk′=A′ and the corresponding private key sk′=S′ such that the signature sigμ=(z,c) is a valid signature on the message μ under the new public key pk′. To succeed in weak key substitution attack, it is sufficient to find matrices A′ and S′ such that A′z≡Azmod⁡2q and A′S′≡qInmod⁡2q. In the following we show how to find such matrices A′ and S′.(1)
Compute a matrixM∈Z2qn×n such that M≡Inmod⁡2 and MAz≡Azmod⁡q, which imply that MAz≡Azmod⁡2q.
(a)
Computing such a matrix,M is easy if Az≢0mod⁡q. We first compute a matrix Y∈Zqn×n such that Y·Az≡0mod⁡q. We then set M=2Y+Inmod⁡2q. It is clear to see that M≡Inmod⁡2 and MAz≡Azmod⁡q.(2)
We setpk′=A′=MAmod⁡2q.Sincepk=A and sk=S satisfy AS≡qInmod⁡2q, we have AS≡0mod⁡q and AS≡Inmod⁡2. From the construction of M, we also have MAS≡0mod⁡q and MAS≡Inmod⁡2, which imply A′S≡qInmod⁡2q. Thus, the signer obtains a valid key pair pk′=A′ and sk′=S.The validity ofsigμ=(z,c) as a signature on the message μ under the public key pk′=A′ can be checked as follows:(i)
z2≤B2 and z∞≤q/4 since sigμ is a valid signature.(ii)
c=H(A′z+qcmod⁡2q,μ) from the following equations: (15)c=HAz+qcmod⁡2q,μandAz≡MAz≡A′zmod⁡2q.Therefore, the signer of the signaturesigμ=(z,c) succeeds in a weak key substitution attack on the matrix version of BLISS signature scheme.


### 3.3.2. Ring Version of BLISS

Description of the Ring Version of BLISS. We describe the key generation algorithm KeyGen.BLISS, signature generation algorithm Sign.BLISS, and verification algorithm Verify.BLISS of the ring version of the BLISS signature scheme. Let us define p=⌊2q/2d⌋ where d is the number of dropped bits, and ζ such that ζ·(q-2)≡1mod⁡2q.The notationf(x)←Dσn means that f(x)=∑0≤i<nfixi and (f0,…,fn-1) are sampled from the distribution Dσn.ForS=(s1,s2)T∈R2q and an integer τ≤n, define (16)NτS=maxI⊂1,…,n#I=τ∑i∈ImaxJ⊂1,…,n#J=τ⁡∑j∈JTi,j,where T=(Ti,j)=S^TS^∈Rn×n and S^=(S^1,S^2)T is a matrix in R2n×n such that j-th column of S^i∈Rn×n is the coefficient vector of polynomial sixj-1mod⁡xn+1 for i=1,2 and j=1,…,n.KeyGen.BLISS(1κ): On the given input 1κ, the algorithm outputs the key pair (pk=A,sk=S) generated as follows. We note that a key pair (A,S) satisfies AS≡qmod⁡2q. The algorithm sets η∈R so that Prz←Dσ2n[z≤η2nσ]≤1-2κ. The algorithm also sets a positive integer τ≤n and a constant C so that 25% of the keys are accepted. Let H denote a hash function H:{0,1}∗→Bωn. The algorithm also outputs public parameter pp=(H,σ,B2:=ηnσ,B∞) where 2B∞+(2d+1)<q/2.
(1)
Choosef,g as uniform polynomials of degree less than n with exactly d1=⌈δ1n⌉ entries in {±1}, d2=⌈δ2n⌉ entries in {±2}, and other entries in {0} where 0≤δ1<1 and 0≤δ2<1 are given densities.(2)
S=(s1,s2)T←(f,2g+1)T.(3)
IfNτ(S)≥C2·5·(⌈δ1n⌉+4⌈δ2n⌉)·τ, thenrestart.(4)
aq←(2g+1)/fmod⁡q (restart if f is not invertible).(5)
A=(a1,q-2)←(2aq,q-2)mod⁡2q.Sign.BLISS(pp,sk,pk,μ∈{0,1}∗): On the given inputs pp, sk, pk, and a message μ, the algorithm computes a signature sigμ=(z1,z2†,c) of the message μ as follows:
(1)
y1,y2←Dσn.(2)
u←ζ·a1·y1+y2mod⁡2q.(3)
c←H(⌊udmod⁡p,μ).(4)
Choose a random bitb.(5)
z1←y1+(-1)bs1c.(6)
z2←y2+(-1)bs2c.(7)
Continue with probability 1/(Mexp⁡-Sc2/2σ2cosh⁡z,Sc/σ2); otherwiserestart.(8)
z2†←ud-u-z2dmod⁡p.(9)
Output(z1,z2†,c).Verify.BLISS(pp,pk,μ,sigμ): On the given inputs pp,pk,μ,sigμ=(z1,z2†,c), the algorithm accepts or rejects the signature according to the following steps:
(1)
z←z1∣(2d·z2†).(2)
Ifz2>B2, then output 0.(3)
Ifz∞>B∞, then output 0.(4)
Output 1 if and only ifc=H(ζ·a1·z1+ζ·q·cd+z2†mod⁡p,μ).As in the matrix version of BLISS, the signer outputs the signature(z1,z2†,c) where z1 is sampled from Dσn by Lemma 7.Strong Key Substitution Attack. Suppose that a valid signature sigμ=(z1,z2†,c)∈R2q×R2q×R2q on a message μ∈0,1∗ under the public key A=(a1,q-2)∈R2q×R2q is given. One proceeds as follows to obtain a new public key pk′ where the signature sigμ is a valid signature on the message μ under the new public key pk′.Since we want to findA′=(a1′,q-2) satisfying the equation (17)Hζ·a1′·z1+ζ·q·cd+z2†mod⁡p,μ=Hζ·a1·z1+ζ·q·cd+z2†mod⁡p,μ,where ζ(q-2)≡1mod⁡2q, it suffices to find a1′∈R2q such that a1′z1≡a1z1mod⁡2q. To find such a polynomial a1′, we consider the greatest common divisor of two polynomials z1 and xn+1. Let gq(x) be the gcd of z1 and xn+1 modulo q, and let g2(x) be the gcd of z1 and xn+1 modulo 2. Since q≡1mod⁡2n, the polynomial xn+1 is completely factorized as a product of distinct linear polynomials modulo q; that is, xn+1≡∏i=1n(x-αi)mod⁡q,αi∈Zq. Since n is a power of two, we also have xn+1≡(x+1)nmod⁡2.Case 1.
Ifgq(x)≠1, there exists i∈{1,…,n} such that z1≡(x-αi)zˇ1mod⁡q for some zˇ1∈Rq. We set h(x)≡(xn+1)/(x-αi)mod⁡q and define a1′≡a1+2hmod⁡(2q,xn+1). In this case, we output A′=(a1′,q-2) as a new public key pk′ and sigμ=(z1,z2†,c) as a signature on the message μ under the public key pk′.Case 2.
Ifg2(x)≠1, we set h(x)≡(xn+1)/(x+1)≡(x+1)n-1mod⁡2 and define a1′≡a1+qhmod⁡2q,xn+1. In this case, we output A′=(a1′,q-2) as a new public key pk′ and sigμ=(z1,z2†,c) as a signature on the message μ under the public key pk′.In both cases, the validity ofsigμ=(z1,z2†,c) as a signature on the message μ under the public key pk′ can be checked as follows:(i)
z1∣(2d·z2†)≤B2 and z1∣(2d·z2†)∞≤B∞ since sigμ is a valid signature.(ii)
In both casesgq≠1 and g2≠1, we have a1z1≡a1′z1mod(2q,xn+1), which implies (18)ζ·a1′·z1+ζ·q·cd+z2†mod⁡p=ζ·a1·z1+ζ·q·cd+z2†mod⁡p.Thus, we havec=H(ζ·a1′·z1+ζ·q·cd+z2†mod⁡p,μ).As described, our attack succeeds whenz1 is noninvertible in R2 or z1 is noninvertible in Rq. Note that the signer outputs the signature (z1,z2†,c) where z1 is distributed according to Dσn by Lemma 7. Therefore it is enough to estimate the success probability of our attack for z1←Dσn. To compute success probability of our attack, we first consider the case that z1 is noninvertible in R2. Recall that, by Lemma 2, if σ≥ηϵ(2Zn), the distribution of (Dσnmod⁡2Zn) is within statistical distance at most 2ϵ of uniform over (Znmod⁡2Zn). Noting that (2Zn)∗=1/2Zn and λ1∞(2Zn)∗=1/2, by Lemma 3, we have (19)ηϵ2Zn≤1λ1∞2Zn∗ln⁡2n/1+1/ϵπ=2ln⁡2n/1+1/ϵπ.Therefore, if σ≥2ln(2n/(1+1/ϵ))/π, then the distribution of (Dσnmod⁡2Zn) is uniform over Zn/2Zn≅Z2n within statistical distance at most 2ϵ. Hence, for z1(x)←Dσn, the probability that z1(x) is not invertible in R2 is greater than or equal to 1/2-2ϵ. This is summarized in the following theorem.Theorem 14.
Ifσ≥2ln(2n/(1+1/ϵ))/π, (20)Prfx←Dσnfxis  non-invertible  inR2≥12-2ϵ.Takingϵ=2-n, we have ηϵ(2Zn)<2ln(n). For the proposed parameter sets for BLISS, we have σ≥100 and n≥256, which imply σ≥2ln(n)≥ηϵ(2Zn). Thus, the probability that z1(x) is noninvertible in R2 is greater than or equal to 1/2-2-n+1.We now consider the case thatz1(x) is noninvertible in Rq. Before continuing we first show that the following theorem holds. Note that this is essentially from [13, Lemma 11].Theorem 15.
Letn≥8 be a power of 2 such that Φ(x)=xn+1 splits into n linear factors modulo prime q≥5 as Φ(x)≡∏i=1n(x-αi)mod⁡q,αi∈Zq. Let ϵ∈(0,1/2) be an arbitrary real number. For i≠j∈{1,…,n}, we have the following. (i)
Ifσ≥nln⁡(2n(1+1/ϵ))/π·q1/n, (21)Prfx←Dσnfαi≡0mod⁡q≥1q-2ϵ.(ii)
Ifσ≥nln⁡(2n(1+1/ϵ))/π·q2/n, (22)Prfx←Dσnfαi≡0mod⁡q∧fαj≡0mod⁡q≤1q2+2ϵ.Proof.
LetI=〈q,x-αi〉 be an ideal of R=Z[x]/Φ(x). From R/I≅Zq[x]/(x-αi)≅Zq, we have N(I)=q and so λ1(I)≤nq1/n by Minkowski’s theorem. Since I is an ideal of R, we have λn(I)=λ1(I), and Lemma 4 gives ηϵ(I)≤ln⁡(2n(1+1/ϵ))/π·λn(I)≤nln⁡(2n(1+1/ϵ))/π·q1/n. Thus, if σ≥nln⁡(2n(1+1/ϵ))/π·q1/n, by Lemma 2, (fmod⁡I) is within statistical distance ≤2ϵ to the uniform distribution on R/I. As a result, we have Prf(x)←Dσn[f(x)≡0mod⁡I]=Prf(x)←Dσn[f(αi)≡0mod⁡q]≥1/q-2ϵ.
LetJ=〈q,(x-αi)(x-αj)〉 be an ideal of R. We then have N(J)=q2 and λ1(J)≤nq2/n, because R/J≅Zq[x]/(x-αi)(x-αj). Lemmas 4 and 2 then show that (fmod⁡J) is within statistical distance ≤2ϵ to the uniform distribution on R/J when σ≥nln⁡(2n(1+1/ϵ))/π·q2/n. On the other hand, since f(x)≡Ax+Bmod⁡J for A=(αi-αj)-1(f(αi)-f(αj))mod⁡q, B=f(αi)-Aαimod⁡q, f(x)≡0mod⁡J is equivalent to f(αi)≡0mod⁡q and f(αj)≡0mod⁡q. Thus, by combining these results, we have Prf(x)←Dσn[f(x)≡0mod⁡J]=Prf(x)←Dσn[f(αi)≡0mod⁡q∧f(αj)≡0mod⁡q]≤1/q2+2ϵ.Ifσ≥nln⁡(2n(1+1/ϵ))/π·q2/n, we have (23)Prz1x←Dσnz1is  non-invertible  inRq=Prz1x←Dσn⋁1≤i≤nz1αi≡0mod⁡q≥∑1≤i≤nPrz1x←Dσn⁡z1αi≡0mod⁡q-∑1≤i≠j≤nPrz1x←Dσn⁡z1αi≡0mod⁡q∧z1αj≡0mod⁡q≥n1q-2ϵ-n21q2+2ϵ=nq-nn-12q2-nn+1ϵ.Takingϵ=q-3, if σ≥nln⁡(2n(1+q3))/π·q2/n, the probability that z1←DZn,σ is noninvertible in Rq is at least n/q-n(n-1)/2q2-n(n+1)/q3, which is nonnegligible in n since in general q is polynomial in n. For the proposed parameter sets of BLISS having at least 128-bit security, we have n=512 and q=12289 and σ>100 always satisfies σ≥nln⁡2n1+q3/π·q2/n; thus the success probability is at least 0.04.Weak Key Substitution Attack. We present a weak key substitution attack on the ring version of the BLISS signature scheme. In this case, our attack is successful only in a very limited case.Suppose that a valid signaturesigμ=(z1,z2†,c) on a message μ∈0,1∗ under the public key pk=(a1,q-2) is given. In weak key substitution attacks the signer who owns the key pair pk=(a1,q-2),sk=(f,2g+1)T wants to obtain a new public key pk′=(a1′,q-2) and the corresponding private key sk′=(s1′,s2′)T so that the signature sigμ is a valid signature on the message μ under the new public key pk′.Similar to the strong key substitution attack on BLISS, it suffices to finda1′∈R2q and (f′,2g′+1) such that a1′z1≡a1z1mod⁡2q and a1′≡(2g′+1)/f′mod⁡q. In the following we show how to find such polynomials.(1)
Compute a polynomialb∈R2q such that bz1=0 in R2q by using a similar method in the strong key substitution attack. This implies that (2b/f)z1=0 in R2q.(2)
We setaq′=aq+(2b)/f in R2q.Sinceaq≡(2g+1)/fmod⁡q, we have aq′≡(2(g+b)+1)/fmod⁡q. However, we cannot guarantee that g′=(g+b) is small enough. Therefore, the signer obtains a valid key pair pk′=(a1′,q-2)=(2aq′,q-2) and sk′=(f′,2g′+1) only if one can make g′ small. One way to get a smaller g′ is to apply a lattice reduction algorithm on the ideal lattice generated by bmod⁡q. However, it does not guarantee that g′ is small enough to be a valid private key.The validity ofsigμ=(z,c) as a signature on the message μ under pk′=A′ can be checked as follows:(i)
z2≤B2 and z∞≤B∞ since sigμ is a valid signature.(ii)
c=H(ζ·a1′·z1+ζ·q·cd+z2†mod⁡p,μ) from the following equalities: c=H(ζ·a1·z1+ζ·q·cd+z2†mod⁡p,μ)anda1·z1≡a1′·z1mod⁡2q.Therefore, the signer ofsigμ=(z,c) succeeds in a weak key substitution attack on BLISS of ring version as long as g′ is small enough for a valid private key.


## 3.3.1. Matrix Version of BLISS

Description of the Matrix Version of BLISS. We describe the key generation algorithm KeyGen.mBLISS, signature generation algorithm Sign.mBLISS, and verification algorithm Verify.mBLISS of the matrix version of the BLISS signature scheme.KeyGen.mBLISS(1κ): On the given input 1κ, the algorithm outputs the key pair (pk=A,sk=S) such that S∈Zm×n2q has a small norm, A∈Z2qn×m, and AS≡qInmod⁡2q. The algorithm set η∈R so that Prz←Dσm[z≤ηmσ]≤1-2κ. Let H denote a hash function H:{0,1}∗→Bωn. The algorithm also outputs public parameter pp=(H,σ,B2:=ηmσ).Sign.mBLISS(pp,sk,pk,μ∈0,1∗): On the given inputs pp, sk, pk, and a message μ, the algorithm computes a signature sigμ=(z,c) of the message μ as follows:
(1)
y←Dσm.(2)
c←H(Aymod⁡2q,μ).(3)
Choose a random bitb∈{0,1}.(4)
z←y+(-1)bSc.(5)
Output(z,c) with probability 1/(Mexp⁡-Sc2/2σ2coshz,Sc/σ2); otherwiserestart.Verify.mBLISS(pp,pk,μ,sigμ): On the given inputs pp,pk,μ, and a signature sigμ=(z,c), the algorithm accepts or rejects the signature according to the following steps:
(1)
Ifz>B2, then output 0.(2)
Ifz∞≥q/4, then output 0.(3)
Output 1 if and only ifc=H(Az+qcmod⁡2q,μ).Note that the signer outputs the signature(z,c) where z is distributed according to Dσm. It can be seen from Lemma 7 by taking gv=(1/2)DSc,σm+(1/2)D-Sc,σm and f=Dσm where v=Sc.Strong Key Substitution Attack. We present a strong key substitution attack on the matrix version of BLISS signature scheme.Suppose that a valid signaturesigμ=(z,c)∈Z2qm×Z2qm on a message μ∈{0,1}∗ under the public key pk=A∈Z2qn×m is given. One proceeds as follows to obtain a new public key pk′ such that the signature sigμ=(z,c) is a valid signature on the message μ under the new public key pk′.To succeed in strong key substitution attack, it is enough to find a new matrixA′∈Z2qn×m such that c=H(A′z+qcmod⁡2q,μ), which holds when A′z≡Azmod⁡2q. In the following we show how to find such a matrix A′.(1)
We may assume that there existsj∈{1,…,m} such that zj is invertible modulo 2q.(2)
Lett=(t1,…,tn)T=Azmod⁡2q and z=(z1,…,zm)T. For each i∈{1,…,n}, choose ai,1′,…,ai,j-1′,ai,j+1′,…,ai,m′ uniformly at random from Z2q, and then compute ai,j′≡zj-1ti-∑1≤k≠j≤mai,k′zkmod⁡2q.(3)
Defining a matrixA′=(ai,j′)∈Z2qn×m, we have A′z≡tmod⁡2q because of step (2).(4)
Outputpk′=A′ and sigμ=(z,c) as a signature on the message μ under the public key pk′.We note that the validity ofsigμ=(z,c) as a signature on the message μ under pk′=A′ can be checked as follows:(i)
z2≤B2 and z∞<q/4 since sigμ is a valid signature.(ii)
The equationA′z+qc≡Az+qcmod⁡2q implies that c=H(Az+qcmod⁡2q,μ)=H(A′z+qcmod⁡2q,μ).The described attack succeeds unless there is noj∈{1,…,m} such that zj is invertible in Z2q. Note that the signer outputs the signature (z,c) where z is distributed according to Dσm by Lemma 7. Therefore it is enough to estimate the success probability of our attack for z←Dσm. Let f(x)=e-x2/(2σ2) and a be a positive real number. Since f is a nonincreasing function in [0,∞), ∑x=0∞f(x)≥∫0∞f(x)dx and ∑x=1∞f(ax)≤(1/a)∫0∞f(x)dx. We thus have f(Z)=∑x∈Zf(x)≥∫-∞∞f(x)dx-f(0)=2πσ-1 and f(aZ)=∑x∈Zf(ax)≤1+1/a∫-∞∞f(x)dx=1+2πσ/a. We also note that Prz←Dσmz=a=∏1≤i≤mPrzi←Dσm[zi=ai] for any a∈Zm. Then (14)Prz←Dσmzjis  non-invertible  modulo2q=Przj←Dσ⁡zjis  non-invertible  modulo2q≤∑zj≡0mod⁡2ρσzj+∑zj≡0mod⁡qρσzj∑zj∈Zρσzj=ρσ2Z+ρσqZρσZ≤12+1q+ϵ, where ϵ=(5q+2)/2q(2πσ-1)<0.013 for parameters proposed in BLISS (σ≥100). This implies that the probability that all of z1,…,zm are noninvertible modulo 2q is at most (1/2+1/q+ϵ)m. Thus, the success probability of our attack is at least 1-(1/2+1/q+ϵ)m which is very high.Weak Key Substitution Attack. We now present a weak key substitution attack on the matrix version of BLISS signature scheme.Suppose that a valid signaturesigμ=(z,c)∈Z2qm×Z2qm on a message μ∈{0,1}∗ under the public key pk=A∈Z2qn×m is given. The signer, who owns pk=A and sk=S such that AS≡qInmod⁡2q, proceeds as follows to obtain a new public key pk′=A′ and the corresponding private key sk′=S′ such that the signature sigμ=(z,c) is a valid signature on the message μ under the new public key pk′. To succeed in weak key substitution attack, it is sufficient to find matrices A′ and S′ such that A′z≡Azmod⁡2q and A′S′≡qInmod⁡2q. In the following we show how to find such matrices A′ and S′.(1)
Compute a matrixM∈Z2qn×n such that M≡Inmod⁡2 and MAz≡Azmod⁡q, which imply that MAz≡Azmod⁡2q.
(a)
Computing such a matrix,M is easy if Az≢0mod⁡q. We first compute a matrix Y∈Zqn×n such that Y·Az≡0mod⁡q. We then set M=2Y+Inmod⁡2q. It is clear to see that M≡Inmod⁡2 and MAz≡Azmod⁡q.(2)
We setpk′=A′=MAmod⁡2q.Sincepk=A and sk=S satisfy AS≡qInmod⁡2q, we have AS≡0mod⁡q and AS≡Inmod⁡2. From the construction of M, we also have MAS≡0mod⁡q and MAS≡Inmod⁡2, which imply A′S≡qInmod⁡2q. Thus, the signer obtains a valid key pair pk′=A′ and sk′=S.The validity ofsigμ=(z,c) as a signature on the message μ under the public key pk′=A′ can be checked as follows:(i)
z2≤B2 and z∞≤q/4 since sigμ is a valid signature.(ii)
c=H(A′z+qcmod⁡2q,μ) from the following equations: (15)c=HAz+qcmod⁡2q,μandAz≡MAz≡A′zmod⁡2q.Therefore, the signer of the signaturesigμ=(z,c) succeeds in a weak key substitution attack on the matrix version of BLISS signature scheme.


## 3.3.2. Ring Version of BLISS

Description of the Ring Version of BLISS. We describe the key generation algorithm KeyGen.BLISS, signature generation algorithm Sign.BLISS, and verification algorithm Verify.BLISS of the ring version of the BLISS signature scheme. Let us define p=⌊2q/2d⌋ where d is the number of dropped bits, and ζ such that ζ·(q-2)≡1mod⁡2q.The notationf(x)←Dσn means that f(x)=∑0≤i<nfixi and (f0,…,fn-1) are sampled from the distribution Dσn.ForS=(s1,s2)T∈R2q and an integer τ≤n, define (16)NτS=maxI⊂1,…,n#I=τ∑i∈ImaxJ⊂1,…,n#J=τ⁡∑j∈JTi,j,where T=(Ti,j)=S^TS^∈Rn×n and S^=(S^1,S^2)T is a matrix in R2n×n such that j-th column of S^i∈Rn×n is the coefficient vector of polynomial sixj-1mod⁡xn+1 for i=1,2 and j=1,…,n.KeyGen.BLISS(1κ): On the given input 1κ, the algorithm outputs the key pair (pk=A,sk=S) generated as follows. We note that a key pair (A,S) satisfies AS≡qmod⁡2q. The algorithm sets η∈R so that Prz←Dσ2n[z≤η2nσ]≤1-2κ. The algorithm also sets a positive integer τ≤n and a constant C so that 25% of the keys are accepted. Let H denote a hash function H:{0,1}∗→Bωn. The algorithm also outputs public parameter pp=(H,σ,B2:=ηnσ,B∞) where 2B∞+(2d+1)<q/2.
(1)
Choosef,g as uniform polynomials of degree less than n with exactly d1=⌈δ1n⌉ entries in {±1}, d2=⌈δ2n⌉ entries in {±2}, and other entries in {0} where 0≤δ1<1 and 0≤δ2<1 are given densities.(2)
S=(s1,s2)T←(f,2g+1)T.(3)
IfNτ(S)≥C2·5·(⌈δ1n⌉+4⌈δ2n⌉)·τ, thenrestart.(4)
aq←(2g+1)/fmod⁡q (restart if f is not invertible).(5)
A=(a1,q-2)←(2aq,q-2)mod⁡2q.Sign.BLISS(pp,sk,pk,μ∈{0,1}∗): On the given inputs pp, sk, pk, and a message μ, the algorithm computes a signature sigμ=(z1,z2†,c) of the message μ as follows:
(1)
y1,y2←Dσn.(2)
u←ζ·a1·y1+y2mod⁡2q.(3)
c←H(⌊udmod⁡p,μ).(4)
Choose a random bitb.(5)
z1←y1+(-1)bs1c.(6)
z2←y2+(-1)bs2c.(7)
Continue with probability 1/(Mexp⁡-Sc2/2σ2cosh⁡z,Sc/σ2); otherwiserestart.(8)
z2†←ud-u-z2dmod⁡p.(9)
Output(z1,z2†,c).Verify.BLISS(pp,pk,μ,sigμ): On the given inputs pp,pk,μ,sigμ=(z1,z2†,c), the algorithm accepts or rejects the signature according to the following steps:
(1)
z←z1∣(2d·z2†).(2)
Ifz2>B2, then output 0.(3)
Ifz∞>B∞, then output 0.(4)
Output 1 if and only ifc=H(ζ·a1·z1+ζ·q·cd+z2†mod⁡p,μ).As in the matrix version of BLISS, the signer outputs the signature(z1,z2†,c) where z1 is sampled from Dσn by Lemma 7.Strong Key Substitution Attack. Suppose that a valid signature sigμ=(z1,z2†,c)∈R2q×R2q×R2q on a message μ∈0,1∗ under the public key A=(a1,q-2)∈R2q×R2q is given. One proceeds as follows to obtain a new public key pk′ where the signature sigμ is a valid signature on the message μ under the new public key pk′.Since we want to findA′=(a1′,q-2) satisfying the equation (17)Hζ·a1′·z1+ζ·q·cd+z2†mod⁡p,μ=Hζ·a1·z1+ζ·q·cd+z2†mod⁡p,μ,where ζ(q-2)≡1mod⁡2q, it suffices to find a1′∈R2q such that a1′z1≡a1z1mod⁡2q. To find such a polynomial a1′, we consider the greatest common divisor of two polynomials z1 and xn+1. Let gq(x) be the gcd of z1 and xn+1 modulo q, and let g2(x) be the gcd of z1 and xn+1 modulo 2. Since q≡1mod⁡2n, the polynomial xn+1 is completely factorized as a product of distinct linear polynomials modulo q; that is, xn+1≡∏i=1n(x-αi)mod⁡q,αi∈Zq. Since n is a power of two, we also have xn+1≡(x+1)nmod⁡2.Case 1.
Ifgq(x)≠1, there exists i∈{1,…,n} such that z1≡(x-αi)zˇ1mod⁡q for some zˇ1∈Rq. We set h(x)≡(xn+1)/(x-αi)mod⁡q and define a1′≡a1+2hmod⁡(2q,xn+1). In this case, we output A′=(a1′,q-2) as a new public key pk′ and sigμ=(z1,z2†,c) as a signature on the message μ under the public key pk′.Case 2.
Ifg2(x)≠1, we set h(x)≡(xn+1)/(x+1)≡(x+1)n-1mod⁡2 and define a1′≡a1+qhmod⁡2q,xn+1. In this case, we output A′=(a1′,q-2) as a new public key pk′ and sigμ=(z1,z2†,c) as a signature on the message μ under the public key pk′.In both cases, the validity ofsigμ=(z1,z2†,c) as a signature on the message μ under the public key pk′ can be checked as follows:(i)
z1∣(2d·z2†)≤B2 and z1∣(2d·z2†)∞≤B∞ since sigμ is a valid signature.(ii)
In both casesgq≠1 and g2≠1, we have a1z1≡a1′z1mod(2q,xn+1), which implies (18)ζ·a1′·z1+ζ·q·cd+z2†mod⁡p=ζ·a1·z1+ζ·q·cd+z2†mod⁡p.Thus, we havec=H(ζ·a1′·z1+ζ·q·cd+z2†mod⁡p,μ).As described, our attack succeeds whenz1 is noninvertible in R2 or z1 is noninvertible in Rq. Note that the signer outputs the signature (z1,z2†,c) where z1 is distributed according to Dσn by Lemma 7. Therefore it is enough to estimate the success probability of our attack for z1←Dσn. To compute success probability of our attack, we first consider the case that z1 is noninvertible in R2. Recall that, by Lemma 2, if σ≥ηϵ(2Zn), the distribution of (Dσnmod⁡2Zn) is within statistical distance at most 2ϵ of uniform over (Znmod⁡2Zn). Noting that (2Zn)∗=1/2Zn and λ1∞(2Zn)∗=1/2, by Lemma 3, we have (19)ηϵ2Zn≤1λ1∞2Zn∗ln⁡2n/1+1/ϵπ=2ln⁡2n/1+1/ϵπ.Therefore, if σ≥2ln(2n/(1+1/ϵ))/π, then the distribution of (Dσnmod⁡2Zn) is uniform over Zn/2Zn≅Z2n within statistical distance at most 2ϵ. Hence, for z1(x)←Dσn, the probability that z1(x) is not invertible in R2 is greater than or equal to 1/2-2ϵ. This is summarized in the following theorem.Theorem 14.
Ifσ≥2ln(2n/(1+1/ϵ))/π, (20)Prfx←Dσnfxis  non-invertible  inR2≥12-2ϵ.Takingϵ=2-n, we have ηϵ(2Zn)<2ln(n). For the proposed parameter sets for BLISS, we have σ≥100 and n≥256, which imply σ≥2ln(n)≥ηϵ(2Zn). Thus, the probability that z1(x) is noninvertible in R2 is greater than or equal to 1/2-2-n+1.We now consider the case thatz1(x) is noninvertible in Rq. Before continuing we first show that the following theorem holds. Note that this is essentially from [13, Lemma 11].Theorem 15.
Letn≥8 be a power of 2 such that Φ(x)=xn+1 splits into n linear factors modulo prime q≥5 as Φ(x)≡∏i=1n(x-αi)mod⁡q,αi∈Zq. Let ϵ∈(0,1/2) be an arbitrary real number. For i≠j∈{1,…,n}, we have the following. (i)
Ifσ≥nln⁡(2n(1+1/ϵ))/π·q1/n, (21)Prfx←Dσnfαi≡0mod⁡q≥1q-2ϵ.(ii)
Ifσ≥nln⁡(2n(1+1/ϵ))/π·q2/n, (22)Prfx←Dσnfαi≡0mod⁡q∧fαj≡0mod⁡q≤1q2+2ϵ.Proof.
LetI=〈q,x-αi〉 be an ideal of R=Z[x]/Φ(x). From R/I≅Zq[x]/(x-αi)≅Zq, we have N(I)=q and so λ1(I)≤nq1/n by Minkowski’s theorem. Since I is an ideal of R, we have λn(I)=λ1(I), and Lemma 4 gives ηϵ(I)≤ln⁡(2n(1+1/ϵ))/π·λn(I)≤nln⁡(2n(1+1/ϵ))/π·q1/n. Thus, if σ≥nln⁡(2n(1+1/ϵ))/π·q1/n, by Lemma 2, (fmod⁡I) is within statistical distance ≤2ϵ to the uniform distribution on R/I. As a result, we have Prf(x)←Dσn[f(x)≡0mod⁡I]=Prf(x)←Dσn[f(αi)≡0mod⁡q]≥1/q-2ϵ.
LetJ=〈q,(x-αi)(x-αj)〉 be an ideal of R. We then have N(J)=q2 and λ1(J)≤nq2/n, because R/J≅Zq[x]/(x-αi)(x-αj). Lemmas 4 and 2 then show that (fmod⁡J) is within statistical distance ≤2ϵ to the uniform distribution on R/J when σ≥nln⁡(2n(1+1/ϵ))/π·q2/n. On the other hand, since f(x)≡Ax+Bmod⁡J for A=(αi-αj)-1(f(αi)-f(αj))mod⁡q, B=f(αi)-Aαimod⁡q, f(x)≡0mod⁡J is equivalent to f(αi)≡0mod⁡q and f(αj)≡0mod⁡q. Thus, by combining these results, we have Prf(x)←Dσn[f(x)≡0mod⁡J]=Prf(x)←Dσn[f(αi)≡0mod⁡q∧f(αj)≡0mod⁡q]≤1/q2+2ϵ.Ifσ≥nln⁡(2n(1+1/ϵ))/π·q2/n, we have (23)Prz1x←Dσnz1is  non-invertible  inRq=Prz1x←Dσn⋁1≤i≤nz1αi≡0mod⁡q≥∑1≤i≤nPrz1x←Dσn⁡z1αi≡0mod⁡q-∑1≤i≠j≤nPrz1x←Dσn⁡z1αi≡0mod⁡q∧z1αj≡0mod⁡q≥n1q-2ϵ-n21q2+2ϵ=nq-nn-12q2-nn+1ϵ.Takingϵ=q-3, if σ≥nln⁡(2n(1+q3))/π·q2/n, the probability that z1←DZn,σ is noninvertible in Rq is at least n/q-n(n-1)/2q2-n(n+1)/q3, which is nonnegligible in n since in general q is polynomial in n. For the proposed parameter sets of BLISS having at least 128-bit security, we have n=512 and q=12289 and σ>100 always satisfies σ≥nln⁡2n1+q3/π·q2/n; thus the success probability is at least 0.04.Weak Key Substitution Attack. We present a weak key substitution attack on the ring version of the BLISS signature scheme. In this case, our attack is successful only in a very limited case.Suppose that a valid signaturesigμ=(z1,z2†,c) on a message μ∈0,1∗ under the public key pk=(a1,q-2) is given. In weak key substitution attacks the signer who owns the key pair pk=(a1,q-2),sk=(f,2g+1)T wants to obtain a new public key pk′=(a1′,q-2) and the corresponding private key sk′=(s1′,s2′)T so that the signature sigμ is a valid signature on the message μ under the new public key pk′.Similar to the strong key substitution attack on BLISS, it suffices to finda1′∈R2q and (f′,2g′+1) such that a1′z1≡a1z1mod⁡2q and a1′≡(2g′+1)/f′mod⁡q. In the following we show how to find such polynomials.(1)
Compute a polynomialb∈R2q such that bz1=0 in R2q by using a similar method in the strong key substitution attack. This implies that (2b/f)z1=0 in R2q.(2)
We setaq′=aq+(2b)/f in R2q.Sinceaq≡(2g+1)/fmod⁡q, we have aq′≡(2(g+b)+1)/fmod⁡q. However, we cannot guarantee that g′=(g+b) is small enough. Therefore, the signer obtains a valid key pair pk′=(a1′,q-2)=(2aq′,q-2) and sk′=(f′,2g′+1) only if one can make g′ small. One way to get a smaller g′ is to apply a lattice reduction algorithm on the ideal lattice generated by bmod⁡q. However, it does not guarantee that g′ is small enough to be a valid private key.The validity ofsigμ=(z,c) as a signature on the message μ under pk′=A′ can be checked as follows:(i)
z2≤B2 and z∞≤B∞ since sigμ is a valid signature.(ii)
c=H(ζ·a1′·z1+ζ·q·cd+z2†mod⁡p,μ) from the following equalities: c=H(ζ·a1·z1+ζ·q·cd+z2†mod⁡p,μ)anda1·z1≡a1′·z1mod⁡2q.Therefore, the signer ofsigμ=(z,c) succeeds in a weak key substitution attack on BLISS of ring version as long as g′ is small enough for a valid private key.


## 4. Attack Possibility and Its Defense

### 4.1. Possibility of Key Substitution Attacks

In general, there are two ways for the certificate authority to register a new user as the owner of a public key. One is that the certificate authority (CA) requires users to prove possession of user’s private key before issuing certificates using zero-knowledge proof. The other is that CA only checks whether the public key is different from any previously issued one.Clearly, if CA only checks freshness of public keys to issue certificates, by our strong key substitution attacks, GPV signature scheme, Lyubashevsky’s signature scheme, and BLISS do not provide the nonrepudiation property.Thus, a simple and natural way to prevent strong key substitution attack is to require that CA issues certificate only after checking the possession of private key using zero-knowledge proofs. The problem with this solution is that all known approaches for lattice-based zero-knowledge proofs are not practical. The first zero-knowledge proofs in the lattice setting were introduced by Kawachi et al. and Ling et al. [17, 18]. If one would like to have 128 bits of quantum security, one of the most basic application[19] requires 400KB of total proof size and more complicated applications need more megabytes. Baum and Lyubashevsky [20] give a new approach for constructing amortized zero-knowledge proofs of knowledge of short solutions over polynomial rings. When the number of relations is as small as the security parameter, their proof is practical. However, as the number of samples increases, the protocol has the same efficiency as the previous works. Still, it seems that more researches on the lattice-based zero-knowledge proofs need to be done to design efficient lattice-based authentication systems.Even if CA issues certificates using zero-knowledge proof, in order to provide the nonrepudiation property, it requires that the underlying signature scheme be secure under the weak key substitution attack since any malicious signer can be a successful weak key substitution attacker and repudiates his/her valid signature in the system. Our weak key substitution attacks on GPV signature scheme, Lyubashevsky’s signature scheme, and BLISS show that these schemes cannot provide nonrepudiation of the signatures.


### 4.2. How to Prevent Key Substitution Attacks

Another way to prevent key substitution attack is to modify signature schemes to resist this attack. Menezes and Smart [5] took such an approach and suggested a method, we call it MS conversion, that converts a signature scheme Σ into a new signature scheme MS-Σ by prepend the signer’s public key to the message in some unambiguous way prior to signing (for example, a field of fixed length may be reserved for the public key). By using formatted messages specific to each public key, the goal of the key substitution attack against Σ is converted to compute pk′,pk′∥μ,sig from a valid triple pk,pk∥μ,sig, which was regarded as meaningless by Menezes and Smart [5] since it belongs to message key substitution (MKS) attacks against MS-Σ.However, we note that MS conversion is not enough to guarantee the original meaning of KS security without considering MKS security. The specific MKS attack of computingpk′,pk′∥μ,sig indicates that anyone can use it to claim that the signature sig on the message μ is signed by the user with the public key pk′, which is exactly the goal of key substitution attack. Therefore, it is important to check the infeasibility of computing pk′,pk′∥μ,sig from a valid triple pk,pk∥μ,sig in the MS conversions to guarantee the security against key substitution attacks. Form our analysis, it is straightforward to prove that MS-Lyubashevsky’s signature scheme and MS-BLISS signature scheme are secure against key substitution attacks if the hash function H is collision resistant.Unlike these Fiat-Shamir type signature schemes as Lyubashevsky’s signature scheme and BLISS, we see that the collision resistance of the hash functionH is not enough for the MKS security of MS-GPV signature scheme. The MKS security of MS-GPV scheme introduces the following new problem: given a (A,sigμ,μ) such that A·sigμ≡HA∥μmod⁡q, compute a new A′ satisfying A′·sigμ≡HA′∥μmod⁡q. One can solve this new problem as follows: for a given (A,sigμ,μ),Step 1.
ComputeY=Y∈Zqn×m∣Ysigμ=0mod⁡q.Step 2.
ComputeXY∈Zqn×n and Y∈Y such that (24)HXY·Ymod⁡q∥μ=0.Step 3.
OutputA′=XY·Ymod⁡q.It is clear to see thatA′·sigμ≡HA′∥μmod⁡q. The hardness of this new problem has not been studied for the parameters of the GPV signature. It seems somewhat heuristic, but it needs more research to assess the hardness of the problem and we expect that it is easier than the classical computational problems such as the collision resistance of a hash function or SIS problem.Table1 summarizes the results of our key substitution attacks on three signature schemes and MS conversion.Table 1
Key substitution attacks (KSA) on signature schemes based on SIS problem.
Scheme Target equation for KSA Result GPV [7] A⋅sigμ≡Hμmod⁡q insecure Lyubashevsky [8] c=H(Az-Tcmod⁡q,μ) insecure matrix-BLISS [9] c=H(Az+qcmod⁡2q,μ) insecure ring-BLISS [9] c=H(ζ⋅a1⋅z1+ζ⋅q⋅cd+z2†mod⁡p,μ) i n s e c u r e ‡ M S-GPV A⋅sigμ≡HA∥μmod⁡q unknown M S-Lyubashevsky c = A z - T c mod ⁡ q , T ∥ μ secure M S-matrix-BLISS c=HAz+qcmod⁡2q,A∥μ secure M S-ring-BLISS c=ζ⋅a1⋅c1+ζ⋅q⋅cd+z2†mod⁡p,a1,q-2∥μ secure ‡Insecure under some conditions.


## 4.1. Possibility of Key Substitution Attacks

In general, there are two ways for the certificate authority to register a new user as the owner of a public key. One is that the certificate authority (CA) requires users to prove possession of user’s private key before issuing certificates using zero-knowledge proof. The other is that CA only checks whether the public key is different from any previously issued one.Clearly, if CA only checks freshness of public keys to issue certificates, by our strong key substitution attacks, GPV signature scheme, Lyubashevsky’s signature scheme, and BLISS do not provide the nonrepudiation property.Thus, a simple and natural way to prevent strong key substitution attack is to require that CA issues certificate only after checking the possession of private key using zero-knowledge proofs. The problem with this solution is that all known approaches for lattice-based zero-knowledge proofs are not practical. The first zero-knowledge proofs in the lattice setting were introduced by Kawachi et al. and Ling et al. [17, 18]. If one would like to have 128 bits of quantum security, one of the most basic application[19] requires 400KB of total proof size and more complicated applications need more megabytes. Baum and Lyubashevsky [20] give a new approach for constructing amortized zero-knowledge proofs of knowledge of short solutions over polynomial rings. When the number of relations is as small as the security parameter, their proof is practical. However, as the number of samples increases, the protocol has the same efficiency as the previous works. Still, it seems that more researches on the lattice-based zero-knowledge proofs need to be done to design efficient lattice-based authentication systems.Even if CA issues certificates using zero-knowledge proof, in order to provide the nonrepudiation property, it requires that the underlying signature scheme be secure under the weak key substitution attack since any malicious signer can be a successful weak key substitution attacker and repudiates his/her valid signature in the system. Our weak key substitution attacks on GPV signature scheme, Lyubashevsky’s signature scheme, and BLISS show that these schemes cannot provide nonrepudiation of the signatures.


## 4.2. How to Prevent Key Substitution Attacks

Another way to prevent key substitution attack is to modify signature schemes to resist this attack. Menezes and Smart [5] took such an approach and suggested a method, we call it MS conversion, that converts a signature scheme Σ into a new signature scheme MS-Σ by prepend the signer’s public key to the message in some unambiguous way prior to signing (for example, a field of fixed length may be reserved for the public key). By using formatted messages specific to each public key, the goal of the key substitution attack against Σ is converted to compute pk′,pk′∥μ,sig from a valid triple pk,pk∥μ,sig, which was regarded as meaningless by Menezes and Smart [5] since it belongs to message key substitution (MKS) attacks against MS-Σ.However, we note that MS conversion is not enough to guarantee the original meaning of KS security without considering MKS security. The specific MKS attack of computingpk′,pk′∥μ,sig indicates that anyone can use it to claim that the signature sig on the message μ is signed by the user with the public key pk′, which is exactly the goal of key substitution attack. Therefore, it is important to check the infeasibility of computing pk′,pk′∥μ,sig from a valid triple pk,pk∥μ,sig in the MS conversions to guarantee the security against key substitution attacks. Form our analysis, it is straightforward to prove that MS-Lyubashevsky’s signature scheme and MS-BLISS signature scheme are secure against key substitution attacks if the hash function H is collision resistant.Unlike these Fiat-Shamir type signature schemes as Lyubashevsky’s signature scheme and BLISS, we see that the collision resistance of the hash functionH is not enough for the MKS security of MS-GPV signature scheme. The MKS security of MS-GPV scheme introduces the following new problem: given a (A,sigμ,μ) such that A·sigμ≡HA∥μmod⁡q, compute a new A′ satisfying A′·sigμ≡HA′∥μmod⁡q. One can solve this new problem as follows: for a given (A,sigμ,μ),Step 1.
ComputeY=Y∈Zqn×m∣Ysigμ=0mod⁡q.Step 2.
ComputeXY∈Zqn×n and Y∈Y such that (24)HXY·Ymod⁡q∥μ=0.Step 3.
OutputA′=XY·Ymod⁡q.It is clear to see thatA′·sigμ≡HA′∥μmod⁡q. The hardness of this new problem has not been studied for the parameters of the GPV signature. It seems somewhat heuristic, but it needs more research to assess the hardness of the problem and we expect that it is easier than the classical computational problems such as the collision resistance of a hash function or SIS problem.Table1 summarizes the results of our key substitution attacks on three signature schemes and MS conversion.Table 1
Key substitution attacks (KSA) on signature schemes based on SIS problem.
Scheme Target equation for KSA Result GPV [7] A⋅sigμ≡Hμmod⁡q insecure Lyubashevsky [8] c=H(Az-Tcmod⁡q,μ) insecure matrix-BLISS [9] c=H(Az+qcmod⁡2q,μ) insecure ring-BLISS [9] c=H(ζ⋅a1⋅z1+ζ⋅q⋅cd+z2†mod⁡p,μ) i n s e c u r e ‡ M S-GPV A⋅sigμ≡HA∥μmod⁡q unknown M S-Lyubashevsky c = A z - T c mod ⁡ q , T ∥ μ secure M S-matrix-BLISS c=HAz+qcmod⁡2q,A∥μ secure M S-ring-BLISS c=ζ⋅a1⋅c1+ζ⋅q⋅cd+z2†mod⁡p,a1,q-2∥μ secure ‡Insecure under some conditions.


## 5. Conclusion

In this paper, we present strong/weak key substitution attacks on GPV signature scheme, Lyubashevsky’s signature scheme, and BLISS. These attacks draw concerns in practice since they make the digital signature scheme to disable the functionalities of nonrepudiation and authentication. And we suggest using the MS conversion [5] which binds the signer’s public key and the message being signed on Lyubashevsky’s signature scheme and BLISS. Also, we point out that it is necessary to prove the security againstmessage and key substitution (MKS) attacks for the MS conversion of digital signature in order to guarantee the security against key substitution attacks.



---

*Source: 8525163-2018-09-23.xml*