Tuesday, October 7, 2014

Book review: Signal Design for Good Correlation For Wireless Communication, Cryptography, and Radar

I recently reviewed the book "Signal Design for Good Correlation For Wireless Communication, Cryptography, and Radar" by Golomb and Gong for IACR.

This is the review of the first edition of the book \textit{Signal Design for Good Correlation for Wireless Communication, Cryptography and Radar}. The book is written by two well-known researchers with significant contributions to the theory and applications of binary sequences. In 2013, Golomb had received the National Medal of Science for his advances in mathematics and communication.

This book is very technical and offers a comprehensive coverage of signal design for various applications. It is suitable for engineers, computer scientists and graduate students working in the area of signal design for communication, radar and cryptography.

The book will be a useful reference for expert readers, engineers and computer scientists working in the area of signal design for communication, radar and cryptography. It is also suitable to be used as a textbook for graduate course in the area. Researchers working on symmetric key cryptography, especially designing and analyzing synchronous stream ciphers and random number generators based on feedback shift registers will be interested in Chapters 4, 5 and 11.

Summary of the book

The book is organized into 12 chapters. The chapters provide examples, exercises, open questions, and historical discussions on the results.  The book can benefit from structural improvements, for example introduction and organization are missing in some of the chapters.

Chapter 1: General Properties of Correlation. The first chapter of the book introduces the correlation measure, with different definitions such as continuous correlation, binary correlation and complex correlation depending on the domain of the functions. The chapter also defines autocorrelation and crosscorrelation. This chapter provides definitions, without going too much into detail. No examples or exercises are provided for the chapter.

Chapter 2: Applications of Correlation to the Communication of Information. The chapter starts with discussing maximum likelihood detectors and coherent versus incoherent detection. It also provides definitions of Hadamard and cyclic Hadamard matrices.

Chapter 3: Finite Fields. The chapter includes a brief overview of finite fields, starting with the definitions of groups and rings. Finite fields have wide range of applications in information theory, combinatorics, coding theory, and modern cryptography. A good understanding of finite fields is essential, especially for cryptographic algorithms that utilize finite fields, such as Diffie-Hellman key exchange, elliptic curve public-key cryptography, and the Digital Signature standard. The chapter presents description and properties of some of the fields that are widely used in cryptography. The chapter also provides examples, exercises and an example Maple program, along with a list of primitive polynomials for reference.
\item \textbf{Chapter 4: Feedback shift registers.} Feedback shift registers are commonly used in synchronous stream ciphers and random number generators in cryptography.  The focus of the chapter is on feedback shift registers with linear feedback polynomials; such registers are called Linear Feedback Shift Registers (LFSRs). The chapter gives different definitions and representations (matrix and trace) of LFSRs and discusses the periodicity properties of the LFSR sequences, by providing the relations between periodicity and the minimal polynomials of the registers. The chapter provides decomposition of LFSR sequences, when the feedback is a product of distinct irreducible polynomials over $F_q$. Nonlinear feedback shift registers which are more popular in recent stream cipher designs are not discussed. Part of the content is also available in Golomb’s \textit{Shift Register Sequences} book, first published in 1967.

Chapter 5: Randomness Measurements and $m$-Sequences.
This chapter presents Golomb's three randomness postulates for binary sequences; regarding frequency of ones and zeroes, number of runs, and autocorrelation. These postulates are also extended to non-binary sequences. The chapter provides a proof that shows $m$-sequences (outputs of primitive LFSRs) satisfy these randomness postulates. Part of the content of this chapter is also available in Golomb's \textit{Shift Register Sequences} book. The chapter ends by Golomb's conjecture from 1980, claiming that binary sequences that satisfy both ideal $n$-tuple distribution and two-level autocorrelation are $m$-sequences.

Chapter 6: Transforms of sequences and functions. The chapter deals with Fourier, Hadamard and convolution transforms that are important in signal processing. The chapter provides fundamental tools for designing sequences with special properties, and two-level autocorrelation.

Chapter 7: Cyclic Difference Sets and Binary Sequences with Two-level Autocorrelation. The chapter introduces cyclic difference sets which are important combinatorial tools and provides the relationship between cyclic difference sets and binary sequences with 2-level autocorrelation.

Chapter 8-9: Cyclic Hadamard Sequences, Part I and II. Cyclic Hadamard sequences have ideal autocorrelation properties. Chapter 8 and 9 are devoted to the construction of these sequences. Early construction methods (before 1997) include a method using $m$-sequences, a method based on a number theoretic approach, and a construction associated with intermediate subfields. Chapter 8 investigates general constructions of two-level autocorrelation sequences over $F_q$ with subfield decompositions. The chapter also discusses the randomness, linear span, shift-distinct property and implementation of the output sequences. Chapter 9 is devoted to the progress in new constructions (including constructions with multiple trace terms, hyper-oval constructions and Kasami power construction), since 1997.

