SCIENCE CHINA Information Sciences, Volume 63, Issue 3: 132103(2020) https://doi.org/10.1007/s11432-019-2670-7

## An improved Durandal signature scheme

• AcceptedSep 1, 2019
• PublishedFeb 11, 2020
Share
Rating

### Abstract

Constructing secure and effective code-based signature schemes has been an open problem. In this paper, we efficiently reduce the key size of the Durandal signature scheme introduced by Aragon et al. (EUROCRYPT 2019). We prove that the improved scheme is EUF-CMA secure by reducing its security to the advanced product spaces subspaces indistinguishability ($\rm{PSSI}^+$) problem, the decisional rank syndrome decoding (DRSD) problem, and the affine rank syndrome decoding (ARSD) problem under the random oracle model. Furthermore, our signature scheme is more secure than the Durandal scheme because recovering key attacks are equivalent to solving the rank syndrome decoding (RSD) problem, instead of the rank support learning (RSL) problem in the original Durandal scheme. Our signature scheme takes less time to generate a signature owing to the fact that our signature scheme enjoys smaller security parameters in comparison to the Duradual scheme. We compare the new scheme with existing code-based signature schemes and find that our signature scheme has advantages in terms of the public key size.

### Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61822202, 61872087, 61841701, 61902070) and GuangDong Natural Science Foundation (Grant No. 2019B010137002).

### References

[1] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994. 124--134. Google Scholar

[2] Dou Z, Xu G, Chen X B. A secure rational quantum state sharing protocol. Sci China Inf Sci, 2018, 61: 022501 CrossRef Google Scholar

[3] Yang L, Wu C M, Xie H Q. Mutual authenticated quantum no-key encryption scheme over private quantum channel. Sci China Inf Sci, 2018, 61: 022502 CrossRef Google Scholar

[4] Dong X Y, Wang X Y. Quantum key-recovery attack on Feistel structures. Sci China Inf Sci, 2018, 61: 102501 CrossRef Google Scholar

[5] Wang Y, Tian C X, Su Q. Measurement-device-independent quantum secret sharing and quantum conference based on Gaussian cluster state. Sci China Inf Sci, 2019, 62: 72501 CrossRef Google Scholar

[6] Mceliece R J. A public-key cryptosystem based on algebraic coding theory. Technical Report DSN Progress Report, 1978, 4244: 114--116. Google Scholar

[7] Niederreiter H. Knapsack-Type cryptosystems and algebraic coding thoery. Prob Control Inf Theory, 1986, 15: 159--166. Google Scholar

[8] Berlekamp E, McEliece R, van Tilborg H. On the inherent intractability of certain coding problems (Corresp.). IEEE Trans Inform Theor, 1978, 24: 384-386 CrossRef Google Scholar

[9] Courtois N, Finiasz M, Sendrier N. How to achieve a McEliece-Based digital signature scheme. In: Proceedings of ASIACRYPT, Gold Coast, 2001. 157--174. Google Scholar

[10] Baldi M, Bianchi M, Chiaraluce F, et al. Using LDGM codes and sparse syndromes to achieve digital signatures. In: Proceedings of PQCrypto, Limoges, 2013. 1--15. Google Scholar

[11] Löndahl C, Johansson T. A new version of McEliece PKC based on convolutional codes. In: Proceedings of the 14th International Conference on Information and Communications Security, Hong Kong, 2012. 461--470. Google Scholar

[12] Phesso A, Tillich J P. An efficient attack on a code-based signature scheme. In: Proceedings of PQCrypto, Fukuoka, 2016. 86--103. Google Scholar

[13] Landais G, Tillich J P. An efficient attack of a McEliece cryptosystem variant based on convolutional codes. In: Proceedings of PQCrypto, Limoges, 2013. 102--117. Google Scholar

[14] Gaborit P, Ruatta O, Schrek J, et al. RankSign: an efficient signature algorithm based on the rank metric. In: Proceedings of PQCrypto, Waterloo, 2014. 88--107. Google Scholar

[15] Gaborit P, Ruatta O, Schrek J, et al. New results for rank-based cryptography. In: Proceedings of AFRICACRYPT, Marrakesh, 2014. 1--12. Google Scholar

