Biometric noise is often discarded in many biometric template protection systems. However, the noise ratio between two templates encodes specific correlational properties 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 protocol, SIAN(Secure Iris Authentication using Noise), adapting secure two-party computation and incorporating uncertainty 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 proposed protocol has information-theoretic security and low computational complexity, making it suitable for practical real-time applications.

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 tradeoff among the security and functionality attributes, communication, and computational costs is achieved for the proposed scheme as compared to other schemes.

In a network of$n$nodes (modeled 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$-roundPSMTprotocols, 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: 1)adversarial mobility does not affect its tolerability:PSMTtolerating a static$t$-adversary is possibleif and only ifPSMTtolerating mobile$t$-adversary is possible; and 2)mobility does not affect the round optimality:the fastestPSMTprotocol tolerating a static$t$-adversary isnot fasterthan the one tolerating a mobile$t$-adversary.

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” parts of the input. However, arriving at a good work partitioning is usually non-trivial and may require extensive empirical search. Such an extensive 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 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: finding the connected components of a graph (CC), multiplying two unstructured sparse matrices (spmm), and multiplying two scalefree sparse matrices. 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.

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.

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

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.

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 aprovably secureandblindbiometric 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.

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.

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.

A robust combiner for a cryptographic primitive gives a secure implementation of the primitive when at least some of the input candidates are secure. Such constructions provide robustness against insecure implementations and incorrect assumptions underlying the candidate schemes. Robust combiners are useful tools for ensuring better security in applied cryptography. Combiners from the perspective of threshold schemes have been previously studied. However, such threshold schemes typically fail to capture all possible scenarios. In this paper, we characterize the possibility of a transparent black-box combiner for oblivious transfer (OT), given an access structure over the candidate implementations. We also propose a circuit-based framework for the construction of such combiners, and hence reduce the problem of optimal OT combiners to circuit optimization.

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.

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.

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.

Global consistency or Byzantine Agreement (BA) and reliable point-to-point communication are two of the most important and well-studied problems in distributed computing. Informally, BA is about maintaining a consistent view of the world among all the non-faulty players in the presence of faults. 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] Specifically, in the standard unauthenticated model, (2t + 1)-connectivity is necessary whereas in the authenticated setting (t + 1)-connectivity is required. Thus, a folklore is that maintaining global consistency 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 graphs exist only if it is possible to simulate an overlay-ed complete graph. Surprisingly, we show that the folklore is far from true-- achieving global consistency can be strictly easier than all-pair point-to-point communication.

We consider the problem of probabilistic reliable communication (PRC) over directed networks: Over a synchronous directed network N} = (P,E) where P is the set of vertices and E denotes the set of arcs/edges in the network, the sender S ∈ P wishes to send a message m to the receiver R ∈ P in a robust manner such that the message is correctly received by R with a very high probability, in spite of the presence of up to t Byzantine-faulty nodes in N. We ask the specific question if PRC is affected when the players have only partial knowledge of the network topology. 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 [1, 3]. In this work, we show an example where partial knowledge of the topology results in the failure of PRC, whereas complete knowledge of the same, makes PRC possible.

Shortest path computation in presence of obstacles has been a subject of study since long and so has been the study of privacy preserving algorithms. In this paper we design efficient privacy preserving algorithms for computing the shortest path circumventing convex polygonal obstacles. Specifically, we assume that a party A has source s and destination d while another party B has the list of convex polygonal obstacles and A wishes to find the shortest path from s to d without compromising each others' privacy. That is, at the end of the protocol, A must not know anything else about the obstacles other that what may be revealed by the shortest path that is output and B must not know anything about A's source/destination.

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.

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.

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.

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.

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(tb,tf), who has unbounded computing power and can corrupt tb and tf nodes in the network in Byzantine and fail-stop fashion respectively.

No abstract available.

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.

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.

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.

No abstract available.

Consider a synchronous network of n players, each with a local input. The goal of distributed consensus is to globally agree on one of the valid inputs even if some non-trivial subset of the players are faulty. By valid input, we mean the input of any non-faulty player. Extant results in Byzantine agreement literature capture the behaviour of faulty players in an "all-or-nothing" fashion. For instance, a (Byzantine) faulty player is completely unconstrained and could behave differently with different players. This leads to a gross underestimation of the achievable fault-tolerance. In this work, we propose a fault-model that considerably improves the estimation of fault-tolerance and helps capture real-life scenarios better. For instance, if two (honest) players were part of the same LAN (which is essentially a broadcast network), it is impossible for a external faulty player to behave differently with these two players (though the faulty player may behave with "equal" malice with both these players!). Among our results, we introduce the sectional fault-model that is more general and can capture practical scenarios not captured by any extant model. We provide a complete characterization of the tolerable faults and present efficient protocols to achieve consensus. We remark that the results of this paper strictly generalize the extant characterizations of fault-tolerance. For example, consider a network of four players P1, P2, P3 and P4, under the corrupting influence of a Byzantine adversary given by the adversary structure A = {(P1, P2), (P2, P3), (P4)}. Agreement is impossible in such a scenario, since the three sets from A cover the player set. However, it would be evident from our results that consensus in the above scenario was indeed possible if (and only if) the players P1, P3 and P4 belonged to a single LAN in the network!

No abstract available.

We study the interplay of network connectivity and perfectly secure message transmission under the corrupting influence of generalized Byzantine adversaries. It is known that in the threshold adversary model, where the Byzantine adversary can corrupt upto any t among the n players (nodes), perfectly secure communication among any pair of players is possible if and only if the underlying synchronous network is (2t + 1)-connected. Strictly generalizing these results to the non-threshold setting, we show that perfectly secure communication among any pair of players is possible if and only if the union of no two sets in the adversary structure is a vertex cutset of the synchronous network. The computation and communication complexities of the transmission protocol are polynomial in the size of the network and the maximal basis of the adversary structure.