On Linear Complexity of Finite Sequences : Coding Theory and Applications to Cryptography

Edoardo Persichetti; Tovohery Randrianarisoa

Paper 2022/966

On Linear Complexity of Finite Sequences : Coding Theory and Applications to Cryptography

Edoardo Persichetti

, Florida Atlantic University

Tovohery Randrianarisoa

, Florida Atlantic University

Abstract

We define two metrics on vector spaces over a finite field using the linear complexity of finite sequences. We then develop coding theory notions for these metrics and study their properties. We give a Singleton-like bound as well as constructions of subspaces achieving this bound. We also provide an asymptotic Gilbert-Varshamov-like bound for random subspaces. We show how to reduce the problem of finding codewords with given Hamming weight into a problem of finding a vector of a given linear complexity. This implies that our new metric can be used for cryptography in a similar way to what is currently done in the code-based setting.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. IWSEC 2022
Keywords: Linear Complexity Coding Theory Digital Signatures
Contact author(s): epersichetti @ fau edu
trandrianarisoa @ fau edu
History: 2022-07-28: approved; 2022-07-27: received; See all versions
Short URL: https://ia.cr/2022/966
License: CC BY

BibTeX

@misc{cryptoeprint:2022/966,
      author = {Edoardo Persichetti and Tovohery Randrianarisoa},
      title = {On Linear Complexity of Finite Sequences : Coding Theory and Applications to Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2022/966},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/966}},
      url = {https://eprint.iacr.org/2022/966}
}