[16] Gaborit P, Murat G, Ruatta O, et al. Low rank parity check codes and their application to cryptography. In: Proceedings of the Workshop on Coding and Cryptography, Bergen, 2013. 167--179. Google Scholar

[17] Aragon N, Gaborit P, Hauteville A, et al. RankSign-a signature proposal for the NIST's call. First Round Submission to the NIST Post-Quantum Cryptography Call, 2017. Google Scholar

[18] Debris-Alazard T, Tillich J P. Two attacks on rank metric code-based schemes: RankSign and an IBE scheme. In: Proceedings of ASIACRYPT, Brisbane, 2018. 62--92. Google Scholar

[19] Fiat A, Shamir A. How to prove yourself: practical solutions to identification and signature problems. In: Proceedings of CRYPTO, Santa Barbara, 1986. 186--194. Google Scholar

[20] Stern J. A new identification scheme based on syndrome decoding. In: Proceedings of CRYPTO, Santa Barbara, 1993. 13--21. Google Scholar

[21] Cayrel P, Véron P, Alaoui S M E Y. A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In: Proceedings of Selected Areas in Cryptography, Waterloo, 2010. 171--186. Google Scholar

[22] Aragon N, Blazy O, Gaborit P, et al. Durandal: a rank metric based signature scheme. In: Proceedings of EUROCRYPT, Darmstadt, 2019. 728--758. Google Scholar

[23] Persichetti E. Improving the efficiency of code-based cryptography. Dissertation for Ph.D. Degree. Auckland: University of Auckland, 2012. 111--115. Google Scholar

[24] Persichetti E. Efficient One-Time Signatures from Quasi-Cyclic Codes: A Full Treatment. Cryptography, 2018, 2: 30 CrossRef Google Scholar

[25] Fukushima K, Roy P S, Xu R, et al. Random code-based signature scheme (RaCoSS) First Round Submission to the NIST Post-quantum Cryptography Call. 2017. https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions. Google Scholar

[26] Roy P S, Morozov K, Fukushima K, et al. Code-Based signature scheme without trapdoors. IEICE Technical Report, 2018, 118: 17--22. Google Scholar

[27] Lyubashevsky V. Lattice signatures without trapdoors. In: Proceedings of EUROCRYPT, Cambridge, 2012. 738--755. Google Scholar

[28] Melchor C A, Aragon N, Bettaieb S, et al. Rank quasi-cyclic (RQC) Second Round Submission to the NIST Post-quantum Cryptography Call, 2019. https://pqc-rqc.org/doc/rqc-specification_2019-04-10.pdf. Google Scholar

[29] Loidreau P. Properties of codes in rank metric. 2006,. arXiv Google Scholar

[30] Gaborit P. Shorter keys for code based cryptography. In: Proceedings of the Workshop on Coding and Cryptography, Bergen, 2005. 81--91. Google Scholar

[31] Hauteville A, Tillich J P. New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem. In: Proceedings of International Symposium on Information Theory, Hong Kong, 2015. 2747--2751. Google Scholar

[32] Gabidulin E M, Paramonov A V, Tretjakov O V. Ideals over a non-commutative ring and thier applications in cryptology. In: Proceedings of EUROCRYPT, Brighton, 1991. 482--489. Google Scholar

[33] Gaborit P, Zemor G. On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes. IEEE Trans Inform Theor, 2016, 62: 7245-7252 CrossRef Google Scholar

[34] Bartz H. Algebraic decoding of subspace and rank-metric codes. Dissertation for Ph.D. Degree. Germany: Technical University Munich, 2017. 1--184. Google Scholar

[35] Gaborit P, Ruatta O, Schrek J. On the Complexity of the Rank Syndrome Decoding Problem. IEEE Trans Inform Theor, 2016, 62: 1006-1019 CrossRef Google Scholar

[36] Aragon N, Gaborit P, Hauteville A, et al. A new algorithm for solving the rank syndrome decoding problem. In: Proceedings of International Symposium on Information Theory, Vail, 2018. 2421--2425. Google Scholar

[37] Guo Q, Johansson T, Londahl C. A New Algorithm for Solving Ring-LPN With a Reducible Polynomial. IEEE Trans Inform Theor, 2015, 61: 6204-6212 CrossRef Google Scholar

[38] L?ndahl C, Johansson T, Koochak Shooshtari M. Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension. Des Codes Cryptogr, 2016, 80: 359-377 CrossRef Google Scholar

