Function fields produce secure multi-sequences with large complexity
Multi-sequences with large linear and error linear complexity from function fields
Information Theory
Summary
Stream ciphers protect messages by mixing data with sequences that are hard to predict. The authors developed a way to create multi-sequences—sets of sequences that run together—that have high linear complexity, meaning they are difficult for attackers to approximate or decode. They also maintain this complexity even when some errors occur. Their approach uses mathematical structures called function fields and leads to many new sequences with different lengths and properties. Additionally, they generated new types of error-correcting codes from the same ideas.
What this means in practice
- •For cryptographers: Design strong stream cipher sequences that resist decoding and errors using multi-sequences built from function fields.
- •For coding theory engineers: Create new quasi-cyclic algebraic geometric codes with improved parameters for data transmission and storage systems.
Authors
Xubin Hu, Shu Liu, Liming Ma, Chaoping Xing
Abstract
The linear complexity and the error linear complexity of multi-sequences are measures for security in stream ciphers. In this manuscript, we present a general framework for constructing periodic multi-sequences via function fields. We prove that the constructed multi-sequences possess both large linear complexity and large error linear complexity. We apply this framework of constructing multi-sequences to various maximal function fields and we obtain many new multi-sequences with various lengths and dimensions. As a byproduct, we adopt this idea and produce many new quasi-cyclic algebraic geometric codes as well.