sesa 16(7): e3

Research Article

Filtering Nonlinear Feedback Shift Registers using Welch-Gong Transformations for Securing RFID Applications

Download998 downloads
  • @ARTICLE{10.4108/eai.8-12-2016.151726,
        author={Kalikinkar Mandal and Guang Gong},
        title={Filtering Nonlinear Feedback Shift Registers using Welch-Gong Transformations for Securing RFID Applications},
        journal={EAI Endorsed Transactions on Security and Safety},
        volume={3},
        number={7},
        publisher={EAI},
        journal_a={SESA},
        year={2016},
        month={12},
        keywords={Nonlinear feedback shift registers, pseudorandom sequence generators, stream ciphers,WG-7 stream cipher, RFID},
        doi={10.4108/eai.8-12-2016.151726}
    }
    
  • Kalikinkar Mandal
    Guang Gong
    Year: 2016
    Filtering Nonlinear Feedback Shift Registers using Welch-Gong Transformations for Securing RFID Applications
    SESA
    EAI
    DOI: 10.4108/eai.8-12-2016.151726
Kalikinkar Mandal1,*, Guang Gong1
  • 1: Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, N2L 3G1, CANADA
*Contact email: kmandal@uwaterloo.ca

Abstract

Pseudorandom number generators play an important role to provide security and privacy on radio frequency identi cation (RFID) tags. In particular, the EPC Class 1 Generation 2 (EPC C1 Gen2) standard uses a pseudorandom number generator in the tag identi cation protocol. In this paper, we rst present a pseudorandom number generator family, we call it the ltering nonlinear feedback shift register using Welch-Gong (WG) transformations ( ltering WG-NLFSR) and propose an instance of this family for EPC C1 Gen2 RFID tags. We then investigate the periodicity of a sequence generated by the ltering WG-NLFSR by considering the model, named nonlinear feedback shift registers using Welch-Gong (WG) transformations (WG-NLFSR). The periodicity of WG-NLFSR sequences is investigated in two ways. First, we perform the cycle decomposition of WG-NLFSR recurrence relations over di erent nite elds by computer simulations where the nonlinear recurrence relation is composed of a characteristic polynomial and a WG transformation module. Second, we conduct an empirical study on the period distribution of the sequences generated by the WG-NLFSR. The empirical study shows that a sequence with period bounded below by the square root of the maximum period can be generated by the WG-NLFSR with high probability for any initial state. Furthermore, we study the cycle structure and randomness properties of a composited recurrence relation and its sequences, respectively over nite elds.