PaperlayerView exact revision on arXiv

Source-linked AI summary

Constructions of Secure Convertible Codes

Manasa Suresh B P, Vinayak Ramkumar, Myna Vajha

arXiv:2610.34863v1cs.ITmath.IT

TL;DR

Secure convertible codes must protect a message from passive eavesdroppers observing symbols across initial and final codewords. This paper constructs two access-optimal families that extend protection to unchanged, retired, and new symbols. MRD codes cover all valid merge and split parameters but require large fields, while GRS codes use smaller fields for certain parameter ranges.

  • Problem

    Prior secure convertible codes may fail to protect the message when an eavesdropper accesses a mix of unchanged and retired symbols, rather than only unchanged symbols.

    Source: §I · p. 2

  • Method

    The paper constructs secure convertible codes using MRD-based precoding for broad parameter coverage and GRS-based codes for certain merge and split parameter ranges.

    Source: §I · p. 2, §V · p. 7

  • Results

    The constructions provide ℓ-secrecy against access to unchanged, retired, and new symbols; the MRD family covers all valid merge and split parameters, while the GRS family applies to certain ranges.

    Source: §I · p. 2

  • Takeaways & Limitations

    The constructions extend secrecy protection beyond unchanged symbols to eavesdropper access across the initial and final codewords.

    Source: §I · p. 2, B. Nested Matrix-Based Precoding · p. 3

    The MRD-based construction requires a large field, while the GRS-based construction applies only for certain parameter ranges.

    Source: §I · p. 2, §V · p. 7

Abstract

from arXiv · show

Secure convertible codes, introduced by Zhang and Rashmi, achieve secrecy capacity under a passive eavesdropper model in which an eavesdropper is allowed to access any $\ell$ symbols from the initial and final codewords. In this paper, we construct two families of access-optimal secure convertible codes. The first family of codes based on Maximum Rank Distance (MRD) codes is constructed for all parameters in the merge and split regimes and requires a large field size. The second family of codes, constructed using Generalized Reed-Solomon codes, uses smaller fields but is applicable only for certain parameters in the merge and split regimes.

I. INTRODUCTION

Secure convertible codes add information-theoretic secrecy against passive eavesdroppers to code conversion. The paper addresses a gap in prior constructions by building codes secure against access to unchanged, retired, and new symbols, with different parameter and field-size trade-offs across two construction families.

I. INTRODUCTION

  • Conversion efficiency is measured by access cost, the number of symbols accessed, and bandwidth cost, the amount of data read and written.The paper considers initial and final codewords carrying a secure message under this secrecy model.Source: §I · p. 1, §II · p. 2
  • The paper identifies that Zhang and Rashmi’s construction may not protect against eavesdroppers accessing a mix of unchanged and retired symbols.The proposed constructions target access to any ℓ unchanged, retired, and new symbols.Source: §I · p. 2
  • MRD-based codes cover all valid merge and split parameters but require a large field; GRS-based codes use a smaller field for certain parameter ranges.The GRS construction uses GRS generator matrices for the initial and final codes.Source: §I · p. 2

II. PRELIMINARIES

  • The framework requires that an eavesdropper observing any ℓ symbols across initial and final configurations obtain no information about the secure message.It preserves the decoding and code-conversion properties of the standard convertible-code framework.Source: §II · p. 2

A. Necessary and Sufficient Conditions for Secrecy

The section characterizes secrecy through the rank of the key-generating part of a code’s generator matrix. For MDS codes, the resulting criterion is equivalent to a nested-matrix condition.

A. Necessary and Sufficient Conditions for Secrecy

  • An [n, k] linear code is (ℓ, k̂)-secure exactly when each tapped set of j ≤ ℓ columns has rank j in both the full generator matrix and its key-generating submatrix.The secure message is encoded by Gs, while Gκ provides the random key component.Source: A. Necessary and Sufficient Conditions… · pp. 2–3
  • Full rank of Gκ makes every observed value equally likely for every secret, yielding perfect secrecy.For a tapped set of j symbols, the proof counts q^(k−k̂−j) solutions for the key.Source: A. Necessary and Sufficient Conditions… · p. 3
  • An [n, k] MDS code is (ℓ, k−ℓ)-secure exactly when it has an ℓ-nested generator matrix.The nested matrix’s key-generating rows form a generator matrix of an [n, k−k̂] MDS code.Source: A. Necessary and Sufficient Conditions… · p. 3

