© Wuhan University 2022

0 Introduction

Since the first computer was intruded, hackers have been developing the technology of “backdoor” which allows them to enter the system again. The main functions of the backdoor is that it has no ability to prevent the system manager from entering this system again and discover these hackers. Many techniques have been used in this “backdoor”, such as intercepting postal shipping to steal and substitute networking hardware, sabotaging Internet routers, injecting malware, installing backdoors, wire-tapping undersea cables and so on ^[1-3].

In 2013, Edward Snowden brought shocking news that many ongoing surveillance programs with an underlying “backdoor” target at citizens conducting by National Security Agency (NSA) and partners from all over the world ^[4]. A typical example is a pseudorandom generator (PRG) named Dual_EC_ DRBG backdoored by NSA, from NIST (National Institute of Standards and Technology). After choosing a few concrete parameters employed in the PRG, an attacker or any adversary is not able to differentiate exports on PRG from any random number but can forecast following exports^[5]. In this circumstances, post-Snowden cryptography attracts much of attentions in recent years.

As one of the research topics in post-Snowden cryptography, the notion of algorithm substitution attack (ASA) was formalized by Bellare et al^[6] in some semantics from algorithms named symmetric encryption algorithms. The ASA method is capable of any attacker or old big brother to substitute a few of pieces of randomized encryption algorithms or signature algorithms with a modified one such that it can leak secret keys subliminally and undetectably to the adversary. Ateniese et al^[7] first proposed a model of ASA on signature schemes, however, the subverted signature is generic and inefficient. Then Liu et al^[8] introduced a much high efficient ASA method about one affirmatory crowd in some signature schemes. Recently, Beak et al^[9] presented a much more efficient and undetectable method ASA from a classical DSA (digital signature algorithm) digital signature. At present most proposed subverted signatures only consider how to subvert signature schemes, there still needs some countermeasures to address big brother’s threat, while a new proposed signatures named double authentication preventing signatures can be used to deter this kind of big brother’s action.

The double authentication preventing signatures (DAPS) are a class of extraordinary digital signatures with double signatures extractability which means deterable when there exist two different signatures from messages (m₀, p₁) and (m₀, p₂), where p₁≠p₂. When a signature is subverted and satisfies double signature extractability, the subverted signature can be deterable by revealing real signature’s signing secret keys to anyone. Unlike these two ring signatures with linkability and traceability^[10-13], our DAPRS (double authentication preventing ring signatures) has stronger accountability which leads any two pairs of signatures produced by same member in a ring set to reveal his (or her) secret signing keys. As for linkable ring signatures, it allows anyone to efficiently decide whether any two pairs of signatures are produced by the same member without revealing his (or her) identity. As for traceable ring signatures, it can reveal his (or her) identity if any two signatures are produced by the same member. On the basis of the digital signatures in Refs. [14-16], most designed DAPS based on discrete logarithm problems and large integer factorization problems face new challenges because there exist polynomial computational complexity quantum algorithms to solve the two problems, such as Shor algorithm^[17,18]. Hence, it is necessary to study some post quantum secure DAPS.

Lattice-based signature is a cutting-edge cryptographic “technology”. It has several interesting properties, such as high computational efficiency, novel and powerful cryptographic functionalities/applications, strong provable security guarantees, believed “post-quantum” security and so on. Therefore, it is vital for us to study some lattice-based algorithm substitution attacks. While most efficient lattice-based signatures which are a promising post-quantum cryptography belong to Fiat-Shamir signature paradigms (e.g., BLISS^[19,20], GLP^[21], PASSSign^[22], Ring-TESLA^[23]) and Hash-and-sign paradigms (e.g., GGH^[24], NTRUSign^[25], GPV^[25]) at the NIST workshop on post-quantum cryptography. Lattice-based Hash-and-sign paradigm follows that a trapdoor function can be provided by a short lattice basis. Most of them are heuristic security (no actual security proofs) and are relatively inefficient than lattice-based Fiat-Shamir (FS) signature paradigms^[26]. Furthermore most lattice-based Hash-and-sign paradigms have unique signatures which are against subversion attacks^[7]. Hence we aim at algorithm substitution attacks on FS lattice signature paradigms (FS-LBS). In this paper, we present ASA against those schemes that any three consecutive subverted signatures can extract signing keys. At the same time, we provide some countermeasures against ASA by using DAPS to deter the big brother’s threaten. And we show that our scheme can be applied to some practical architectures based on some concrete experiment analysis.

