PaperlayerView exact revision on arXiv

Source-linked AI summary

Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes

Alain Couvreur, Philippe Gaborit, Valérie Gauthier-Umaña, Ayoub Otmani, Jean-Pierre Tillich

arXiv:1307.6458v2cs.CRcs.ITmath.IT

TL;DR

Several public-key schemes based on generalized Reed-Solomon codes followed an earlier GRS-based cryptosystem that had been shown insecure, leaving the security of modified schemes at issue. The paper uses component-wise products to recover secret structure in these schemes and presents a product-based filtration as an alternative way to recover a GRS code’s defining structure.

  • Problem

    After the original GRS-based Niederreiter scheme was shown insecure, several modified GRS-based public-key schemes were proposed, raising the question of their key-recovery security.

    Source: Introduction · p. 1

  • Method

    The paper uses component-wise-product distinguishers to detect GRS-derived structure and recover secret keys, and builds a decreasing product-based filtration to recover a GRS code’s structure.

    Source: Introduction · p. 3, Conclusion · p. 20

  • Results

    The authors report efficient key-recovery attacks against schemes based on GRS codes, including the Niederreiter, Wieschebrink, Baldi et al., and Bogdanov–Lee schemes.

    Source: Conclusion · p. 20

  • Takeaways & Limitations

    The attacks show that modified public codes derived from GRS codes can retain structure exploitable for key recovery.

    Source: Conclusion · p. 20

    The filtration attack is more complex than Sidelnikov–Shestakov’s, although it avoids computing minimum-weight codewords.

    Source: §5 · p. 18

Abstract

from arXiv · show

Because of their interesting algebraic properties, several authors promote the use of generalized Reed-Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed-Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et \textit{al.} which hides the generalized Reed-Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these public-key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed-Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed-Solomon code.

Introduction

The paper develops component-wise-product distinguishers into key-recovery attacks on three modified McEliece schemes based on generalized Reed-Solomon codes. It also gives a product-based filtration for recovering a secret GRS code’s structure.

Introduction

  • The attacks target Wieschebrink, Bogdanov–Lee, and Baldi et al. schemes; for Baldi et al., the analysis assumes m = 1 and z = 1, the parameter form proposed in [BBC+11].These choices give the smallest public keys and deciphering complexity within that scheme class.Source: Introduction · p. 2
  • Component-wise-product distinguishers exploit the abnormal square-code dimensions of GRS codes, which distinguish them from random codes at any rate.The cited comparison says the analogous distinguisher succeeds for Goppa codes only at rates close to 1.Source: Introduction · p. 2
  • For Bogdanov–Lee, punctured square-code dimensions reveal which columns belong to the secret set L, enabling recovery of L and decryption.The attack differs from Brakerski’s independently found attack.Source: Introduction · pp. 2–3
  • For Baldi et al., a product-dimension distinguisher identifies elements of the embedded secret GRS code, which can then be recovered and used to decode ciphertexts.The public code itself is not GRS; it contains a large secret GRS code.Source: Introduction · p. 3
  • For Wieschebrink’s variant, refining the distinguisher recovers the added random-column positions, after which Sidelnikov–Shestakov recovers the remaining GRS structure.The paper distinguishes this approach from an adaptation of the Sidelnikov–Shestakov attack.Source: Introduction · p. 3
  • A product-based decreasing filtration gives another way to recover a GRS code’s support and nonzero scalars, with complexity O(k2n3 + k3n2) field operations.It is more complex than the original Sidelnikov–Shestakov attack but avoids computing minimum-weight codewords and may apply to other code families.Source: Introduction · p. 3

1 Reed-Solomon Codes and the Square Code Construction

This section introduces generalized Reed-Solomon codes and their component-wise product, then explains how square-code dimensions distinguish structured GRS codes from random codes.

1 Reed-Solomon Codes and the Square Code Construction

  • A star product spans component-wise products of codewords, and a code’s square is its star product with itself.The paper uses the square code as the main tool for comparing structured codes with random ones.Source: §1 · p. 4
  • For k ≤ (n + 1)/2, the square of a dimension-k GRS code is a GRS code of dimension 2k − 1.The section presents this as the characteristic dimension behavior underlying the distinguisher.Source: §1 · p. 5
  • The square of a random linear code of dimension k is expected to have dimension of order min…The supplied passage gives no completion of the expression, but contrasts this behavior with the roughly doubled GRS dimension.Source: §1 · p. 5
  • Comparing square-code dimensions therefore distinguishes GRS codes from random linear codes; the paper also notes that the distinguisher works for GRS codes of any rate.For q-ary alternant codes such as Goppa codes, the cited prior result applies at very high rates.Source: §1 · p. 5
  • Wieschebrink’s earlier use of the star product identified a possible GRS description for a subcode, then used Sidelnikov–Shestakov on its square.The paper distinguishes that use from its own distinguisher-based key-recovery approach.Source: §1 · p. 6

