Change search
ReferencesLink to record
Permanent link

Direct link
An Algorithm for Constructing a Fastest Galois NLFSR Generating a Given Sequence
KTH, School of Information and Communication Technology (ICT), Electronic Systems.
KTH, School of Information and Communication Technology (ICT), Electronic Systems.
KTH, School of Information and Communication Technology (ICT), Electronic Systems.ORCID iD: 0000-0001-7382-9408
2010 (English)In: SEQUENCES AND THEIR APPLICATIONS-SETA 2010 / [ed] Carlet C; Pott A, 2010, Vol. 6338, 41-54 p.Conference paper (Refereed)
Abstract [en]

The problem of efficient implementation of security mechanisms for advanced contactless technologies like RFID is gaining increasing attention. Severe constraints on resources such as area, power consumption, and production cost make the application of traditional cryptographic techniques to these technologies a challenging task. Non-Linear Feedback Shift Register (NLFSR)-based stream ciphers are promising candidates for cryptographic primitives for RFIDs because they have the smallest hardware footprint of all existing cryptographic systems. This paper presents a heuristic algorithm for constructing a fastest Galois NLFSR generating a given sequence. The algorithm takes an NLFSR in the Fibonacci configuration and transforms it to an equivalent Galois NLFSR which has the minimal delay. Our key idea is to find a best position for a given feedback connection without changing the positions of the other feedback connections. We use a technology dependent cost function which approximates the delay of an NLFSR after the technology mapping. The experimental results on 57 NLFSRs used in existing stream ciphers show that, on average, the presented algorithm allows us to decrease the delay by 25.5% as well as to reduce the area by 4.1%.

Place, publisher, year, edition, pages
2010. Vol. 6338, 41-54 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 6338
Keyword [en]
Best position, Contactless technology, Cryptographic primitives, Cryptographic systems, Cryptographic techniques, Efficient implementation, Feedback connection, Fibonacci, Non-linear, Power Consumption, Production cost, Security mechanism, Stream Ciphers, Technology mapping, Computer hardware description languages, Cryptography, Heuristic algorithms, Hydraulics, Shift registers
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-31370DOI: 10.1007/978-3-642-15874-2_3ISI: 000286453100003ScopusID: 2-s2.0-78249252672ISBN: 978-3-642-15873-5OAI: diva2:404051
6th International Conference on Sequences and Their Applications, Telecom ParisTech, Paris, FRANCE, SEP 13-17, 2010
QC 20110315Available from: 2011-03-15 Created: 2011-03-14 Last updated: 2011-03-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Chabloz, Jean-MichelSharif Mansouri, ShohrehDubrova, Elena
By organisation
Electronic Systems
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 60 hits
ReferencesLink to record
Permanent link

Direct link