PROTOCOLS FOR RELIABLE AND SECURE MESSAGE TRANSMISSION

PROTOCOLS FOR RELIABLE AND SECUREMESSAGE TRANSMISSIONA THESISsubmitted byASHISH CHOUDHURYfor the award of the degreeofDOCTOR OF PHILOSOPHYDEPARTMENT OF COMPUTER SCIENCE AND ENGINEERINGINDIAN INSTITUTE OF TECHNOLOGY, MADRASMAY 2010

Thesis CertificateThis is to certify that the thesis entitled Protocols for Reliable and SecureMessage Transmission submitted by Ashish Choudhury to the Indian Instituteof Technology Madras, Chennai for the award of the Degree of Doctor of Philosophyis a record of bona-fide research work carried out by him under my supervision andguidance. The contents of this thesis have not been submitted to any other universityor institute for the award of any degree or diploma.Chennai 600036Research GuideDate:(Prof. C. Pandu Rangan)i

Dedicated ToTo the All Mighty Supreme Personality of Godhead Sri Krsna andto My Parents, Who Brought Me to This Worldii

AcknowledgementsFirst of all, I would like to thank my advisor Prof. C.Pandu Rangan who has beenhaving a tremendous influence on my professional development. He introduced me tothe world of Algorithms, which motivated me to do research in Theoretical ComputerScience, specially in the field of cryptography. I still remember the day when I wentto him with a urge to join PhD under him and asked ”Sir, will you guide me if I joinPhD under you?” and he replied ”you are most welcome”. That day really changed mycareer. I never thought that in him, I am going to get a great advisor, a great teacher,a great critic, a great friend and overall a great philosopher. For the past four years,we have developed a special bond, which is much much more than a student-advisorrelationship. I have always considered him my father figure and truly speaking, he alsonever let me down and always treated me like his own pet child. He always providedme with the best facilities, whether it is a research environment (I can never forget thesmall, separate TCS Lab II, which he allocated to me for doing peaceful research) orwhether it is financial help (I can never forget the personal money which he gave meas advance to visit U.S and Canada for attending CRYPTO 2009 and PODC 2009)or whether it is personal advise (he always gave me personal suggestions whenever Irequired it). I am always going to miss his after leaving IITM. Nevertheless, I willalways be indebted to him for whatever he has done for me till now.Beside my advisor, I also would like to acknowledge the members of my doctoralcommittee namely, Prof. P. Sreenivasa Kumar, Prof. S. V. Raghavan, Prof. KamalaKrithivasan, Prof. S. A. Choudam and Dr. A. Thangaraj for their encouragement andinvaluable suggestions during my doctoral committee meetings. I would specially liketo thank Prof. Kamala Krithivasan, who was my advisor during my M. S (by research)at IITM. She always took special interest in my progress and always motivated andencouraged me to do well. I would also like to thank the present and previous head ofthe department, Prof. C. Siva Ram Murthy and Prof. T. A. Golsalves, respectively fortheir kind help.I would like to thank Dr. Tal Rabin, IBM research for her collaboration and lotof insightful remarks on some of our articles. Her critical remarks helped me a lotto improve my writing style and presentations. I can never forget the brain stormingsession and interaction that we used to have over Internet.My special thanks to Dr. Kannan Srinathan of IIT Hyderabad, who was my seniorat TCS lab. Truly speaking, he is the one who motivated me to do research in securedistributed computing. I have never seen a person like him. His simplicity and innocence is one thing, which I always tried to follow but without any success. For me, heis the best researcher that TCS lab has produced.I would like to thank Prof. Bimal Roy and Prof. Palash Sarkar of ISI Kolkatafor fruitful discussions (both technical as well as personal) that we had during everytime we meet for various conferences. Specially I would like to thank Prof. Bimal Roy(Bimal da) who helped me significantly during by visit to Imphal for National levelinstructional workshop.My sincere thanks to all of our department office staffs Radhai Madam, SaradhaMadam, Balu Sir, Prema madam and Murali for helping me whenever I required. Iwould also like to thank Saraswati madam and Raghu sir of administrative block forprocessing my administrative papers quickly, whenever I required it.My lab mates Esha, Chaya, Billy, Thiru, Sai, Shinku, Amjed, Nisha, Saki, Manila,Kishore, Sobin, Madhu, Preetha madam, KP, Siddharth, Meena, Harini, Balu, Ashiii

