Abstract

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

Abstract

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.

Abstract

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.

Abstract

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

Abstract

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.

Abstract

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.

Abstract

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.

Abstract

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.

Abstract

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.

Abstract

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.