On Boolean functions in the context of coding theory and cryptography

(1)

ON BOOLEAN FUNCTIONS IN THE CONTEXT OF CODING THEORY AND CRYPTOGRAPHY

By

ANAND BALLABH JOSHI

Department of Mathematics

Submitted in fulfillment of the requirements of the degree of Doctor of Philosophy

to the

Indian Institute of Technology Delhi

July 2012

(2)

Certificate

This is to certify that the thesis entitled “On Boolean Functions in the Context of Coding Theory and Cryptography” submitted by “Mr. Anand Ballabh Joshi” to the Indian Institute of Technology Delhi, for the award of the Degree of Doctor of Philosophy, is a record of the original bona fide research work carried out by him under our supervision and guidance. The thesis has reached the standards fulfilling the requirements of the regulations relating to the degree.

The results contained in this thesis have not been submitted in part or full to any other university or institute for the award of any degree or diploma.

Dr. R. K. Sharma Dr. Sugata Gangopadhyay

Professor Associate Professor

Department of Mathematics ISI Chennai Center

IIT Delhi, Delhi Chennai

(3)

Acknowledgements

This thesis could not have been written without the stimulation, cooperation and support, which I have received from many people. I am taking this opportunity to express my gratitude to all those who are associated to me directly or indirectly, throughout my Ph.D. work.

My first and foremost heart-felt gratitude goes to my supervisors Prof. R. K. Sharma and Dr. Sugata Gangopadhyay for their valuable guidance. I am very much thankful to them for their care and interests on my work, for stimulating discussions, and for their valuable advices on a number of issues during my research work. Apart from academics, they always gave me moral support for every problem of my life.

I can not forget the unconditional support, encouragement, motivation, knowledge got from Prof. R.

K. Sharma. I always appreciate the support, knowledge and motivation which I got from Dr. Sugata Gangopadhyay, he encourages me every time for doing good research, listen and give suggestion about my personal problem too. It would not have been possible to reach here without the support of these two guys.

I acknowledge Council of Scientific & Industrial Research, New Delhi, India for providing financial support during the research period. I also thank IIT Delhi authorities for providing the essential academic as well as campus facilities for pursuing the research. I express my regards to Prof. B. S. Panda, Head of the Department, Dr. Aparna Mehra, Dr. Anima Nagar and Dr. Dharamrajan for their suggestions, support and affection. Special thanks to my SRC (Student Research Committee) members: Dr. Wagish Shukla and Dr. S. K. Gupta for their valuable suggestions. I express my gratitude to all the faculty members of Department of Mathematics, IIT Delhi, for their suggestions.

I am thankful to Prof. Rudolf Mathar, and Dr. Anupam Chatopadhayay RWTH university Aachen, Germany, for their valuable suggestions on my research work. I am thankful to Dr. Aditi Gangopadhay IIT Roorkee. I am also thankful to the authorities of, IIT Roorkee, for providing me accommodation

(4)

I am very much thankful to European Commission for providing me scholarship for the period of one and half year, for my research visit to RWTH university, Germany. I thanks to Prof. Rudolf Mathar, Head of the department, Theoretical Information Technologies (TI), RWTH university, Germany, for providing me essential academic facilities, in his department, for pursuing my research work during my stay in Germany. Thanks to Prof. Garhard Lakemeyer for his support in the RWTH university. I would like to thanks to Wolfgang, Alex, Milan, Paung, Haaren, Karu, and Shalini my research colleagues in RWTH university.

I am quite fortunate to have friends like Alok, Sarvesh, Balchand, Sunil, Sunil P, Dhirender, Ratikant, Amit, Subho, Vandana, Puneet, Sudhakar and Pooja. Thanks for all the care, love, understanding, and encouragement. I spent a great time with them. Thanks to Arpit, R. Delhi Babu and sunny, I had a great time with these guys in Aachen (Germany). Thanks to Prof. Bhagwan for his support and valuable advise in Aachen (Germany).

It is my pleasure to thank my senior colleagues Dr. Kanchan, Dr. Megha, Dr. Pandey, and Dr.

Mukesh. I have gained a lot of experience from them. Thanks to my college friends Ashish and Nitin for their constant inspirations. Thanks to my friends Richansu, Mayank, Danish, and Lalit. Thanks to Anand Sir and Dubey Sir.

