The non-gap sequence of a subcode of a generalized Reed-Solomon code
type: Item
instance of: scholarly article
title: The non-gap sequence of a subcode of a generalized Reed-Solomon code
zbMATH Open document ID: 1263.94039
author: Irene Márquez-Corbella
author: E. Martínez-Moro
author: Ruud Pellikaan
published in: Designs, Codes and Cryptography
publication date: 2013-01-28T00:00:00Z
review text: 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''.
Mathematics Subject Classification ID: 94B27
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 6131802
zbMATH Keywords: Berger-Loidreau cryptosystem
zbMATH Keywords: square codes
zbMATH Keywords: GRS codes
zbMATH Keywords: gaps of a code
reviewed by: Adrian Atanasiu
describes a project that uses: McEliece
MaRDI profile type: Publication
full work available at URL: s10623-012-9694-2
OpenAlex ID: W2126075688
cites work: How to mask the structure of codes for a cryptographic use
cites work: Grover vs. McEliece
cites work: New directions in cryptography
cites work: Distance bounds for algebraic geometric codes
cites work: On the order bounds for one-point AG codes
cites work: Q4242017
cites work: New generalizations of the Reed-Muller codes--I: Primitive codes
cites work: On the equivalence of McEliece's and Niederreiter's public-key cryptosystems
cites work: Q3752293
cites work: Code-based cryptography
cites work: On the edge-independence number and edge-covering number for regular graphs
cites work: A lower bound for the number of solutions of equations over finite fields
cites work: Algebraic function fields and codes
cites work: Public Key Cryptography - PKC 2006
cites work: Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes
DOI: 10.1007/S10623-012-9694-2
Recommended article: Public Key Cryptography - PKC 2006
Recommended article: Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes
Recommended article: Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice
Recommended article: A note on the Sidelnikov-Shestakov attack of Niederreiter scheme
Recommended article: Q3758716
Recommended article: Bounded distance+1 soft-decision Reed-Solomon decoding
Recommended article: On the decoder error probability for Reed - Solomon codes (Corresp.)
Recommended article: Q4474270
Recommended article: How to avoid the Sidel'nikov-Shestakov attack
Recommended article: CHARACTERISTICS OF HADAMARD SQUARE OF SPECIAL REED — MULLER SUBCODES
description: scientific article; zbMATH DE number 6131802