2 Wieschebrink’s Encryption Scheme

Wieschebrink’s scheme adds random columns to a GRS generator matrix. The attack uses square-code dimensions and shortening to locate those columns, then applies the Sidelnikov–Shestakov attack to the remaining GRS code.

2 Wieschebrink’s Encryption Scheme

  • The scheme inserts r random columns into a length-n, dimension-k GRS generator matrix before applying secret row mixing and a column permutation.The attack seeks to recover the GRS description from the public generator matrix.Source: §2 · p. 6
  • The analysis states a square-dimension bound for the augmented code, and reports that its right-hand inequality is sharp experimentally when 2k − r − 1 < n.With proposed values and k = (n−r)/2−1, Equation (2) held in all 1000 random instances.Source: §2 · pp. 6–7
  • When 2k − 1 + r ≤ n, puncturing at a position and comparing square-code dimensions distinguishes random-column positions from GRS positions.The two cases have different expected square-code dimensions.Source: §2 · p. 7
  • When 2k − 1 + r > n, shortening first reduces the parameters so the same dimension test can be applied.The passage gives conditions for choosing the number of shortened positions and says they can be met when n > k + r.Source: §2 · p. 7
  • After identifying the random columns, puncturing them leaves the GRS code for a Sidelnikov–Shestakov attack; the column-guessing work uses matrix-rank computations.The attack was implemented in Magma and reported as effective for the parameters proposed in.Source: §2 · pp. 7–8

3 Bogdanov-Lee Homomorphic Cryptosystem

This section describes the Bogdanov–Lee linear-code homomorphic scheme, then shows how square-code dimensions expose its secret set L and reveal an inherent low-dimension weakness.

3.1 Description of the scheme

  • Bogdanov–Lee [BL11] uses secret (L, G), publishes P = SG, and encrypts m as c = xP + m1 + e.The secret set L has cardinality 3ℓ.Source: §3.1 · p. 8

3.2 An efficient key-recovery attack

  • The polynomial-time attack recovers L from square-code dimension changes: removing an L-position lowers dimension by one, while removing another position leaves it unchanged.After recovering L, the attack breaks the scheme.Source: §3.2 · p. 10

3.3 Inherent weakness of the scheme

  • The decryption relation requires a nonzero solution supported in L, so the dual of C^2 must contain such a vector.The solutions of equation (9) are precisely the dual of C^2.Source: §3.3 · p. 11
  • The scheme naturally yields codes with abnormally low square-code dimension; in particular, C_L has length 3ℓ and dimension ℓ.The paper characterizes this as non-random behavior with respect to square-product dimension.Source: §3.3 · pp. 10–11

4 BBCRS Cryptosystem

This section describes the BBCRS cryptosystem with a rank-one hiding matrix and presents key-recovery attacks based on component-wise-product dimensions. The approach isolates and reconstructs the secret code to derive a decryption-equivalent pair, and extends to additional parameters using the dual public code.

4.1 Description of the scheme

  • BBCRS uses Π + R to hide a GRS generator matrix; for the studied m = 1, z = 1 case, decryption guesses eR among at most q possibilities.The attack does not directly apply to the later parameters in [BBC+12], where Π is sparse with row/column weight between 1 and 2.Source: §4.1 · pp. 11–12

4.2 Key-recovery attack when 2k + 2 < n

  • For 2k + 2 < n, the attack identifies Cλ⊥ as a dimension-(k − 1) subcode shared by Cpub and the permuted secret GRS code C.If a·b = −1, the public code is itself GRS and can instead be attacked with Sidelnikov–Shestakov [SS92] or the paper’s alternative attack.Source: §4.2 · pp. 12–13

4.2.3 Deriving a and λ from C and Cλ⊥

  • Given C and Cλ⊥, the attack finds a valid pair (a0, λ0) whose map sends C onto Cpub, completing key recovery and enabling decryption.A valid pair is sought by extending the common codimension-one subcode with vectors from C and Cpub and testing the induced map.Source: §4.2 · p. 13, §4.2.3 · p. 16

4.2.1 Computing a basis of Cλ⊥

  • For three random public-code vectors, the generated products generally span dimension 3k −3; if all three lie in Cλ⊥, they generate a much smaller-dimensional subspace, enabling Algorithm 1 to compute a basis of Cλ⊥.Algorithm 1 distinguishes dimensions at most 2k + 2 from higher dimensions when condition (10) holds.Source: §4.2.1 · p. 14