The remainder of this paper is organized in the following sequence. Section 1 shows some preliminaries and cryptographic knowledge. Section 2 provides some notions about deterable subverted signatures and some design requirements. Section 3 presents our concrete deterable subverted FS-LBS scheme and gives proof of key extraction, undetectability and deterability. In Section 4, we make some parameter analysis and performance evaluation. Finally, we give our conclusions.

1 Preliminaries

1.1 Notations

Some basic notations have been shown in Table 1.

1.2 Cryptographic Problems on Lattices

Definition 1  　(Ring-SIS_q,m,β^[27,28]) Given m uniformly elements $R_i\in {\Re }_q$ at random and let $a=(a_1,\cdots ,a_m)$, search a vector $z\in {\Re }^m$ but not zero vector with the relation $\Vert z\Vert \le \beta$ satisfying$a\cdot z=\text{0}\in {\Re }_q$

Note that in ring-SIS, each $a_i\in {\Re }_q$ corresponds to n related vectors $a_i\in Z_q^n$ in SIS, where n is the degree of $\Re$. Each $z_i\in \Re$ of a ring-SIS solution corresponds to a block of n integers, that means $a_i\in Z_q^{m\times m}$ and $z\in Z_{}^{m\times m}$.

Definition 2  　(Ring-LWE ${}_{n,q,D_{R,\sigma }}$^[27,28]) Given m uniformly elements $a_i,b_i\in {\Re }_q$ at random and let $a=(a_1,\cdots ,a_m)\in {\Re }_q,b=(b_1,\cdots ,b_m)\in {\Re }_q$, this algorithm is to search a vector $s\in {\Re }^m$ satisfying $b=as+e$, here $e\leftarrow D_{{\Re }^m,\sigma }$.

Definition 3  　(Rejection sampling lemma ^[29-33])

Suppose that $V\subseteq Z_{}^m$. Let $h:V\to R$ be a random distribution from a Hash value, and $\sigma =\omega (\sqrt{logm})$. If a constant M exists, the following distribution

1) $v\leftarrow h$

2) $z\leftarrow D_{\sigma }^m$

3) Output $(z,v)$ with probability of $\frac{1}{m}$ and the below distribution

1) $v\leftarrow h$

2) $z\leftarrow D_{v,\sigma }^m$

3) Output $(z,v)$ with probability of $\min (\frac{D_{\sigma }^m(z)}{M{D}_{v,\sigma }^m(z)},1)$ is statistically indistinguishable within distance of $\frac{2^{-\omega (logm)}}{M}$. In the following, we use the RejectionSample to represent the algorithm.

1.3 Description of Lattice Based Fiat-Shamir Type Signature Schemes

The Fiat-Shamir type signatures based on lattice consist of algorithms in the following:

Key Generation:

1) Pick $a\leftarrow \Re$ at random.

2) Choose uniformly random $s_1\leftarrow {\Re }_1,s_2\leftarrow {\Re }_1$

3) Compute $t=a{s}_1+s_2$

4) Output a pair of public key and secret key: $(a,t);(s_1,s_2)$

Sign $(\mu ,a,s_1,s_2,t)$:

Select two random numbers$y_1\leftarrow {\Re }_1,y_2\leftarrow {\Re }_1$

2) Calculate $w=a{y}_1+y_2$

3) Compute a value $c=H(a,t,w,\mu )$

4) Obtain $z_1=y_1+c{s}_1,z_2=y_2+c{s}_2$

5) Run the RejectionSample $(z_1,z_2,c{s}_1,c{s}_2)$ and go to 1) if it rejects.

6) Output a pair of signature $(c,z_1,z_2)$

Verify $(\mu ,a,z_1,z_2,t)$:

1) Check $w=a{z}_1+z_2-ct$ mod q whether holds or not.

2) Accept if and only if the equation $c=H(a,t,w,\mu )$ and a small norm $\Vert (z_1,z_2)\Vert$ holds.

Here ${\Re }_1$ with tiny modulus is the subset of $\Re$. Cryptographic Hash function H outputs a low norm subset of $\Re$.

1.4 Double Authentication Preventing Signatures

A DAPS includes four probability polynomial time (PPT) algorithms (KGen, Sign,Ver, Extract) as follows:

1) Given a security parameter $\lambda$, the algorithm KGen(1^λ) outputs public keys pk and private keys sk.

