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

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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. IWSEC 2022
Linear Complexity Coding Theory Digital Signatures
Contact author(s)
epersichetti @ fau edu
trandrianarisoa @ fau edu
2022-07-28: approved
2022-07-27: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.