Paper 2022/966 Original: eprint.iacr.org/2022/966 ↗
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2022-07-27: last updated
- 2022-07-27: published
- Short URL
- https://ia.cr/2022/966
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2022/966}
}