Issue 
Wuhan Univ. J. Nat. Sci.
Volume 27, Number 1, March 2022



Page(s)  17  25  
DOI  https://doi.org/10.1051/wujns/2022271017  
Published online  16 March 2022 
Computer Science
CLC number: TP391
An Algorithm Substitution Attack on FiatShamir Signatures Based on Lattice
^{1} School of Cyber Security, Northwestern Polytechnical University, Xi’an 710072, Shaanxi, China
^{2} Research & Development Institute of Northwestern Polytechnical University, Shenzhen 518057, Guangdong, China
^{3} School of Cyber Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, Shaanxi, China
^{4} School of Computer Science, Guizhou University of Finance and Economics, Guiyang 550025, Guizhou, China
^{5} School of Computer Science, Wuhan University, Wuhan 430072, Hubei, China
^{†} To whom correspondence should be addressed. Email: yuyongxy@163.com
Received: 15 September 2021
Many evidences have showed that some intelligence agencies (often called big brother) attempt to monitor citizens’ communication by providing coerced citizens a lot of subverted cryptographic algorithms and coercing them to adopt these algorithms. Since legalized services on large number of various applications and system architectures depend on digital signature techniques, in the context some coerced users who use double authentication preventing signatures to design some novel digital signature techniques, have some convincing dissertations to defuse requests from authorities and big brothers creating some corresponding subverted signatures. As rapid progress in quantum computers, National Security Agency advisory memorandum and announcement of National Institute of Standards and Technology procedures from standardization focus on some cryptographic algorithms which are post quantum secure. Motivated by these issues, we design an algorithm substitution attack against FiatShamir family based on lattices (e.g., BLISS, BG, RingTESLA, PASSSign and GLP) that are proven postquantum computational secure. We also show an efficient deterable way to eliminate big brother’s threat by leaking signing keys from signatures on two messages to be public. Security proof shows that our schemes satisfy key extraction, undetectability and deterability. Through parameters analysis and performance evaluation, we demonstrate that our deterring subverted FiatShamir signature is practical, which means that it can be applied to privacy and protection in some system architectures.
Key words: algorithm substitution attack / double authentication preventing signatures / lattice / ringSIS (small integer solution) problem
Biography: LIU Jinhui, female, Ph.D., research direction: information security and cryptography. Email: jh.liu6666@ nwpu.edu.cn
Foundation item: Supported by the National Natural Science Foundation of China (61802239, 61872229, 62062019, 62074131) , Key Research and Development Program of Shaanxi Province (2020ZDLGY0906, 2021ZDLGY0604, 2021ZDLGY0501) , Natural Science Basic Research Plan in Shaanxi Province (2019JQ667, 2020JQ422) , and Shenzhen Fundamental Research Program (20210317191843003)
© Wuhan University 2022
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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, wiretapping undersea cables and so on ^{[13]}.
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, postSnowden cryptography attracts much of attentions in recent years.
As one of the research topics in postSnowden 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_{0}, p_{1}) and (m_{0}, p_{2}), where p_{1}≠p_{2}. 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^{[1013]}, 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. [1416], 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.
Latticebased signature is a cuttingedge cryptographic “technology”. It has several interesting properties, such as high computational efficiency, novel and powerful cryptographic functionalities/applications, strong provable security guarantees, believed “postquantum” security and so on. Therefore, it is vital for us to study some latticebased algorithm substitution attacks. While most efficient latticebased signatures which are a promising postquantum cryptography belong to FiatShamir signature paradigms (e.g., BLISS^{[19,20]}, GLP^{[21]}, PASSSign^{[22]}, RingTESLA^{[23]}) and Hashandsign paradigms (e.g., GGH^{[24]}, NTRUSign^{[25]}, GPV^{[25]}) at the NIST workshop on postquantum cryptography. Latticebased Hashandsign 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 latticebased FiatShamir (FS) signature paradigms^{[26]}. Furthermore most latticebased Hashandsign paradigms have unique signatures which are against subversion attacks^{[7]}. Hence we aim at algorithm substitution attacks on FS lattice signature paradigms (FSLBS). 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 FSLBS 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.
Notations
1.2 Cryptographic Problems on Lattices
Definition 1 (RingSIS_{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 ringSIS, 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 ringSIS 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 (RingLWE ${}_{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 ^{[2933]})
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 $\mathrm{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 FiatShamir Type Signature Schemes
The FiatShamir 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 (EUFCMA) 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. [79].
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 nonsubverted 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}_{i1})$
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,\text{\hspace{0.17em}}1\}$ randomly, the game ${A}^{\text{Sign}{O}_{b}(\xb7),\mathrm{Re}\text{set}(\xb7)}(\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}_{i1})$
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}{\text{\hspace{0.17em}}}_{\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 FiatShamir Type Signatures
This section introduces a selfenhancement or subverted attack on FiatShamir type lattice signatures.
Our subverted FiatShamir type latticebased signatures (FSLBS) are described as follows:
● Subverted key generation ${\overline{\text{SIG}}}_{\text{FSLBS}}$: 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{FSLBS}}$ outputs ${\kappa}_{1},{\kappa}_{2}$ and F which can be described as subk = (descF, ${\kappa}_{1},{\kappa}_{2}$).
● Subverted sign ${\overline{\text{Sign}}}_{\text{FSLBS}}$: On inputting public keys $(a,t)$ of FSLBS, 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 FSLBS 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 bigbrother or authority agency demands. Aiming at the subverted latticebased FiatShamir type signatures, we add a Deter algorithm. Our Deter algorithm makes sure that the latticebased FiatShamir type signature is against algorithm substitution attack.
● Deter
By the principle of DAPS, if there exists two FSLBS 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 FSLBS $\overline{\text{FSLBS}}$, we show that the signing private keys of the FSLBS can be extracted from the $\overline{\text{FSLBS}}$. That is to say, any consecutive $\overline{\text{FSLBS}}$ starting with odd or even index is able to release the signing private keys. Below we give the formal proof.
Theorem 1 Given subverted FSLBS scheme $\overline{\text{FSLBS}}$ which outputs any three consecutive signatures, the signing private keys of FSLBS can be revealed with probability 1.
Proof Given three messages $m,{m}^{\prime},{m}^{\u2033}$, an adversary ℬ obtains three consecutive subverted FSLBS ${\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}^{\u2033},{z}_{1}^{\u2033},{z}_{2}^{\u2033})$, 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}^{\u2033},{z}_{1}^{\u2033},{z}_{2}^{\u2033})$ 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{FSLBS}}$. Hence,${\text{Adv}}_{\mathcal{B},\overline{\text{FSLB}S}}^{\text{extract}}(\lambda )=1.$
Undetectability. We show that our constructed subverted FSLBS scheme $\overline{\text{FSLBS}}$ is undetectable by Theorem 2.
Theorem 2 Given subverted FSLBS scheme $\overline{\text{FSLBS}}$, the detection advantage is negligible under the assumption of pseudorandom 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{FSLBS},\overline{\text{FSLBS}}}(\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 FSLBS 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}}{\leftq\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 FSLBS scheme $\overline{\text{FSLBS}}$ is identical to the distribution of real FSLBS 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}{\text{\hspace{0.17em}}}_{\mathcal{A},\text{FSLBS,}\overline{\text{FSLBS}}}^{\text{detect}}(\lambda )\le {\text{Adv}}_{\mathcal{A},F}^{\text{prf}}(\lambda )+\frac{{Q}_{S}^{2}}{\leftq\right}.$
Theorem 3 (Deterability). Given FSLBS scheme, the $\overline{\text{FSLBS}}$ can be deterable under solving a linear equation with probability 1.
Proof When FSLBS scheme is not subverted, assume that an adversary $\mathcal{B}$ gets two FSLBS 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}),\text{\hspace{0.17em}}{\mu}_{2}=(a,{p}_{2})$. By the signature algorithm of FSLBS, $\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 FSLBS 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 FSLBS signature or a subverted signature $\overline{\text{FSLBS}}$. Hence, the $\overline{\text{FSLBS}}$ 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 FSLBS 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 resourceconsuming 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 FSLBS which does not affect practicality of the subverted FSLBS. 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 FSLBS in Refs. [20, 21, 2932]. From Tables 23, we can see that our deterable subverted signatures have reasonable efficiency in terms of communication cost, computational overhead and storage overhead.
Storage and communication overhead of deterable subverted FSLBS scheme
Computational overhead of deterable subverted FSLBS scheme
4.2 Implementation
The implementation is conducted with NFLlib, which is a NTTbased fast lattice cryptography library, on Intel i77700 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 FSLBS 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×(jl) ms, 0.1275×l+0.2351 ×(jl) ms, 0.1895×l+0.3623×(jl) ms, 0.2084×l+ 0.3789 ×(jl) ms, 0.4141×l+0.674 4×(jl) 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.
The cryptographic operation time in the scheme ms
5 Conclusion
This paper first explores a novel algorithm substitution method on latticebased FiatShamir 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
 Easttom W. Cryptographic backdoors [C]//Modern Cryptography. Berlin: SpringerVerlag, 2021: 373383. [Google Scholar]
 Peyrin T, Wang H. The Malicious framework: Embedding backdoors into tweakable block ciphers[C]// Proc Annual International Cryptology Conference. Berlin: Springer Verlag, 2020: 249278. [Google Scholar]
 Dauterman E, CorriganGibbs H, Mazières D, et al. True2F:Backdoorresistant authentication tokens [C]// 2019 IEEE Symposium on Security and Privacy (SP). Washington D C: IEEE, 2019: 398416. [Google Scholar]
 Ball J, Borger J, Greenwald G. Revealed: How US and UK spy agencies defeat internet privacy and security[J]. The Guardian, 2013, ED6: 28. [Google Scholar]
 Bernstein D J, Lange T, Niederhagen R. Dual EC: A standardized back door[J]. The New CodebreakersVolume 9100, 2015: 256281. DOI: https://doi.org/10.1007/978366249301 4_17. [Google Scholar]
 Bellare M, Paterson K G, Rogaway P. Security of symmetric encryption against mass surveillance [C] // Advances in Cryptology, CRYPTO 2014. Berlin:SpringerVerlag, 2014: 119. [Google Scholar]
 Ateniese G, Magri B, Venturi D. Subversionresilient signature schemes [C]// Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, New York: ACM, 2015: 364375. [Google Scholar]
 Liu C, Chen R, Wang Y, et al. Asymmetric subversion attacks on signature schemes [C]// Australasian Conference on Information Security and Privacy. Berlin: SpringerVerlag, 2018: 376395. [Google Scholar]
 Baek J, Susilo W, Kim J, et al. Subversion in practice: How to efficiently undermine signatures [C]// IEEE Access, 2019: 376395. [Google Scholar]
 Catalano D, Fuchsbauer G, Soleimanian A. Doubleauthenticationpreventing signatures in the standard model [C]// International Conference on Security and Cryptography for Networks. Berlin: SpringerVerlag, 2020: 338358. [Google Scholar]
 Poettering B, Stebila D. Doubleauthenticationpreventing signatures [C]// ESORICS. Berlin: SpringerVerlag, 2014: 122. [Google Scholar]
 Boneh D, Kim S, Nikolaenko V. Latticebased DAPS and generalizations: Selfenforcement in signature schemes [C]// International Conference on Applied Cryptography and Network Security. Berlin: SpringerVerlag, 2017: 457477. [Google Scholar]
 Poettering B, Stebila D. Short double and ntimesauthenticationpreventing signatures from ECDSA and more [C]// 2018 IEEE European Symposium on Security and Privacy (EuroS&P). Washington D C: IEEE Press, 2018: 273287. [Google Scholar]
 Poettering B. Shorter doubleauthentication preventing signatures for small address spaces [C]//International Conference on Cryptology in Africa, AFRICACRYPT 2018. Lecture Notes in Computer Science. Berlin: SpringerVerlag, 2018: 344361. [Google Scholar]
 Derler D, Ramacher S, Slamanig D. Generic doubleauthentication preventing signatures and a postquantum instantiation [C]// International Conference on Cryptology in Africa. Berlin:SpringerVerlag, 2018: 258276. [Google Scholar]
 Liu J H, Yu Y, Jia J, et al. Latticebased doubleauthentica tionpreventing ring signature for security and privacy in vehicular AdHoc networks [J]. Tsinghua Science and Technology, 2019, 24(5): 575584. [Google Scholar]
 Lyubashevsky V. Lattice signatures without trapdoors [C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: SpringerVerlag, 2012: 738755. [Google Scholar]
 Shor P W. Polynomialtime algorithms for prime factorization and discrete logarithms on a quantum computer [J]. SIAM Review, 1999, 41(2): 303332. [NASA ADS] [CrossRef] [MathSciNet] [Google Scholar]
 Ajtai M. Generating hard instances of lattice problems [C]// Proceedings of the TwentyEighth Annual ACM Symposium on Theory of Computing. New York: ACM, 1996: 99108. [Google Scholar]
 Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal Gaussians [C]// Annual Cryptology Conference. Berlin: SpringerVerlag, 2013: 4056. [Google Scholar]
 Güneysu T, Lyubashevsky V, Pöppelmann T, et al. Practical latticebased cryptography: A signature scheme for embedded systems [C]// International Workshop on Cryptographic Hardware and Embedded Systems, ACM Transactions on Embedded Computter Systems. New York: ACM, 2012: 530547. [Google Scholar]
 Hoffstein J, Pipher J, Schanck J M, et al. Practical signatures from the partial Fourier recovery problem [C]//International Conference on Applied Cryptography and Network Security. Berlin: SpringerVerlag, 2014: 476493. [Google Scholar]
 Akleylek S, Bindel N, Buchmann J, et al. An efficient lattice based signature scheme with provably secure instantiation [C]// International Conference on Cryptology in Africa. Berlin: SpringerVerlag, 2016: 4460. [Google Scholar]
 Goldreich O, Goldwasser S, Halevi S. Publickey cryptosystems from lattice reduction problems [C]//Annual International Cryptology Conference. Berlin: SpringerVerlag, 1997: 112131. [Google Scholar]
 Hoffstein J, HowgraveGraham N, Pipher J, et al. Digital signatures using the NTRU lattice [C]//Cryptographers Track RSA Conference. Berlin: SpringerVerlag, 2003: 122140. [Google Scholar]
 Espitau T, Fouque P A, Gerard B, et al. Loopabort faults on lattice based signature schemes and key exchange protocols [J]. IEEE Transactions on Computers, 2018, 67(11): 15351549. [MathSciNet] [Google Scholar]
 Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings [J]. Journal of the ACM, 2013, 60(6): 134. [CrossRef] [Google Scholar]
 Bert P, Fouque P A, RouxLanglois A, et al. Practical implementation of ringSIS/LWE based signature and IBE [C]//International Conference on PostQuantum Cryptography. Berlin: SpringerVerlag, 2018: 271291. [Google Scholar]
 Bai S, Galbraith S D. An improved compression technique for signatures based on learning with errors [C]// Cryptographers’ Track at the RSA Conference. Berlin: Springer Verlag, 2014: 2847. [Google Scholar]
 Ducas L, Kiltz E, Lepoint T, et al. Crystalsdilithium: A latticebased digital signature scheme [C]//IACR Transactions on Cryptographic Hardware and Embedded Systems, A LatticeBased Digital Signature Scheme. New York: IACR, 2018: 238268. [Google Scholar]
 Chopra A. GLYPH: A new insantiation of the GLP digital signature scheme [C]// IACR Cryptology ePrint Archive. New York: IACR, 2017: 114. [Google Scholar]
 Ducas L. Accelerating Bliss: The geometry of ternary polynomials[C]// IACR Cryptology ePrint Archive. New York: IACR, 2014: 112. [Google Scholar]
 Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions [C]// Proceedings of the 40th Annual ACM Symposium on Theory of Computing. New York: ACM Press, 2008: 1720. [Google Scholar]
All Tables
All Figures
Fig. 1 Simulation results of our construction for different j, l  
In the text 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.