Scholarlink

<p>Galois nonlinear feedback shift registers (NFSRs) are used in many recent stream ciphers. One security criterion for the design of a stream cipher is to ensure that its keystream has a long period, which requires the used NFSR to have a long state cycle. Meanwhile, to avoid equivalent keys, the keystream’s period must not be compressed compared with the NFSR’s state cycle length, which can be guaranteed if the NFSR is observable. The cycle structure of a general Galois NFSR is an open hard problem, and the observability of Galois NFSRs is less studied because of the lack of efficient tools. This paper considers the cycle structure and observability of two types of Galois NFSRs, using the semi-tensor product-based Boolean network approach. It discloses that each Galois NFSR has the maximum state cycle for the first type, but has equal-length state cycles for the second. Some easily verifiable necessary and/or sufficient conditions are given for the observability of each Galois NFSR for both types, generalizing the corresponding previous results on single-cycle triangular functions. Each Galois NFSR in both types has simple feedback functions and has extensive selections for its output function to assure it to be observable, helpful for the design of stream ciphers.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Cycle structure and observability of two types of Galois NFSRs

  • 期刊论文

  • 发表日期：

    2025年6月20日

查看全文
  • Xianghan Wang,
  • Jianghua Zhong,
  • Dongdai Lin

摘要

Galois nonlinear feedback shift registers (NFSRs) are used in many recent stream ciphers. One security criterion for the design of a stream cipher is to ensure that its keystream has a long period, which requires the used NFSR to have a long state cycle. Meanwhile, to avoid equivalent keys, the keystream’s period must not be compressed compared with the NFSR’s state cycle length, which can be guaranteed if the NFSR is observable. The cycle structure of a general Galois NFSR is an open hard problem, and the observability of Galois NFSRs is less studied because of the lack of efficient tools. This paper considers the cycle structure and observability of two types of Galois NFSRs, using the semi-tensor product-based Boolean network approach. It discloses that each Galois NFSR has the maximum state cycle for the first type, but has equal-length state cycles for the second. Some easily verifiable necessary and/or sufficient conditions are given for the observability of each Galois NFSR for both types, generalizing the corresponding previous results on single-cycle triangular functions. Each Galois NFSR in both types has simple feedback functions and has extensive selections for its output function to assure it to be observable, helpful for the design of stream ciphers.