An Algorithm for Constructing a Fastest Galois NLFSR Generating a Given Sequence
2010 (English)In: SEQUENCES AND THEIR APPLICATIONS-SETA 2010 / [ed] Carlet C; Pott A, 2010, Vol. 6338, 41-54 p.Conference paper (Refereed)
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
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
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-31370DOI: 10.1007/978-3-642-15874-2_3ISI: 000286453100003ScopusID: 2-s2.0-78249252672ISBN: 978-3-642-15873-5OAI: oai:DiVA.org:kth-31370DiVA: diva2:404051
6th International Conference on Sequences and Their Applications, Telecom ParisTech, Paris, FRANCE, SEP 13-17, 2010
QC 201103152011-03-152011-03-142011-03-15Bibliographically approved