win, Raghavendra, Naresh, Sharmila and Vivek deserve special acknowledgements.Specially, I would like to thank Ashwin (BV) for few of the collaborative work that wedid together. Special mention goes to Billy, Thiru, Sai, Shinku, Nainesh and the pair(Vivek, Sharmi) for their nice company. Also, their cute son and future cryptographerof TCS lab, swithin deserves special acknowledgement.The gang of close friends, Rima, Tanmoy, Prasun, Pawan, Hima, Tarun, Ashish,Hitesh, Kanchan, Kishore, Priya have stood by me though the ups and downs of mylife. Specially, I would like to thank Kanchan, Priya and Bhanu didi, whom I alwaysloved like my own sisters. They always prayed for me during my undergrad and theirprayers helped me a lot to achieve what I am today. All my friends at GRKIST,specially Ashish, Shanil, Rochak, Purvik, Shataksh and many others deserve specialacknowledgement. The time that I spent with them during my undergrad is simplyunforgettable. My close friends Pawan and Prasun at IITM made my stay in IITM apleasurable and memorable experience. I will never forget about those endless gossips,laughs that we had at our mess table. Cheers to you guys! Your friendship is trulybeyond words of acknowledgement.My sincere acknowledgements to Infosys Technology India for their Ph.D. fellowshipand financial assistance during this work. I would also like to thank IARCS for thefinancial support provided to me during my visit to Japan for attending ICITS 2009.Now I would like to thank few remarkable people who had, are having and willcontinue to have a tremendous influence on my life. My parents, Dr. Ajit Choudhuryand Chanda Choudhury, for introducing me to the world and bestowing me with allthe love of the world. Though my parents do not know too much about research,they somehow always supported me to do research. Salim uncle, who though beingnot my own uncle, has always loved me like his own son, deserved a very very specialacknowledgement. My uncle, Ashit Choudhury from whom I got the first inspirationto do higher studies also holds a special place for me. My aunt Sikha and my cousinAnamika also deserves special acknowledgement. My dearest brother Avinash (Rahul)holds special place for me. Though we have several conflictions over various issues, healways respected me. He will always hold a special place in my life. I would alwaysrespect my maternal grand other and maternal grand father, who virtually gave me anew life. Otherwise, after getting the paralysis attack during my childhood, I wouldhave simply lied down in the bed for the rest of my life. The fact that I am normaltoday is ONLY and ONLY due to their effort. My grandfather, grandmother, maternaluncle and aunt also deserves special acknowledgement for their blessings for me.My father in law, mother in law and sister in law also deserves special acknowledgement. In them, I got another family. They always treated me like their own sonand brother respectively. My father in law, Mr. Ahibhusan Patra deserves specialacknowledgement. I have never seen a true karma yogi like him. He always inspiredme to do my best.Now I would like to say something about one of the most special person in my life.She is no other than my sweet wife Arpita Patra, who also happened to be my researchcolleague. In her, I have found a true friend, a true critic, a true pillar of support, atrue philosopher, a true well wisher and above all, a true loving wife. My every momentof research and personal life has been a cherishing experience in her company. Though,we fight and argue a lot everyday over various personal and research relate issues, atthe end of day, she is my loving wife. She is the best gift that IIT Madras has giftedto me.Finally, I would like to thank the Supreme personality of Godhead, Lord Krsna,who created the universe and gave the supreme knowledge of “niskama karmayoga”iv

(The art of performing prescribed duties without having any attachment to its fruitand without having any material expectations) to mankind (that I am trying my bestto implement in my life). I would sincerely like to thank the devotees of ISKCON,for their wonderful lectures on Bhagwad Gita. This helped me a lot to discover thespirituality within me and understand the true principles of life.v

AbstractConsider the following problem: a sender S and a receiver R are part of an unreliable,connected, distributed network. The distrust in the network is modelled by an entitycalled adversary, who has unbounded computing power and who can corrupt some ofthe nodes of the network (excluding S and R) in a variety of ways. S wishes to sendto R a message mS that consists of ℓ elements, where ℓ 1, selected uniformly from afinite field F. The challenge is to design a protocol, such that after interacting with S asper the protocol, R should output mS without any error (perfect reliability). Moreover,this hold irrespective of the disruptive actions done by the adversary. This problemis called reliable message transmission or RMT in short. The problem of secure message transmission or SMT in short requires an additional constraint that the adversaryshould not get any information about the message what so ever in information theoreticsense (perfect secrecy). Security against an adversary with infinite computing poweris also known as non-cryptographic or information theoretic or Shannon security andthis is the strongest notion of security. Notice that since the adversary has unboundedcomputing power, we cannot solve RMT and SMT problem by using classical cryptographic primitives such as public key cryptography, digital signatures, authenticationschemes, etc as the security of all these primitives holds good only against an adversaryhaving polynomially bounded computing power.RMT and SMT problem can be studied in various network models and adversarialsettings. We may use the following parameters to describe different settings/modelsfor studying RMT/SMT:1. Type of Underlying Network — Undirected Graph, Directed Graph, Hypergraph.2. Type of Communication — Synchronous, Asynchronous.3. Adversary capacity — Threshold Static, Threshold Mobile, Non-threshold Static,Non-threshold Mobile.4. Type of Faults — Fail-stop, Passive, Byzantine, Mixed.Irrespective of the settings in which RMT/SMT is studied, the following issues arecommon:1. Possibility: What are the necessary and sufficient structural conditions to besatisfied by the underlying network for the existence of any RMT/SMT protocol,tolerating a given type of adversary?2. Feasibility: Once the existence of a RMT/SMT protocol in a network is ascertained, the next natural question is, does there exist an efficient protocol on thegiven network?3. Optimality: Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any RMT/SMT protocol to transmitthe message and how to design a polynomial time RMT/SMT protocol whosetotal communication complexity matches the lower bound on the communicationcomplexity (optimal protocol)?In this dissertation, we look into the above issues in several network models andadversarial settings. This thesis reports several new/improved/efficient/optimal solutions, gives affirmative/negative answers to several significant open problems and lastbut not the least, provides first solutions to several newly formulated problems.vi