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

##### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/966

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.