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 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

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 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

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

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

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

In this paper we consider range-aggregate query problems wherein we wish to preprocess a set S of geometric objects such that given a query orthogonal range q, a certain aggregation function on the objects S0 = S \ q can be answered eciently. Range-aggregate version of point enclosure queries, 1-d segment intersection, 2-d orthogonal seg- ment intersection (with/without distance constraint) are revisited and we improve the existing results for these problems. We also provide semi- dynamic (insertions) solutions to some of these problems. This paper is the rst attempt to provide dynamic solutions to problems involving geometric aggregation operations.

Abstract

We consider the dominating point set reporting problem in two-dimension. We propose a data structure for finding the set of dominating points inside a given orthogonal query rectangle. Given a set of n points in the plane, it supports 4-sided queries in O (log n+ k), where k is size of the output, using O (n log n) space. This work can be of application when range queries are generated using mobile devices with limited display capacity.

Abstract

In this work we study the problem of finding axesparallel regions of maximum density for weighted point sets in IR2 and IR3. The 2-d variant is motivated by applications in thermal analysis of VLSI chips.