Sharif Digital Repository

Efficient storage and handling of data stored in a peer-to-peer (P2P) network, proves vital for various applications such as query processing and data mining. This paper presents a distributed, scalable and robust layered overlay (L-overlay) to index and manage multidimensional data in a dynamic P2P network. The proposed method distinguishes between the data and peer layers, with efficient mapping between the two. The data is organized such that semantically similar data objects are accessed hastily. Grid and tree structures are proposed for the peer layer. As application examples of L-overlay in query processing and data mining, k-nearest neighbors query processing and distributed Naïve... 

Today there are many Internet sites which require only the entry by human users but unfortunately some computer softwares called bots are designed by some hackers to enter these sites and use their resources through false registration. As a result some systems named CAPTCHA have been introduced to tell apart human users and computer software. This paper introduces a new CAPTCHA method. In this method a simple mathematical problem is generated according to a predefined pattern but instead of some object's name, we put their images. Then the whole problem is saved and shown to the user inform of an image to be answered by him. But since answering this problem requires four abilities of... 

In this paper, we study the problem of finding the shortest path between two points inside a simple polygon such that there is at least one point on the path from which a query point is visible. We provide an algorithm which preprocesses the input in O (n2 + n K) time and space and provides logarithmic query time. The input polygon has n vertices and K is a parameter dependent on the input polygon which is O (n2) in the worst case but is much smaller for most polygons. The preprocessing algorithm sweeps an angular interval around every reflex vertex of the polygon to store the optimal contact points between the shortest paths and the windows separating the visibility polygons of the query... 

With the advent of cloud computing and Internet of Things and delegation of data collection and aggregation to third parties, the results of the computations should be verified. In distributed models, there are multiple sources. Each source creates authenticators for the values and sends them to the aggregator. The aggregator combines the authenticated values and creates a verification object for verifying the computation/aggregation results. In this paper, we propose two constructions for verifying the results of countable and window-based countable functions. These constructions are useful for aggregate functions such as median, max/min, top-k/first-k, and range queries, where the... 

An important security challenge in database outsourcing scenarios is the correctness verification of query results. The proposed approaches in the literature, impose high overhead on both the service provider and specially the clients. In this paper, we propose the Trust-Based Fake Tuples approach to audit the correctness of query results. In this approach, some fake tuples are included among the real ones in order to verify the correctness of the results. The experience learnt from past results is used in this paper to evaluate the trust toward the service provider. This trust value is used to tune the number of fake tuples and subsequently the imposed overhead. As the trust value toward... 

Enforcing dynamic and confidential access control policies is a challenging issue of data outsourcing to external servers due to the lack of trust towards the servers. In this paper, we propose a scalable yet flexible access control enforcement mechanism when the underlying relational data, on which access policies are defined, has been shared through a secret sharing scheme. For sharing values of an attribute in a relation, the attribute is assigned a secret distribution key and its values are split and distributed among data servers according to a Shamir based secret sharing scheme. Given access control policies over attributes of the relation schema, access to distribution keys, used... 

Enforcing dynamic and confidential access control policies is a challenging issue of data outsourcing to external servers due to the lack of trust towards the servers. In this paper, we propose a scalable yet flexible access control enforcement mechanism when the underlying relational data, on which access policies are defined, has been shared through a secret sharing scheme. For sharing values of an attribute in a relation, the attribute is assigned a secret distribution key and its values are split and distributed among data servers according to a Shamir based secret sharing scheme. Given access control policies over attributes of the relation schema, access to distribution keys, used... 

An adjustable join (AdjoinAdjoin) scheme [4] is a symmetric-key primitive that enables a user to securely outsource his database to a server, and later to issue join queries for a pair of columns. When queries are extended to a list of columns, the 3Partition3Partition security of Adjoin schemes [8] does not capture the expected security. To address this deficiency, we introduce the syntax and security notion of multi-adjustable join (M-AdjoinM-Adjoin) schemes. We propose a new security notion for this purpose, which we refer to as M3PartitionM3Partition. The 3Partition3Partition security of AdjoinAdjoin extends to the M3PartitionM3Partition security of M-AdjoinM-Adjoin in a straightforward... 

Security of database outsourcing, due to the untrustworthiness of service provider, is a basic challenge to have Database As a Service in a cloud computing environment. Having disparate assumptions to solve different aspects of security such as confidentiality and integrity is an obstacle for an integrated secure solution through the combination of existing approaches. Concentrating on confidentiality and integrity aspects of database outsourcing, this paper proposes an approach in which each attribute value is split up between several data servers using a customized threshold secret sharing scheme. Our approach preserves data confidentiality and at the same time provides the correctness... 