B. Nested Matrix-Based Precoding

Nested matrix-based precoding masks the secure message when the eavesdropper accesses only message/unchanged symbols, but does not guarantee secrecy for parity-symbol access. The framework constructs secure codes for broader access patterns by precoding the message and key before base-code encoding.

B. Nested Matrix-Based Precoding

  • A [kI, kI] ℓ-nested precoder alone does not ensure ℓ-secrecy for arbitrary codeword-symbol access; the effective generator GI must also be [nI, kI] ℓ-nested.For a systematic base generator, the nested property protects access to any ℓ of the first kI symbols, but parity-symbol access requires the stronger condition on GI.Source: B. Nested Matrix-Based Precoding · p. 3
  • The example shows that one accessed parity symbol can reveal the secure message, so nested precoding does not guarantee secrecy when parity symbols are exposed.The encoded vector includes the secure message directly in its last symbol.Source: B. Nested Matrix-Based Precoding · p. 3

1) Initial Code:

  • In the initial-code construction, each secure message vector is concatenated with a key, precoded by an invertible P, and encoded using the base initial generator ˆGI.The resulting effective generator is GI = P ˆGI, which remains an [nI, kI] MDS generator when P is invertible.Source: 1) Initial Code · p. 4

2) Unified Generator Matrix:

A unified generator matrix represents all initial and final codeword symbols together, allowing secrecy to be checked across both configurations. The final-code construction assembles each codeword from the relevant initial-message portions and retains the base code's access cost and decoding properties.

2) Unified Generator Matrix:

  • The unified generator Gjoint maps the concatenated message and key to all initial and final codeword symbols, enabling joint analysis of eavesdropper access across configurations.Its first λI nI columns reproduce the initial codewords, and the stated rank condition provides a sufficient condition for ℓ-secrecy.Source: 2) Unified Generator Matrix · p. 4

3) Final Code:

  • Each final codeword is assembled from the precoded message portions associated with the initial partitions it intersects, using an extended final generator matrix.The extended matrix is zero for initial partitions that do not contribute to that final codeword.Source: 3) Final Code · p. 5
  • The construction preserves the base convertible code's access cost, and decoding follows from recovering the precoded message and applying the invertible transformation.The text states the decoding property for the merge regime and says the split-regime argument is similar.Source: 3) Final Code · p. 5

1) Final Secure Code:

The final-code construction precodes each message-and-key vector before applying the base final generator, yielding the effective final generator GF = P ˆGF.

2) Initial Code:

  • Each final message vector combines a secure message with a key and is encoded using an invertible precoder P.The secure-message component has length kF − ℓ, while the key has length ℓ.Source: 1) Final Secure Code · p. 5
  • The precoded vector is encoded by the base final generator ˆGF to produce the final codeword.The codeword is d(j) = m(j)P ˆGF.Source: 1) Final Secure Code · p. 5
  • The effective generator matrix for the final configuration is GF = P ˆGF.Source: 1) Final Secure Code · p. 5

2) Initial Code:

The initial codeword is represented using an extended generator matrix that aligns the initial partition with the final-codeword partitions contributing to it.

2) Initial Code:

  • For each initial partition Ui, the set Si identifies the final partitions that intersect it.The initial message symbols are grouped by these intersections, whose coordinate sets partition Ui.Source: 2) Initial Code · p. 6
  • The extended initial generator matrix represents the encoding of [s κ] into the i-th initial codeword.For a final-partition index outside Si, the corresponding extended matrix is zero.Source: 2) Initial Code · p. 6
  • The i-th initial codeword is formed by applying that extended generator to the precoded message and key.The passage gives c(i) = [s κ]P ˆGI ext,i.Source: 2) Initial Code · p. 6

3) Unified Generator Matrix:

The joint generator matrix represents the encoding of all initial and final codewords. For λI < λF, the secrecy condition is tested across symbols from both configurations.

3) Unified Generator Matrix:

  • For λI < λF, Gjoint jointly describes all initial and final codewords and has size λF kF × (λI nI + λF nF).The construction assumes λI kI = λF kF.Source: 3) Unified Generator Matrix · p. 6
  • Gjoint is formed as P D times the base joint matrix ˆGjoint, whose blocks include extended initial generator matrices and repeated final generator matrices.The extended initial matrices map the concatenated final-message vector to each initial codeword.Source: 3) Unified Generator Matrix · p. 6
  • ℓ-secrecy follows if every full-column-rank accessed submatrix of ˆGjoint remains full column rank after multiplication by the key-component matrix Pκ,D.The proof uses the invertibility of P D to preserve the relevant rank.Source: 3) Unified Generator Matrix · p. 6

IV. SECURE CONVERTIBLE CODES FROM MRD CODES

The MRD-based construction uses a precoding matrix derived from an MRD code to secure convertible codes. It applies across valid merge and split parameters, with a large field-size requirement.

IV. SECURE CONVERTIBLE CODES FROM MRD CODES

  • Known MRD constructions such as Gabidulin codes require m ≥ kI, implying field size O(q^kI) in the λI ≥ λF regime.q is the field size required by the underlying access-optimal convertible code.Source: §IV · p. 7
  • A generator matrix Pκ of an [kI, ℓ] MRD code is used in the precoder with systematic generator matrices from any access-optimal convertible code.The resulting matrices satisfy the ℓ-secrecy property.Source: §IV · p. 7
  • The secrecy proof derives a contradiction because a nonzero dual-MRD codeword must have rank at least ℓ+1, while its entries imply rank at most ℓ.The entries of the relevant vector are Fq-linear combinations of v1 through vℓ.Source: §IV · p. 7
  • The MRD-based construction yields access-optimal secure convertible codes in merge and split regimes for all valid parameters, with field size O(q^min(kF,kI)).Here q is the field size required by the underlying access-optimal convertible code.Source: §IV · p. 7

V. SECURE CONVERTIBLE CODES FROM GRS CODES

The GRS-based construction reduces the field-size requirement while preserving secrecy guarantees for specified merge and split parameter ranges. Its scope is narrower than the MRD-based construction.

V. SECURE CONVERTIBLE CODES FROM GRS CODES

  • The GRS-based construction requires only a base field of size q, reducing the field-size requirement from exponential to linear in code length.The MRD-based construction's field size grows exponentially with min(kI, kF).Source: §V · p. 7
  • For the merge construction, the initial and final GRS generator matrices use a parallel-block-reconstructible matrix, with λI ≤ max(rF, rI).The construction relies on initial and final codes from the GRS family.Source: §V · p. 7
  • The GRS construction gives an (ℓ, kS)-secure convertible code with kS = λI(kI − ℓ) when λI ≤ max(rI, rF).Interchanging initial and final codes gives a split-regime construction when λF ≤ max(rI, rF).Source: §V · p. 8

APPENDIX

The appendix proves ℓ-secrecy by showing that the key-component matrix preserves full rank for the eavesdropper's accessed symbols. The argument uses the GRS construction's block-reconstructibility property.

APPENDIX

  • Parallel-block-reconstructibility makes each final parity column in a row block a nonzero scalar multiple of an initial parity column.This property is used in proving ℓ-secrecy.Source: APPENDIX · p. 9
  • The proof reduces secrecy to showing that Pκ,D ˆGjoint(:, B) has full rank whenever the accessed submatrix ˆGjoint(:, B) has full rank.The access set B includes symbols from initial codewords and final-code parity symbols, and contains at most ℓ symbols.Source: APPENDIX · p. 9
  • The proof uses the [nI, ℓ]-MDS property of Pκ ˆGI to establish full column rank on Si, then concludes the null space is trivial.This yields full rank for Pκ,D ˆGjoint(:, B) and hence ℓ-secrecy.Source: APPENDIX · p. 9
Loading 2610.34863v1…