[39] Sendrier N. Decoding one out of many. In: Proceedings of PQCrypto, Taipei, 2011. 51--67. Google Scholar

[40] Faugère J C, Levy-dit-Vehel F, Perret L. Cryptanalysis of MinRank. In: Proceedings of CRYPTO, Santa Barbara, 2008. 280--296. Google Scholar

[41] Faugère J C, Din M S E, Spaenlehauer P J. Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In: Proceedings of Symbolic and Algebraic Computation, International Symposium, Munich, 2010. 257--264. Google Scholar

[42] Debris-Alazard T, Sendrier N, Tillich J P. Wave: a new code-based signature scheme. 2018,. arXiv Google Scholar

[43] Kabatianskii G, Krouk E, Smeets B. A digital signature scheme based on random error-correcting codes. In: Proceedings of Cryptography and Coding, 6th IMA International Conference, Cirencester, 1997. 161--167. Google Scholar

[44] Cayrel P L, Otmani A, Vergnaud D. On Kabatianskii-Krouk-Smeets signatures. In: Proceedings of Arithmetic of Finite Fields, First International Workshop, Madrid, 2007. 237--251. Google Scholar

[45] Gaborit P, Girault M. Lightweight code-Based identification and signature. In: Proceedings of International Symposium on Information Theory, Nice, 2007. 191--195. Google Scholar

• Table 1   Sets of parameters for our scheme and the Durandal signature scheme in bits.
 Instance $q$ $m$ $n$ $r$ $d$ $w$ $l$ $l'$ $\lambda$ PKS SS Security Our parameters uppercaseexpandafterromannumeral1 2 229 83 3 7 59 – – 3 95035 25835 128 Durandal [22] 2 241 101 6 6 57 4 1 12 121961 32514 128
•

Algorithm 1 The Durandal signature scheme [22]

Key generation:

- Choose a parameter set $(q,~m,~n,~r,~w,~d,~l,~l&apos;,~\lambda)$.

- Construct a hash function $\mathsf{H}$ from bit strings of arbitrary length to strings of length $l&apos;k$ of $F$, i.e., $\mathsf{H}:~\{0,1\}^*\rightarrow~F^{l&apos;k}$.

- Consider an random ideal ideal matrix $\boldsymbol~H~\in~\mathbb{F}_{q^m}^{n\times~2n}$.