2) The algorithm Sign(sk, a, p) outputs a signature $\pi$ on a pair of public/private key (pk, sk) and a subject/message pair (a, p).

3) The algorithm Ver(pk, a, p, $\pi$) outputs either 0 for rejection or 1 for acceptance on pk, (a, p) and $\pi$.

4) The algorithm Extract outputs the private key sk on input pk, $\text{(}{a}_1,p_1),(a_2,p_2)$ and ${\sigma }_1,{\sigma }_2$, where $a_1=a_2,p_1\ne p_2$.

A DAPS satisfies two properties of existential unforgeability under chosen message attack (EUF-CMA) and double signature deterability (DSE)^[13].

2 Our Deterable Subverted Signatures

We first provide the threat model in this section. Then we give formal definitions for the syntax of deterable subverted signatures. Compared with regular deterable digital signatures, these schemes need a “extraction key” for their manipulates if there exists a subversion attack. Finally we provide some security and functionality features of a deterable subverted signatures on the basis Refs. [7-9].

2.1 Threat Model

Since authentication services of various system models and applications depend upon digital signatures, in the context coerced users who use a DAPS to design some court convincing signatures to refuse big brothers’ (or attackers’) requirements, we construct a subverted signature with a deterable function by using an algorithm substitution attack on double authentication preventing signatures.

2.2 Notions of Deterable Subverted Signatures

Definition 4  　A deterable subverted signature $\overline{\text{SIG}}$ for nonsubverted signature SIG includes four PPT algorithms as follows:

1) On inputting a security parameter $\mathcal{l}$, this algorithm $\overline{\text{Gen}}$ outputs a subversion key subk.

2) On inputting a subversion key subk, a state l, a private key sk, and a message $\mu$, the algorithm $\overline{\text{SIG}}$ outputs a subverted signature $\sigma$ by an updated status l.

3) On inputting a message $\mu$, a public key pk and a subverted signature $\sigma$, this algorithm Ver outputs 1 which means accept and outputs 0 which means reject.

4) On inputting a pair of colliding messages $({\mu }_1,{\mu }_2)$, a public key pk, and its corresponding non-subverted signatures ${\sigma }_1,{\sigma }_2$, this algorithm Deter outputs the private key sk.

2.3 Security and Functionality Features

The key extraction algorithm means that anyone including big brothers and attackers can compute the signature private key from known information if he or she makes a signature on a pair of colliding messages.

Definition 5  　Assume that $\text{SIG=(Gen,\hspace{0.17em}Sign,\hspace{0.17em}Ver)}$ is generic signature scheme and $\overline{\text{SIG}}\text{=(}\overline{\text{Gen}}\text{,\hspace{0.17em}}\overline{\text{SIG}}\text{,}$$\text{Ver,\hspace{0.17em}Deter)}$ is a deterable subverted signatures for SIG. Consider a key extraction game ${\text{Keyextraction}}_{\beta \text{,SIG,}\overline{\text{SIG}}(\mathcal{l})}$ as follows:

1) Using $\text{Gen}(1^{\mathcal{l}})$, it can generate a pair of (pk, sk).

2) By the algorithm $\overline{\text{Gen}}(1^{\mathcal{l}})$, it can generate a subversion key subk.

3) For $i=1,2,\cdots ,Q_S$,

Compute $({\overline{\sigma }}_i,l_i)\leftarrow \overline{\text{SIG}}(\text{subk,sk},{\mu }_i,l_{i-1})$

if an adversary ℬ queries every message ${\mu }_i$

Return $({\overline{\sigma }}_i,l_i)$ to ℬ.

4) ℬ outputs $\text{s}{\text{k}}^{\prime }$ by $(\text{pk,subk},\{{\sigma }_1,\cdots ,{\sigma }_{\mathcal{l}}\})$

5) Check the equation $\text{s}{\text{k}}^{\prime }=\text{sk}$ whether holds or not. If it holds, return 1. Otherwise, it returns 0.

Define an advantage${\text{Adv}}_{\mathcal{B},\text{SIG,}\overline{\text{SIG}}}^{\text{keyextract}}(\mathcal{l})=\mathrm{Pr}[{\text{Keyextraction}}_{{\rm B},\text{SIG,}\overline{\text{SIG}}}(\mathcal{l})=1].$

Given the private key sk and its corresponding public key pair pk, the functionality undetectability means that any users can not find the detecting subversion.

