PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Complementary Pairs of Quasi-Cyclic and Quasi-Twisted Codes

Kanat Abdukhalikov, Duy Ho, San Ling, Gyanendra K. Verma

arXiv:2504.15231v2cs.ITmath.IT

TL;DR

LCPs have applications in resistance against side-channel and fault-injection attacks, and prior work has characterized some related code families. This paper provides polynomial characterizations for index-2 quasi-cyclic and quasi-twisted LCPs and reports examples with optimal security parameters.

  • Problem

    LCPs have cryptographic applications, while prior characterizations cover some code families, motivating characterization of index-2 quasi-cyclic and quasi-twisted LCPs.

    Source: §1 · pp. 2–3

  • Method

    The paper develops polynomial characterizations for index-2 quasi-cyclic and quasi-twisted LCPs, including necessary and sufficient conditions for one-generator quasi-cyclic LCPs.

    Source: §1 · p. 3, §3 · p. 5, §4 · pp. 8–9

  • Results

    n=8, k=4, and dLCP(C,D)=4=dopt for a ternary quasi-cyclic LCP; the paper also reports several quasi-cyclic and quasi-twisted LCP examples with optimal security parameters.

    Source: §6 · p. 13, Conclusion · p. 15

  • Takeaways & Limitations

    The characterizations are used to construct examples of quasi-cyclic and quasi-twisted LCPs with optimal security parameters.

    Source: §6 · p. 12, Conclusion · p. 15

Abstract

from arXiv · show

In this paper, we provide a polynomial characterization of linear complementary pairs of quasi-cyclic and quasi-twisted codes of index 2. We also give several examples of linear complementary pairs of quasi-cyclic and quasi-twisted codes with optimal security parameters.

1 Introduction

The introduction motivates linear complementary pairs (LCPs) through their algebraic structure and cryptographic applications, then sets out polynomial characterizations for index-2 quasi-cyclic and quasi-twisted codes and examples with optimal security parameters.

1 Introduction

  • Quasi-cyclic codes include cyclic codes, are asymptotically good, and are used in post-quantum systems such as QC-MDPC protocols.Quasi-twisted codes also generalize cyclic codes and are known to be asymptotically good.Source: §1 · p. 2
  • LCPs support resistance against side-channel and fault-injection attacks through Direct Sum Masking, with security parameters depending on min{d(C), d(D⊥)}.For an LCD code, the security parameter depends only on its minimum distance.Source: §1 · p. 2
  • Prior work characterized LCPs of quasi-cyclic codes using CRT decomposition and gave necessary and sufficient conditions for constacyclic and double-circulant pairs.For some code families, an LCP implies permutation equivalence between C and D⊥, but this need not hold for quasi-cyclic LCPs.Source: §1 · p. 2
  • This paper gives polynomial characterizations of index-2 quasi-cyclic and quasi-twisted LCPs and examples of quasi-twisted LCPs with optimal security parameters.The introduction also outlines later sections on index-2 and one-generator quasi-cyclic LCPs and quasi-twisted LCPs.Source: §1 · p. 3

2 Preliminaries

The preliminaries define LCPs and related code structures, then use polynomial and CRT representations to relate quasi-cyclic codes to constituent codes.

2 Preliminaries

  • An LCP consists of same-length codes with trivial intersection whose direct sum is the ambient space; an LCD code is an LCP with D=C⊥.The two LCP codes have complementary dimensions, [n,k] and [n,n−k].Source: §2 · p. 3
  • A λ-quasi-twisted code is invariant under ℓ applications of the λ-twisted shift; λ=1 gives quasi-cyclic codes, and ℓ=1 gives constacyclic codes.Such a code of length n=mℓ can be represented as an Rλ-submodule of Rλ^ℓ, with codeword coordinates mapped to polynomials.Source: §2 · p. 3
  • When gcd(m,q)=1, CRT decomposes the quasi-cyclic ring into component fields, and each code decomposes into constituent codes over those fields.An LCP is equivalent to every corresponding pair of constituent codes being an LCP.Source: §2 · pp. 3–4
  • For an r-generator quasi-cyclic code, each constituent is spanned by evaluating the generator polynomials at the corresponding CRT root.The constituents are described through the generators of the code.Source: §2 · p. 4

3 LCPs of quasi-cyclic codes of index 2

This section characterizes when two index-2 quasi-cyclic codes form an LCP using polynomial conditions on their generators. The proof reduces the criterion to constituent codes and verifies their intersections and dimensions.

