Reconstructing Truncated Sequences Derived From Primitive Sequences Over Integer Residue Rings

Under the influence of eSTREAM project,it is universally accepted that a secure stream cipher should be built on nonlinear driving blocks.Since the existence of complex carry operations,the linear recurring sequences over integer residue rings(called sequences over rings in short)inherently have complex nonlinear structure at the bit level.We can get a number of binary nonlinear sequences by the 2-adic expansion of the sequences over rings.These nonlinear sequences have many excellent cryptographic properties,such as a large period,good element distribution and so on,which cater to the requirement of a secure stream cipher.Therefore,the sequences over rings become an important object in the research of the current stream cipher.This dissertation explores the security of the sequences over rings from the perspective of inverse reconstruction.Let m be a integer,(?) =(at)t?0 be a primitive sequence and l?2.we call (?) mod 2l=(at mod 2l)t?0 be an l-bit truncated sequence of (?).We study the problem of how to recover the original primitive sequences under the condition that the value of (?) mod 2l at some point(succession or discrete)is known,which is called the problem of reconstructing truncated sequences derived from sequences over rings.It is of great significance to the design of the cryptographic algorithm based on the sequences over rings.The main results are as follow:1.A recovering algorithm is presented based on the lattice basis reduction algorithm.Firstly,the problem of reconstruction of truncated sequences can be reduced to the problem of finding small integer solutions to systems of linear congruences.Hence,it can be solved by lattice basis reduction algorithm.Then we improve the algorithm of finding small integer solutions to systems of linear congruences by substituting variables.The correctness of the above reconstruction has been verified experimentally.That is to say,when the recursive relationship is known,we can recover the primitive sequences of order 16 over Z/(231-1)of the ZUC algorithm from its 8 least significant bits with about 128 elements.2.The lower bound of the number of elements required for the reconstruction of truncated sequences is given.The problem of reconstruction of truncated sequences is reduced to the lattice closest vector problem.When m be a square-free odd integer,we prove that the original sequences can be uniquely reconstructed by d elements of its l least significant bits with the probability at least 1-1/m if l?2 and d?O((n+1)log m/l-1).The above result is obtained under the assumption that one can access to an oracle for the lattice closest vector problem for the infinity norm.Moreover,the correctness of the above theoretical result has been verified experimentally when the dimension of lattice is small.