-------------------------------------------------------------------------------
                                       
                                       
                   B O S T O N   U N I V E R S I T Y
                                       
                      Computer Science Department
                                       
                          C O L L O Q U I U M

   Algebraic Feedback Shift Registers and the Security of Stream Ciphers

                            Andrew Klapper 
            Dept. of Computer Science, University of Kentucky


 			Wednesday, February 16 
                                      
                               4:00 PM
                       (Coffee served at 3:45pm)

                                       
                         Seminar Room / MCS 135
                                       

    Linear feedback shift registers (LFSRs) are simple, fast generators of 
    binary sequences that have been used for the past four decades in a 
    wide variety of applications, such as spread spectrum communication,
    radar, Monte Carlo simulation, and error correcting codes.  They have
    been used in cryptography both for cryptanalysis and as building blocks
    for fast stream ciphers.

    In 1994, in joint work with Mark Goresky, I invented a new type of 
    binary sequence generator called Feedback with Carry Shift Registers 
    (FCSRs).  These generators have many properties that are parallel to 
    those of LFSRs.  In this talk I will survey what we have learned about 
    FCSRs in the ensuing years.  I will discuss their structure and basic 
    properties, the algebraic tools that can be used to analyze them, and 
    their use in cryptanalysis.  I will also describe a generalization that
    encompasses both LFSRs and FCSRs.

    For cryptography, a fundamental question about a sequence is whether
    a generator of the sequence can be found from a short subsequence (this
    is known as the register synthesis problem).  I will describe two 
    solutions to this problem that work for different generalizations of
    FCSRs.

    This is joint work with Mark Goresky and Jinzhong Xu.

-------------------------------------------------------------------------------

    Host:  Steve Homer (homer@cs.bu.edu)

-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------------