Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On analysis and synthesis of (n, k)-Non-Linear Feedback Shift Registers
KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.ORCID iD: 0000-0001-7382-9408
KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
2008 (English)In: 2008 Design, Automation And Test In Europe: Vols 1-3, 2008, 1128-1133 p.Conference paper, Published paper (Refereed)
Abstract [en]

Non-Linear Feedback Shift Registers (NLFSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for generating pseudo-random sequences for stream ciphers. In this paper, we introduce (n, k)-NLFSRs which can be considered a generalization of the Galois type of LFSR. In an (n, k)-NLFSR, the feedback can be taken from any of the n bits, and the next state functions can be any Boolean function of up to k variables. Our motivation for considering this type NLFSRs is that their Galois configuration makes it possible to compute each next state function in parallel, thus increasing the speed of output sequence generation. Thus, for stream cipher application where the encryption speed is important, (n,k)-NLFSRs may be a better alternative than the traditional Fibonacci ones. We derive a number of properties of (n,k)NLFSRs. First, we demonstrate that they are capable of generating output sequences with good statistical properties which cannot be generated by the Fibonacci type of NLFSRs. Second, we show that the period of the output sequence of an (n, k)-NLFSR is not necessarily equal to the length of the largest cycle of its states. Third, we compute the period of an (n,k)-NLFSR constructed from several parallel NLFSRs whose outputs are XOR-ed and show how to maximize this period. We also present an algorithm for estimating the length of cycles of states of (n, k)-NLFSRs which uses Binary Decision Diagrams for representing the set of states and the transition relation on this set.

Place, publisher, year, edition, pages
2008. 1128-1133 p.
Series
Design, Automation and Test in Europe Conference and Expo, ISSN 1530-1591
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-38755DOI: 10.1109/DATE.2008.4484856ISI: 000257940700195Scopus ID: 2-s2.0-49749116065ISBN: 978-3-9810801-3-1 (print)OAI: oai:DiVA.org:kth-38755DiVA: diva2:439260
Conference
Design, Automation and Test in Europe, DATE 2008; Munich; 10 March 2008 through 14 March 2008
Available from: 2011-09-07 Created: 2011-08-31 Last updated: 2011-09-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Dubrova, Elena

Search in DiVA

By author/editor
Dubrova, ElenaTeslenko, MaximTenhunen, Hannu
By organisation
Electronic, Computer and Software Systems, ECS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 39 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf