Faculty - Dashboard

@inproceedings{bib_Bloc_2024, AUTHOR = {Gujar, Sujit Prakash and Srinathan, Kannan and Jain, Anurag }, TITLE = {Blockchain system for mining transaction using parallel blocks to improve scalability and a method thereof}, BOOKTITLE = {United States Patent}. YEAR = {2024}}

(57) ABSTRACT A blockchain system for mining a transaction using parallel blocks to improve scalability is provided. The blockchain system includes a sender node, a blockchain network, and mining nodes. The sender node (i) creates a transaction, and (ii) broadcasts the transaction on the blockchain network. Each of the mining nodes is configured to (I) split the transaction into disjoint subsets based on a hash value of the public key;(II) assign the disjoint subsets to a plurality of sub-chains that are mined in parallel by a plurality of miners;(III) mine the parallel block followed by a mining block; and (IV) verify multiple sets of transactions associated with the parallel block using an umbrella-proof-of-work method, thereby improving scalability of the blockchain system.

@inproceedings{bib_Syst_2024, AUTHOR = {Srinathan, Kannan }, TITLE = {System and method for proven secret key agreement between initiating unit and responding unit}, BOOKTITLE = {United States Patent}. YEAR = {2024}}

A system and method for establishing a secure communication agreement between an initiating unit 102 and a responding unit 104 through a channel 106 are provided. The method includes generating, using first set of local random numbers, multi-dimensional matrices by an initiating unit. The method includes computing a transcript by the initiating unit based on multi-dimensional matrices and communicating to the responding unit. The method includes determining response by selecting a subset of the transcript to communicate response to the initiating unit. The method includes iteratively generating, communicating a subsequent transcript and waiting for a subsequent response from the responding unit for one or more times. The method includes computing a secret key as a function of the first set of local random numbers, the second set of local numbers, the subsequent transcripts, the subsequent responses

@inproceedings{bib_PIUD_2023, AUTHOR = {Raj, Shubham and JOSHI, SNEHIL and Srinathan, Kannan }, TITLE = {PIUDI: Private Information Update for Distributed Infrastructure}, BOOKTITLE = {International Conference on Security and Cryptography}. YEAR = {2023}}

Encrypted data is susceptible to side-channel attacks like usage and access analysis. Techniques like Oblivious-RAM (ORAM) and privacy information retrieval and writing aim to hide clients’ access pattern while accessing encrypted data on a distrusted server. However, current techniques are constructed for a single server model making them unsuitable and inefficient for contemporary distributed architectures. In our work, we address this problem and provide a solution to private information update using packed secret sharing. Our protocol, named “Private Information Update for Distributed Infrastructure” PIUDI, aims to mitigate the attacks to which PIR-Writing protocols are more susceptible in a distributed environment. Our scheme is secure in presence of up to t + k − 1 compromised parties where k is the size of the data set. We also provide an analysis of our protocol for computational efficiency and gas cost in blockchains.

@inproceedings{bib_S-BA_2023, AUTHOR = {Manvi, Praguna and Manohar, Desai Achintya and Kannan, Srinathan and Namboodiri, Anoop }, TITLE = {S-BAN: Secure Biometric Authentication using Noise}, BOOKTITLE = {Indian Conference on Computer Vision, Graphics and Image Processing}. YEAR = {2023}}

Biometric signal consisting of irrelevant or non-distinctive features can contain useful correlational properties that privacy-preserving verification schemes can exploit. While an efficient protocol for iris verification using noise has been presented, it is not applicable to other widely used modalities, i.e., face and fingerprint, since the methods of noise extraction and comparison are different. In this work, we design a verification protocol for secure dot product computation and also propose noise extraction mechanisms for face and fingerprint modalities. We evaluate the performance of the protocol on CFP, LFW, CelebA, FVC 2004 DB1A, DB2A, DB3A, and SOCOFing datasets. While the protocol exhibits a slight degradation in accuracy, it provides information-theoretic security with a practical computational complexity.

@inproceedings{bib_Inte_2022, AUTHOR = {Jain, Anurag and Kannan, Srinathan and Gujar, Sujit P }, TITLE = {Interlude: Balancing Chaos And Harmony For Fair and Fast Blockchains}, BOOKTITLE = {Technical Report}. YEAR = {2022}}

Blockchains lie at the heart of Bitcoin and other cryptocurrencies that have shown great promise to revolutionize finance and commerce. Although they are gaining increasing popularity, they face technical challenges when it comes to scaling to support greater demand while maintaining their desirable security properties. In an exciting line of recent work, many researchers have proposed various scalable blockchain protocols that demonstrate the potential to solve these challenges. However, many of these protocols come with the assumptions of honest majority and symmetric network access which may not accurately reflect the real world where the participants may be self-interested or rational. Secondly, these works show that their protocol works in an ideal environment where each party has equal access to the network whereas different parties have varying latencies and network speeds. These assumptions may render the protocols susceptible to security threats in the real world, as highlighted by the literature focused on exploring gametheoretic attacks on these protocols. We propose a scalable blockchain protocol, Interlude, which comes with the typical security guarantees while focusing on game-theoretic soundness and network fairness. The novelty of Interlude is that it has a relatively simple design consisting of a sequence of parallel blocks containing disjoint transaction sets that can be mined quickly followed by a series block that is slow to mine and gives the honest parties in the network time to synchronize. Thus, between the chaos of parallel blocks, our blockchain protocol masquerades an interlude moment of harmony in series blocks that synchronize the network.

@inproceedings{bib_SIAN_2022, AUTHOR = {Manvi, Praguna and DESAI, ACHINTYA and Kannan, Srinathan and Namboodiri, Anoop }, TITLE = {SIAN: Secure Iris Authentication using Noise}, BOOKTITLE = {International Joint Conference on Biometrics}. YEAR = {2022}}

Biometric noise is often discarded in many biometric template protection systems. However, the noise ratio be- tween two templates encodes specific correlational proper- ties that template protection schemes can exploit. Biometric authentication usually occurs between mutually distrusting parties, which calls for privacy-preserving techniques. In this paper, we propose a novel biometric authentication pro- tocol, SIAN(Secure Iris Authentication using Noise), adapt- ing secure two-party computation and incorporating un- certainty constraints from biometric noise for security. We evaluate it on three iris datasets: MMU v1, Ubiris v1, and IITD v1, and observe a low EER degradation. The pro- posed protocol has information-theoretic security and low computational complexity, making it suitable for practical real-time applications.

@inproceedings{bib_ATSS_2022, AUTHOR = {JOSHI, SNEHIL and PANDEY, DURGESH and Kannan, Srinathan }, TITLE = {ATSSIA: Asynchronous Truly-Threshold Schnorr Signing for Inconsistent Availability}, BOOKTITLE = {International conference on information security and cryptology}. YEAR = {2022}}

Threshold signature schemes allow any qualified subset of participants (t-out-of-n) to combine its shares and generate a signature that can be verified using a single threshold public key. While there are several existing threshold signature schemes, most are either n-out-of-n and/or require consistent availability of the exact same set of participants through several rounds. This can result in signer availability becoming a bottleneck in the signing process. Our threshold signature scheme removes this dependence by introducing truly threshold asynchronous signatures, i.e., once the message to be signed has been revealed, the signers simply sign and broadcast their signature. Our scheme also uses misbehaviour detection to impose accountability for invalid signing. We prove that our scheme is safe against known distributed attacks and is EUF−CMA secure in the Random Oracle Model for up to t−1 malicious participants.

@inproceedings{bib_Revo_2021, AUTHOR = {MUDHOLKAR, PRAKASH and V, Chiranjeevi and Chakrabarty, Indranil and Kannan, Srinathan }, TITLE = {Revocation and Reconstruction of Shared Quantum Secrets}, BOOKTITLE = {Technical Report}. YEAR = {2021}}

In Quantum secret sharing we can share both quantum and classical secrets with a quantum resource. In this article we study the problem of revocation of quantum secret shared by the dealer with two shareholders in a three party scenario. In the existing secret sharing protocols there are no means by which the dealer can retrieve back the secret once he/she finds all the share holders to be dishonest. Our protocol makes a significant advancement in solving this problem by designing strategy in bringing back the secret in the worst possible situation when all the shareholders/receivers are dishonest1. In our proposed strategy the dealer also possesses a quantum share of the secret which empowers the dealer to bring back the secret even after sharing is done. However the protocol along with the revocation process also ensures the normal reconstruction at the share holder’s location when they are honest. This advantage comes with the expense of extra one qubit on dealer’s side and consequently we require a four qubit resource to start with for 1-dealer and 2-share holder’s scenario. Here in this article we not only give the description of our protocol but also give an example where our protocol is working with the help of a four qubit entangled state. We also explicitly found out the range of parameter for the input state for which the protocol will be successful.

@inproceedings{bib_Mult_2020, AUTHOR = {Manohar, Desai Achintya and Raj, Shubham and Kannan, Srinathan }, TITLE = {Multiplicative Depth Independent & Efficient MPC in the Presence of Mixed Adversary}, BOOKTITLE = {IACR Cryptology ePrint Archive}. YEAR = {2020}}

An extensive research of MPC protocols in different adversarial settings over the past few years has led to various improvements in this domain. Goyal et al.[14] in their paper addressed the issue of an efficient MPC protocol in active adversarial setting by removing the dependency on multiplication depth Dm in the arithmetic circuit. This development was followed by Hirt et al.[16] which proposed an efficient MPC protocol tolerating mixed adversary with communication complexity of O ((ci+ cm+ co) nκ+ ciBA (κ)+ Dm (n3κ+ nBA (κ))) bits, where Dm is the multiplicative depth of the circuit and κ is the size of an element in the field. Additionally, Hirt et al.[16], proposed an open problem to construct a protocol for the mixed adversarial setting, independent of the multiplicative depth Dm, with linear communication complexity. In this paper, we resolve this problem in the affirmative by providing an efficient MPC protocol in the mixed adversarial setting independent of the multiplicative depth of the circuit.

@inproceedings{bib_Cert_2019, AUTHOR = {Malani, Saurav and Srinivas, Jangirala and Das, Ashok Kumar and Kannan, Srinathan and Jo, Minho }, TITLE = {Certificate-Based Anonymous Device Access Control Scheme for IoT Environment}, BOOKTITLE = {IEEE Internet of Things Journal}. YEAR = {2019}}

As the “Internet communications infrastructure” develops to encircle smart devices, it is very much essential for designing suitable methods for secure communications with these smart devices, in the future Internet of Things (IoT) applications context. Due to wireless communication among the IoT smart devices and the gateway node (GWN), several security threats may arise in the IoT environment, including replay,man-in-the-middle, impersonation, malicious devices deployment,and physical devices capture attacks. In this article, to mitigate such security threats, we design a new certificate-based device access control scheme in IoT environment which is not only secure against mentioned attacks, but it also preserves anonymity property. A detailed security analysis using the widely accepted real-or-random (ROR) model-based formal security analysis, informal security analysis, and also formal security verification based on the broadly accepted automated validation of Internet security protocols and applications (AVISPAs) tool has been performed on the proposed scheme to show that it is secure against various known attacks. In addition, a comprehensive comparative analysis among the proposed scheme and other relevant schemes shows that a better trade off among the security and functionality attributes, communication, and computational costs is achieved for the proposed scheme as compared to other schemes.

@inproceedings{bib_Perf_2019, AUTHOR = {Kishore, Ravi and ANUPRIYA, INUMELLA and Kannan, Srinathan }, TITLE = {Perfectly secure message transmission over partially synchronous networks}, BOOKTITLE = {International Conference on Distributed Computing and Networking}. YEAR = {2019}}

In a distributed network, we consider two special nodes called the sender S and the receiver R that are connected by n node-disjoint (except for S and R) bi-directional wires. Out of these n wires, the adversary can control at most t wires (of its choice) in Byzantine fashion. In this setting, our goal is to design a message transmission protocol Π that assures the following two conditions hold: (1) by the end of the protocol Π, R gets the correct message m transmitted by S without any error (perfect reliability), and (2) the adversary learns no information aboutm, whatsoever, in information theoretic sense (perfect secrecy). Protocols that satisfy these two conditions are known as the Perfectly Secure Message Transmission (PSMT) protocols.

@inproceedings{bib_On_m_2018, AUTHOR = {KISHORE, VASALA RAVI and CHIRANJEEVI, V and Kannan, Srinathan }, TITLE = {On minimal connectivity requirements for secure message transmission in directed networks}, BOOKTITLE = {Information Processing Letters}. YEAR = {2018}}

In a synchronous distributed network of n nodes, the goal of a Secure Message Transmission (SMT) protocol is to securely deliver the sender’s message at the receiver’s end in the presence of a computationally unbounded adversary that can partially control the network by corrupting some of its nodes (except the sender and the receiver). In a network modelled as a directed graph, to achieve unconditional security tolerating tb Byzantine faults, it is known that: (1) if all the paths are one-way connected from the sender to the receiver – called as forward channels – then 2tb + 1 vertex-disjoint forward channels are necessary and sufficient (2) for 1 ≤ u ≤ tb, if there exist 2tb + 1 − u vertex-disjoint forward channels then u vertex-disjoint paths from the receiver to the sender – known as feedback channels – are necessary and sufficient. Moreover, similar characterization exists for tolerating mixed faults – up to t f fail-stop faults in addition to tp passive faults. We notice that these results characterized the networks by studying the required number of extra vertex-disjoint feedback channels, conditioned on the existence of a certain number of forward channels. In this work, we give a generic characterization without attaching any such if condition. Specifically, we answer the following questions. In a given directed graph, that is abstracted as a collection of strong paths from S to R and R to S, under what conditions is SMT (im)possible tolerating: (1) up to tp passive faults?, (2) mixed faults – up to t f fail-stop faults in addition to tp passive faults?, and (3) up to tb Byzantine faults? Also, for each of these three problems, we explicitly show that there are networks in which SMT protocols exist whereas the existing results do not characterize such networks.

@inproceedings{bib_Near_2017, AUTHOR = {Mallipeddia, Hardhik and Banerjee, Dip Sankar and Ramamoorthy, Kiran Raj and Kannan, Srinathan and Kothapalli, Kishore }, TITLE = {Nearly Balanced Work Partitioning for Heterogeneous Algorithms}, BOOKTITLE = {International Conference on Parallel Processing}. YEAR = {2017}}

The architectural trend towards heterogeneity has pushed heterogeneous computing to the fore of parallel computing research. Heterogeneous algorithms, often carefully handcrafted, have been designed for several important problems from parallel computing such as sorting, graph algorithms, matrix computations, and the like. A majority of these algorithms follow a work partitioning approach where the input is divided into appropriate sized parts so that individual devices can process the “right-sized” parts of the input. However, arriving at a good work partitioning is usually non-trivial and may crucially depend also on the input instance apart from the heterogeneous algorithm used. An extensive empirical search is not helpful as such an empirical search can potentially offset any gains accrued out of heterogeneous algorithms. Other recently proposed approaches too are in general inadequate. In this paper, we propose a simple and effective technique for work partitioning in the context of heterogeneous algorithms. Our technique is based on randomized sampling and therefore can adapt to both the algorithm used and the input instance. Our technique is generic in its applicability as we will demonstrate in this paper. We validate our technique on three problems: multiplying two unstructured sparse matrices (spmm), multiplying two scale-free sparse matrices, and finding the connected components of a graph (CC). For these problems, we show that using our method, we can find the required threshold that is under 10% away from the best possible thresholds respectively.

@inproceedings{bib_On_t_2017, AUTHOR = {KISHORE, VASALA RAVI and KUMAR, ASHUTOSH and CHIRANJEEVI, V and Kannan, Srinathan }, TITLE = {On the Price of Proactivizing Round-Optimal Perfectly Secret Message Transmission}, BOOKTITLE = {IEEE Transactions on Information Theory}. YEAR = {2017}}

In a network of n nodes (modelled as a digraph), the goal of a perfectly secret message transmission (PSMT) protocol is to replicate sender’s message m at the receiver’s end without revealing any information about m to a computationally unbounded adversary that eavesdrops on any t nodes. The adversary may be mobile too – that is, it may eavesdrop on a different set of t nodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence of r-round PSMT protocols, for any given r > 0; further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall communication complexity of O(n) elements of a finite field to perfectly transmit one field element. Apart from optimality/scalability, two interesting implications of our results are: (a) adversarial mobility does not affect its tolerability: PSMT tolerating a static tadversary is possible if and only if PSMT tolerating mobile t-adversary is possible; and (b) mobility does not affect the round optimality: the fastest PSMT protocol tolerating a static t-adversary is not faster than the one tolerating a mobile t-adversary.

@inproceedings{bib_Disc_2016, AUTHOR = {CHANDRAN, ADITYA and JAIN, LOKESH and Rawat, Sanjay and Kannan, Srinathan }, TITLE = {Discovering Vulnerable Functions: A Code Similarity Based Approach}, BOOKTITLE = {International Symposium on Security in Computing and Communication}. YEAR = {2016}}

This paper extends recent work on vulnerability extrapolation. A surge in vulnerability exploits against old and new softwares, urges the importance of detection of vulnerabilities and possible attacks prior to the attacker. How sophisticated an exploit may be, an underlying prerequisite remains to be the presence of at least one memory corruption bug, serving as entry point for the exploit. Therefore several rigorous software testing techniques are borrowed to detect and eliminate software bugs as early as possible. Code similarity based bug detection is one of such techniques, which, in the parlance of software security, is also termed as vulnerability extrapolation. In this paper, we present a source code similarity based bug identification technique by considering code features that are relevant for security related bugs. Our technique works by enriching (augmenting) abstract syntax trees (ASTs) of functions by considering security relevant properties of the code. We show the effectiveness of the augmented AST based similarity approach over existing methods by evaluating proposed method on real-world applications.

@inproceedings{bib_On_P_2016, AUTHOR = {KISHORE, VASALA RAVI and CHIRANJEEVI, V and JHA, TUSHANT and Kannan, Srinathan }, TITLE = {On Perfectly Secret Message Transmission in Digraphs Tolerating Dual Failures}, BOOKTITLE = {International Conference on Distributed Computing and Networking}. YEAR = {2016}}

Consider a synchronous distributed network which is partly controlled by an adversary. In a Perfectly Secret Message Transmission(PSMT) protocol, the sender S wishes to transmit a message to the receiver R such that the adversary learns nothing about the message. We characterize the set of directed graphs that admit PSMT protocols tolerating a dual failure model where up to tp nodes are passively corrupted and further up to any tf nodes may fail.

@inproceedings{bib_Unsu_2016, AUTHOR = {KUMAR, NIRAJ and Kannan, Srinathan and Kalidindi, Vasudeva Varma }, TITLE = {Unsupervised deep semantic and logical analysis for identification of solution posts from community answers}, BOOKTITLE = {International Journal of Information and Decision Sciences}. YEAR = {2016}}

These days' discussion forums provide dependable solutions to the problems related to multiple domains and areas. However, due to the presence of huge amount of less-informative/inappropriate posts, the identification of the appropriate problem-solution pairs has become a challenging task. The emergence of a variety of topics, domains and areas has made the task of manual labelling of the problem solution-post pairs a very costly and time consuming task. To solve these issues, we concentrate on deep semantic and logical relation between terms. For this, we introduce a novel semantic correlation graph to represent the text. The proposed representation helps us in the identification of topical and semantic relation between terms at a fine grain level. Next, we apply the improved version of personalised pagerank using random walk with restarts. The main aim is to improve the rank score of terms having direct or indirect relation with terms in the given question. Finally, we introduce the use of the node overlapping version of GAAC to find the actual span of answer text. Our experimental results show that the devised system performs better than the existing unsupervised systems.

@inproceedings{bib_A_gr_2016, AUTHOR = {KUMAR, NIRAJ and Kannan, Srinathan and Kalidindi, Vasudeva Varma }, TITLE = {A graph-based unsupervised N-gram filtration technique for automatic keyphrase extraction}, BOOKTITLE = {International Journal of Data Mining, Modelling and Management}. YEAR = {2016}}

In this paper, we present a novel N-gram (N> = 1) filtration technique for keyphrase extraction. To filter the sophisticated candidate keyphrases (N-grams), we introduce the combined use of: 1) statistical feature (obtained by using weighted betweenness centrality scores of words, which is generally used to identify the border nodes/edges in community detection techniques); 2) co-location strength (calculated by using nearest neighbour Dbpedia texts). We also introduce the use of N-gram (N> = 1) graph, which reduces the bias effect of lower length N-grams in the ranking process and preserves the semantics of words (phraseness), based upon local context. To capture the theme of the document and to reduce the effect of noisy terms in the ranking process, we apply an information theoretic framework for key-player detection on the proposed N-gram graph. Our experimental results show that the devised system performs better than the current state-of-the-art unsupervised systems and comparable/better than supervised systems.

@inproceedings{bib_Retr_2015, AUTHOR = {Sazim, S. and CHIRANJEEVI, V and Chakrabarty, Indranil and Kannan, Srinathan }, TITLE = {Retrieving and Routing Quantum Information in a Quantum Network}, BOOKTITLE = {Quantum Information Processing}. YEAR = {2015}}

In extant quantum secret sharing protocols, once the secret is shared in a quantum network (qnet) it cannot be retrieved, even if the dealer wishes that his/her secret no longer be available in the network. For instance, if the dealer is part of two qnets, say Q1 and Q2 and he/she subsequently finds that Q2 is more reliable than Q1, he/she may wish to transfer all her secrets from Q1 to Q2. Known protocols are inadequate to address such a revocation. In this work we address this problem by designing a protocol that enables the source/dealer to bring back the information shared in the network, if desired. Unlike classical revocation, the no-cloning theorem automatically ensures that the secret is no longer shared in the network.

@inproceedings{bib_A_No_2015, AUTHOR = {RAJ, S R KIRAN and BANERJEE, DIP SANKAR and Kannan, Srinathan and Kothapalli, Kishore }, TITLE = {A Novel Heterogeneous Algorithm for Multiplying Scale-Free Sparse Matrices}, BOOKTITLE = {International Parallel & Distributed Processing Symposium Workshops}. YEAR = {2015}}

Multiplying two sparse matrices, denoted spmm, is a fundamental operation in linear algebra with several applications. Hence, efficient and scalable implementation of spmm has been a topic of immense research. Recent efforts are aimed at implementations on GPUs, multicore architectures, FPGAs, and such emerging computational platforms. Owing to the highly irregular nature of spmm, it is observed that GPUs and CPUs can offer comparable performance. In this paper, we study CPU+GPU heterogeneous algorithms for spmm where the matrices exhibit a scale-free nature. Focusing on such matrices, we propose an algorithm that multiplies two sparse matrices exhibiting scale-free nature on a CPU+GPU heterogeneous platform. Our experiments on a wide variety of real-world matrices from standard datasets show an average of 25% improvement over the best possible algorithm on a CPU+GPU heterogeneous platform. We show that our approach is both architecture-aware, and workload-aware.

@inproceedings{bib_Repo_2015, AUTHOR = {Das, Ananda Swarup and Gupta, Prosenjit and Kothapalli, Kishore and Kannan, Srinathan }, TITLE = {Reporting and counting maximal points in a query orthogonal rectangle}, BOOKTITLE = {Journal on Discrete Alogorithms}. YEAR = {2015}}

In this work we show that given a set S of n points with coordinates on an n × n grid, we can construct data structures for (i) reporting and (ii) counting the maximal points in an axes-parallel query rectangle in sub-logarithmic time. We assume our model of computation to be the word RAM with size of each word being log n bits.

@inproceedings{bib_Impr_2014, AUTHOR = {KHARE, SANKALP and AGARWAL, JATIN and MOIDU, NADEEM and Kannan, Srinathan }, TITLE = {Improved Bounds for Smallest Enclosing Disk Range Queries.}, BOOKTITLE = {Annual Canadian Conference on Computational Geometry}. YEAR = {2014}}

Let S be a set of n points in the plane. We present a method where, using O(n log2 n) time and space, S can be pre-processed into a data structure such that given an axis-parallel query rectangle q, we can report the radius of the smallest enclosing disk of the points lying in S ∩ q in O(log6 n) time per query

@inproceedings{bib_Choo_2014, AUTHOR = {RAJEEVALOCHANA, M.R. and Kannan, Srinathan }, TITLE = {Choosing and Working of an Anonymous Leader}, BOOKTITLE = {International Conference on Applied Algorithms.}. YEAR = {2014}}

We revisit the problem of anonymous communication where nodes communicate without revealing their identity. We propose its use in the choosing of a node as an anonymous leader and subsequent communication to and from this leader such that its identity is not revealed. We give indistinguishability definitions for anonymous leader and prove it to be secure in an arbitrary reliable network.

@inproceedings{bib_On_g_2014, AUTHOR = {MOIDU, NADEEM and AGARWAL, JATIN and KHARE, SANKALP and Kothapalli, Kishore and Kannan, Srinathan }, TITLE = {On generalized planar skyline and convex hull range queries}, BOOKTITLE = {International Workshop on Algorithms and Computation}. YEAR = {2014}}

We present output sensitive techniques for the generalized reporting versions of the planar range maxima problem and the planar range convex hull problem. Our solutions are in the pointer machine model, for orthogonal range queries on a static point set. We solve the planar range maxima problem for two-sided, three-sided and four-sided queries. We achieve a query time of O(logn + c) using O(n) space for the two-sided case, where n denotes the number of stored points and c the number of colors reported. For the three-sided case, we achieve query time O(log2 n + clogn) using O(n) space while for four-sided queries we answer queries in O(log3 n + clog2 n) using O(nlogn) space. For the planar range convex hull problem, we provide a solution that answers queries in O(log2 n + clogn) time, using O(nlog2 n) space.

@inproceedings{bib_On_r_2014, AUTHOR = {Das, Ananda Swarup and Gupta, Prosenjit and Kothapalli, Kishore and Kannan, Srinathan }, TITLE = {On reporting the L1 metric closest pair in a query rectangle}, BOOKTITLE = {Information Processing Letters}. YEAR = {2014}}

In this work, we consider the problem of finding the closest pair (in L 1 metric) of points in an orthogonal query rectangle. Given a set of n static points on a U× U grid, we preprocess these points into a data structure of size O (m f (m) log 2 m) that can be queried in time O ((g (m)+ log log m) log 3 m), for m= O (n log U) and (i) f (m)= O (1) and g (m)= O (log ε m);(ii) f (m)= O (log log m) and g (m)= O (log log m);(iii) f (m)= O (log ε m) and g (m)= O (1). Here ε: 0< ε< 1 is a small but arbitrary constant.

@inproceedings{bib_Inte_2013, AUTHOR = {ABHINAV, and AGRAWAL, SHASHANK and Kannan, Srinathan }, TITLE = {Interplay between (im) perfectness, synchrony and connectivity: The case of reliable message transmission}, BOOKTITLE = {Theoretical Computer Science}. YEAR = {2013}}

Reliable message transmission is a fundamental problem in distributed communication networks. Of late, several interesting results have been obtained by modelling the network as a directed graph. An important result among them was due to Bhavani et al. [Unconditionally reliable message transmission in directed networks, 18 in: SODA’08: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, USA, 2008, pp. 1048–1055], where it was shown that if a negligible probability of error is allowed, the connectivity required in a synchronous network for unconditionally reliable message transmission (URMT) is significantly reduced. We refer to the variant of URMT studied by them as Monte Carlo URMT; here the receiver is allowed to output an incorrect message with small probability. Another interesting variant which has received little attention so far in the literature is the Las Vegas variant, where the receiver is allowed to abort with a small probability, but never to output an incorrect message. We show that the minimum connectivity requirements for the existence of Las Vegas URMT protocols over synchronous networks are the same as that of Monte Carlo URMT protocols over asynchronous networks—a surprising equivalence between two very different models. Furthermore, we show that the higher connectivity requirements of Las Vegas URMT over asynchronous networks match exactly with that of zero-error (perfect) variant over (a)synchronous networks. We also show that there exists a family of graphs where in the number of critical edges for the ‘easier’ randomized variants are asymptotically higher than that for the perfect variants. Hence, our results demonstrate an interesting interplay between (im)perfectness, synchrony and connectivity for the case of reliable message transmission.

@inproceedings{bib_Expl_2013, AUTHOR = {KUMAR, NIRAJ and Gangadharia, Rashmi and Kannan, Srinathan and Kalidindi, Vasudeva Varma }, TITLE = {Exploring the Role of Logically Related Non-Question Phrases for Answering Why-Questions}, BOOKTITLE = {Technical Report}. YEAR = {2013}}

In this paper, we show that certain phrases although not present in a given question/query, play a very important role in answering the question. Exploring the role of such phrases in answering questions not only reduces the dependency on matching question phrases for extracting answers, but also improves the quality of the extracted answers. Here matching question phrases means phrases which co-occur in given question and candidate answers. To achieve the above discussed goal, we introduce a bigram-based word graph model populated with semantic and topical relatedness of terms in the given document. Next, we apply an improved version of ranking with a prior-based approach, which ranks all words in the candidate document with respect to a set of root words (ie non-stopwords present in the question and in the candidate document). As a result, terms logically related to the root words are scored higher than terms that are not related to the root words. Experimental results show that our devised system performs better than state-of-the-art for the task of answering Why-questions.

@inproceedings{bib_A_kn_2013, AUTHOR = {KUMAR, NIRAJ and Kannan, Srinathan and Kalidindi, Vasudeva Varma }, TITLE = {A knowledge induced graph-theoretical model for extract and abstract single document summarization}, BOOKTITLE = {International Conference on Intelligent Text Processing and Computational Linguistics}. YEAR = {2013}}

Summarization mainly provides the major topics or theme of document in limited number of words. However, in extract summary we depend upon extracted sentences, while in abstract summary, each summary sentence may contain concise information from multiple sentences. The major facts which affect the quality of summary are: (1) the way of handling noisy or less important terms in document, (2) utilizing information content of terms in document (as, each term may have different levels of importance in document) and (3) finally, the way to identify the appropriate thematic facts in the form of summary. To reduce the effect of noisy terms and to utilize the information content of terms in the document, we introduce the graph theoretical model populated with semantic and statistical importance of terms. Next, we introduce the concept of weighted minimum vertex cover which helps us in identifying the most representative and thematic facts in the document. Additionally, to generate abstract summary, we introduce the use of vertex constrained shortest path based technique, which uses minimum vertex cover related information as valuable resource. Our experimental results on DUC-2001 and DUC-2002 dataset show that our devised system performs better than baseline systems.

@inproceedings{bib_Coun_2013, AUTHOR = {DAS, ANANDA SWARUP and Gupta, Prosenjit and Kannan, Srinathan }, TITLE = {Counting maximal points in a query orthogonal rectangle}, BOOKTITLE = {International Workshop on Algorithms and Computation}. YEAR = {2013}}

In this work, we propose a solution with sub-logarithmic query time for counting the number of maximal points in an axis parallel query rectangle. The problem has been previously studied in [3]and [5]. To the best of our knowledge, this is the first sub-logarithmic query time solution for the problem. Our model of computation is the word RAM with word size of Θ(logn) bits.

@inproceedings{bib_Effi_2013, AUTHOR = {AGARWAL, JATIN and MOIDU, NADEEM and Kothapalli, Kishore and Kannan, Srinathan }, TITLE = {Efficient Range Reporting of Convex Hull}, BOOKTITLE = {Technical Report}. YEAR = {2013}}

We consider the problem of reporting convex hull points in an orthogonal range query in two dimensions. Formally, let $ P $ be a set of $ n $ points in $\mathbb {R}^{2} $. A point lies on the convex hull of a point set $ S $ if it lies on the boundary of the minimum convex polygon formed by $ S $. In this paper, we are interested in finding the points that lie on the boundary of the convex hull of the points in $ P $ that also fall with in an orthogonal range $[x_ {lt}, x_ {rt}]\times {}[y_b, y_t] $. We propose a $ O (n\log^{2} n) $ space data structure that can support reporting points on a convex hull inside an orthogonal range query, in time $ O (\log^{3} n+ h) $. Here $ h $ is the size of the output. This work improves the result of (Brass et al. 2013)\cite {brass} that builds a data structure that uses $ O (n\log^{2} n) $ space and has a $ O (\log^{5} n+ h) $ query time. Additionally, we show that our data structure can be modified slightly to solve other related problems. For instance, for counting the number of points on the convex hull in an orthogonal query rectangle, we propose an $ O (n\log^{2} n) $ space data structure that can be queried upon in $ O (\log^{3} n) $ time. We also propose a $ O (n\log^{2} n) $ space data structure that can compute the $ area $ and $ perimeter $ of the convex hull inside an orthogonal range query in $ O (\log^{3} n $) time.

@inproceedings{bib_Allo_2013, AUTHOR = {HORA, DHARMEET SINGH and BANSAL, PIYUSH and Kothapalli, Kishore and Kannan, Srinathan }, TITLE = {Allowing Multiple Rounds in the Shared Whiteboard Model: Some More Impossibility Results}, BOOKTITLE = {International Conference on Advanced Computing, Networking and Security}. YEAR = {2013}}

The shared whiteboard model for distributed computing is one of the recent interesting models to be proposed (See Becker et al. (SPAA 2012)). In its basic form, this model allows all nodes to write a message of no more than O(log n) bits on a whiteboard that every node can read. However, each node can write at most once. In this model, a variety of problems from graphs are shown to be either possible or impossible. In this paper we extend the work of Becker et al. to allow for nodes to write on the shared whiteboard more than once. However, each node can write at most O(log n) bits at any one instant. Interestingly, in this model, we show that allowing just two rounds of writing on the whiteboard, one can color the vertices of a d-degenerate graph using d+1 colors. Similarly, we show that two rounds suffice to find maximal independent set (MIS), whereas 2-ruling sets can be computed in one round in simultaneous synchronous models. Finally, we show that for finding connected components in a graph, even O(1) rounds is not enough in general. We show that any deterministic algorithm that follows certain rules requires at least Omega(log nlog log n) rounds to find the connected components of an n-vertex graph. At the same time, we show the existence of a O(log n) round algorithm for the same. Thus, our results indicate that the multi-round shared whiteboard model has interesting consequences.

@inproceedings{bib_WYSW_2012, AUTHOR = {ASHOK, KHOT ROHIT and Kumaraguru, Ponnurangam and Kannan, Srinathan }, TITLE = {WYSWYE: shoulder surfing defense for recognition based graphical passwords}, BOOKTITLE = {Australian Computer-Human Interaction Conference}. YEAR = {2012}}

Recognition based graphical passwords are inherently vulnerable to shoulder surfing attacks because of their visual mode of interaction. In this paper, we propose and evaluate two novel shoulder-surfing defense techniques for recognition based graphical passwords. These techniques are based on WYSWYE (Where You See is What You Enter) strategy, where the user identifies a pattern of password images within a presented grid of images and replicates it onto another grid. We conducted controlled laboratory experiments to evaluate the usability and security of the proposed techniques. Both the schemes had high login success rates with no failures in authentication. More than seventy percent of participants successfully logged on to the system in their first attempt in both the schemes. The participants were satisfied with the schemes and were willing to use it in public places. In addition, both the schemes were significantly secure against shoulder surfing than normal unprotected recognition based graphical passwords. The login efficiency improved with practice in one of the proposed scheme. We believe, WYSWYE strategy has considerable potential and can easily be extended to other types of authentication systems such as text passwords and PINS.

@inproceedings{bib_Usin_2012, AUTHOR = {KUMAR, NIRAJ and Kannan, Srinathan and Kalidindi, Vasudeva Varma }, TITLE = {Using wikipedia anchor text and weighted clustering coefficient to enhance the traditional multi-document summarization}, BOOKTITLE = {International Conference on Intelligent Text Processing and Computational Linguistics}. YEAR = {2012}}

Similar to the traditional approach, we consider the task of summarization as selection of top ranked sentences from ranked sentence-clusters. To achieve this goal, we rank the sentence clusters by using the importance of words calculated by using page rank algorithm on reverse directed word graph of sentences. Next, to rank the sentences in every cluster we introduce the use of weighted clustering coefficient. We use page rank score of words for calculation of weighted clustering coefficient. Finally the most important issue is the presence of a lot of noisy entries in the text, which downgrades the performance of most of the text mining algorithms. To solve this problem, we introduce the use of Wikipedia anchor text based phrase mapping scheme. Our experimental results on DUC-2002 and DUC-2004 dataset show that our system performs better than unsupervised systems and better than/comparable with novel supervised systems of this area.

@inproceedings{bib_Usin_2012, AUTHOR = {KUMAR, NIRAJ and Kannan, Srinathan and Kalidindi, Vasudeva Varma }, TITLE = {Using graph based mapping of co-occurring words and closeness centrality score for summarization evaluation}, BOOKTITLE = {International Conference on Intelligent Text Processing and Computational Linguistics}. YEAR = {2012}}

The use of predefined phrase patterns like: N-grams (N>=2), longest common sub sequences or pre defined linguistic patterns etc do not give any credit to non-matching/smaller-size useful patterns and thus, may result in loss of information. Next, the use of 1-gram based model results in several noisy matches. Additionally, due to presence of more than one topic with different levels of importance in summary, we consider summarization evaluation task as topic based evaluation of information content. Means at first stage, we identify the topics covered in given model/reference summary and calculate their importance. At the next stage, we calculate the information coverage in test / machine generated summary, w.r.t. every identified topic. We introduce a graph based mapping scheme and the concept of closeness centrality measure to calculate the information depth and sense of the co-occurring words in every identified topic. Our experimental results show that devised system is better than/comparable with best results of TAC 2011 AESOP dataset.

@inproceedings{bib_A_Ne_2012, AUTHOR = {GUPTA, ANUJ and ANUMANCHIPALLI, PRASANT GOPAL and BANSAL, PIYUSH and Kannan, Srinathan }, TITLE = {A New Look at Composition of Authenticated Byzantine Generals}, BOOKTITLE = {Technical Report}. YEAR = {2012}}

The problem of Authenticated Byzantine Generals (ABG) aims to simulate a virtual reliable broadcast channel from the General to all the players via a protocol over a real (point-to-point) network in the presence of faults. We propose a new model to study the self-composition of ABG protocols. The central dogma of our approach can be phrased as follows: Consider a player who diligently executes (only) the delegated protocol but the adversary steals some private information from him. Should such a player be considered faulty? With respect to ABG protocols, we argue that the answer has to be no. In the new model we show that in spite of using unique session identifiers, if , there cannot exist any ABG protocol that composes in parallel even twice. Further, for , we design ABG protocols that compose for any number of parallel executions. Besides investigating the composition of ABG under a new light, our work also brings out several new insights into Canetti's Universal Composability framework. Specifically, we show that there are several undesirable effects if one deviates from our dogma. This provides further evidence as to why our dogma is the right framework to study the composition of ABG protocols.

@inproceedings{bib_Dist_2012, AUTHOR = {BADANIDIYURU, ASHWINKUMAR and PATRA, ARPITA and CHOUDHURY, ASHISH and Kannan, Srinathan and Rangan, C Pandu }, TITLE = {Distributed Computing-Article 22 (35 pages)-On the Trade-Off between Network Connectivity, Round Complexity, and Communication Complexity of Reliable Message Transmission}, BOOKTITLE = {Association for Computing Machinery}. YEAR = {2012}}

Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit a message to a receiver in an unreliable network, even in the presence of a computationally unbounded adversary. In this article, we study the inherent trade-off between the three important parameters of the PRMT protocols, namely, the network connectivity (n), the round complexity (r), and the communication complexity by considering the following generic question (which can be considered as the holy grail problem) in the context of the PRMT protocols. Given an n-connected network, a message of size ℓ (to be reliably communicated) and a limit c for the total communication allowed between the sender and the receiver, what is the minimum number of communication rounds required by a PRMT protocol to send the message, such that the communication complexity of the protocol is O(c)? We answer this interesting question by deriving a nontrivial lower bound on the round complexity. Moreover, we show that the lower bound is tight in the amortized sense, by designing a PRMT protocol whose round complexity matches the lower bound. The lower bound is the first of its kind, that simultaneously captures the inherent tradeoff between the three important parameters of a PRMT protocol.

@inproceedings{bib_Rang_2012, AUTHOR = {Das, Ananda Swarup and Gupta, Prosenjit and KALAVAGATTU, ANIL KISHORE and AGARWAL, JATIN and Kannan, Srinathan and Kothapalli, Kishore }, TITLE = {Range aggregate maximal points in the plane}, BOOKTITLE = {International Workshop on Algorithms and Computation}. YEAR = {2012}}

In this work, we study the problem of reporting and counting maximal points in a query rectangle for a set of n integer points that lie on an n×n grid. A point is said to be maximal inside a query rectangle if it is not dominated by any other point inside the query rectangle. Our model of computation is unit-cost RAM model with word size of O(logn) bits. For the reporting version of the problem, we present a data structure of size words and support querying in time where k is the size of the output. For the counting version, we present a data structure of size words which supports querying in . Both the data structures are static in nature. The reporting version of the problem has been studied in [1] and [5]. To the best of our knowledge, this is the first sub-logarithmic result for the reporting version and the first work for the counting version of the problem.

@inproceedings{bib_Secu_2011, AUTHOR = {AGRAWAL, SHASHANK and ABHINAV, and Kannan, Srinathan }, TITLE = {Secure message transmission in asynchronous directed graphs}, BOOKTITLE = {International Conference on Cryptology in India.}. YEAR = {2011}}

We study the problem of secure message transmission (SMT) in asynchronous directed graphs, where an unbounded Byzantine adversary can corrupt some subset of nodes specified via an adversary structure. We focus on the particular variant (0, δ)-SMT, where the message remains perfectly private, but there is a small chance that the receiver R may not obtain it. This variant can be of two kinds: Monte Carlo - where R may output an incorrect message with small probability; and Las Vegas - where R never outputs an incorrect message. For a Monte Carlo (0, δ)-SMT protocol to exist in an asynchronous directed graph, we show that the minimum connectivity required in the network does not decrease even when privacy of the message being transmitted is not required. In the case of Las Vegas (0, δ)-SMT, we show that the minimum connectivity required matches exactly with the minimum connectivity requirements of the zero-error variant of SMT – (0, 0)-SMT. For a network that meets the minimum connectivity requirements, we provide a protocol efficient in the size of the graph and the adversary structure. We also provide a protocol efficient in the size of the graph for an important family of graphs, when the adversary structure is threshold.

@inproceedings{bib_Priv_2011, AUTHOR = {JAGDISHBHAI, RAVAL NISARG and RUSHI, P. MADHUCHAND and BANSAL, PIYUSH and Kannan, Srinathan and V, Jawahar C }, TITLE = {Privacy preserving outlier detection using locality sensitive hashing}, BOOKTITLE = {International Conference on Data Mining Workshops}. YEAR = {2011}}

In this paper, we give approximate algorithms for privacy preserving distance based outlier detection for both horizontal and vertical distributions, which scale well to large datasets of high dimensionality in comparison with the existing techniques. In order to achieve efficient private algorithms, we introduce an approximate outlier detection scheme for the centralized setting which is based on the idea of Locality Sensitive Hashing. We also give theoretical and empirical bounds on the level of approximation of the proposed algorithms.

@inproceedings{bib_Usin_2011, AUTHOR = {KUMAR, NIRAJ and Kannan, Srinathan and Kalidindi, Vasudeva Varma }, TITLE = {Using Unsupervised System with least linguistic features for TAC-AESOP Task.}, BOOKTITLE = {Text Analysis Conference Workshop}. YEAR = {2011}}

We consider AESOP Task as Topic based evaluation of information content. Means at first stage, we identify the topics covered in given model/reference summary and calculate their importance. At the next stage, we calculate the information coverage in test/machine generated summary, wrt every identified topic. We use the local importance of words in calculation of importance of topics. From experiments it is clear that use of different methods for identification of topics and calculation of information coverage in test documents wrt every identified topic, have different effect on the result. It is important to note that our devised system do not require any linguistic support or learning or training in entire execution of the system.

@inproceedings{bib_LSH__2011, AUTHOR = {RUSHI, P. MADHUCHAND and JAGDISHBHAI, RAVAL NISARG and BANSAL, PIYUSH and Kannan, Srinathan and V, Jawahar C }, TITLE = {LSH based outlier detection and its application in distributed setting}, BOOKTITLE = {International Conference on Information and Knowledge Management}. YEAR = {2011}}

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.

@inproceedings{bib_Byza_2011, AUTHOR = {BANSAL, PIYUSH and Gopal, Prasant and GUPTA, ANUJ and Kannan, Srinathan and V, PRANAV KUMAR VASISHTA G }, TITLE = {Byzantine Agreement Using Partial Authentication}, BOOKTITLE = {International Symposium on Distributed Computing}. YEAR = {2011}}

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.

@inproceedings{bib_Secu_2011, AUTHOR = {Choudhury, Ashish and Patra, Arpita and Ashwinkumar, BV and Kannan, Srinathan and Rangan, C Pandu }, TITLE = {Secure message transmission in asynchronous networks}, BOOKTITLE = {Journal of Parallel and Distributed Computing}. YEAR = {2011}}

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.

@inproceedings{bib_Mini_2011, AUTHOR = {NAYAK, MANAN and AGRAWAL, SHASHANK and Kannan, Srinathan }, TITLE = {Minimal connectivity for unconditionally secure message transmission in synchronous directed networks}, BOOKTITLE = {International Conference on Information Theoretic Security}. YEAR = {2011}}

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

@inproceedings{bib_Mara_2011, AUTHOR = {ASHOK, KHOT ROHIT and Kannan, Srinathan and , Ponnurangam Kumaraguru }, TITLE = {Marasim: a novel jigsaw based authentication scheme using tagging}, BOOKTITLE = {International Conference of Human Factors in Computing Systems}. YEAR = {2011}}

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

@inproceedings{bib_NAPT_2011, AUTHOR = {ASHOK, KHOT ROHIT and Kannan, Srinathan and Khot, Rutuja Ashok }, TITLE = {NAPTune: fine tuning graphical authentication}, BOOKTITLE = {International Conference on Human Computer Interaction.}. YEAR = {2011}}

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.

@inproceedings{bib_Need_2011, AUTHOR = {IYER, VASANTH and Iyengar, S. Sitharama and Garimella, Ramamurthy and Kannan, Srinathan and Regeti, Govindarajulu and Singh, Dhananjay and Srinivas, Mandalika B. }, TITLE = {Needle in a cross-layer sensor stack}, BOOKTITLE = {International Conference on Advanced Communication Technology}. YEAR = {2011}}

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.

@inproceedings{bib_Unco_2011, AUTHOR = {AGRAWAL, SHASHANK and ABHINAV, and Kannan, Srinathan }, TITLE = {Unconditionally Reliable Message Transmission in Directed Neighbour Networks.}, BOOKTITLE = {ACM-SIAM Symposium on Discrete Algorithms}. YEAR = {2011}}

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.

@inproceedings{bib_Dete_2011, AUTHOR = {DAS, ANANDA SWARUP and Gupta, Prosenjit and Kannan, Srinathan }, TITLE = {Detecting VLSI Layout, Connectivity Errors in a Query Window.}, BOOKTITLE = {Annual Canadian Conference on Computational Geometry}. YEAR = {2011}}

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.

@inproceedings{bib_Secu_2011, AUTHOR = {AGRAWAL, SHASHANK and ABHINAV, and Kannan, Srinathan }, TITLE = {Secure Message Transmission In Asynchronous Directed Networks.}, BOOKTITLE = {Journal of Parallel and Distributed Computing}. YEAR = {2011}}

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.

@inproceedings{bib_Rang_2011, AUTHOR = {RAHUL, S and DAS, ANANDA SWARUP and Sundara, Rajan Krishnan and Kannan, Srinathan }, TITLE = {Range-Aggregate Queries Involving Geometric Aggregation Operations}, BOOKTITLE = {International Workshop on Algorithms and Computation}. YEAR = {2011}}

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.

@inproceedings{bib_On_F_2011, AUTHOR = {KALAVAGATTU, ANIL KISHORE and DAS, ANANDA SWARUP and Kothapalli, Kishore and Kannan, Srinathan }, TITLE = {On Finding Skyline Points for Range Queries in Plane.}, BOOKTITLE = {Annual Canadian Conference on Computational Geometry}. YEAR = {2011}}

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.

@inproceedings{bib_Find_2011, AUTHOR = {DAS, ANANDA SWARUP and Gupta, Prosenjit and Kannan, Srinathan and Kothapalli, Kishore }, TITLE = {Finding Maximum Density Axes Parallel Regions for Weighted Point Sets.}, BOOKTITLE = {Annual Canadian Conference on Computational Geometry}. YEAR = {2011}}

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.

@inproceedings{bib_INSP_2010, AUTHOR = {IYER, VASANTH and Iyengar, S. Sitharama and Garimella, Ramamurthy and Kannan, Srinathan and Phoha, Vir and Srinivas, Mandalika B. }, TITLE = {INSPIRE-DB: Intelligent Networks Sensor Processing of Information using Resilient Encoded-Hash DataBase}, BOOKTITLE = {International Conference on Sensor Technologies and Applications}. YEAR = {2010}}

Sensor networks consist of small motes attached with sensors to measure ambient parameters like temperature, humidity and light. As these motes are unreliable due to wireless link quality and also the data measuring sensors cannot be calibrated accurately for a given applications need. The unique data fusion needs are that parameter being measured is distributed across the network and needs to be computed reliably and with minimum overhead and redundancy due to data value being correlated. We show the asymptotic complexity of topology control when applied to power-aware routing is scalable and argue that the accuracy and reliability of the estimated sensor values can be accurately predicted for the physical value being sensed and aggregating. A prefix-based routing protocol is used for data-centric storage, which allows querying distributed parameters using a KEY, VALUE pairs without the need of the sensor node to know its exact geographic information. Intelligent sensor information processing, which is driven by these requirements, is discussed under the framework INSPIRE-DB.

@inproceedings{bib_Phot_2010, AUTHOR = {ASHOK, KHOT ROHIT and Kannan, Srinathan }, TITLE = {PhotoSense: emergent semantics based approach to image annotation}, BOOKTITLE = {International Conference of Human Factors in Computing Systems}. YEAR = {2010}}

Tagging of images using descriptive keywords (tags), contributed by ordinary users, is a powerful way of organizing them. However, due to the richness of the image content, it is often difficult to choose tags that best describe the content of the image to the viewing audience and ensure access to the image. In this paper, we present a novel tagging framework based on the theory of emergent semantics to assist the user in the tag selection process. Our idea is to enrich the current" looking at" experience of tagging with the" looking for" experience of searching. We describe the design of our approach along with a preliminary user study conducted with a prototype Flickr application.

@inproceedings{bib_GoFi_2010, AUTHOR = {ASHOK, KHOT ROHIT and Kannan, Srinathan }, TITLE = {GoFish: fishing thousand words worth a picture}, BOOKTITLE = {international conference on Interaction Design & International Development}. YEAR = {2010}}

Marking the image content with descriptive keywords (also known as tags) is an effective way of improving the accessibility of images. However, doing so practically is boring as well as laborious to most humans. In the recent times, there have been number of attempts to inspire humans to annotate images. Notable examples are social tagging like Flickr and online games like ESP. However, existing methods in their present form are inadequate to result in annotations of superior quality. Therefore, we present GoFish, an intelligent system for semantic annotation of images. GoFish is a web variant of standard Go Fish, a popular playing card game. GoFish utilizes the theory of Emergent Semantics to ensure that all images will have superior tags. We describe the complete design of the game and discuss its benefits. Results of a preliminary user study are encouraging.

@inproceedings{bib_On_c_2010, AUTHOR = {GUPTA, ANUJ and Hans, Sandeep and Kannan, Srinathan and Rangan, C Pandu }, TITLE = {On composability of reliable unicast and broadcast}, BOOKTITLE = {International Conference on Distributed Computing and Networking}. YEAR = {2010}}

In the recent past composability has emerged as a key requirement for various distributed protocols. It is not enough for a protocol to be robust when it runs in isolation or in a “stand-alone” setting but it should be robust even in an environment where several copies of the same protocol or other protocol(s) are running simultaneously. In this work, we investigate the composability for protocols that tolerate a bounded adversary modeled as a probabilistic polynomial time Turing machine. We examine composability of protocols for two fundamental problems in distributed computing - reliable unicast and reliable broadcast. We show that any composable protocol – for reliable unicast tolerating an adversary, that corrupts up to any t nodes, requires 2t + 1 connectivity and for reliable broadcast tolerating an adversary, that corrupts up to any t nodes, requires n > 3t and 2t + 1 connectivity.

@inproceedings{bib_Auth_2010, AUTHOR = {GUPTA, ANUJ and ANUMANCHIPALLI, PRASANT GOPAL and BANSAL, PIYUSH and Kannan, Srinathan }, TITLE = {Authenticated Byzantine generals in dual failure model}, BOOKTITLE = {International Conference on Distributed Computing and Networking}. YEAR = {2010}}

Pease et al. introduced the problem of Byzantine Generals (BGP) to study the effects of Byzantine faults in distributed protocols for reliable broadcast. It is well known that BGP among n players tolerating up to t faults is (efficiently) possible iff n > 3t. To overcome this severe limitation, Pease et al. introduced a variant of BGP, Authenticated Byzantine General (ABG). Here players are supplemented with digital signatures (or similar tools) to thwart the challenge posed by Byzantine faults. Subsequently, they proved that with the use of authentication, fault tolerance of protocols for reliable broadcast can be amazingly increased to n > t (which is a huge improvement over the n > 3t). Byzantine faults are the most generic form of faults. In a network not all faults are always malicious. Some faulty nodes may only leak their data while others are malicious. Motivated from this, we study the problem of ABG in (t b ,t p )-mixed adversary model where the adversary can corrupt up to any t b players actively and control up to any other t p players passively. We prove that in such a setting, ABG over a completely connected synchronous network of n nodes tolerating a (t b ,t p )-adversary is possible iff n > 2t b +min(t b ,t p ) when t p > 0. Interestingly, our results can also be seen as an attempt to unify the extant literature on BGP and ABG.

@inproceedings{bib_Expl_2010, AUTHOR = {KUMAR, NIRAJ and Vemula, Vinay Babu and Kannan, Srinathan and Kalidindi, Vasudeva Varma }, TITLE = {Exploiting N-gram Importance and Wikipedia based Additional Knowledge for Improvements in GAAC based Document Clustering.}, BOOKTITLE = {International Conference on Knowledge Discovery and Information Retrieval}. YEAR = {2010}}

This paper provides a solution to the issue:“How can we use Wikipedia based concepts in document clustering with lesser human involvement, accompanied by effective improvements in result?” In the devised system, we propose a method to exploit the importance of N-grams in a document and use Wikipedia based additional knowledge for GAAC based document clustering. The importance of N-grams in a document depends on a many features including, but not limited to: frequency, position of their occurrence in a sentence and the position of the sentence in which they occur, in the document. First, we introduce a new similarity measure, which takes the weighted N-gram importance into account, in the calculation of similarity measure while performing document clustering. As a result, the chances of topical similarity in clustering are improved. Second, we use Wikipedia as an additional knowledge base both, to remove noisy entries from the extracted N-grams and to reduce the information gap between N-grams that are conceptually-related, which do not have a match owing to differences in writing scheme or strategies. Our experimental results on the publicly available text dataset clearly show that our devised system has a significant improvement in performance over bag-of-words based state-of-the-art systems in this area.

@inproceedings{bib_Unco_2010, AUTHOR = {Patra, Arpita and Choudhury, Ashish and , C. Pandu Rangan and Kannan, Srinathan }, TITLE = {Unconditionally reliable and secure message transmission in undirected synchronous networks: Possibility, feasibility and optimality}, BOOKTITLE = {International Journal on Applied Cryptography}. YEAR = {2010}}

We study the interplay of network connectivity and the issues related to the 'possibility', 'feasibility' and 'optimality' for unconditionally reliable message transmission (URMT) and unconditionally secure message transmission (USMT) in an undirected synchronous network, under the influence of an adaptive mixed adversary having unbounded computing power, who can corrupt some of the nodes in the network in Byzantine, omission, fail-stop and passive fashion respectively. We consider two types of adversary, namely threshold and non-threshold. One of the important conclusions we arrive at from our study is that allowing a negligible error probability significantly helps in the 'possibility', 'feasibility' and 'optimality' of both reliable and secure message transmission protocols. To design our protocols, we propose several new techniques which are of independent interest.

@inproceedings{bib_An_E_2010, AUTHOR = {KUMAR, NIRAJ and Kannan, Srinathan and Kalidindi, Vasudeva Varma }, TITLE = {An Effective Approach for AESOP and Guided Summarization Task.}, BOOKTITLE = {Text Analysis Conference Workshop}. YEAR = {2010}}

In this paper we, present (1) an unsupervised system for AESOP task and (2) a generic multi-document summarization system for guided summarization task. We propose the use of:(1) the role and importance of words and sentences in document and,(2) number and coverage strength of topics in document for both AESOP and Guided summarization task. We also use some other statistical features, simple heuristics and grammatical facts to capture the important facts and information from source document (s).

@inproceedings{bib_Inte_2010, AUTHOR = {ABHINAV, and AGRAWAL, SHASHANK and Kannan, Srinathan }, TITLE = {Interplay between (im) perfectness, synchrony and connectivity: The case of probabilistic reliable communication}, BOOKTITLE = {Theoretical Computer Science}. YEAR = {2010}}

Reliable message transmission is a fundamental problem in distributed communication networks. Of late, several interesting results have been obtained by modelling the network as a directed graph. An important result among them was due to Bhavani et al. [Unconditionally reliable message transmission in directed networks, 18 in: SODA’08: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, USA, 2008, pp. 1048–1055], where it was shown that if a negligible probability of error is allowed, the connectivity required in a synchronous network for unconditionally reliable message transmission (URMT) is significantly reduced. We refer to the variant of URMT studied by them as Monte Carlo URMT; here the receiver is allowed to output an incorrect message with small probability. Another interesting variant which has received little attention so far in the literature is the Las Vegas variant, where the receiver is allowed to abort with a small probability, but never to output an incorrect message. We show that the minimum connectivity requirements for the existence of Las Vegas URMT protocols over synchronous networks are the same as that of Monte Carlo URMT protocols over asynchronous networks—a surprising equivalence between two very different models. Furthermore, we show that the higher connectivity requirements of Las Vegas URMT over asynchronous networks match exactly with that of zero-error (perfect) variant over (a)synchronous networks. We also show that there exists a family of graphs where in the number of critical edges for the ‘easier’ randomized variants are asymptotically higher than that for the perfect variants. Hence, our results demonstrate an interesting interplay between (im)perfectness, synchrony and connectivity for the case of reliable message transmission.

@inproceedings{bib_Blin_2010, AUTHOR = {UPMANYU, MANEESH and Namboodiri, Anoop and Kannan, Srinathan and V, Jawahar C }, TITLE = {Blind authentication: a secure crypto-biometric verification protocol}, BOOKTITLE = {IEEE Transactions on Information Forensics and Security}. YEAR = {2010}}

Concerns on widespread use of biometric authentication systems are primarily centered around template security, revocability, and privacy. The use of cryptographic primitives to bolster the authentication process can alleviate some of these concerns as shown by biometric cryptosystems. In this paper, we propose a provably secure and blind biometric authentication protocol, which addresses the concerns of user’s privacy, template protection, and trust issues. The protocol is blind in the sense that it reveals only the identity, and no additional information about the user or the biometric to the authenticating server or vice-versa. As the protocol is based on asymmetric encryption of the biometric data, it captures the advantages of biometric authentication as well as the security of public key cryptography. The authentication protocol can run over public networks and provide nonrepudiable identity verification. The encryption also provides template protection, the ability to revoke enrolled templates, and alleviates the concerns on privacy in widespread use of biometrics. The proposed approach makes no restrictive assumptions on the biometric data and is hence applicable to multiple biometrics. Such a protocol has significant advantages over existing biometric cryptosystems, which use a biometric to secure a secret key, which in turn is used for authentication. We analyze the security of the protocol under various attack scenarios. Experimental results on four biometric datasets (face, iris, hand geometry, and fingerprint) show that carrying out the authentication in the encrypted domain does not affect the accuracy, while the encryption key acts as an additional layer of security.

@inproceedings{bib_Effi_2010, AUTHOR = {UPMANYU, MANEESH and Namboodiri, Anoop and Kannan, Srinathan and V, Jawahar C }, TITLE = {Efficient privacy preserving k-means clustering}, BOOKTITLE = {Pacific Asia Workshop on Intelligence and Security Informatics.}. YEAR = {2010}}

This paper introduces an efficient privacy-preserving protocol for distributed K-means clustering over an arbitrary partitioned data, shared among N parties. Clustering is one of the fundamental algorithms used in the field of data mining. Advances in data acquisition methodologies have resulted in collection and storage of vast quantities of user’s personal data. For mutual benefit, organizations tend to share their data for analytical purposes, thus raising privacy concerns for the users. Over the years, numerous attempts have been made to introduce privacy and security at the expense of massive additional communication costs. The approaches suggested in the literature make use of the cryptographic protocols such as Secure Multiparty Computation (SMC) and/or homomorphic encryption schemes like Paillier’s encryption. Methods using such schemes have proven communication overheads. And in practice are found to be slower by a factor of more than 106. In light of the practical limitations posed by privacy using the traditional approaches, we explore a paradigm shift to side-step the expensive protocols of SMC. In this work, we use the paradigm of secret sharing, which allows the data to be divided into multiple shares and processed separately at different servers. Using the paradigm of secret sharing, allows us to design a provably-secure, cloud computing based solution which has negligible communication overhead compared to SMC and is hence over a million times faster than similar SMC based protocols

@inproceedings{bib_On_p_2009, AUTHOR = {Hans, Sandeep and CHANDRA, A.V. SARATH and GUPTA, ANUJ and Kannan, Srinathan }, TITLE = {On privacy preserving convex hull}, BOOKTITLE = {International Conference on Availability, Reliability and Security}. YEAR = {2009}}

Computing convex hull for a given set of points is one of the most explored problems in the area of computational geometry (CG). If the set of points is distributed among a set of parties who jointly wish to compute the convex hull, each party can send his points to every other party, and can then locally compute the hull using any of the existing algorithms in CG. However such an approach does not work if the parties wish to compute the convex hull securely, i.e., no party wishes to reveal any of his input points to any other party apart from those that are part of the answer. The problem of secure computation of convex hull for two parties was first introduced by Du and Atallah (NSPW '01). The first solution to the problem was given by Wang et. al(ARES '08). However, the proposed solution was based on well known algorithms for computing convex hull in CG which are proven to be sub-optimal. We propose a new solution for secure computation of convex hull with a considerable improvement in computational complexity. We further show how to extend our two-party protocol for the case of any number of parties.

@inproceedings{bib_Unco_2009, AUTHOR = {Kannan, Srinathan and Patra, Arpita and Choudhary, Ashish and Rangan, C. Pandu }, TITLE = {Unconditionally secure message transmission in arbitrary directed synchronous networks tolerating generalized mixed adversary}, BOOKTITLE = {Symposium on Information, Computer and Communications Security}. YEAR = {2009}}

In this paper, we re-visit the problem of unconditionally secure message transmission (USMT) from a sender S to a receiver R, who are part of a distributed synchronous network, modeled as an arbitrary directed graph. Some of the intermediate nodes between S and R can be under the control of an adversary having unbounded computing power. Desmedt and Wang [4] have given the characterization of USMT in directed networks. However, in their model, the underlying network is abstracted as directed node disjoint paths (also called as wires/channels) between S and R, where the intermediate nodes are oblivious, message passing nodes and perform no other computation. In this work, we first show that the characterization of USMT given by Desmedt et.al [4] does not hold good for arbitrary directed networks, where the intermediate nodes can perform some computation, beside acting as message forwarding nodes. We then give the characterization of USMT in arbitrary directed networks, considering the entire network as a whole. As far our knowledge is concerned, this is the first ever characterization of USMT in arbitrary directed networks.

@inproceedings{bib_A_ne_2009, AUTHOR = {KUMAR, NIRAJ and Kannan, Srinathan }, TITLE = {A new approach for clustering variable length documents}, BOOKTITLE = {International Conference on Advanced Computing}. YEAR = {2009}}

This paper proposes a method to cluster documents of variable length. The main idea is to apply (a) automatic identification of 1, 2, and 3 grams (To reduce the dependency on huge background vocabulary support or learning or complex probabilistic approach), (b) order them by some measure of relevance, which is developed with the help of Tf-Idf and Term-Weighting approach, and finally (c) use them (instead of bag of words based approach) to create vector space model and apply some known clustering methods i. e. Bisecting K-means, K-means, hierarchical method (single link) and Graph based method. Our experimental results with publicly available text dataset (Cogprints and NewsGroup20) show remarkable improvements in the performance of these clustering algorithms with this new approach.

@inproceedings{bib_On_m_2009, AUTHOR = {Choudhary, Ashish and Patra, Arpita and Ashwinkumar, B. V. and Kannan, Srinathan and Rangan, C. Pandu }, TITLE = {On minimal connectivity requirement for secure message transmission in asynchronous networks}, BOOKTITLE = {International Conference on Distributed Computing and Networking}. YEAR = {2009}}

In the PSMT problem, a sender S and a receiver R are part of a distributed network and connected through n node disjoint paths, also called as wires among which at most t are controlled by an all powerful Byzantine adversary At. S has a message m, which S intends to send to R. The challenge is to design a protocol, such that at the end, R should correctly output m without any error (perfect reliability) and At should not get any information about m, what so ever, in information theoretic sense (perfect security). The problem of USMT is same as PSMT, except that R should output m with a small probability of error.Sayeed et al. [15] have given a PSMT protocol in an asynchronous network tolerating At, where S and R are connected by n = 2t + 1 wires. However, we show that their protocol does not provide perfect security. We then prove that in an asynchronous network, if all the n wires are directed from S to R, then any PSMT protocol tolerating At is possible iff n > 3t. Surprisingly, we further prove that even if all the n wires are bi-directional, then any PSMT protocol in asynchronous network tolerating At is possible iff n > 3t. This is quite interesting because for synchronous networks, by the results of Dolev et al. [6], if all the wires are unidirectional (directed from S to R), then PSMT tolerating At is possible iff n > 3t, where as if all the wires are bi-directional then PSMT tolerating At is possible iff n > 2t. This shows that synchrony of the network affects the connectivity requirement for PSMT protocols. However, we show that n > 2t wires are necessary and sufficient for the existence of any USMT protocol in asynchronous network tolerating At, irrespective of whether the n wires are unidirectional from S to R or the n wires are bi-directional.

@inproceedings{bib_iCAP_2009, AUTHOR = {ASHOK, KHOT ROHIT and Kannan, Srinathan }, TITLE = {iCAPTCHA: Image tagging for free}, BOOKTITLE = {the Proc. Conference on Usable Software and Interface Design}. YEAR = {2009}}

Semantic annotation or tagging of images can greatly improve the accuracy and efficiency of image search engines. However, humans rarely annotate images as they find the task of image annotation boring and laborious despites its benefits in terms of search and retrieval. In this paper, we introduce a novel approach of luring users into image annotation: by embedding image annotation into a CAPTCHA design. A CAPTCHA is a standard security mechanism used by popular commercial websites to prevent automated programs from abusing the online services. Millions of users solve CAPTCHAs daily in order to access web content and services. We aim to utilize human effort spent in solving the CAPTCHA into a productive work of image annotation. We introduce iCAPTCHA, a user friendly and productive CAPTCHA design. Our premise is based on the human ability to recognize images and label them in proper categories. Each time a user solves an iCAPTCHA, he/she is helping to label images in proper categories which will in turn improve image search and retrieval.

@inproceedings{bib_A_pe_2009, AUTHOR = {Kothapalli, Kishore and MUKHERJEE, RISHABH and REHMAN, MOHAMMED SUHAIL and PATIDAR, SURYAKANT and J, Narayanan P and Kannan, Srinathan }, TITLE = {A performance prediction model for the CUDA GPGPU platform}, BOOKTITLE = {International Conference on High Performance Computing}. YEAR = {2009}}

The significant growth in computational power of modern Graphics Processing Units (GPUs) coupled with the advent of general purpose programming environments like NVIDIA's CUDA, has seen GPUs emerging as a very popular parallel computing platform. Till recently, there has not been a performance model for GPGPUs. The absence of such a model makes it difficult to definitively assess the suitability of the GPU for solving a particular problem and is a significant impediment to the mainstream adoption of GPUs as a massively parallel (super)computing platform. In this paper we present a performance prediction model for the CUDA GPGPU platform. This model encompasses the various facets of the GPU architecture like scheduling, memory hierarchy, and pipelining among others. We also perform experiments that demonstrate the effects of various memory access strategies. The proposed model can be used to analyze pseudo code for a CUDA kernel to obtain a performance estimate, in a way that is similar to performing asymptotic analysis. We illustrate the usage of our model and its accuracy with three case studies: matrix multiplication, list ranking, and histogram generation.

@inproceedings{bib_Effi_2009, AUTHOR = {UPMANYU, MANEESH and Namboodiri, Anoop and Kannan, Srinathan and V, Jawahar C }, TITLE = {Efficient Biometric Verification in Encrypted Domain}, BOOKTITLE = {International conference on Biometrics}. YEAR = {2009}}

Biometric authentication over public networks leads to a variety of privacy issues that needs to be addressed before it can become popular. The primary concerns are that the biometrics might reveal more information than the identity itself, as well as provide the ability to track users over an extended period of time. In this paper, we propose an authentication protocol that alleviates these concerns. The protocol takes care of user privacy, template protection and trust issues in biometric authentication systems. The protocol uses asymmetric encryption, and captures the advantages of biometric authentication. The protocol provides non-repudiable identity verification, while not revealing any additional information about the user to the server or vice versa. We show that the protocol is secure under various attacks. Experimental results indicate that the overall method is efficient to be used in practical scenarios.

@inproceedings{bib_Effi_2009, AUTHOR = {UPMANYU, MANEESH and Namboodiri, Anoop and Kannan, Srinathan and V, Jawahar C }, TITLE = {Efficient privacy preserving video surveillance}, BOOKTITLE = {International Conference on Computer Vision}. YEAR = {2009}}

Widespread use of surveillance cameras in offices and other business establishments, pose a significant threat to the privacy of the employees and visitors. The challenge of introducing privacy and security in such a practical surveillance system has been stifled by the enormous computational and communication overhead required by the solutions. In this paper, we propose an efficient framework to carry out privacy preserving surveillance. We split each frame into a set of random images. Each image by itself does not convey any meaningful information about the original frame, while collectively, they retain all the information. Our solution is derived from a secret sharing scheme based on the Chinese Remainder Theorem, suitably adapted to image data. Our method enables distributed secure processing and storage, while retaining the ability to reconstruct the original data in case of a legal requirement. The system installed in an office like environment can effectively detect and track people, or solve similar surveillance tasks. Our proposed paradigm is highly efficient compared to Secure Multiparty Computation, making privacy preserving surveillance, practical.

@inproceedings{bib_Secu_2009, AUTHOR = {ADDEPALLI, SARAT CHANDRA and BANSAL, PIYUSH and Kannan, Srinathan and Krishna, K Madhava }, TITLE = {Secured Multi-Robotic Active Localization without Exchange of Maps: A Case of Secure Cooperation Amongst Non-trusting Robots}, BOOKTITLE = {International Conference on Availability, Reliability and Security}. YEAR = {2009}}

Secure multiparty protocols have found applications in numerous domains, where multiple nontrusting parties wish to evaluate a function of their private inputs. In this paper, we consider the case of multiple robots wishing to localize themselves, with maps as their private inputs. Though localization of robots has been a well studied problem, only recent studies have shown how to actively localize multiple robots through coordination. In all such studies, localization has typically been achieved through constructing a publicly known global map. Here, we show how a similar solution can be given in the case of nontrusting robots, which do not wish to disclose their local maps.

@inproceedings{bib_On_f_2009, AUTHOR = {SAWHNEY, RAHUL and Krishna, K Madhava and Kannan, Srinathan }, TITLE = {On fast exploration in 2D and 3D terrains with multiple robots}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2009}}

We present a fast multi-robotic exploration methodology for 2D and 3D terrains. An asynchronous exploration strategy is introduced which shows significant improvements over the existing synchronous ones. A per-time visibility metric is being utilized by the algorithm. The metric allots the same weight for points for next view whose visibility over time ratios are equal. The outcome of this is that while the number of points visited to explore a terrain is nearly the same as other popular metrics found in literature, the time length of the paths are smaller in this case resulting in reduced time exploration. The results have been verified through extensive simulations in 2D and 3D. In 2D multiple robots explore unknown terrains that are office like, cluttered, corridor like and various combinations of these. In 3D we consider the case of multiple UAVs exploring a terrain represented as height fields. We introduce a way for calculating expected visibilities and a way of incorporating explored features in the per-time metric. The maximum height of the UAV at each location is governed by the so called exposure surface, beneath which the UAVs are constrained to fly. We also show performance gain of the present metric over others in experiments on a Pioneer 3DX robot.

@inproceedings{bib_Fast_2008, AUTHOR = {RAJU, C NARSIMHA and GANUGULA, UMA DEVI and Kannan, Srinathan and V, Jawahar C }, TITLE = {Fast and secure real-time video encryption}, BOOKTITLE = {Indian Conference on Computer Vision, Graphics and Image Processing}. YEAR = {2008}}

Advances in digital content transmission have increased in the past few years. Security and privacy issues of the transmitted data have become an important concern in multimedia technology. In this paper, we propose a computationally efficient and secure video encryption algorithm. This makes secure video encryption feasible for real-time applications without any extra dedicated hardware. We achieve computational efficiency by exploiting the frequently occurring patterns in the DCT coefficients of the video data. Computational complexity of the encryption is made proportional to the influence of the DCT coefficients on the visual content. On an average, our algorithm takes only 8.32 ms of encryption time per frame.

@inproceedings{bib_A_re_2008, AUTHOR = {RAJU, C NARSIMHA and Kannan, Srinathan and V, Jawahar C }, TITLE = {A real-time video encryption exploiting the distribution of the DCT coefficients}, BOOKTITLE = {IEEE Region 10 Conference}. YEAR = {2008}}

Most of the video encryptions algorithms considered in the literature significantly increase the video size independent of encryption algorithm employed. This is because these algorithms encrypt DCTs without considering their characteristics or relationship to the visual content. This adversely affects the transmission throughput. We propose a fast video encryption algorithm that exploits the statistics of the DCTs in the video data sets. Our algorithm reduces the video size significantly without any compromise in security. The proposed algorithm performs encryption followed by permutation of the DCTs. On an average, increase in video size is restricted to 23.41% of the original.

@inproceedings{bib_A_no_2008, AUTHOR = {RAJU, C NARSIMHA and GANUGULA, UMA DEVI and Kannan, Srinathan and V, Jawahar C }, TITLE = {A novel video encryption technique based on secret sharing}, BOOKTITLE = {International Conference on Image Processing}. YEAR = {2008}}

The rapid growth of Internet and digitized content has made video distribution easy. Hence the need for video data protection is on the rise. In this paper, we propose a secure and computationally feasible video encryption algorithm based on the method of Secret Sharing. In an MPEG video, the strength of the DC is distributed among the AC values based on Shamir's Secret Sharing (SSS) scheme. The proposed algorithm guarantees security, speed and error tolerance with a small increase in video size.

@inproceedings{bib_Auto_2008, AUTHOR = {KUMAR, NIRAJ and Kannan, Srinathan }, TITLE = {Automatic keyphrase extraction from scientific documents using N-gram filtration technique}, BOOKTITLE = {ACM Symposium on Document Engineering}. YEAR = {2008}}

In this paper we present an automatic Keyphrase extraction technique for English documents of scientific domain. The devised algorithm uses n-gram filtration technique, which filters sophisticated n-grams {1dnd4} along with their weight from the words of input document. To develop n-gram filtration technique, we have used (1) LZ78 data compression based technique, (2) a simple refinement step, (3) A simple Pattern Filtration algorithm and, (4) a term weighting scheme. In term weighting scheme, we have introduced the importance of position of sentence (where given phrase occurs first) in document and position of phrase in sentence for documents of scientific domain (which is literally more organized than other domains). The entire system is based upon statistical observations, simple grammatical facts, heuristics, and lexical information of English language. We remark that the devised system does not require a learning phase. Our experimental results with publically available text dataset, shows that the devised system is comparable with other known algorithms.

@inproceedings{bib_Priv_2008, AUTHOR = {JAGARLAMUDI, SHASHANK and P, Kowshik and Kannan, Srinathan and V, Jawahar C }, TITLE = {Private content based image retrieval}, BOOKTITLE = {Computer Vision and Pattern Recognition}. YEAR = {2008}}

For content level access, very often database needs the query as a sample image. However, the image may contain private information and hence the user does not wish to reveal the image to the database. Private content based image retrieval (PCBIR) deals with retrieving similar images from an image database without revealing the content of the query image - not even to the database server. We propose algorithms for PCBIR, when the database is indexed using hierarchical index structure or hash based indexing scheme. Experiments are conducted on real datasets with popular features and state of the art data structures. It is observed that specialty and subjectivity of image retrieval (unlike SQL queries to a relational database) enables in computationally efficient yet private solutions.

@inproceedings{bib_Unco_2008, AUTHOR = {SHANKAR, G BHAVANI and ANUMANCHIPALLI, PRASANT GOPAL and Kannan, Srinathan and Rangan, C. Pandu }, TITLE = {Unconditionally reliable message transmission in directed networks}, BOOKTITLE = {Cryptology and Network Security}. YEAR = {2008}}

(URMT) problem, two non-faulty players, the sender S and the receiver R are part of a synchronous network modeled as a directed graph. S has a message that he wishes to send to R; the challenge is to design a protocol such that after exchanging messages as per the protocol, the receiver R should correctly obtain S’s message with arbitrarily small error probability δ, in spite of the influence of a Byzantine adversary that may actively corrupt up to t nodes in the network (we denote such a URMT protocol as (t,(1− δ))-reliable). While it is known that (2t+ 1) vertex disjoint directed paths from S to R are necessary and sufficient for (t, 1)-reliable URMT (that is with zero error probability), we prove that a strictly weaker condition, which we define and denote as (2t, t)-special-connectivity, together with just (t+ 1) vertex disjoint directed paths from S to R, is necessary and sufficient for (t,(1− δ))-reliable URMT with arbitrarily small (but non-zero) error probability, δ. Thus, we demonstrate the power of randomization in the context of reliable message transmission. In fact, for any positive integer k> 0, we show that there always exists a digraph Gk such that (k, 1)-reliable URMT is impossible over Gk whereas there exists a (2k,(1− δ))-reliable URMT protocol, δ> 0 in Gk. In a digraph G on which (t,(1− δ))-reliable URMT is possible, an edge is called critical if the deletion of that edge renders (t,(1− δ))-reliable URMT impossible. We give an example of a digraph G on n vertices such that G has Ω (n2) critical edges. This is quite baffling since no such graph exists for the case of perfect reliable message transmission (or equivalently (t, 1)-reliable URMT) or when the underlying graph is undirected. Such is the anomalous behavior of URMT protocols (when “randomness meet directedness”) that it makes it extremely hard to design efficient protocols over arbitrary digraphs. However, if URMT is possible between every pair of vertices in the network, then we present efficient protocols for the same.

@inproceedings{bib_Alte_2008, AUTHOR = {SHANKAR, G BHAVANI and Kannan, Srinathan and Rangan, C. Pandu }, TITLE = {Alternative protocols for generalized oblivious transfer}, BOOKTITLE = {International Conference on Distributed Computing and Networking}. YEAR = {2008}}

Protocols for Generalized Oblivious Transfer(GOT) were introduced by Ishai and Kushilevitz [10]. They built it by reducing GOT protocols to standard 1-out-of-2 oblivious transfer protocols based on private protocols. In our protocols, we provide alternative reduction by using secret sharing schemes instead of private protocols. We therefore show that there exist a natural correspondence between GOT and general secret sharing schemes and thus the techniques and tools developed for the latter can be applied equally well to the former.

@inproceedings{bib_Brie_2008, AUTHOR = {Kannan, Srinathan and Choudhary, Ashish and Patra, Arpita and Rangan, C Pandu }, TITLE = {Brief Announcement: Efficient Single Phase Unconditionally Secure Message Transmission with Optimum Communication Complexity}, BOOKTITLE = {ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing}. YEAR = {2008}}

In the problem of USMT [1, 2] 1, a sender S and a receiver R. are connected by n= 2t+ 1 bi-directional synchronous channels (also called as wires) such that any t out of the n channels are corrupted in Byzantine fashion by an adversary jA. t, having unbounded computing power. S intends to communicate a message m to R (where m£ F and I> 1 with F being a finite field) by executing a protocol such that after interacting in terms of phases, 2 R outputs m with probability at least (1—2~") and At gets no information about m. In [2], it shown that in any single phase USMT protocol with n= 2t+ 1,Xi>'J'+ 1, where 5 denotes the message space of S, X, denotes the set of possible data sent through the ith wire and 0< 6<^ is the error probability. 4 In [2], a single phase inefficient USMT protocol with communication complexity approximately matching the above bound has been proposed. We present a single phase polynomial time USMT protocol whose communication complexity is

@inproceedings{bib_On_T_2008, AUTHOR = {B.V, Ashwinkumar and Patra, Arpita and Choudhary, Ashish and Kannan, Srinathan and Rangan, C. Pandu }, TITLE = {On Tradeoff Between Network Connectivity, Phase Complexity and Communication Complexity of Reliable Communication Tolerating Mixed Adversary}, BOOKTITLE = {ACM symposium on Principles of distributed computing}. YEAR = {2008}}

In this paper, we study the inherent tradeoff between the network connectivity, phase complexity and communication complexity of perfectly reliable message transmission (PRMT) problem in undirected synchronous network, tolerating a mixed adversary A^ b, t,) i who has unbounded computing power and can corrupt£(, and tf nodes in the network in Byzantine and fail-stop fashion respectively.

@inproceedings{bib_How__2008, AUTHOR = {GV, PRANAV KUMAR VASISHTA and GUPTA, ANUJ and Gopal, Prasant and BANSAL, PIYUSH and MUKHERJEE, RISHABH and POORNIMA, M and Kannan, Srinathan and Kothapalli, Kishore }, TITLE = {How Far Must You See To Hear Reliably.}, BOOKTITLE = {IACR Cryptology ePrint Archive}. YEAR = {2008}}

We consider the problem of probabilistic reliable communication (PRC) over synchronous networks modeled as directed graphs in the presence of a Byzantine adversary when players’ knowledge of the network topology is not complete. We show that possibility of PRC is extremely sensitive to the changes in players’ knowledge of the topology. This is in complete contrast with earlier known results on the possibility of perfectly reliable communication over undirected graphs where the case of each player knowing only its neighbours gives the same result as the case where players have complete knowledge of the network. Specifically, in either case,(2t+ 1)-vertex connectivity is necessary and sufficient, where t is the number of nodes that can be corrupted by the adversary [DDWY93, SKR+05]. We introduce a novel model for quantifying players’ knowledge of network topology, denoted by T K. Given a directed graph G, influenced by a Byzantine adversary that can corrupt up to any t players, we give a necessary and sufficient condition for possibility of PRC over G for any arbitrary topology knowledge T K. It follows from our main characterization theorem that knowledge of up to d=⌊ n− 2t

@inproceedings{bib_On_r_2008, AUTHOR = {SAWHNEY, RAHUL and Krishna, K Madhava and Kannan, Srinathan and MOHAN, MAHESH }, TITLE = {On reduced time fault tolerant paths for multiple UAVs covering a hostile terrain}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2008}}

We present a method for finding reduced time coverage paths of multiple UAVs (Unmanned Air Vehicles) monitoring a 3D terrain represented as height fields. A novel metric based on per time visibility is used that couples visibility gained at a terrain point with the time spent to reach the point. This coupled metric is utilized to form reduced time paths by maximizing the visibility gained per unit time at every step. We compare the results of this approach with an approach that covers the terrain based on a per distance visibility metric, which reduces the sum, over distances covered by each UAV path. The comparisons show that the current method gives substantially time reduced paths albeit with an expected increase in sum over distances of UAV paths. We also show that time taken to cover the terrain based on the current metric is far less than prevalent methods that try to decompose the terrain based on visibility followed by time or time followed by visibility in a decoupled fashion. The method is further extended to provide for fault tolerance on a hostile terrain. Each terrain point is guaranteed to be seen by at-least one UAV that has not been damaged due to any calamity, shot or otherwise.

@inproceedings{bib_Cove_2008, AUTHOR = {MOHAN, MAHESH and SAWHNEY, RAHUL and Krishna, K Madhava and Kannan, Srinathan and M.B, Srikanth }, TITLE = {Covering hostile terrains with partial and complete visibilities: On minimum distance paths}, BOOKTITLE = {International Conference on Intelligent Robots and Systems}. YEAR = {2008}}

We present a method for finding paths for multiple unmanned air vehicles (UAVs) such that the sum over their lengths is minimum as they cover a 3D terrain (represented as height fields). The paths are constrained to lie beneath an exposure surface to ensure stealth from enemy outposts. The exposure surface is also computed as a height field. The algorithm greedily clusters the terrain such that gain in visibility per distance would be higher for intra-cluster points than points across clusters. Paths generated on clusters formed by such a per distance visibility metric are reduced by more than 25% over other related decoupled methods. The method is extended to cover terrains with partial visibilities. The advantage of the coupled metric extends under constrained visibility also. We again show performance gain by comparing with an existing decoupled algorithm that solves a similar problem of minimum distance terrain coverage with constrained visibility. The paper reveals that decomposing the terrain based on visibility first and then distance is always better than the other way round to cover the terrain in shorter distances.

@inproceedings{bib_Priv_2007, AUTHOR = {DAS, ANANDA SWARUP and Kannan, Srinathan }, TITLE = {Privacy preserving cooperative clustering service}, BOOKTITLE = {International Conference on Advanced Computing and Communications}. YEAR = {2007}}

The growth of Internet has opened up new avenues for business and corporate model. Information sharing over Internet can help business houses in better cooperative strategic planning and growth. However despite such an impact, business houses are quite reluctant to share information because of the fear of information leakage. In this paper we study and propose an elegant, simple and practical solution for the problem of how can one party avail the data clustering service of another party without affecting each other's privacy. In our solution, we introduce the following two problems: (a) Secure multiparty computation of a depth of a query point, (b) Secure multiparty computation of whether a query point is a hull vertex. To the best of our knowledge this is the first time in literature that the aforementioned problems have been considered in privacy preserving framework.

@inproceedings{bib_On_e_2007, AUTHOR = {Kannan, Srinathan and Rangan, C. Pandu and Kumaresan, R. }, TITLE = {On exponential lower bound for protocols for reliable communication in networks}, BOOKTITLE = {International Conference on Information Theoretic Security}. YEAR = {2007}}

This work deals with the problem of fault-tolerant communication over networks, some of whose nodes are corrupted by a centralized byzantine adversary. The extant literature’s perspective of the problem of reliable communication, especially in networks whose topology is known, is that of a simple problem to which even some naive solutions (like message-flooding etc.) turn out to be reasonably efficient. In this paper, we give an example of a directed graph and a non threshold adversary structure, which will require every protocol for perfect reliable unicast to transmit exponential number of bits in order to reliably transmit a single bit.

@inproceedings{bib_On_t_2007, AUTHOR = {Kannan, Srinathan and Prasad, N. R. and Rangan, C. Pandu }, TITLE = {On the optimal communication complexity of multiphase protocols for perfect communication}, BOOKTITLE = {IEEE Symposium on Security and Privacy}. YEAR = {2007}}

In the perfectly secure message transmission (PSMT) problem, two synchronized non-faulty players (or processors), the Sender S and the Receiver R are connected by n wires (each of which facilitates 2-way communication); S has a message, represented by a sequence oft elements from a finite field, that he wishes to send to R; after exchanging messages in phases R should correctly obtain S 's message, while an adversary listening on and actively controlling any set of t (or less) wires should have no information about S 's message. Similarly, in the problem of perfect reliable message transmission (PRMT), the receiver R should correctly obtain S's message, in spite of the adversary actively controlling any set oft (or less) wires.

@inproceedings{bib_Priv_2007, AUTHOR = {DAS, ANANDA SWARUP and Kannan, Srinathan and TIWARI, RITESH KUMAR and SRIVASTAVA, VAIBHAV }, TITLE = {Privacy preserving computation of shortest path in presence of a single convex polygonal obstacle}, BOOKTITLE = {International Conference on Mobile Data Management}. YEAR = {2007}}

Shortest path computation has always been a subject of study and research in the history of computer science. In this paper we introduce and initiate the study of the problem of finding the shortest path in a privacy preserving manner, in presence of single convex polygonal obstacle. We also propose an efficient, elegant and simple solution for the problem.

@inproceedings{bib_Self_2007, AUTHOR = {ASHOK, KHOT ROHIT and Poola, Ravikant and Kothapalli, Kishore and Kannan, Srinathan }, TITLE = {Self-stabilizing routing algorithms for wireless ad-hoc networks}, BOOKTITLE = {International Conference on Distributed Computing and Internet Technology}. YEAR = {2007}}

This paper considers the problem of unicasting in wireless ad hoc networks. Unicasting is the problem of finding a route between a source and a destination and forwarding the message from the source to the destination. In theory, models that have been used oversimplify the problem of route discovery in ad hoc networks. The achievement of this paper is threefold. First we use a more general model in which nodes can have different transmission and interference ranges and we present a new routing algorithm for wireless ad hoc networks that has several nice features. We then combine our algorithm with that of known greedy algorithms to arrive at an average case efficient routing algorithm in the situation that GPS information is available. Finally we show how to schedule unicast traffic between a set of source-destination pairs by providing a proper vertex coloring of the nodes in the wireless ad hoc network. Our coloring algorithm achieves a O(Δ)–coloring that is locally distinct within the 2-hop neighborhood of any node.

@inproceedings{bib_Cons_2006, AUTHOR = {Patra, Arpita and Choudhary, Ashish and Kannan, Srinathan and Rangan, C. Pandu }, TITLE = {Constant phase bit optimal protocols for perfectly reliable and secure message transmission}, BOOKTITLE = {International Conference on Cryptology}. YEAR = {2006}}

In this paper, we study the problem of perfectly reliable message transmission(PRMT) and perfectly secure message transmission(PSMT) between a sender S and a receiver R in a synchronous network, where S and R are connected by n vertex disjoint paths called wires, each of which facilitates bidirectional communication. We assume that atmost t of these wires are under the control of adversary. We present two-phase-bit optimal PRMT protocol considering Byzantine adversary as well as mixed adversary. We also present a three phase PRMT protocol which reliably sends a message containing l field elements by overall communicating O(l) field elements. This is a significant improvement over the PRMT protocol proposed in [10] to achieve the same task which takes log(t) phases. We also present a three-phase-bit-optimal PSMT protocol which securely sends a message consisting of t field elements by communicating O(t 2) field elements.

@inproceedings{bib_Perf_2006, AUTHOR = {Narayanan, Arvind and Kannan, Srinathan and Rangan, C. Pandu }, TITLE = {Perfectly reliable message transmission}, BOOKTITLE = {Information Processing Letters}. YEAR = {2006}}

We consider the problem of reliable message transmission between two synchronous players connected by n wires, some t< n 2 of which may be faulty. We show how to get reliability “for free”—reliable transmission of b bits involves a total communication of only O (b) bits, when b is large enough. We also construct an efficient Perfectly Secure Message Transmission Protocol.

@inproceedings{bib_Poss_2006, AUTHOR = {Kannan, Srinathan and Rangan, C. Pandu }, TITLE = {Possibility and complexity of probabilistic reliable communication in directed networks}, BOOKTITLE = {ACM symposium on Principles of distributed computing}. YEAR = {2006}}

We provide a complete characterization of directed networks in which probabilistic reliable communication is possible. We also outline a round optimal protocol for the same.

@inproceedings{bib_Roun_2006, AUTHOR = {Fitzi, Matthias and Garay, Juan and Rangan, C. Pandu and Kannan, Srinathan }, TITLE = {Round-optimal and efficient verifiable secret sharing}, BOOKTITLE = {Theory of Cryptography Conference}. YEAR = {2006}}

We consider perfect verifiable secret sharing (VSS) in a synchronous network of n processors (players) where a designated player called the dealer wishes to distribute a secret s among the players in a way that no t of them obtain any information, but any t + 1 players obtain full information about the secret. The round complexity of a VSS protocol is defined as the number of rounds performed in the sharing phase. Gennaro, Ishai, Kushilevitz and Rabin showed that three rounds are necessary and sufficient when n > 3t. Sufficiency, however, was only demonstrated by means of an inefficient (i.e., exponential-time) protocol, and the construction of an efficient three-round protocol was left as an open problem. In this paper, we present an efficient three-round protocol for VSS. The solution is based on a three-round solution of so-called weak verifiable secret sharing (WSS), for which we also prove that three rounds is a lower bound. Furthermore, we also demonstrate that one round is sufficient for WSS when n > 4t, and that VSS can be achieved in 1 + ε amortized rounds (for any ε > 0 ) when n>3t.