Round 1 (Additional Signatures) OFFICIAL COMMENT: SDitH
252 views
Skip to first unread message
Kevin Carrier
Dec 6, 2023, 2:21:43 AM12/6/23
to pqc-co...@nist.gov, pqc-...@list.nist.gov
Dear SDitH consortium, dear all,
We would like to communicate on the security of SDitH
(i) as it was submitted to the NIST, which is called SDiTH v1.0, by the authors and of
(ii) SDiTH v1.1 when it was updated by the authors on November 23 and announced on the pqc forum by Thibauld Feneuil the same day (see https://sdith.org/).
We already announced on the NIST forum on July 31 that the security of SDiTH was underestimated by around 1 to 9 bits depending on the parameters if we choose the same methodology as the authors to estimate the security. This was due to the fact that for the regime of parameters chosen by the authors there were multiple solutions to the decoding problem which were not taken into account. This point has been corrected in SDiTH v.1.1. Note that in SDiTH v.1.1 there is now a 4 to 5 bits margin between the security level asked by the NIST and the estimate of the authors of the best attack against their scheme. For instance in SDiTH, SDitH_L1_gf256 v1.1 for which 143 bits of security are mandatory the estimate of the best attack provided in the specifications has complexity >= 2^{147.7}. It should also be noted that the authors chose to ignore the cost of Gaussian elimination in their estimate of the best attack both for SDiTH v1.0 and SDiTH v.1.1.
In https://arxiv.org/abs/2312.02607, we have
(i) studied the security of SDiTH v1.0 and of SDiTH v1.1 with the help of a slight tweak on Stern's decoding algorithm.
It consists in noticing that we can speed up decoding by considering a projective version of the decoding problem. This trick can be incorporated in standard decoding algorithms with a complexity gain of up to log q bits where q is the field size of the code which is decoded. The gain we obtain is not negligible when we work on large finite field as is the case for SDitH where $q$ is either 251 or 256.
(ii) analyzed the effect of this tweak on Peters' improvements (and adaptation) on Stern's decoding [1,2] for codes defined over F_q.
The cost of Gaussian elimination is not negligible and we have taken this into account in our analysis.
(iii) concluded that on
a) SDiTH v.1.0 the combined effect of multiple solutions + new projective Stern/Peters decoder gives an attack which is between 9 and 14 bits below the NIST requirements.
b) SDiTH v.1.1 our attack is about 3 to 6 bits below the estimate of the best attack provided on https://sdith.org/. Due to the 4-5 bits security margin taken by the authors after preliminary results were announced on November 20 in our workshop on code based cryptography (see the slides on https://anses.hal.science/ETIS-ICI/hal-04311262v1) the estimate of our attack is sometimes above or below by about 1 bit on the security level asked by the NIST.
The following table summarizes the results we obtain. We give here
(i) the security level required by the NIST,
(ii) the security claimed by the SDitH consortium (and the corrected values when taking into account the number of solutions to the decoding problem),
(iii) the actual complexity of our "projective" Stern/Peters’ decoder.
SDitH_L1_gf256 v1.0: (i) 143 bits, (ii) >143.5 bits (>135.3 bits), (iii) 129.2 bits.
SDitH_L1_gf251 v1.0: (i) 143 bits, (ii) >143.5 bits (>134.6 bits), (iii) 128.5 bits.
SDitH_L3_gf256 v1.0: (i) 207 bits, (ii) >207.7 bits (>202.4 bits), (iii) 199.3 bits.
SDitH_L3_gf251 v1.0: (i) 207 bits, (ii) >207.6 bits (>201.3 bits), (iii) 198.2 bits.
SDitH_L5_gf256 v1.0: (i) 272 bits, (ii) >272.4 bits (>267.4 bits), (iii) 264.3 bits.
SDitH_L5_gf251 v1.0: (i) 272 bits, (ii) >272.3 bits (>265.9 bits), (iii) 262.8 bits.
SDitH_L1_gf256 v1.1: (i) 143 bits, (ii) >147.7 bits, (iii) 141.5 bits.
SDitH_L1_gf251 v1.1: (i) 143 bits, (ii) >147.7 bits, (iii) 141.5 bits.
SDitH_L3_gf256 v1.1: (i) 207 bits, (ii) >211.1 bits, (iii) 207.9 bits.
SDitH_L3_gf251 v1.1: (i) 207 bits, (ii) >211.0 bits, (iii) 207.9 bits.
SDitH_L5_gf256 v1.1: (i) 272 bits, (ii) >276.3 bits, (iii) 273.3 bits.
SDitH_L5_gf251 v1.1: (i) 272 bits, (ii) >276.3 bits, (iii) 273.2 bits.
Best regards,
Kévin Carrier, Valérian Hatey and Jean-Pierre Tillich
References:
[1] Christiane Peters. "Information-set decoding for linear codes over Fq." In Post-Quantum Cryptography 2010, volume 6061 of LNCS, pages 81–94. Springer, 2010.
[2] Christiane Peters. Curves, Codes, and Cryptography. PhD thesis, Chapter 6, Tech- nische Universiteit Eindhoven, 2011.
We would like to communicate on the security of SDitH
(i) as it was submitted to the NIST, which is called SDiTH v1.0, by the authors and of
(ii) SDiTH v1.1 when it was updated by the authors on November 23 and announced on the pqc forum by Thibauld Feneuil the same day (see https://sdith.org/).
We already announced on the NIST forum on July 31 that the security of SDiTH was underestimated by around 1 to 9 bits depending on the parameters if we choose the same methodology as the authors to estimate the security. This was due to the fact that for the regime of parameters chosen by the authors there were multiple solutions to the decoding problem which were not taken into account. This point has been corrected in SDiTH v.1.1. Note that in SDiTH v.1.1 there is now a 4 to 5 bits margin between the security level asked by the NIST and the estimate of the authors of the best attack against their scheme. For instance in SDiTH, SDitH_L1_gf256 v1.1 for which 143 bits of security are mandatory the estimate of the best attack provided in the specifications has complexity >= 2^{147.7}. It should also be noted that the authors chose to ignore the cost of Gaussian elimination in their estimate of the best attack both for SDiTH v1.0 and SDiTH v.1.1.
In https://arxiv.org/abs/2312.02607, we have
(i) studied the security of SDiTH v1.0 and of SDiTH v1.1 with the help of a slight tweak on Stern's decoding algorithm.
It consists in noticing that we can speed up decoding by considering a projective version of the decoding problem. This trick can be incorporated in standard decoding algorithms with a complexity gain of up to log q bits where q is the field size of the code which is decoded. The gain we obtain is not negligible when we work on large finite field as is the case for SDitH where $q$ is either 251 or 256.
(ii) analyzed the effect of this tweak on Peters' improvements (and adaptation) on Stern's decoding [1,2] for codes defined over F_q.
The cost of Gaussian elimination is not negligible and we have taken this into account in our analysis.
(iii) concluded that on
a) SDiTH v.1.0 the combined effect of multiple solutions + new projective Stern/Peters decoder gives an attack which is between 9 and 14 bits below the NIST requirements.
b) SDiTH v.1.1 our attack is about 3 to 6 bits below the estimate of the best attack provided on https://sdith.org/. Due to the 4-5 bits security margin taken by the authors after preliminary results were announced on November 20 in our workshop on code based cryptography (see the slides on https://anses.hal.science/ETIS-ICI/hal-04311262v1) the estimate of our attack is sometimes above or below by about 1 bit on the security level asked by the NIST.
The following table summarizes the results we obtain. We give here
(i) the security level required by the NIST,
(ii) the security claimed by the SDitH consortium (and the corrected values when taking into account the number of solutions to the decoding problem),
(iii) the actual complexity of our "projective" Stern/Peters’ decoder.
SDitH_L1_gf256 v1.0: (i) 143 bits, (ii) >143.5 bits (>135.3 bits), (iii) 129.2 bits.
SDitH_L1_gf251 v1.0: (i) 143 bits, (ii) >143.5 bits (>134.6 bits), (iii) 128.5 bits.
SDitH_L3_gf256 v1.0: (i) 207 bits, (ii) >207.7 bits (>202.4 bits), (iii) 199.3 bits.
SDitH_L3_gf251 v1.0: (i) 207 bits, (ii) >207.6 bits (>201.3 bits), (iii) 198.2 bits.
SDitH_L5_gf256 v1.0: (i) 272 bits, (ii) >272.4 bits (>267.4 bits), (iii) 264.3 bits.
SDitH_L5_gf251 v1.0: (i) 272 bits, (ii) >272.3 bits (>265.9 bits), (iii) 262.8 bits.
SDitH_L1_gf256 v1.1: (i) 143 bits, (ii) >147.7 bits, (iii) 141.5 bits.
SDitH_L1_gf251 v1.1: (i) 143 bits, (ii) >147.7 bits, (iii) 141.5 bits.
SDitH_L3_gf256 v1.1: (i) 207 bits, (ii) >211.1 bits, (iii) 207.9 bits.
SDitH_L3_gf251 v1.1: (i) 207 bits, (ii) >211.0 bits, (iii) 207.9 bits.
SDitH_L5_gf256 v1.1: (i) 272 bits, (ii) >276.3 bits, (iii) 273.3 bits.
SDitH_L5_gf251 v1.1: (i) 272 bits, (ii) >276.3 bits, (iii) 273.2 bits.
Best regards,
Kévin Carrier, Valérian Hatey and Jean-Pierre Tillich
References:
[1] Christiane Peters. "Information-set decoding for linear codes over Fq." In Post-Quantum Cryptography 2010, volume 6061 of LNCS, pages 81–94. Springer, 2010.
[2] Christiane Peters. Curves, Codes, and Cryptography. PhD thesis, Chapter 6, Tech- nische Universiteit Eindhoven, 2011.
Reply all
Reply to author
Forward
0 new messages