Definition 6  　Assume that a general signature $\text{SIG=(Gen,\hspace{0.17em}Sign,\hspace{0.17em}Ver)}$ and a deterable signature$\overline{\text{SIG}}\text{=(}\overline{\text{Gen}}\text{,\hspace{0.17em}}\overline{\text{SIG}}\text{,\hspace{0.17em}Ver,\hspace{0.17em}Deter)}$for SIG. Consider an undetectability game

${\text{Detect}}_{\mathcal{A},\text{SIG,}\overline{\text{SIG}}}(\mathcal{l})$ as follows:

1) Generate a pair of public/private key $\text{(pk,sk)}$ by the algorithm $\text{Gen}(1^{\mathcal{l}})$.

2) By the algorithm $\text{Gen}(1^{\mathcal{l}})$, it can generate a subversion key subk.

3) Choose $b\in \{0,1\}$ randomly, the game $A^{\text{Sign}{O}_b(·),\mathrm{Re}\text{set}(·)}(\text{sk,\hspace{0.17em}pk})$ outputs its guess $b^{\prime }$.

4) If $b^{\prime }\ne b$, it returns 0, otherwise it returns 1.

$\text{Sign}{O}_b({\mu }_i)$ is given as follows:

5) If b = 0, compute ${\sigma }_i^{\prime }\leftarrow \text{Sign(sk},{\mu }_i)$

6) If b = 1, compute$({\sigma }_i^{\prime },l_i)\leftarrow \overline{\text{Sign}}(\text{subk},\text{sk},{\mu }_i,l_{i-1})$

7) Return ${\sigma }_i^{\prime }$

Reset(∙) is given as follows: Reset(rt_i) ∥ rt_i is a reset query.

Define advantage${\text{Adv}}_{\mathcal{A},\text{SIG,}\overline{\text{SIG}}}^{\text{detect}}(\mathcal{l})=|\mathrm{Pr}[{\text{Detect}}_{\mathcal{A},\text{SIG,}\overline{\text{SIG}}}(\mathcal{l})=1]-\frac{1}{2}|$

For any PPT adversary $\mathcal{A}$, if there exists a negligible function $\epsilon (\mathcal{l})$ satisfying$\text{Adv}{}_{\mathcal{A},\text{SIG,}\overline{\text{SIG}}}^{\text{detect}}(\mathcal{l})=|\mathrm{Pr}[{\text{Detect}}_{\mathcal{A},\text{SIG,}\overline{\text{SIG}}}(\mathcal{l})=1]-\frac{1}{2}|\le \epsilon (\mathcal{l})$the deterable subverted signature is undetectable. It means that the Ver algorithm can output some same results when it is a subverted signature or a normal signature on some same messages.

Deterability means that it can be deterred if there exists algorithm substitution attack on signature scheme.

Definition 7  　Given a general signature $\text{SIG=}$$\text{(Gen,Sign,Ver)}$ and a deterrable signature

$\overline{\text{SIG}}\text{=(}\overline{\text{Gen}}\text{,\hspace{0.17em}}\overline{\text{SIG}}\text{,\hspace{0.17em}Ver,\hspace{0.17em}Deter)}$ for SIG, the detera- bility game ${\text{Deter}}_{\mathcal{C},\text{SIG,}\overline{\text{SIG}}}(\mathcal{l})$ is given as follows:

1) According to the algorithm $\text{Gen}(1^{\mathcal{l}})$, it generates a pair of public/private (pk, sk).

2) Run $\mathcal{C}$(pk, sk), then generate $({\mu }_1,{\mu }_2,{\sigma }_1,{\sigma }_2)$.

3) Return 0 if ${\mu }_1$ and ${\mu }_2$ are not colliding.

4) $v_i\leftarrow \text{Ver(pk},{\mu }_i,{\sigma }_i)$ for i = 1, 2.

5) Return 0 if $v_1=0$ or $v_2=0$.

6) Run $\text{Deter(pk},{\mu }_1,{\mu }_2,{\sigma }_1,{\sigma }_2)$, then generate sk’.

7) Return 0 if $\text{s}{\text{k}}^{\prime }\ne \text{sk}$. Else return 1.

We define the advantage${\text{Adv}}_{\mathcal{C},\text{SIG,}\overline{\text{SIG}}}^{\text{Deter}}(\mathcal{l})=\mathrm{Pr}[{\text{Deter}}_{\mathcal{C},\text{SIG,}\overline{\text{SIG}}}(\mathcal{l})=1]$

