Abstract

We study the problem of information-theoretically secure message transmission (SMT) in asynchronous directed networks. In line with the literature, the distrust and failures of the network is captured via a computationally unbounded Byzantine adversary that may corrupt some subset of nodes. We give a characterization of networks over which SMT from sender S to receiver R is possible in both the well-known settings, namely perfect SMT (PSMT) and unconditional SMT (USMT). We distinguish between two variants of USMT: one in which R can output an incorrect message (with small probability) and another in which R never outputs a wrong message, but may choose to abort (with small probability). We also provide efficient protocols for an important class of networks.

Abstract

The VLSI layout designing is a highly complex process and hence a layout is often subjected to Layout Verification that includes (a) Design Rule Checking to check if the layout satisfies various design rules and (b) Connectivity Extraction to check if the components of the layout are properly electrically connected. In this work we study two geometric query problems which have applications in the above layout verification phase.

Abstract

The problem of unconditionally reliable message transmission (URMT) is to design a protocol which when run by players in a network enables a sender s to deliver a message to a receiver r with high probability, even when some players in the network are under the control of an unbounded adversary. Renault and Tomala [JoC2008] gave a characterization of undirected neighbour networks over which URMT tolerating Byzantine adversary is possible. In this paper, we generalize their result to the case of directed networks.

Abstract

In this problem, the process start with real-valued inputs and are supposed to decide eventually on real-valued outputs. The process is permitted to send real-valued data in messages. Instead of having to agree exactly, as in the ordinary agreement problem, this time the requirement is just that they agree with within a small positive real-valued tolerance ε. In the standard implementation agreement problem converges to a consistent value for each sensor measurement, which is nonfaculty using Byzantine algorithm with at-least n >; 3 faulty sensors. We define a pre-processing BestBasis cost function which allows to find a coherent range, which can be measured using intra-sensor in an ensemble of real-values. The overlap of the range is calculated by using a clique, with a runtime of O(nk) in the worst-case, where the size of clique, k, is a variable. The computation of the pre-processing takes O log(D), where D is the number of levels in a sparse signal basis. Which are some times analogously compared to needle in a hay stack definition.

Abstract

Graphical passwords are considered to be a secure and memorable alternative to text passwords. Users of such systems, authenticate themselves by identifying a subset of images from the set of displayed images. However, despite the impressive results of user studies on experimental graphical passwords schemes, their overall commercial adaptations have been relatively low. In this paper, we investigate the reasons behind the low commercial acceptance of graphical passwords and present recommendations to overcome the same. Based on these recommendations, we design a simple graphical password scheme, which we call as NAPTune. NAPTune is aimed to work as a cued recognition based graphical authentication scheme that allows users to choose both text as well as images as their password with the same underlying design and interaction. In doing so, we blend the strengths of Numbers, Alphabets and Pictures (NAP) together to effectively defeat prevalent forms of social hacking. We conducted a user study with 35 participants to evaluate the viability of our proposed design. Results of the study are encouraging which indicates that our proposed design is potentially secure and usable method of authentication.

Abstract

In this paper we propose and evaluate Marasim, a novel Jigsaw based graphical authentication mechanism using tagging. Marasim is aimed at achieving the security of random images with the memorability of personal images. Our scheme relies on the human ability to remember a personal image and later recognize the alternate visual representations (images) of the concepts occurred in the image. These concepts are retrieved from the tags assigned to the image. We illustrate how a Jigsaw based approach helps to create a portfolio of system-chosen random images to be used for authentication. The paper describes the complete design of Marasim along with the empirical studies of Marasim that provide evidences of increased memorability. Results show that 93% of all participants succeeded in the authentication tests using Marasim after three months while 71% succeeded in authentication tests using Marasim after nine months. Our findings indicate that Marasim has potential applications, especially where text input is hard (e.g., PDAs or ATMs), or in situations where passwords are infrequently used (e.g., web site passwords).

Abstract

