Structure of Feedforward Inverses
In Chaps. 1 and 3, we have adopted two methods, the state tree method and the R a R b transformation method, to deal with the structure problem. The former is suitable for general finite automata but not easy to manipulate for large parameters. Contrarily
- PDF / 2,983,894 Bytes
- 410 Pages / 439.371 x 666.139 pts Page_size
- 72 Downloads / 235 Views
Finite Automata and Application to Cryptography
Foreword The important summarizing work of RENJI TAO appears now in book form. It is a great pleasure for me to see this happen, especially because I have known Professor Tao as one of the very early contributors to public-key cryptography. The research community has missed a book such as the present one now published by Tsinghua University Press and Springer. The book will be of special interest for students and researchers in the theories of finite automata, cryptography and error correcting codes. One of the phenomena characterizing the second half of the last century is the rapid growth of computer science and informatics in general. The theory of finite automata, models of computing devices with a finite non-extensible memory, was initiated in the 1940s and 1950s, mainly by McCulloch, Pitts and Kleene. It has found numerous applications in most diverse areas, as exemplified by the series of yearly international conferences in implementation and applications of finite automata. The present work by Professor Tao develops a theory and contains strong results concerning invertible finite automata: the input sequence can be recovered from the output sequence. This is a desirable feature both in cryptography and error correcting codes. The book considers various types of invertibility and, for instance, the effect of bounded delay to invertibility. Cryptography, secret writing, has grown enormously both in extent and importance and quality during the past few decades. This is obvious in view of the fact that so many transactions and so much confidential information are nowadays sent over the Internet. After the introduction of public-key cryptography by Diffie and Hellman in the 1970s, many devices were tried and applied for the construction of public-key cryptosystems. Professor Tao was one of such initiators in applying invertible finite automata. Although mostly in Chinese, his work was known also in the West. I referred to it already some twenty years ago. Later on, for instance, a PhD thesis was written about this topic in my university. Many of the results in this book appear now for the first time in book form. The book systematizes important and essential results, as well as gives a comprehensive list of references. It can be used also as a starting point for further study. Different parts of the book are of varying importance for students and researchers, depending on their particular interests. Professor Tao gives useful guidelines about this in his Preface.
ii
Foreword
Much of the material in this book has not been previously available for western researchers. As a consequence, some of the results obtained by Professor Tao and his group already in the late 1970s have been independently rediscovered later. This concerns especially shift register sequences, for instance, the decimation sequence and the linear complexity of the product sequence. I feel grateful and honored that Professor Tao has asked me to write this preface. I wish success for the book. Turku, Finla
Data Loading...