- Choose randomly an $\mathbb{F}_{q}$-subspace $E$ of dimension $r$ of $\mathbb{F}_{q^m}$, i.e., $E\stackrel{\$}{\leftarrow}~\bf{Gr}(r,~\mathbb{F}_{q^m})$. - Choose randomly$l$vectors$\boldsymbol~s_i~\in~E^{2n}$and construct an$ln\times~2n$matrix$\boldsymbol~S$by all$\boldsymbol~s_i$and their$n$shifts. nolinebreak - Choose randomly$l&apos;$vectors$\boldsymbol~s&apos;_i~\in~E^{2n}$and construct an$l&apos;n\times~2n$matrix$\boldsymbol~S&apos;$by all$\boldsymbol~s&apos;_i$and their$n$shifts. - Compute$\boldsymbol{HS}^\mathrm{T}=\boldsymbol~T$and$\boldsymbol{HS}&apos;^{\mathrm{T}}=\boldsymbol~T&apos;$. - The private key:$\boldsymbol~S$and$\boldsymbol~S&apos;$. - The public key:$\boldsymbol~H$,$\boldsymbol~T$, and$\boldsymbol~T&apos;$. Signature: To sign a message$\boldsymbol~m~\in~\{0,1\}^*$. - Choose randomly an$\mathbb{F}_{q}$-subspace$~W$of dimension$w$of$\mathbb{F}_{q^m}$and an$\mathbb{F}_{q}$-subspace$F$of dimension$d$of$\mathbb{F}_{q^m}$, i.e.,$F\stackrel{\$}{\leftarrow}~\bf{Gr}(d,~\mathbb{F}_{q^m})$ and $W\stackrel{\$}{\leftarrow}~\bf{Gr}(w,~\mathbb{F}_{q^m})$. - Choose randomly a$\boldsymbol~y~\in~(W+EF)^{2n}~$, i.e.,$\boldsymbol~y$is a vector of length$2n$from the support$W+EF$. - Compute$\boldsymbol~x~=\boldsymbol{Hy}^{\mathrm{T}}$. - Compute$\boldsymbol~c~=~\mathsf{H}(\boldsymbol~x,~\boldsymbol~m,~F)$. - Choose an$\mathbb{F}_{q}$-subspace$U$of dimension$dr-\lambda$of the product space$EF$such that$U$does not contain any non-zero values in the form of$ef$for all$f\in~F$and$~e\in~E$. - Compute$\boldsymbol~p~\in~F^{n}$such that$\mathrm{Supp}(\boldsymbol~y~+~\boldsymbol~c~{\boldsymbol~S}&apos;~+\boldsymbol~p~{\boldsymbol~S})\subset~U+W$and let$\boldsymbol~z~=~\boldsymbol~y~+~\boldsymbol~c\boldsymbol~S&apos;~+\boldsymbol~p\boldsymbol~S$.nolinebreak - The signature:$(\boldsymbol~z~,~F,~\boldsymbol~c,~\boldsymbol~p~)$. Verification: To verify a signature$(\boldsymbol~z,~F,~\boldsymbol~c,~\boldsymbol~p)$on a message$\boldsymbol~m$. - Computes$\hat{\boldsymbol~x}~=\boldsymbol{Hz}^\mathrm{T}-~\boldsymbol~T&apos;\boldsymbol~c^\mathrm{T}-~\boldsymbol~T\boldsymbol~p^\mathrm{T}$. - If$\mathsf{H}(\hat{\boldsymbol~x},~\boldsymbol~m,~F)=~\boldsymbol~c$. - If$\|\boldsymbol~z\|\leq~dr~-~\lambda~+~w$. • Table 2 Sets of parameters for our scheme and the Durandal scheme in bits  Instance$qmnrdwll'\lambda$PKS SS DA FA KRA Security Our prameters uppercaseexpandafterromannumeral1 2 229 83 3 7 59 – – 3 95035 25835 193 591 148 128 Our prameters uppercaseexpandafterromannumeral2 2 233 89 3 8 58 – – 4 103685 27198 193 1334 150 128 Durandal[22] 2 241 101 6 6 57 4 1 12 121961 32514 193 – 461 128 • Algorithm 2 The improved Durandal signature scheme Key generation: - Choose a parameter set$(q,~m,~n,~r,~w,~d,~\lambda)$. - Construct a hash function$\mathsf{H}$from bit strings of arbitrary length to strings of length$dn$of$\mathbb{F}_{q}$, i.e.,$\mathsf{H}:\{0,1\}^*\rightarrow~\{0,~1,~\ldots,~q-1~\}^{nd}$. - Consider an$n\times~2n$systematic parity-check matrix$\boldsymbol~H=[\boldsymbol~I_n|\mathrm{IM}(\boldsymbol~h)]$of a random$[2n,~n]_{q^m}$-ideal code where$\boldsymbol~I_n$is an$n\times~n$identity matrix and$\boldsymbol~h~\in~\mathcal{R}$. - Choose randomly an$\mathbb{F}_{q}$-subspace$E$of dimension$r$of$\mathbb{F}_{q^m}$, i.e.,$E\stackrel{\$}{\leftarrow}~\bf{Gr}(r,~\mathbb{F}_{q^m})$.nolinebreak

- Choose randomly $\boldsymbol~e~=(\boldsymbol~e_1,~\boldsymbol~e_2)~\in~E^{2n}$ where $\boldsymbol~e_1$, $\boldsymbol~e_2~\in~E^{n}$ and $\boldsymbol~e&apos;=(\boldsymbol~e&apos;_1,~\boldsymbol~e&apos;_2)~\in~E^{2n}$ where $\boldsymbol~e&apos;_1~$, $\boldsymbol~e&apos;_2~\in~E^{n}$, i.e., $\boldsymbol~e&apos;$ and $\boldsymbol~e$ are two vectors of length $2n$ with the same support $E$.

- Compute $\boldsymbol~s=\boldsymbol{He}^\mathrm{T}$ and $\boldsymbol~s&apos;=\boldsymbol{He&apos;}^{\mathrm{T}}$.