A major challenge organizations face when hosting or moving their data to the Cloud is how to support complex queries over outsourced data while preserving their confidentiality. In principle, encryption-based systems can support querying encrypted data, but their high complexity has severely limited their practical use. In this paper, we propose an efficient yet secure secret sharing-based approach for outsourcing relational data to honest-but-curious data servers. The problem with using secret sharing in a data outsourcing scenario is how to efficiently search within randomly generated shares. We present multiple partitioning methods that enable clients to efficiently search among shared... 

Given a set S of n disjoint line segments in ℝ2, the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can trivially be solved in logarithmic query time using O(n4) preprocessing time and space. Gudmundsson and Morin proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. They answer any query in Oε(n1−α) with Oε(n2+2α) of preprocessing time and space, where α is a constant 0 ≤ α ≤ 1, ε > 0 is another constant that can be made arbitrarily small, and Oε(f(n)) = O(f(n)nε). In this paper, we propose a randomized approximation algorithm... 

One of the organizations’ main concerns is to protect sensitive data in database systems, especially the ones outsourced to untrusted service providers. An effective solution for this issue is to employ database encryption methods. Among different encryption approaches, Bucket-based method has the advantage of balancing security and performance of database operations. However, generating false-positive results in executing queries is the main drawback of this method. On the other hand, multi-join queries are one of the most critical operations executed on these stored sensitive data. Hence, acceptable processing and response time in executing multi-join queries is required. In this paper, we... 

We study two well-known planar visibility problems, namely visibility testing and visibility counting, in a model where there is uncertainty about the input data. The standard versions of these problems are defined as follows: we are given a set S of n segments in R 2 , and we would like to preprocess S so that we can quickly answer queries of the form: is the given query segment s∈S visible from the given query point q∈R 2 (for visibility testing) and how many segments in S are visible from the given query point q∈R 2 (for visibility counting). In our model of uncertainty, each segment may or may not exist, and if it does, it is located in one of finitely many possible locations, given by a... 

Today, many applications produce and use time series data. The data of this type may contain sensitive information. So they should be protected against unauthorized accesses. In this paper, security issues of time series data are identified and an access and inference control model for satisfying the identified security requirements is proposed. Using this model, administrators can define authorization rules based on various time-based granularities (e.g. day or month) and apply value-based constraints over the accessed times series data. Furthermore, they can define policy rules over the composition of multiple time-series other than the base time-series data. Detecting and resolving... 

We present an ontology based indexing method for unstructured P2P networks. We maintain limited size indexes at each node to identify number of documents accessible on each concept without loosing any indexing information. Out method supports complex queries, combined of conjunction and disjunction phrases. We simulate our search algorithm on an unstructured P2P network and show that our method significantly reduces the network traffic. © 2008 Springer-Verlag  

We introduce the notion of private set operations (PSO) as a symmetric-key primitive in the cloud scenario, where a client securely outsources his dataset to a cloud service provider and later privately issues queries in the form of common set operations. We define a syntax and security notion for PSO and propose a general construction that satisfies it. There are two main ingredients to our PSO scheme: an adjustable join (Adjoin) scheme (MIT-CSAIL-TR-2012-006 (2012) Cryptographic treatment of CryptDB's adjustable join. http://people.csail.mit.edu/nickolai/papers/popa-join-tr.pdf) and a tuple set (TSet) scheme (Cash, D., Jarecki, S., Jutla, C. S., Krawczyk, H., Rosu, M.-C., and Steiner, M.... 

Researchers have been studying security challenges of database outsourcing for almost a decade. Privacy of outsourced data is one of the main challenges when the "Database As a Service" model is adopted in the service oriented trend of the cloud computing paradigm. This is due to the insecurity of the network environment or even the untrustworthiness of the service providers. This paper proposes a method to preserve privacy of outsourced data based on Shamir's secret sharing scheme. We split attribute values into several parts and distribute them among untrusted servers. The problem of using secret sharing in data outsourcing scenario is how to search efficiently within the randomly... 

Online social networks, World Wide Web, media, and technological networks, and other types of so-called information networks are ubiquitous nowadays. These information networks are inherently heterogeneous and dynamic. They are heterogeneous as they consist of multi-Typed objects and relations, and they are dynamic as they are constantly evolving over time. One of the challenging issues in such heterogeneous and dynamic environments is to forecast those relationships in the network that will appear in the future. In this article, we try to solve the problem of continuous-Time relationship prediction in dynamic and heterogeneous information networks. This implies predicting the time it takes... 

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum weight subtree spanning a given subset of (terminal) nodes of the original graph. Minimum Spanning Tree Heuristic (MSTH) is a heuristic for solving the Steiner problem in graphs. In this paper we first review existing algorithms for solving the Steiner problem in graphs. We then introduce a new parallel version of MSTH on three dimensional mesh of trees architecture. We describe our algorithm and analyze its time complexity. The time complexity analysis shows that the algorithm's running time is O(lg2 n) which is comparable with other existing parallel solutions. © 2007...