On Linear Complexity of Finite Sequences: Coding Theory and Applications to Cryptography
On Linear Complexity of Finite Sequences: Coding Theory and Applications to Cryptography
复制标题
DOI：
10.1007/978-3-031-15255-9_2
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Edoardo Persichetti;T. Randrianarisoa
中科院分区：
文献类型：
--
作者：
Edoardo Persichetti;T. Randrianarisoa
利用有限序列的线性复杂性，我们在有限域上的向量空间上定义了两个度量。然后，我们发展了这些度量的编码理论概念，并研究了它们的性质。我们给出了一个类Singleton的界，以及达到这个界的子空间的构造。我们还给出了随机子空间的一个类似Gilbert-Varshamov的渐近界。我们展示了如何将寻找具有给定汉明重量的码字的问题简化为寻找具有给定线性复杂度的向量的问题。这意味着我们的新度量可以用于密码学，其方式与当前在基于代码的设置中所做的类似。
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.