The non-gap sequence of a subcode of a generalized Reed-Solomon code (Q1934242): Difference between revisions

The Berger-Loidreau cryptosystem [\textit{T. P. Berger} and \textit{P. Loidreau}, ibid. 35, No. 1, 63--79 (2005; Zbl 1136.11327)] is a version of an older scheme based on a class of error-correcting codes, namely the generalized Reed-Solomon (GRS) codes. It was made in order to resist against the Sidel'nikov-Shestakov attack [\textit{V. M. Sidel'nikov} and \textit{S. O. Shestakov}, Discrete Math. Appl. 2, No. 4, 439--444 (1992); translation from Diskretn. Mat. 4, No. 3, 57--63 (1992; Zbl 0796.94006)]. But, using the remark that if the square code of an \((n,k)\)-GRS code is itself a code of length \(2k-1\) then the secret key generated is cryptographically weak (and the Sidel'nikov-Shestakov scheme can construct it in polynomial time). The goal of the paper is to estimate what is the proportion of weak keys in this cryptosystem (meaning the probability that an arbitrary subcode of a GRS code is itself a GRS code). The mathematical instrument used is the notion of non-gaps sequences associated to subcodes (the number of non-gaps sequences is closely related with the number of subcodes of a GRS code which are itself GRS codes). The authors analyse the two possible cases when subcodes of a GRS code are weak keys: (1) when they are themselves GRS codes (Section 4 of the paper concludes that the probability of their occurrence is very small), and (2) they are subcodes whose square code is a GRS code of maximal dimension (Sections 5 and 6 give an estimation of their number, by concluding that the number of weak keys is proportionally high). Even if the restrictions imposed for the last case are somehow strange, the authors claim that they ``are sure that a sharper and more general result can be achieved''.