In this paper we give the minimal connectivity required in a synchronous directed network, which is under the influence of a computationally unbounded Byzantine adversary that can corrupt a subset of nodes, so that Secure Message Transmission is possible between sender S and receiver R. We also show that secure communication between a pair of nodes in a given synchronous directed network is possible in both directions if and only if reliable communication is possible between them. We assume that in a network, every node is capable of computation and we model the network along the lines of [14].

Abstract

In the Perfectly Secure Message Transmission (PSMT) problem, a sender S and a receiver R are part of a distributed network and connected through node disjoint paths, also called as wires, among which at most wires are controlled by a static, Byzantine adversary , having unbounded computing power. S has a message , which S intends to send to R. The challenge is to design a protocol, such that at the end of the protocol, R should correctly output without any error (perfect reliability) and should not get any information about , whatsoever, in information theoretic sense (perfect security). The problem of Statistically Secure Message Transmission (SSMT) is same as PSMT, except that R should correctly output with very high probability. Sayeed and Abu-Amara (1995) [37] have given a PSMT protocol in an asynchronous network tolerating , where S and R are connected by wires. However, we show that their protocol does not provide perfect security. We then prove that in an asynchronous network, if all the wires are directed from S to R, then any PSMT protocol tolerating is possible iff . Surprisingly, we also prove that even if all the wires are bi-directional, then any PSMT protocol in asynchronous network tolerating is possible iff . This is quite surprising because for synchronous networks, by the results of Dolev et al. (1993) [16], if all the wires are unidirectional (directed from S to R), then PSMT tolerating is possible iff , where as if all the wires are bi-directional then PSMT tolerating is possible iff . This shows that asynchrony of the network demands higher connectivity of the network for the existence of PSMT protocols. Interestingly, we further show that wires are necessary and sufficient for the existence of any SSMT protocol in asynchronous network tolerating , irrespective of whether the wires are unidirectional from S to R or the wires are bi-directional. By the results of Franklin and Wright (2000) [18] and Kurosawa and Suzuki (2009) [22], wires are necessary and sufficient for the existence of SSMT in synchronous networks, irrespective of whether the wires are unidirectional from S to R or the wires are bi-directional. This shows that asynchrony of the network does not demand higher connectivity of the network for SSMT protocols.

Abstract

Three decades ago, Pease et al. introduced the problem of Byzantine Agreement [PSL 80] where nodes need to maintain a consistent view of the world in spite of the challenge posed by Byzantine faults. Subsequently, it is well known that Byzantine agreement over a completely connected synchronous network of n nodes tolerating up to t faults is (efficiently) possible if and only if t < n/3. Pease et al. further empowered the nodes with the ability to authenticate themselves and their messages and proved that agreement in this new model (popularly known as authenticated Byzantine agreement (ABA)) is possible if and only if t < n. (which is a huge improvement over the bound of t < n/3 in the absence of authentication for the same functionality). To understand the utility, potential and limitations of using authentication in distributed protocols for agreement, Gupta et al. [GGBS10] studied ABA in new light. They generalize the existing models and thus, attempt to give a unified theory of agreements over the authenticated and non-authenticated domains. In this paper we extend their results to synchronous (undirected) networks and give a complete characterization of agreement protocols. As a corollary, we show that agreement can be strictly easier than all-pair point-to-point communication. It is well known that in a synchronous network over n nodes of which up to any t are corrupted by a Byzantine adversary, BA is possible only if all pair point-to-point reliable communication is possible [Dol82, DDWY93]. Thus, a folklore in the area is that maintaining global consistency (agreement) is at least as hard as the problem of all pair point-to-point communication. Equivalently, it is widely believed that protocols for BA over incomplete networks exist only if it is possible to simulate an overlay-ed complete network. Surprisingly, we show that the folklore is not always true. Thus, it seems that agreement protocols may be more fundamental to distributed computing than reliable communication.

Abstract

In this paper, we give an approximate algorithm for distance based outlier detection using Locality Sensitive Hashing (LSH) technique. We propose an algorithm for the centralized case wherein the entire dataset is locally available for processing. However, in case of very large datasets collected from various input sources, often the data is distributed across the network. Accordingly, we show that our algorithm can be effectively extended to a constant round protocol with low communication costs, in a distributed setting with horizontal partitioning.