3 LCPs of quasi-cyclic codes of index 2

  • The generator form uses (g11(x), g12(x)) and (0, g22(x)), with deg g12(x)<deg g22(x) and g11(x)g22(x) dividing (x^m−1)g12(x).The corresponding generator polynomials for both codes satisfy this stated condition.Source: §3 · pp. 4–5
  • For index-2 quasi-cyclic codes in the stated generator form, being an LCP is equivalent to satisfying conditions (I), (II), and (III).The proof establishes necessity through three lemmas and sufficiency through a constituent-wise argument.Source: §3 · pp. 5, 8
  • For an LCP of codes, condition (I) holds: gcd(f11(x), g11(x)) = 1; if the gcd is not 1, the proof identifies a common divisor and concludes that (Ci, Di) is not an LCP.In that case, dim(Ci + Di) ≠ 2.Source: §3 · p. 5
  • Condition (II) equates gcd(g11(x),g22(x)) with (x^m−1)/lcm(f11(x),f22(x)), and the analogous relation holds with f and g exchanged.Together these relations yield g11(x)g22(x)f11(x)f22(x)=(x^m−1)^2.Source: §3 · p. 6
  • The sufficiency proof checks CRT constituents and establishes trivial intersections and dimensions summing to 2 in each case.The proof divides the factor cases according to the factors of (x^m−1)^2.Source: §3 · pp. 7–8

4 LCPs of one-generator quasi-cyclic codes of index 2

The section characterizes when two one-generator quasi-cyclic codes of index 2 form an LCP using a polynomial gcd condition. It also specializes the criterion to double-circulant codes.

4 LCPs of one-generator quasi-cyclic codes of index 2

  • A one-generator index-2 quasi-cyclic code can be represented by two generators satisfying Condition (∗), with the second coordinate reduced modulo g22(x).Source: §4 · p. 8
  • Two one-generator quasi-cyclic codes form an LCP exactly when gcd(x^m − 1, g11(x)f12(x) − g12(x)f11(x)) = 1.Source: §4 · p. 9
  • For double-circulant codes generated by (1, a(x)) and (1, b(x)), the LCP condition is gcd(a(x) − b(x), x^m − 1) = 1.Source: §4 · p. 10

5 LCPs of quasi-twisted codes of index 2

The section characterizes index-2 quasi-twisted LCPs through their generators and CRT constituents. It gives a polynomial gcd criterion for one-generator pairs.

5 LCPs of quasi-twisted codes of index 2

  • An index-2 quasi-twisted code has generators (g11(x), g12(x)) and (0, g22(x)) satisfying deg g12(x) < deg g22(x) and g11(x)g22(x) | (x^m − λ)g12(x).Source: §5 · p. 10
  • A quasi-twisted pair is an LCP exactly when each corresponding pair of CRT constituent codes is an LCP.Source: §5 · p. 11
  • Theorem 5.3 characterizes LCPs of two-generator index-2 quasi-twisted codes under Condition (∗∗).Source: §5 · p. 11
  • Two one-generator λ-quasi-twisted codes form an LCP exactly when gcd(x^m − λ, g11(x)f12(x) − g12(x)f11(x)) = 1.Source: §5 · p. 11

6 Examples of LCPs of codes with good security parameters

Using the index-2 algebraic characterizations, the examples construct LCPs whose security parameters attain dopt for q>2 and attain dopt−1 or dopt for q=2.

6 Examples of LCPs of codes with good security parameters

  • dLCP(C, D)=dopt for q>2, while the examples attain dopt−1 or dopt for q=2.These constructions illustrate use of the preceding algebraic characterizations.Source: §6 · p. 12
  • dLCP(C, D)=7=dopt for a quasi-cyclic example with n=16 and k=8, although a cyclic code with those parameters does not exist.Source: §6 · p. 12
  • dLCP(C, D)=4=dopt for the ternary quasi-cyclic example with n=8 and k=4.Source: §6 · p. 13
  • dLCP(C, D)=5=dopt for the ternary n=10, k=5 example, improving the security parameter in [5, Table 3] at the same n and k.Source: §6 · p. 13
  • The F4 quasi-cyclic examples compare each pair's dLCP(C, D) with dBKLC.Source: §6 · p. 13, Table 1 · p. 13
  • dLCP(C, D)=8=dBKLC for the quinary quasi-twisted example with n=22 and k=11.Source: §6 · p. 14
  • For binary n=30 examples, dLCP(C, D)=8=dopt at k=14, while it is 7=dopt−1 at k=15.Source: §6 · p. 14
  • dLCP(C, D)=16=dopt for the binary [42, 11, 16] example, exceeding the stated lower bound dopt−1.Source: §6 · p. 15

Conclusion

The paper presents polynomial characterizations of index-2 quasi-cyclic and quasi-twisted LCPs, including necessary and sufficient conditions for one-generator cases. It also gives examples with optimal security parameters.

Conclusion

  • LCPs generalize LCD codes and have applications in resistance against side-channel and fault-injection attacks.Source: Conclusion · p. 15
  • The paper presents a polynomial characterization of LCPs of index-2 quasi-cyclic and quasi-twisted codes.Source: Conclusion · p. 15
  • The paper provides several quasi-cyclic and quasi-twisted LCP examples with optimal security parameters.Source: Conclusion · p. 15
Loading 2504.15231v2…