The advantage means that for any PPT adversary $\mathcal{C}$, if there exists a negligible function ε(∙) satisfying$\mathrm{Pr}[{\text{Deter}}_{\mathcal{C},\text{SIG,}\overline{\text{SIG}}}(\mathcal{l})=1]\le \frac{1}{2}$the deterable subverted signature is deterable. It means that our scheme can deter some signatures embedding backdoors.

3 Our Deterable Subverted Lattice Based Fiat-Shamir Type Signatures

This section introduces a self-enhancement or subverted attack on Fiat-Shamir type lattice signatures.

Our subverted Fiat-Shamir type lattice-based signatures (FS-LBS) are described as follows:

● Subverted key generation ${\overline{\text{SIG}}}_{\text{FS-LBS}}$: On inputting a security parameter $\mathcal{l}$, a pseudo random Hash function $F:{\{0,1\}}^{\mathcal{l}}\times \Re \to {\Re }_1$ and a random number ${\kappa }_1,{\kappa }_2\in$${\{0,1\}}^{\mathcal{l}}$, the algorithm ${\overline{\text{Gen}}}_{\text{FS-LBS}}$ outputs ${\kappa }_1,{\kappa }_2$ and F which can be described as subk = (descF, ${\kappa }_1,{\kappa }_2$).

● Subverted sign ${\overline{\text{Sign}}}_{\text{FS-LBS}}$: On inputting public keys $(a,t)$ of FS-LBS, message $\mu$, private keys $(s_1,s_2)$, subversion key subk and a state $l=(j,\tau )$, the algorithm outputs $(\overline{\sigma },l)$ as follows.

j ← 0, τ← 0

If $j=0$ mod 2,

1) Select two random numbers$y_1\leftarrow {\Re }_1,y_2\leftarrow {\Re }_1$

2) Calculate $w=a{y}_1+y_2$

3) Compute a value $c=H(A,t,w,\mu )$

4) Obtain $z_1=y_1+c{s}_1,z_2=y_2+c{s}_2$

5) Run the RejectionSample $(z_1,z_2,c{s}_1,c{s}_2)$ and go to 1) if it rejects.

6) Let $\tau =c$ and $\overline{\sigma }=(c,z_1,z_2)$

Else

7) Calculate $w=a{y}_1^{\prime }+y_2^{\prime }$

8) Compute a value $c^{\prime }=H(A,t,w^{\prime },\mu )$

9) Obtain $z_1^{\prime }=y_1^{\prime }+c^{\prime }{s}_1,z_2^{\prime }=y_2^{\prime }+c^{\prime }{s}_2$

10) Run RejectionSample $(z_1^{\prime },z_2^{\prime },c^{\prime }{s}_1,c^{\prime }{s}_2)$ and go to 1) if it rejects.

11) Set $\tau =c^{\prime }$ and $\overline{\sigma }=(c^{\prime },z_1^{\prime },z_2^{\prime })$

j = j + 1

Let $l=(j,\tau )$

Return ($(\overline{\sigma },l)$

Verify $(\mu ,\overline{\sigma },a,t)$:

1) Check $w^{\prime }=a{z}_1^{\prime }+z_2^{\prime }-c^{\prime }t$ mod $q$ whether holds or not.

2) Accept if and only if the equation $c^{\prime }=H(a,t,w^{\prime },\mu )$ and a small norm $\Vert (z_1^{\prime },z_2^{\prime })\Vert$ hold.

If a FS-LBS scheme is subverted, the action of the signer can be found by revealing real signer’s signing secret keys to anyone. When the signing keys is vital for him, in some cases the signer will be punished or the signer will result in great economic losses, or there exist some court convincing reasons to deny big-brother or authority agency demands. Aiming at the subverted lattice-based Fiat-Shamir type signatures, we add a Deter algorithm. Our Deter algorithm makes sure that the lattice-based Fiat-Shamir type signature is against algorithm substitution attack.

● Deter

By the principle of DAPS, if there exists two FS-LBS signatures${\sigma }_1=(c_1,z_{11},z_{12}),{\sigma }_2=(c_2,z_{21},z_{22})$

