6168983
Privacy Preserving Nearest Neighbor Search
Data mining is frequently obstructed by privacy concerns. In many cases data is distributed, and bringing the data together in one place for analysis is not possible due to privacy laws (e.g. HIPAA) or policies. Privacy preserving data mining techniques have been developed to address this issue by providing mechanisms to mine the data while giving certain privacy guarantees. In this work we address the issue of privacy preserving nearest neighbor search, which forms the kernel of many data mining applications. To this end, we present a novel algorithm based on secure multiparty computation primitives to compute the nearest neighbors of records in horizontally distributed data. We show how this algorithm can be used in three important data mining algorithms, namely LOF outlier detection, SNN clustering, and kNN classification
8456310
Detecting Phantom Nodes in Wireless Sensor Networks
In an adversarial environment, various kinds of security attacks become possible if malicious nodes could claim fake locations that are different from where they are physically located. In this paper, we propose a secure localization mechanism that detects the existence of these nodes, termed as phantom nodes, without relying on any trusted entities, an approach significantly different from the existing ones. The proposed mechanism enjoys a set of nice features. First, it does not have any central point of attack. All nodes play the role of verifier, by generating local map, i.e. a view constructed based on ranging information from its neighbors. Second, this distributed and localized construction results in quite strong results: even when the number of phantom nodes is greater than that of honest nodes, we can Alter out most phantom nodes. Our analysis and simulations under realistic noisy settings demonstrate our scheme is effective in the presence of a large number of phantom nodes.
47302704
On the performance of group key agreement protocols
Group key agreement (GKA) is a fundamental building block for securing peer group communication systems (GCS). Several group key agreement protocols were proposed in the past, all assuming an underlying group communication infrastructure. This paper presents a performance evaluation of 5 notable GKA protocols integrated with a reliable group communication system (Spread). They are: centralized group key distribution (CKD), Burmester-Desmedt (BD), Steer et al. (STR), group Diffie-Hellman GDH) and tree-based group Diffie-Hellman (TGDH).. We present concrete results obtained in experiments on local- and wide-area networks. Our analysis of these results offers insights into their relative scalability and practicality.
7213506
Batch Verifications with ID-Based Signatures
An identity (ID)-based signature scheme allows any pair of users to verify each other’s signatures without exchanging public key certificates. With the advent of Bilinear maps, several ID-based signatures based on the discrete logarithm problem have been proposed. While these signatures have an advantage in the fact that the system secret can be shared by several parties using a threshold scheme (thereby overcoming the security problem of RSA-based ID-based signature schemes), they all share the same efficiency disadvantage. To overcome this, some schemes have focused on finding ways to verify multiple signatures at the same time (i.e. the batch verification problem). While they had some success in improving efficiency of verification, each had a slightly diversified definition of batch verification. In this paper, we propose a taxonomy of batch verification against which we analyze security of well-known ID-based signature schemes. We also propose a new ID-based signature scheme that allows for all types of multiple signature batch verification, and prove its security in random oracle model.
14346631
Remote Software-Based Attestation for Wireless Sensors
Wireless sensor networks are envisioned to be deployed in mission-critical applications. Detecting a compromised sensor, whose memory contents have been tampered, is crucial in these settings, as the attacker can reprogram the sensor to act on his behalf. In the case of sensors, the task of verifying the integrity of memory contents is difficult as physical access to the sensors is often infeasible. In this paper, we propose a software-based approach to verify the integrity of the memory contents of the sensors over the network without requiring physical contact with the sensor. We describe the building blocks that can be used to build a program for attestation purposes, and build our attestation program based on these primitives. The success of our approach is not dependent on accurate measurements of the execution time of the attestation program. Further, we do not require any additional hardware support for performing remote attestation. Our attestation procedure is designed to detect even small memory changes and is designed to be resistant against modifications by the attacker.
6315809
On the performance of group key agreement protocols
Group key agreement is a fundamental building block for secure peer group communication systems. Several group key management techniques were proposed in the last decade, all assuming the existence of an underlying group communication infrastructure to provide reliable and ordered message delivery as well as group membership information. Despite analysis, implementation, and deployment of some of these techniques, the actual costs associated with group key management have been poorly understood so far. This resulted in an undesirable tendency: on the one hand, adopting suboptimal security for reliable group communication, while, on the other hand, constructing excessively costly group key management protocols.This paper presents a thorough performance evaluation of five notable distributed key management techniques (for collaborative peer groups) integrated with a reliable group communication system. An in-depth comparison and analysis of the five techniques is presented based on experimental results obtained in actual local- and wide-area networks. The extensive performance measurement experiments conducted for all methods offer insights into their scalability and practicality. Furthermore, our analysis of the experimental results highlights several observations that are not obvious from the theoretical analysis.
6480057
Distance Measures in Genetic Algorithms
Metric is one of the fundamental tools for understanding space. It gives induced topology to the space and it is the most basic way to provide the space with topology. Di.erent metrics make di.erent topologies. The shape of the space largely depends on its metric. In understanding genetic algorithms, metric is also basic and important. In genetic algorithms, a good distance measure not only helps to analyze their search spaces, but can also improve their search capability. Hamming distance has been popular in most researches for genetic algorithms that deal with discrete spaces. It has also been widely adopted in studies about the analysis of the problem space. In this paper, we propose more reasonable distance measures depending on situations in the process of genetic algorithms and show that they are actually metrics. We propose three distance measures: one for the population-based search, another for the solution space based on K-ary encoding, and the third as an approximate measure of performance improvement of linkage-based genetic algorithms.
30845722
Accurate exploration of timing and area trade-offs in arithmetic optimization using carry-save-adders
Timing and area of circuits are two of the most important design criteria to be optimized in data path synthesis. In addition, carry-save-adder (CSA) has been proven to be one of the most efficient implementation units in optimizing timing and/or area of arithmetic circuits. However, the existing approaches are restricted in using CSAs, i.e., optimizing operation trees separately without any interaction between them, resulting in a locally optimized CSA circuit. To overcome this limitation, we propose a practically efficient solution to the problem of an accurate exploration of timing and area trade-offs in optimizing arithmetic circuits in the presence of multiple operation trees using CSAs. The application of our approach is able to find a best CSA implementation of circuit in terms of timing and area.
12076
Multi-attractor gene reordering for graph bisection
We propose a new gene reordering scheme for the graph bisection problem. Our gene reordering starts with two or more vertices to capture the clustering structure of graphs effectively. We devised a chromosome repairing method for hybrid genetic search, which helps exploit clusters when combined with gene reordering. Experimental tests showed that the suggested reordering scheme significantly improves the performance of genetic algorithms over previous reordering methods.
19448510
A Genetic Approach for Gene Selection on Microarray Expression Data
Microarrays allow simultaneous measurement of the expression levels of thousands of genes in cells under different physiological or disease states. Because the number of genes exceeds the number of samples, class prediction on microarray expression data leads to an extreme “curse of dimensionality” problem. A principal goal of these studies is to identify a subset of informative genes for class prediction to reduce the curse of dimensionality. We propose a novel genetic approach that selects a subset of predictive genes for classification on the basis of gene expression data. Our genetic algorithm maximizes correlation between genes and classes and minimizes intercorrelation among genes. We tested the genetic algorithm on leukemia data sets and obtained improved results over previous results.
17676271
Ontology Modeling and Storage System for Robot Context Understanding
A mobile robot that interacts with its environment needs a machine-understandable representation of objects and their usages. We present an ontology of objects, with generic shape representations obtained through form-function reasoning. Sets of objects are associated with typical human activities, which supports context understanding. We describe an efficient ontology document storage system, which is based on stable and well-known relational databases. We first design a relational data schema appropriate for Web Ontology Language (OWL) documents, and then develop a transformation mechanism from OWL documents to the relational schema.