Chapter 10: Signal Sets with Low Crosscorrelation. The chapter considers sequences with low crosscorrelation, which have important applications in CDMA communications. The chapter  first introduces basic concepts and properties for crosscorrelation of sequences, signal sets, and one-to-one correspondences among sequences, polynomial functions and Boolean functions. Next, the chapter presents three classical constructions, namely the Gold-pair construction, the Kasami set construction and the bent function signal set construction.

Chapter 11: Correlation of Boolean Functions. Construction of cryptographically strong Boolean functions are related to constructing sequences with good correlation, due to the existence of one-to-one correspondences between sequences, polynomial functions and Boolean functions. Chapter 11 deals with some of the cryptographic properties of Boolean functions such as correlation immunity, nonlinearity, and resiliency.

Chapter 12: Applications of Radar, Sonar, Synchronization and CDMA. The last chapter of the book focuses on applications. The chapter talks about different types of signals and correlations and introduces Barker and Generalized Barker sequences, optimal rulers. The chapter also includes some related open questions.

Friday, February 1, 2013

Riddle of 100 Passengers

Here is a riddle, that I came across recently. Enjoy!

There are a hundred passengers to board a plane with a hundred seats. Each passenger has a ticket with number from 1 to 100 and enters the plane in this order. The first passenger sits on seat 1, and the second sits on seat 2 and so on. However, the first passenger, instead of using his seat, chooses a random seat of the available 100. The second passenger comes in and sits in its seat, if it is available, otherwise chooses randomly from the 99 free seats. Third passenger sits in seat 3, if it is free, otherwise chooses a random seat from the remaining 98, etc. What is the probability that 100th passenger sits in the 100th seat?

Wednesday, October 10, 2012

Sunday, September 2, 2012

Another paper on NFSRs

"On the nonlinearity of maximum-length NFSR feedbacks" is published in Cryptography and Communications journal

Linear Feedback Shift Registers (LFSRs) are the main building block of many classical stream ciphers; however due to their inherent linearity, most of the LFSR-based designs do not offer the desired security levels. In the last decade, using Nonlinear Feedback Shift Registers (NFSRs) in stream ciphers became very popular. However, the theory of NFSRs is not well-understood, and there is no efficient method that constructs a cryptographically strong feedback function and also, given a feedback function it is hard to predict the period. In this paper, we study the maximum-length NFSRs, focusing on the nonlinearity of their feedback functions. First, we provide some upper bounds on the nonlinearity of the maximum-length feedback functions, and then we study the feedback functions having nonlinearity 2 in detail. We also show some techniques to improve the nonlinearity of a given feedback function using cross-joining.

Monday, July 23, 2012

AF is Short of Water!

Finally, I got the chance to visit the National Cryptologic Museum of NSA. Here you can use the German Enigma machines to encrypt your name (it is fun!), also see the huge US Navy Bombe used to decrypt Enigma. There is also a library including the David Kahn's collection. It is very interesting to listen to the stories on the impact of  cryptology. I think, one of the most interesting story is the battle of Midway. There is also a very nice gift shop! :) And, admission is free!

Monday, December 26, 2011

Evolutionary construction of de bruijn sequences

My recent paper presented at Artificial Intelligence and Security Workshop, Chicago, 2011.

A binary de Bruijn sequence of order n is a cyclic sequence of period 2n, in which each n-bit pattern appears exactly once. These sequences are commonly used in random number generation and symmetric key cryptography particularly in stream cipher design, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as a special type of traveling salesman tours and tries to find optimal solutions to this special type of the traveling salesman problem (TSP). We present some experimental results for n < 14.

Sunday, December 19, 2010

SHA-3 Finalists

NIST announced the SHA-3 Finalists on December 9, 2010. Congratulations to the designers of Blake, Grostl, JH, Keccak and Skein. Any comments?

Friday, October 1, 2010

Near-Collisions for the Reduced Round Versions of Some Second Round SHA-3 Compression Functions using Hill Climbing

Our latest paper on near-collision resistance on some of the SHA-3 candidates; Blake, Fugue, JH and Hamsi is accepted for Indocrypt 2010.

Abstract :
A hash function is near-collision resistant, if it is hard to find two messages with hash values that differ in only a small number of bits. In this study, we use hill climbing methods to evaluate the near-collision resistance of some of the second round SHA-3 candidates. We practically obtained (i) 184/256-bit near-collision for the 2-round compression function of Blake-32; (ii) 192/256-bit near-collision for the 2-round compression function of Hamsi-256; (iii) 820/1024-bit near-collisions for 10-round compression function of JH. Among the 130 possible reduced variants of Fugue-256, we practically observed collisions for 7 variants (e.g. (k; r; t) = (1; 2; 5)) and near-collisions for 26 variants (e.g. 234/256 bit near-collision for (k; r; t) = (2; 1; 8)).