On colliding messages ${\mu }_1$ and ${\mu }_2$, respectively, anyone can obtain the signing secret key $s_1=\frac{z_{11}-z_{21}}{c_1-c_2}$ and $s_2=\frac{z_{12}-z_{22}}{c_1-c_2}$ by solving a linear equation respectively.

Then we present our scheme satisfying Key extraction, Undetectability and Deterability.

Key extraction. From the subverted FS-LBS $\overline{\text{FS-LBS}}$, we show that the signing private keys of the FS-LBS can be extracted from the $\overline{\text{FS-LBS}}$. That is to say, any consecutive $\overline{\text{FS-LBS}}$ starting with odd or even index is able to release the signing private keys. Below we give the formal proof.

Theorem 1  　Given subverted FS-LBS scheme $\overline{\text{FS-LBS}}$ which outputs any three consecutive signatures, the signing private keys of FS-LBS can be revealed with probability 1.

Proof  　Given three messages $m,m^{\prime },m^{″}$, an adversary ℬ obtains three consecutive subverted FS-LBS ${\overline{\sigma }}_j=(c,z_1,z_2)$, ${\overline{\sigma }}_{j+1}=(c^{\prime },z_1^{\prime },z_2^{\prime })$ and ${\overline{\sigma }}_{j+2}=$$(c^{″},z_1^{″},z_2^{″})$, respectively.

If $j=0$ mod 2, by using ℬ’s subversion keys subk $({\kappa }_1,{\kappa }_2,F)$, compute signing keys as follows:$y_1^{\prime }=F({\kappa }_1,c),y_2^{\prime }=F({\kappa }_2,c),$

Calculate $w^{\prime }=a{y}_1^{\prime }+y_2^{\prime }$

Compute a value $c^{\prime }=H(A,t,w^{\prime },\mu )$

$s_1={c^{\prime }}^{-1}(z_1^{\prime }-y_1^{\prime })$ and $s_2={c^{\prime }}^{-1}(z_2^{\prime }-y_2^{\prime })$

Return $s_1,s_2$.

If j = 1 mod 2, j + 1 = 0 mod 2. ℬ chooses ${\overline{\sigma }}_{j+1}=(c^{\prime },z_1^{\prime },z_2^{\prime })$ and ${\overline{\sigma }}_{j+2}=(c^{″},z_1^{″},z_2^{″})$ to compute the signing keys $s_1,s_2$ by using the same method as above, so ℬ can compute the signing keys by the subverted signature algorithm ${\overline{\text{Sign}}}_{\text{FS-LBS}}$. Hence,${\text{Adv}}_{\mathcal{B},\overline{\text{FS-LB}S}}^{\text{extract}}(\lambda )=1.$

Undetectability. We show that our constructed subverted FS-LBS scheme $\overline{\text{FS-LBS}}$ is undetectable by Theorem 2.

Theorem 2  　Given subverted FS-LBS scheme $\overline{\text{FS-LBS}}$, the detection advantage is negligible under the assumption of pseudo-random function (PRF) F.

Proof  　By a sequence of games, we prove the theorem. We define the events $S_i(i=1,2,\cdots )$ of games $G_i$ that is $b=b^{\prime }$.

Game 0. The original undetectability game Detect$\text{Detec}{\text{t}}_{\mathcal{A},\text{FS-LBS},\overline{\text{FS-LBS}}}(\lambda ).$

Game 1  　As before, but we modify Game 0 to use b = 0 for answering $\mathcal{A}$’s queries as Game 0 and to use a uniform random string for substituting b = 1 (j = 1 mod 2) and noncomputed $y_1^{\prime },y_2^{\prime }$ by PRF. A detailed description is given as follows.$T\leftarrow \varnothing .$

If b=0, this game responds to a valid FS-LBS scheme and j = 0, $\tau =\varnothing$ to $\mathcal{A}$ after receiving every signing query on m and a reset query rt , respectively.

If b = 1, this game carries on as follows:

When $\mathcal{A}$ does some signing queries on m,

j ←0, τ←0

If j = 0 mod 2

1) Pick $y_1\leftarrow {\Re }_1,y_2\leftarrow {\Re }_1$

2) Compute $w=a{y}_1+y_2$ and

3) Compute $c=H(A,t,w,\mu )$ and

4) Calculate $z_1=y_1+c{s}_1,z_2=y_2+c{s}_2$ and

5) Run the RejectionSample $(z_1,z_2,c{s}_1,c{s}_2)$, and return 0 if it accepts.