4.2.2 Recovering the structure of C

  • After recovering Cλ⊥, the attack applies Wieschebrink’s method to its square code, recovering a GRS description of C and hence the secret support and scalars.The square code is GRS2k−1(x, y ⋆ y); recovering its description yields (x, y) for C.Source: §4.2.2 · p. 15

4.2.3 Deriving a and λ from C and Cλ⊥

  • The construction verifies that (a0, λ0) satisfies both defining conditions, yielding a valid pair.For Condition (b), it suffices to show ψa0,λ0(u) ∈ Cpub; the passage says this holds by construction.Source: §4.2.3 · p. 17

4.2.4 Decryption of any ciphertext

  • To decrypt z=c+e, the attacker tests z+αa0; for α=−λ0·p, decoding p+e in C recovers p and then c.The error e must have a Hamming weight correctable by C’s chosen decoding algorithm.Source: §4.2.4 · p. 17

4.3 Extending the attack for rates larger than 1

  • The dual-code attack recovers C when 2(n−k)+2<n (equivalently, 2k>n+2), extending applicability to parameters outside a narrow interval around n/2.The approach is carried out over C⊥pub to recover C⊥ and therefore C.Source: §4.3 · p. 18

5 McEliece Variants Based on GRS codes

The section develops code-product attacks that recover secret structure in GRS-based McEliece variants, and an alternative filtration attack for fully recovering GRS structure. The attacks exploit abnormally small dimensions of component-wise product codes and avoid requiring minimum-weight codewords as a first step.

5 McEliece Variants Based on GRS codes

  • The alternative GRS attack runs in O(k^2n^3 + k^3n^2) operations, is less efficient than Sidelnikov–Shestakov, but avoids computing minimum-weight codewords first.The authors suggest it may generalize to other algebraic codes whose attacks begin with minimum-weight codeword computation.Source: §5 · p. 18

5.1 Context and notation

  • For dimension k ≤ n/2, the attack may assume the first two support positions are 0 and 1; for larger dimension, it can use the dual code.The subcodes C(i,j) used by the attack remain GRS codes.Source: §5.1 · p. 18

5.2 Computing some subcodes

  • When k ≤ n/2, product identities relate neighboring C(i,j) subcodes to C(i,j)^2, and repeated linear-system solving computes the needed subcodes in O(k^2n^3 + k^3n^2) operations.The initial shortenings are obtained by Gaussian elimination.Source: §5.2 · p. 19

5.3 Description of the attack

  • The recovery procedure forms two shortened-code vectors, takes their punctured coordinatewise quotient, and inverts a fractional map to recover the support.The quotient cancels the GRS multipliers; comparing a recovered vector with the support raised to the k-th power then recovers the multipliers up to an irrelevant scalar.Source: §5.3 · p. 20

Conclusion

  • Square-code dimensions yield efficient key-recovery attacks on schemes based on [BBC+11] [BL11].They detect Wieschebrink’s random columns, recover the Reed-Solomon part of Bogdanov–Lee [BL11], identify a shared GRS subcode in [BBC+11], and recover the GRS structure in.Source: Conclusion · pp. 20–21
  • The conclusion identifies Reed–Muller attacks as a possible extension, while describing attacks on the original McEliece cryptosystem as especially challenging.The authors note that dual Goppa codes have low-dimensional squares only in a limited way.Source: Conclusion · p. 21

A Proof of Proposition 12

The proof computes an intersection dimension using linear maps that are injective on the relevant polynomial space. Its final dimension expression is 2k + |J| − 1.

A Proof of Proposition 12

  • The linear maps ΦI and ΦI\J are injective on the span of x^2 through x^(2k), and the proof uses this to compute the intersection dimension as 2k + |J| − 1.Injectivity follows from interpolation when a = |I| − |J| is greater than 2k.Source: A Proof of Proposition 12 · pp. 24–25

B Proof of Lemma 13

The proof reduces invertibility of Q to that of P, then characterizes P using the scalar product a · b. When a · b = −1, P is a noninvertible projection.

B Proof of Lemma 13

  • Q is invertible exactly when P is, and P is invertible exactly when a · b ≠ −1.When a · b = −1, P is a projection distinct from the identity, hence noninvertible.Source: B Proof of Lemma 13 · p. 26

C Proof of Proposition 15

The proof determines when three relations among the z_i ⋆ g_j are independent by examining the dimension spanned by the z_i.

C Proof of Proposition 15

  • The three relations are independent exactly when the z_i span a space of dimension at least 2, rather than being pairwise collinear.Source: C Proof of Proposition 15 · p. 27
Loading 1307.6458v2…