We would like to thank Charanjit S. Jutla for pointing out an error in Fugue's results, in the previous version of this paper which is presented at the SHA-3 Workshop.

Saturday, August 14, 2010

On the Compression Function of Hamsi

Hamsi is a family of cryptographic hash functions designed by Ozgul Kucuk. It is one of the second round candidates. The iteration mode of Hamsi is based on the `Concatenate-Permute-Truncate` design strategy. We recently published a paper titled "Message Recovery and Pseudo-preimage Attacks on the Compression Function of Hamsi-256" at PROGRESS IN CRYPTOLOGY – LATINCRYPT 2010.

Abstract: Hamsi is one of the second round candidates of the SHA-3 competition. In this study, we present non-random differential properties for the compression function of Hamsi-256. Based on these properties, we first demonstrate a distinguishing attack that requires a few evaluations of the compression function. Then, we present a message recovery attack with a complexity of 210.48 compression function evaluations. Also, we present a pseudo-preimage attack for the compression function with complexity 2254.25.

On Feedback Functions of Maximum Length Nonlinear Feedback Shift Registers

Our recent paper on the feedback functions of maximum length NFSRs is published in IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Science.

Abstract: Feedback shift registers are basic building blocks for many cryptographic primitives. Due to the insecurities of Linear Feedback Shift Register (LFSR) based systems, the use of Nonlinear Feedback Shift Registers (NFSRs) became more popular. In this work, we study the feedback functions of NFSRs with period 2n. First, we provide two new necessary conditions for feedback functions to be maximum length. Then, we consider NFSRs with k-monomial feedback functions and focus on two extreme cases where k=4 and k=2n-1. We study construction methods for these special cases.

Sunday, December 20, 2009

A new book - Computational Intelligence in Expensive Optimization Problems

Here is a book on optimization problems. It is going to be available in April 2010. The book includes a chapter with title "An evolutionary approach for the TSP and the TSP with Backhauls" written by H. Sural, N.E. Ozdemirel, I. Onder and myself.

If you want more details from Springer web page:

"In modern science and engineering, laboratory experiments are replaced by high fidelity and computationally expensive simulations. Using such simulations reduces costs and shortens development times but introduces new challenges to design optimization process. Examples of such challenges include limited computational resource for simulation runs, complicated response surface of the simulation inputs-outputs, and etc. Under such difficulties, classical optimization and analysis methods may perform poorly. This motivates the application of computational intelligence methods such as evolutionary algorithms, neural networks and fuzzy logic, which often perform well in such settings. This is the first book to introduce the emerging field of computational intelligence in expensive optimization problems."
Computational Intelligence , Engineering Design Optimization, Evolutionary Algorithms, Expensive Problems

Tuesday, May 19, 2009

Google SkyMap

My cell phone does not support Skymap for the moment, but I really liked the idea of moving your phone to find a specific star. Well of course I don't need SkyMap to spot Orion or the polar star. But might be useful to find some of the constellations and planets.

Here is its one minute demo.:

Monday, May 18, 2009

Maximum Length NFSRs

Nowadays, I spend most of my time studying on Nonlinear Feedback Shift Registers (NFSRs). Especially the ones with Maximum period.

A feedback shift register is a device that shifts its contents into adjacent positions within the register and fills the position on the other end with a new value generated by the feedback function. If the feedback function is linear, everything is easy! :)But when you start to work on nonlinear feedback functions, things start to get a little bit harder.

There are some important unsolved problems and conjectures related to the selection of feedback function of a NFSR. There is no efficient method that finds feedback function with maximum period and also, given a feedback function it is hard to predict the period.

If you want to learn more about NFSRs, you can start with the following papers and books.

  1. H. Fredricksen. A survey of full length nonlinear shift register cyclealgorithms. Siam Review, 24(2):195–221, 1982

  2. S. W. Golomb. Shift Register Sequences. Aegean Park Press, LagunaHills, CA, USA, 1981

  3. A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook ofapplied cryptography. CRC Press, Boca Raton, Florida, 1996.

If you want to discuss anything about NFSRs, please feel free :)

Wolfram Alpha - Computational Knowledge Engine

It was officially launced today, and I had some chance to 'play' with it. I am impressed by a few of its features. One of them is when you input "ATTAGCGTTCAA", Wolfram Alpha recognizes it as a genome sequence and outputs some matches in human genome. :) Isn't that fun ? I believe it is going to be a serious competitor to Wikipedia.

There are also a few crypto related features. You can hash a given string using MD2, MD5 and SHA.

Here is a 13 minute demo, if you are interested. http://www65.wolframalpha.com/screencast/introducingwolframalpha.html