- The private key: $\boldsymbol~e$ and $\boldsymbol~e&apos;$.

- The public key: $\boldsymbol~H$, $\boldsymbol~s$, and $\boldsymbol~s&apos;$.

Signature: To generate a signature on a message $\boldsymbol~m$.

- Choose randomly an $\mathbb{F}_{q}$-subspace $~W$ of dimension $w$ of $\mathbb{F}_{q^m}$ and an $\mathbb{F}_{q}$-subspace $F$ of dimension $d$ of $\mathbb{F}_{q^m}$, i.e., $F\stackrel{\$}{\leftarrow}~\bf{Gr}(d,~\mathbb{F}_{q^m})$and$W\stackrel{\$}{\leftarrow}~\bf{Gr}(w,~\mathbb{F}_{q^m})$.

- Choose randomly a $\boldsymbol~y~=(\boldsymbol~y_1,~\boldsymbol~y_2)~\in~(W+EF)^{2n}~$ where $\boldsymbol~y_1,~\boldsymbol~y_2~\in~(W+EF)^{n}$, i.e., $\boldsymbol~y$ is a vector of length $2n$ from the support $W+EF$.

- Compute $\boldsymbol~x~=\boldsymbol{Hy}^{\mathrm{T}}$.

- Compute $\boldsymbol~c~=~\mathsf{H}(\boldsymbol~x,~\boldsymbol~m,~F)$ and $\boldsymbol~c~$ will be viewed as elements of $~F^{n}$ in the following steps.nolinebreak

- Choose an $\mathbb{F}_{q}$-subspace $U$ of dimension $dr-\lambda$ of the product space $EF$ such that $U$ does not contain no non-zero values in the form of $ef$ for all $~f\in~F$ and $e\in~E$. It is necessary to note that $e$ is an element in space $E$ and $\boldsymbol~e$ is a vector of length $2n$ in $~E^{2n}$.

- Compute $\boldsymbol~p~\in~F^{n}$ such that $\mathrm{Supp}(\boldsymbol~y~+~\boldsymbol~c~\cdot~{\boldsymbol~e}&apos;~+\boldsymbol~p~\cdot~{\boldsymbol~e})\subset~W+U$ and let $\boldsymbol~z~=~\boldsymbol~y~+~\boldsymbol~c~\cdot~{\boldsymbol~e}&apos;~+\boldsymbol~p~\cdot~{\boldsymbol~e}$ where $\boldsymbol~z~=~(\boldsymbol~z_1,~\boldsymbol~z_2)=(\boldsymbol~y_1+\boldsymbol~c~\cdot~\boldsymbol~e_{1}&apos;+\boldsymbol~p\cdot~\boldsymbol~e_1,~\boldsymbol~y_2+\boldsymbol~c~\cdot~\boldsymbol~e_{2}&apos;+\boldsymbol~p\cdot~\boldsymbol~e_2)$. nolinebreak

- The signature: $(\boldsymbol~z~,~F,~\boldsymbol~c,~\boldsymbol~p~)$.

Verification: To verify a signature $(\boldsymbol~z,~F,~\boldsymbol~c,~\boldsymbol~p)$ on a message $\boldsymbol~m$.

- Compute $\hat{\boldsymbol~x}~=\boldsymbol{Hz}^\mathrm{T}-~\mathrm{IM}(\boldsymbol~s&apos;)\boldsymbol~c^\mathrm{T}-~\mathrm{IM}(\boldsymbol~s)\boldsymbol~p^\mathrm{T}$.

- If $\mathsf{H}(\hat{\boldsymbol~x},~\boldsymbol~m,~F)=~\boldsymbol~c$.

- If $\|\boldsymbol~z\|\leq~dr~-~\lambda+~w$.

• Table 3   Comparison with Durandal scheme in ms
 Scheme KeyGen Sign(Online) Verification Our parameters uppercaseexpandafterromannumeral1 545 62 293 Durandal [22] 7141 93 421
• Table 4   Comparison with existing code-based signature schemes in bits
 Scheme PKS SS Security Our parameters uppercaseexpandafterromannumeral1 95035 25835 128 CFS [9] 9437184 81 83 Stern [45] 347 122880 83 $(U|U+V)$ Sign [42] 8220835 7870 128 KKS [44] 176900 615 80
• #### 0

Citations

• Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有