6) Set $\tau =c$ and $\overline{\sigma }=(c,z_1,z_2)$.

Else

1) If $(\tau ,t_1,t_2)\notin T$, pick randomly $t_1,t_2\in {\Re }_1$ uniformly. Else extract $(\tau ,t_1,t_2)\in T$ and compute

2) $y_1^{\prime }=t_1,y_2^{\prime }=t_2$,

3) $w^{\prime }=a{y}_1^{\prime }+y_2^{\prime }$

4) $c^{\prime }=H(A,t,w^{\prime },\mu )$

5) $z_1^{\prime }=y_1^{\prime }+c^{\prime }{s}_1,z_2^{\prime }=y_2^{\prime }+c^{\prime }{s}_2$

6) Run the RejectionSample $(z_1^{\prime },z_2^{\prime },c^{\prime }{s}_1,c^{\prime }{s}_2)$ and go to 1) if it rejects.

7) Set $T=T\cup \{\tau ,t_1,t_2\}$, $\overline{\sigma }=(c^{\prime },z_1^{\prime },z_2^{\prime })$$j=j+1$

Return $\overline{\sigma }$

When $\mathcal{A}$ makes some reset queries rt, set j = 0, $\tau =\varnothing$.

First, Game 0 and Game 1 are indistinguishable by the distinguishing between PRF and some random functions, i.e.,$|\mathrm{Pr}[S_1]-\mathrm{Pr}[S_0]|={\text{Adv}}_{\mathcal{A},F}^{\text{PRF}}(\lambda ).$

Aiming at Game 2, we modify this game as Game 1 in the following:

If j = 1 mod 2, whether $(\tau ,t_1,t_2)$ in $T$ or not. If is not checked, $(t_1,t_2)\in {\Re }_1$ is chosen randomly and $y_1^{\prime }=t_1,y_2^{\prime }=t_2$.

Secondly, we denote Col be the event that ${\tau }_j={\tau }_l$ for some $l\le Q_S$. Game 1 and Game 2 are both proceeding identically if the algorithm Col can not happen, i.e., $|\mathrm{Pr}[S_2]-\mathrm{Pr}[S_1]|\le \mathrm{Pr}[\text{Col}]\le \frac{Q_S{}^2}{\left|q\right|}$.

Due to Game 3, we modify this game as Game 2 in the following:

While $\mathcal{A}$ makes some reset queries rt, Game 3 is not able to reset j and τ but it answers the adversary $\mathcal{A}$’s other queries by some same ways similar to Game 2.

Finally, the distribution of subverted FS-LBS scheme $\overline{\text{FS-LBS}}$ is identical to the distribution of real FS-LBS scheme except of j=0 mod 2 and j=1 mod 2, because $(t_1,t_2)\in {\Re }_1$ is chosen randomly and $y_1^{\prime }=t_1,y_2^{\prime }=t_2$ depends on $\tau$. That is to say, though this game can not be able to do anything on receiving these reset queries, this distribution between Game 2 and Game 3 is the same. That also means that $\mathcal{A}$ cannot be able to obtain any advantages in surmising $b$ from inquiring about some signing oracles, i.e., $\mathrm{Pr}[S_2]=$$\mathrm{Pr}[S_3]=\frac{1}{2}$.

Taking all together, we have$\text{Adv}{}_{\mathcal{A},\text{FS-LBS,}\overline{\text{FS-LBS}}}^{\text{detect}}(\lambda )\le {\text{Adv}}_{\mathcal{A},F}^{\text{prf}}(\lambda )+\frac{Q_S^2}{\left|q\right|}.$

Theorem 3  　(Deterability). Given FS-LBS scheme, the $\overline{\text{FS-LBS}}$ can be deterable under solving a linear equation with probability 1.

