Primitive Polynomials for Robust Scramblers and Stream Ciphers Against Reverse Engineering

File Size Format
65869_1.pdf 139Kb Adobe PDF View
Title Primitive Polynomials for Robust Scramblers and Stream Ciphers Against Reverse Engineering
Author Wu, Xin-Wen; Koh, Soo Ngee; Chui, Chee-Cheon
Publication Title 2010 IEEE International Symposium on Information Theory, Proceedings
Editor Michael Gastpar, Robert W. Heath, Jr, and Krishna Narayanan
Year Published 2010
Place of publication Unites States
Publisher IEEE
Abstract A linear feedback shift register (LFSR) is a basic component of a linear scrambler and a stream cipher for a communication system. And primitive polynomials are used as the feedback polynomials of the LFSRs. In a non-cooperative context, the reverse-engineering of a linear scrambler and a stream cipher includes recovering the feedback polynomials and the LFSR’s initial states (which are the secret keys in the case of stream ciphers). The problem of recovering the secret keys of stream ciphers has been extensively studied. For example, an effective approach for recovering a secret key is known as the correlation attack in the literature. The problem of reconstructing the feedback polynomials of a stream cipher and a linear scrambler has been studied recently. Both recovering the LFSR initial states by the above-mentioned correlation attack and reconstructing the feedback polynomials are highly dependent on an assumption, that is, they require that the feedback polynomials have sparse multiples of moderate degrees. Hence, in order to build linear scramblers and stream ciphers that are robust against reverse engineering, we should use primitive polynomials which do not have sparse multiples of moderate degrees. In this paper, we study the existence of primitive polynomials which do not have sparse multiples of moderate degrees, and the density of such primitive polynomials among all primitive polynomials. Our results on the existence and density of such primitive polynomials are better than the previous results in the literature.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1109/ISIT.2010.5513547
Copyright Statement Copyright 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
ISBN 978-1-4244-6960-4
Conference name ISIT 2010
Location Austin, United States
Date From 2010-06-13
Date To 2010-06-18
URI http://hdl.handle.net/10072/36970
Date Accessioned 2010-12-02
Date Available 2012-09-02T23:14:56Z
Language en_US
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject PRE2009-Computation Theory and Mathematics
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice