IIIT Hyderabad Publications 


Secure Message Transmission in Asynchronous NetworksAuthor: Anupriya Inumella Date: 20190118 Report no: IIIT/TH/2019/4 Advisor:Kannan Srinathan AbstractModern cryptography is based on the availability of Public Key Infrastructure (PKI) and Digital Signatures. However these schemes are designed around the assumed computational hardness of some problems like the integer factorisation, discrete logarithm, and latticebased problems among others. This hardness assumption may turn out incorrect in future. So it is not advisable to design and implement realworld systems based on an unproven assumption. Also with the decrease in hardware costs and with the advent of new computing paradigms such as the quantum computing, the security of quite a few of such techniques is proven to be ineffective. For instance, one can potentially break RSA by implementing Shore’s Algorithm on a quantum computer. Hence, we must consider informationtheoretically secure schemes which are based on the worst case assumption that the adversary has unbounded computational power. In solving problems in the design and implementation of faulttolerant distributed systems, a basic construct that is assumed to be present is that every pair of nodes in the communication network has a channel between them for communication. This communication channel enables direct delivery of messages between them in a reliable and secure manner without the help of other nodes. However, due to the large scale of realworld distributed systems, a direct channel between every pair of nodes is not feasible/economical. Therefore, nodes depend on other intermediary nodes for communication out of which some can be faulty. We consider the setting where a subset of nodes can be under the control of a computationally unbounded adversary. The problem of simulating a reliable and secure channel from a special node S called the sender to another special node R called the receiver is popularly known as ”Secure Message Transmission (SMT)”. In this thesis, we focus on the variant of SMT protocols called Perfectly Secure Message Transmission (PSMT). The goal of PSMT is to design a protocol that enables S to communicate a secret message m to R assuring the following two conditions: (1) perfect reliability, that is, by the end of the protocol R gets the correct message m without any error and (2) perfect secrecy i.e., the adversary cannot learn any information about m, whatsoever, in information theoretic sense. It is wellknown in the literature that the feasibility of PSMT protocols is influenced by the timing model. We distinguish between two variants to timing models: Synchronous and Asynchronous. While the synchronous model guarantees that the message sent by a node gets delivered to another node after a fixed amount of time, in an asynchronous model there is no such upper bound. Meaning, message delivery from one node to another node can be arbitrarily delayed. While assuming the network to be completely synchronous is too optimistic an assumption to make, assuming the network to be completely asynchronous makes solutions hard. In this work, we establish the concept of serendipitous synchrony with a focus on its influence/utility on the feasibility of PSMT protocols in asynchronous networks. We ask the following natural question: ”If part of a given asynchronous network by fortune turns out to behave synchronously (serendipitous synchrony), then does it affect the feasibility of PSMT protocols?”. We take the similar approach taken in literature and model the network as a set of disjoint wires, say n in number, with nodes inbetween behaving as mere routers, popularly known as wires model. We assume the most powerful adversary considered in the literature viz., Byzantine adversary which can control at most t of these n wires arbitrarily. We quantitatively model serendipitous synchrony in the network as the number of wires that fortunately, happen to be synchronous, say ns (ns < n). Turns out that contrary to our intuition that serendipitous synchrony improves faulttolerance of an asynchronous network, we discovered that, using serendipitous synchrony we either gain all the fault tolerance or we gain nothing from it! We further improve our insights into asynchronous networks by studying them in the presence of failstop faults (the nodes which can crash at will at any point during the execution). The main challenge in this setting is the inability to distinguish between a slow sender and a faulty sender which may sometimes cause otherwise correct protocols to have nonterminating executions. Unlike the approach that is taken in literature, where the network is abstracted as an undirected graph consisting of a set of n node disjoint wires, where each wire from S to R is also a wire from R to S; we consider the network with its directionality. That is, a wire from S to R may not be a wire from R to S. We consider mixed adversary that can cause dual failures. That is adversary can control at most tp wires in passive fashion (it can eavesdrop on messages on these wires) and at most tf wires in failstop fashion. To this end, we introduce a new kind of SMT protocols called the Quiescent SMT protocols in which it is guaranteed that the nodes will eventually stop sending messages as opposed to the terminating protocols in which they go into a halt state. Contrary to the known belief that asynchronous networks require more network connectivity for perfect security than synchronous networks, we prove that quiescent protocols can achieve PSMT with no extra network connectivity over its stateoftheart synchronous counterpart.Hence it is important to consider quiescent protocols for SMT solutions. With the above results, we draw attention to a new kind of SMT protocols, that is, protocols which eventually go into a stable state as opposed to the hard termination. We also show that for perfect secrecy, serendipitous synchrony does not give any extra gain, so it remains open to exploring other settings in which serendipitous synchrony can be useful. Full thesis: pdf Centre for Security, Theory and Algorithms 

Copyright © 2009  IIIT Hyderabad. All Rights Reserved. 