Proof  　When FS-LBS scheme is not subverted, assume that an adversary $\mathcal{B}$ gets two FS-LBS signatures ${\sigma }_1=(c_1,z_{11},z_{12}),{\sigma }_2=(c_2,z_{21},z_{22})$ on colliding messages ${\mu }_1=(a,p_1),{\mu }_2=(a,p_2)$. By the signature algorithm of FS-LBS, $\mathcal{B}$ has the following relations:$\{\begin{array}{l}{z}_{11}=y_1+c_1{s}_1\\ z_{12}=y_2+c_1{s}_2\\ z_{21}=y_1+c_2{s}_1\\ z_{22}=y_2+c_2{s}_2\end{array}$

There are four linear equations with four unknown information $y_1,y_2,s_1,s_2$ on $\Re$. So these unknown information can be solved, i.e.,$s_1=\frac{z_{11}-z_{21}}{c_1-c_2},s_2=\frac{z_{12}-z_{22}}{c_1-c_2}$

If FS-LBS scheme is subverted, the subverted signature can be found. Due to the solved secret keys, a signature can be verified whether the signature is an original FS-LBS signature or a subverted signature $\overline{\text{FS-LBS}}$. Hence, the $\overline{\text{FS-LBS}}$ can be deterable by solving a linear equation with probability 1.

4 Parameter Analysis

4.1 Numerical Analysis

This part first numerically makes some efficiency of our deterable subverted FS-LBS scheme in terms of storage overhead and computational overhead which are listed in Table 2 and Table 3.

As for the storage overhead, it consists of size of pair of public/secret keys and size of signature which is listed in Table 2. The communication cost is determined by the number of j. As for the computational overhead, compared with the Hash functions, the most resource-consuming operation is the multiplication over ring $\Re$. In the signing process, Ver process and Deter process, the computational overhead is listed in Table 2, where the number of multiplications over ring $\Re$ is linear to the number of j. For simplicity, we denote that PM represents the polynomial point multiplications, PA represents the polynomial additions, PS represents the polynomial subtraction, RS represents polynomial Gauss sampling and H and F represent the Hash functions.

By implementation analysis in Ref. [9], we can see that there needs at most three consecutive signatures in the subverted FS-LBS which does not affect practicality of the subverted FS-LBS. So in our constructed scheme, we do not consider signature loss. Here we only analyze the security level, size of secret keys (sk), size of public keys (pk) and size of signature for some deterable subverted FS-LBS in Refs. [20, 21, 29-32]. From Tables 2-3, we can see that our deterable subverted signatures have reasonable efficiency in terms of communication cost, computational overhead and storage overhead.

4.2 Implementation

The implementation is conducted with NFLlib, which is a NTT-based fast lattice cryptography library, on Intel i7-7700 CPU @ 3.60GHz and Ubuntu linux operation system. By statistics, these important algorithm operations mainly consist one polynomial addition, one polynomial multiplication and one polynomial Gaussian. Since the implementation of any Hash function is not included in NFLlib, we test the running time of three hash functions by a HMAC based on SM3 algorithm. The execution time of each cryptographic operation in different parameters is shown in Table 4. Here the execution time of these Hash functions we consider is the same.

Experimental results for proposed deterable subverted FS-LBS of each algorithm are depicted in Fig. 1. We increase the number of j from 2 to 10 for each test to see the time cost of $\overline{\text{Sign}}$, Ver and Deter algorithm. Here procedure of subversion key generation can be considered as a random number, so we can omit its time consumption.

Fig. 1 Simulation results of our construction for different j, l

On one hand, for different parameters in Table 4, the time consuming of subverted sign $\overline{\text{Sign}}$ algorithm is about 0.1278×l+0.2294×(j-l) ms, 0.1275×l+0.2351 ×(j-l) ms, 0.1895×l+0.3623×(j-l) ms, 0.2084×l+ 0.3789 ×(j-l) ms, 0.4141×l+0.674 4×(j-l) ms for the number of j, l. The time efficiency of Ver algorithm is about 0.3344 ms, 0.3451 ms, 0.5373 ms, 0.5559 ms, 0.9614 ms. The time efficiency of Deter algorithm is about 0.0050 ms, 0.0046 ms, 0.0074 ms, 0.0095 ms, 0.0240 ms. On the other hand, suppose that j =10 and l = 1, 2, 3, 4, 5, according to Fig. 1, we can see that time cost of the total algorithm justifies the feasibility.

5 Conclusion

This paper first explores a novel algorithm substitution method on lattice-based Fiat-Shamir type signature schemes. Based on this, then we provide countermeasures to deterable signature subversion. Security proof shows that our construction satisfies three different security and privacy requirements. Parameter analysis demonstrates that our construction is feasible. In future, we will study our algorithm by widening range of possible schemes that is vulnerable to algorithm substitution attack or by other much more valuable methods and countermeasures on these post quantum secure signatures. In addition, some other possible work will focus on some algorithm substitution attacks on other cryptographic primitives.

References

All Tables

All Figures

	Fig. 1 Simulation results of our construction for different j, l
In the text