Last but not least I am very much thankful to my family members my father K. B. joshi, my mother Kamala Joshi, my elder and younger brothers, my sister, my sister-in-laws, my brother-in-laws and my wife for their love, affection, support, and the unfailing faith they have on me. I can not forget the love and caring nature of my my parents, there is a constant blessing of their in my every work. Behind this work there was a constant and continuous support of my parents, my brothers, sister and brother-in-law.

Thanks to my brothers Madan and Ashok for encouraging, motivating and giving me a helping hand always. Thanks to my sister Pushpa and brother-in-law B. D. Kandpal for giving me valuable advises.

Thanks to my wife Ranjana for her suggestions, motivation and patience.

New Delhi Anand Ballabh Joshi

July 2012

(5)

Abstract

The work of this thesis is related to the generalization and construction of Boolean bent functions. The notion of bent function was introduced by Rothaus in 1976. Bent functions on Fⁿ2 with n even and F2 denoting the two-element field, have maximal distance to the set of all affine functions. This outstanding property, with connection to coding theory and cryptography, makes them interesting objects to study. Since the introduction of bent functions, substantial efforts have been directed towards their study in the last three decades. Despite their simple and natural definition, bent functions have turned out to admit a very complicated structure in general. Construction of bent functions is still an important open problem. Many primary and secondary constructions are known but a general understanding of bent functions is still missing.

Many attempts have been made to generalize the bent functions. In 1985, P. V.

Kumar, R. A. Scholtz, and L. R. Welch proposed a natural generalization of bent functions, aiming to constructq-valued bent sequences applicable in CDMA systems. In 2005, a quite natural generalization was given by H. Dobbertin and G. Leander and the goal of this generalization was to give a recursive framework to generate Boolean bent functions. A main obstacle in the study of bent functions is the lack of recurrence laws.

There are only few constructions deriving bent functions from smaller ones. Dobbertin and Leander first time embedded bent functions into the recursive framework ofZ-bent functions. They considered integer-valued functions f on Fⁿ2 with the property that their dual, its Fourier transform ˆf, is also integer-valued. They called these functions Z-bent functions. TheseZ-bent functions can be separated into different levels. Here

(6)

problem of constructingZ-bent functions of arbitrary level. First we generalize partial spreads type bent functions into partial spreads type Z-bent functions and construct partial spreads type class ofZ-bent functions of arbitrary levelr≥1. We also construct P S_ap typeZ-bent functions of levelr ≥1. We show that the dual of P S_ap typeZ-bent function of levelr is also aP S_ap type Z-bent function of levelr.

The motivation behind our work is to give a new primary construction of bent functions using the generalize bent functions which are calledZ-bent functions. Higher level Z-bent functions form building blocks that can be glued together under certain conditions in order to get larger Z-bent functions of lower level. TheZ-bent functions of level r on n variables can be used to construct Z-bent functions of level r −1 on n+ 2 variables by a ‘gluing’ technique introduced by Dobbertin and Leander. In this recursion one finally get the usual bent functions at level zero. We give a new primary construction of classical bent functions using Z-bent functions. We generate all the P S_ap type Z-bent functions of level 1 on 4 variables and “glue” them to construct bent functions on 6 variables. We get all the 6 variables bent functions up to affine equivalence by gluing these P S_ap type Z-bent functions of level 1 on 4 variables. We obtain an 8 variables bent function by using the construction method given by us and demonstrate that it is not equivalent to any P S_ap or Maiorana-McFarland type function.

Study and analysis of different properties of Z-bent functions of different level is important due to the success of recursive law. We generalize the concept of crosscor- relation and autocorrelation of bent functions for Z-bent functions of level r. We find the crosscorrelatio and autocorrelation of partial spreads typeZ-bent functions of level 1.

Finally we construct some particular type of Z-bent functions. We construct Z- bent functions which are analogous to the Maiorana-McFarland type bent functions.

We give the characterization of some functions when they are oddZ-bent functions of level one. We define the rotation symmetricZ-bent functions of level r. We get all the rotation symmetricZ-bent functions of level 1, glue these functions and get the bent

(7)

functions on 6 variables.

(8)

On Boolean functions in the context of coding theory and cryptography