Fast construction of binary ring FCSRs for hardware stream ciphers
type: Item
instance of: scholarly article
title: Fast construction of binary ring FCSRs for hardware stream ciphers
zbMATH Open document ID: 1391.14049
author: Xianqiang Yang
published in: Designs, Codes and Cryptography
publication date: 2018-04-10T00:00:00Z
review text: \textit{A. Klapper} and \textit{M. Goresky} introduced in [Lect. Notes Comput. Sci. 809, 174--178 (1994; Zbl 0943.94515)] feedback with carry shift registers (FCSRs) as an alternative to linear feedback shift registers because the latter are sensible to algebraic attacks. However, FCSRs are also weak against algebraic attacks when the Galois representation is used. In order to solve thios problem \textit{F. Arnault} et al. have introduced a ring FCSRs [Lect. Notes Comput. Sci. 5867, 433--448 (2009; Zbl 1267.94032)]. A ring FCSRs has a main shift register on \(n\) binary cells \(m=(m_0,\dots,m_{n-1})\) and a carry register with \(n\) integer cells \(c=(c_0,\dots,c_{n-1})\). They are updated as follows: \(m(t+1)= A m(t)+c(t)\pmod 2\) \(c(t+1)= A m(t)+c(t)(\operatorname{div} 2)\) where the \(A\), the transition matrix, is an \(n\times n\) matrix with entries either \(0\) or \(1\) of the form \[ \begin{pmatrix} \ast & 1 & & & \\ &\ast & 1 & &(\ast) \\ &&\ast & 1 & \\ &(\ast)&&\ast & 1 \\ 1&&&&\ast \\ \end{pmatrix} \] i.e., \(a_{k,k+1}=1\) and \(a_{n,1}=1\). The authors provide a fast algorithm to construct binary ring FCSRs. In particular their algorithm construct a binary transition matrix , \(A\), satisfying the following conditions: {\parindent=0.7cm\begin{itemize}\item[(C1)] Let \(q=\det(I-2A)\) then \(| q|\) is a prime number with 2 as a primitive root. \item[(C2)] \((| q|-1)/2\) is a prime number. \item[(C3)] The super diagonal of the transition matrix is full of ones. \item[(C4)] The number of nonzero entries for a given row or a given column must be at most 2. \end{itemize}} For it they explicitly compute \(\det(I-2A)\) which help to ensure conditions (C1) and (C2) and design and strategy to construct \(A\) which also verify (C3) and (C4).
reviewed by: Fernando Hernando
Mathematics Subject Classification ID: 94A55
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 6858032
zbMATH Keywords: stream cipher
zbMATH Keywords: l-sequences
zbMATH Keywords: 2-adic ring
zbMATH Keywords: FCSRs
zbMATH Keywords: transition matrix
MaRDI profile type: Publication
full work available at URL: s10623-017-0370-4
OpenAlex ID: W2619201850
Wikidata QID: Q121308106
cites work: 2-Adic shift registers
cites work: Feedback shift registers, 2-adic span, and combiners with memory
cites work: A Survey of Feedback with Carry Shift Registers
cites work: Q2757250
cites work: Fibonacci and Galois representations of feedback-with-carry shift registers
cites work: Fast Software Encryption
cites work: Breaking the stream ciphers F-FCSR-H and F-FCSR-16 in real time
cites work: An efficient state recovery attack on the X-FCSR family of stream ciphers
cites work: A New Approach for FCSRs
cites work: A matrix approach for FCSR automata
cites work: Revisiting LFSRs for Cryptographic Applications
cites work: Construction of Transition Matrices for Ternary Ring Feedback With Carry Shift Registers
cites work: A generalized birthday approach for efficiently finding linear relations in \(\ell\)-sequences
cites work: Linearity properties of binary FCSR sequences
DOI: 10.1007/S10623-017-0370-4
Recommended article: A New Approach for FCSRs
Recommended article: Cryptanalysis of Pseudo-random Generators Based on Vectorial FCSRs
Recommended article: A generalized birthday approach for efficiently finding linear relations in \(\ell\)-sequences
Recommended article: Algebraic feedback shift registers
Recommended article: Practical construction of ring LFSRs and ring FCSRs with low diffusion delay for hardware cryptographic applications
Recommended article: Feedback shift registers, 2-adic span, and combiners with memory
Recommended article: Entropy of the Internal State of an FCSR in Galois Representation
Recommended article: Software Oriented Stream Ciphers Based upon FCSRs in Diversified Mode
description: scientific article; zbMATH DE number 6858032