We introduce a novel privacy-preserving biometric authentication scheme based on irises that allows a user to enroll once at a trusted biometric certification authority (BCA) and authenticate to online service providers (SPs) multiple times without involving the BCA during the authentication. Our scheme preserves the user’s biometric privacy from the SPs and transactional privacy from the BCA, while providing security against a malicious user. During the enrollment, the BCA issues a signed token that encrypts the user’s biometrics. We introduce techniques enabling the SP and the user to perform secure computation of biometric matching between such encrypted biometrics and the user’s biometrics captured at the authentication time. We provide a prototype implementation, a performance evaluation, and a security analysis of the protocol.

This paper addresses the problem of sharing person-specific genomic sequences without violating the privacy of their data subjects to support large-scale biomedical research projects. The proposed method builds on the framework proposed by Kantarcioglu et al. [1] but extends the results in a number of ways. One improvement is that our scheme is deterministic, with zero probability of a wrong answer (as opposed to a low probability). We also provide a new operating point in the space-time tradeoff, by offering a scheme that is twice as fast as theirs but uses twice the storage space. This point is motivated by the fact that storage is cheaper than computation in current cloud computing pricing plans. Moreover, our encoding of the data makes it possible for us to handle a richer set of queries than exact matching between the query and each sequence of the database, including: (i) counting the number of matches between the query symbols and a sequence; (ii) logical OR matches where a query symbol is allowed to match a subset of the alphabet thereby making it possible to handle (as a special case) a “not equal to” requirement for a query symbol (e.g., “not a G”); (iii) support for the extended alphabet of nucleotide base codes that encompasses ambiguities in DNA sequences (this happens on the DNA sequence side instead of the query side); (iv) queries that specify the number of occurrences of each kind of symbol in the specified sequence positions (e.g., two `A' and four `C' and one `G' and three `T', occurring in any order in the query-specified sequence positions); (v) a threshold query whose answer is `yes' if the number of matches exceeds a query-specified threshold (e.g., “7 or more matches out of the 15 query-specified positions”). (vi) For all query types, we can hide the answers from the decrypting server, so that only the client learns the answer. (vii) In all cases, the client deterministically learns only the query's answer, except for query type (v) where we quantify the (very small) statistical leakage to the client of the actual count.

The SQL group-by operator plays an important role in summarizing and aggregating large datasets in a data analytics stack. The Similarity SQL-based Group-By operator (SGB, for short) extends the semantics of the standard SQL Group-by by grouping data with similar but not necessarily equal values. While existing similarity-based grouping operators efficiently realize these approximate semantics, they primarily focus on one-dimensional attributes and treat multi-dimensional attributes independently. However, correlated attributes, such as in spatial data, are processed independently, and hence, groups in the multi-dimensional space are not detected properly. To address this problem, we introduce two new SGB operators for multi-dimensional data. The first operator is the clique (or distance-to-all) SGB, where all the tuples in a group are within some distance from each other. The second operator is the distance-to-any SGB, where a tuple belongs to a group if the tuple is within some distance from any other tuple in the group. Since a tuple may satisfy the membership criterion of multiple groups, we introduce three different semantics to deal with such a case: (i) eliminate the tuple, (ii) put the tuple in any one group, and (iii) create a new group for this tuple. We implement and test the new SGB operators and their algorithms inside PostgreSQL. The overhead introduced by these operators proves to be minimal and the execution times are comparable to those of the standard Group-by. The experimental study, based on TPC-H and a social check-in data, demonstrates that the proposed algorithms can achieve up to three orders of magnitude enhancement in performance over baseline methods developed to solve the same problem.

The SQL group-by operator plays an important role in summarizing and aggregating large datasets in a data analytics stack. While the standard group-by operator, which is based on equality, is useful in several applications, allowing similarity aware grouping provides a more realistic view on real-world data that could lead to better insights. The Similarity SQL-based Group-By operator (SGB, for short) extends the semantics of the standard SQL Group-by by grouping data with similar but not necessarily equal values. While existing similarity-based grouping operators efficiently realize these approximate semantics, they primarily focus on one-dimensional attributes and treat multi-dimensional attributes independently. However, correlated attributes, such as in spatial data, are processed independently, and hence, groups in the multi-dimensional space are not detected properly. To address this problem, we introduce two new SGB operators for multi-dimensional data. The first operator is the clique (or distance-to-all) SGB, where all the tuples in a group are within some distance from each other. The second operator is the distance-to-any SGB, where a tuple belongs to a group if the tuple is within some distance from any other tuple in the group. Since a tuple may satisfy the membership criterion of multiple groups, we introduce three different semantics to deal with such a case: (i) eliminate the tuple, (ii) put the tuple in any one group, and (iii) create a new group for this tuple. We implement and test the new SGB operators and their algorithms inside PostgreSQL. The overhead introduced by these operators proves to be minimal and the execution times are comparable to those of the standard Group-by. The experimental study, based on TPC-H and a social check-in data, demonstrates that the proposed algorithms can achieve up to three orders of magnitude enhancement in performance over baseline methods developed to solve the same problem.

In this work we present a simple, yet effective and practical, scheme to improve the security of stored password hashes, rendering their cracking detectable and insuperable at the same time. We utilize a machine-dependent function, such as a physically unclonable function (PUF) or a hardware security module (HSM) at the authentication server to prevent off-site password discovery, and a deception mechanism to alert us if such an action is attempted. Our scheme can be easily integrated with legacy systems without the need of any additional servers, changing the structure of the hashed password file or any client modifications. When using the scheme the structure of the hashed passwords file, etc/shadow or etc/master.passwd, will appear no different than in the traditional scheme.1 However, when an attacker exfiltrates the hashed passwords file and tries to crack it, the only passwords he will get are the ersatzpasswords --- the "fake passwords". When an attempt to login using these ersatzpasswords is detected an alarm will be triggered in the system. Even with an adversary who knows about the scheme, cracking cannot be launched without physical access to the authentication server. The scheme also includes a secure backup mechanism in the event of a failure of the hardware dependent function. We discuss our implementation and provide some discussion in comparison to the traditional authentication scheme.

Redactable signatures for linear-structured data such as strings have already been studied in the literature. In this paper, we propose a formal security model for leakage-free redactable signatures (LFRS) that is general enough to address authentication of not only trees but also graphs and forests. LFRS schemes have several applications, especially in enabling secure data management in the emerging cloud computing paradigm as well as in healthcare, finance and biological applications. We have also formally defined the notion of secure names. Such secure names facilitate leakage-free verification of ordering between siblings/nodes. The paper also proposes a construction for secure names, and a construction for leakagefree redactable signatures based on the secure naming scheme. The proposed construction computes a linear number of signatures with respect to the size of the data object, and outputs only one signature that is stored, transmitted and used for authentication of any tree, graph and forest.

Many cloud providers offer on demand applications as Business Process as a Service (BPaaS), allowing companies to outsource their processes. For cost saving, some process fragments can be reused on the cloud regardless of privacy risks. In this paper, we propose an anonymization-based approach to preserve client business activity while sharing process fragments between organizations on the cloud.

A running max (or min) filter asks for the maximum or (minimum) elements within a fixed-length sliding window. The previous best deterministic algorithm (developed by Gil and Kimmel, and refined by Coltuc) can compute the 1D max filter using 1.5+o(1) comparisons per sample in the worst case. The best known algorithm for independent and identically distributed input uses 1.25+o(1) expected comparisons per sample(by Gil and Kimmel). In this work, we show that the number of comparisons can be reduced to 1+o(1) comparisons per sample in the worst case. As a consequence of the new max/min filters, the opening (or closing) filter can also be computed using 1+o(1) comparisons per sample in the worst case, where the previous best work requires 1.5+o(1) comparisons per sample (by Gil and Kimmel); and computing the max and min filters simultaneously can be done in 2+o(1) comparisons per sample in the worst case, where the previous best work (by Lemire) requires 3 comparisons per sample. Our improvements over the previous work are asymptotic, that is, the number of comparisons is reduced only when the window size is large.

In practice, assigning access permissions to users must satisfy a variety of constraints motivated by business and security requirements. Here, we focus on Role-Based Access Control (RBAC) systems, in which access permissions are assigned to roles and roles are then assigned to users. User-role assignment is subject to role-based constraints, such as mutual exclusion constraints, prerequisite constraints, and role-cardinality constraints. Also, whether a user is qualified for a role depends on whether his/her qualification satisfies the role's requirements. In other words, a role can only be assigned to a certain set of qualified users. In this paper, we study fundamental problems related to access control constraints and user-role assignment, such as determining whether there are conflicts in a set of constraints, verifying whether a user-role assignment satisfies all constraints, and how to generate a valid user-role assignment for a system configuration. Computational complexity results and/or algorithms are given for the problems we consider.

Skyline computation is widely used in multicriteria decision making. As research in uncertain databases draws increasing attention, skyline queries with uncertain data have also been studied. Some earlier work focused on probabilistic skylines with a given threshold; Atallah and Qi [2009] studied the problem to compute skyline probabilities for all instances of uncertain objects without the use of thresholds, and proposed an algorithm with subquadratic time complexity. In this work, we propose a new algorithm for computing all skyline probabilities that is asymptotically faster: worst-case O(n √ n log n ) time and O(n) space for 2D data; O ( n 2−1/d log d −1 n ) time and O(n log d −2 n ) space for d -dimensional data. Furthermore, we study the online version of the problem: Given any query point p (unknown until the query time), return the probability that no instance in the given data set dominates p . We propose an algorithm for answering such an online query for d -dimensional data in O(n 1−1/ d log d −1 n ) time after preprocessing the data in O(n 2−1/d log d −1 ) time and space.

We give improved protocols for the secure and private outsourcing of linear algebra computations, that enable a client to securely outsource expensive algebraic computations (like the multiplication of large matrices) to a remote server, such that the server learns nothing about the customer's private input or the result of the computation, and any attempted corruption of the answer by the server is detected with high probability. The computational work performed at the client is linear in the size of its input and does not require the client to locally carry out any expensive encryptions of such input. The computational burden on the server is proportional to the time complexity of the current practically used algorithms for solving the algebraic problem (e.g., proportional to n3 for multiplying two n x n matrices). The improvements we give are: (i) whereas the previous work required more than one remote server and assumed they do not collude, our solution works with a single server (but readily accommodates many, for improved performance); (ii) whereas the previous work required a server to carry out expensive cryptographic computations (e.g., homomorphic encryptions), our solution does not make use of any such expensive cryptographic primitives; and (iii) whereas in previous work collusion by the servers against the client revealed to them the client's inputs, our scheme is resistant to such collusion. As in previous work, we maintain the property that the scheme enables the client to detect any attempt by the server(s) at corruption of the answer, even when the attempt is collusive and coordinated among the servers.

Given a d-dimensional array A with N entries, the Range Minimum Query (RMQ) asks for the minimum element within a contiguous subarray of A. The 1D RMQ problem has been studied intensively because of its relevance to the Nearest Common Ancestor problem and its important use in stringology. If constant-time query answering is required, linear time and space preprocessing algorithms were known for the 1D case, but not for the higher dimensional cases. In this paper, we give the first linear-time preprocessing algorithm for arrays with fixed dimension, such that any range minimum query can be answered in constant time.

Modern geographic databases can contain a large volume of data that need to be distributed to subscribed customers. The data can be modeled as a cube, where typical dimensions include latitude, longitude, and time. One way of distributing the data consists of making freely available encrypted versions of selected subsets of the data, and giving each paying customer the decryption keys for their authorized subsets only. In this work, we give efficient key management schemes to balance the number of keys assigned to a customer, and its time to derive the appropriate key for decrypting the data.

Record linkage is the computation of the associations among records of multiple databases. It arises in contexts like the integration of such databases, online interactions and negotiations, and many others. The autonomous entities who wish to carry out the record matching computation are often reluctant to fully share their data. In such a framework where the entities are unwilling to share data with each other, the problem of carrying out the linkage computation without full data exchange has been called private record linkage. Previous private record linkage techniques have made use of a third party. We provide efficient techniques for private record linkage that improve on previous work in that (i) they make no use of a third party; (ii) they achieve much better performance than that of previous schemes in terms of execution time and quality of output (i.e., practically without false negatives and minimal false positives). Our software implementation provides experimental validation of our approach and the above claims.

Graph-theoretic aggregation problems have been considered both in OLAP (grid graph) and XML (tree). This paper gives new results for MIN aggregation in a tree, where we want the MIN in a query subtree consisting of the nodes reachable from a node u along paths of length ≤ k (u and k are query parameters). The same problem is well solved when the aggregation is SUM rather than MIN, but the solutions rely on additive inverses for the “+ ” operator, and they fail for the MIN aggregation which is the topic of this paper. For the directed (rooted tree) case, we give an O(n) space, constant query time solution. For the undirected case, the space complexity is O(n log n) and the query time is O(log n).

Skyline computation is widely used in multi-criteria decision making. As research in uncertain databases draws increasing attention, skyline queries with uncertain data have also been studied, e.g. probabilistic skylines. The previous work requires "thresholding" for its efficiency -- the efficiency relies on the assumption that points with skyline probabilities below a certain threshold can be ignored. But there are situations where "thresholding" is not desirable -- low probability events cannot be ignored when their consequences are significant. In such cases it is necessary to compute skyline probabilities of all data items. We provide the first algorithm for this problem whose worst-case time complexity is sub-quadratic. The techniques we use are interesting in their own right, as they rely on a space partitioning technique combined with using the existing dominance counting algorithm. The effectiveness of our algorithm is experimentally verified.

Abstract 3D computer graphics models and digitally‐controlled manufacturing have come together to enable the design, visualization, simulation, and automated creation of complex 3D objects. In our work, we propose and implement a framework for designing computer graphics objects and digitally manufacturing them such that no adversary can make imitations or counterfeit copies of the physical object, even if the adversary has a large number of original copies of the object, knowledge of the original object design, and has manufacturing precision that is comparable to or superior to that of the legitimate creator of the object. Our approach is to design and embed a signature on the surface of the object which acts as a certificate of genuinity of the object. The signature is detectable by a signature‐reading device, based on methods in computer graphics and computer vision, which contains some of the secret information that was used when marking the physical object. Further, the compromise of a signature‐reading device by an adversary who is able to extract all its secrets, does not enable the adversary to create counterfeit objects that fool other readers, thereby still enabling reliable copy detection. We implemented a prototype of our scheme end‐to‐end, including the production of the physical object and the genuinity‐testing device.

This paper investigates systems that steganographically embed information in the “noise” created by automatic translation of natural language documents. The main thrust of the work focuses on two problems – generation of plausible steganographic text

Hierarchies arise in the context of access control whenever the user population can be modeled as a set of partially ordered classes (represented as a directed graph). A user with access privileges for a class obtains access to objects stored at that class and all descendant classes in the hierarchy. The problem of key management for such hierarchies then consists of assigning a key to each class in the hierarchy so that keys for descendant classes can be obtained via efficient key derivation. We propose a solution to this problem with the following properties: (1) the space complexity of the public information is the same as that of storing the hierarchy; (2) the private information at a class consists of a single key associated with that class; (3) updates (i.e., revocations and additions) are handled locally in the hierarchy; (4) the scheme is provably secure against collusion; and (5) each node can derive the key of any of its descendant with a number of symmetric-key operations bounded by the length of the path between the nodes. Whereas many previous schemes had some of these properties, ours is the first that satisfies all of them. The security of our scheme is based on pseudorandom functions, without reliance on the Random Oracle Model. Another substantial contribution of this work is that we are able to lower the key derivation time at the expense of modestly increasing the public storage associated with the hierarchy. Insertion of additional, so-called shortcut, edges, allows to lower the key derivation to a small constant number of steps for graphs that are total orders and trees by increasing the total number of edges by a small asymptotic factor such as O (log * n ) for an n -node hierarchy. For more general access hierarchies of dimension d , we use a technique that consists of adding dummy nodes and dimension reduction. The key derivation work for such graphs is then linear in d and the increase in the number of edges is by the factor O (log d − 1 n ) compared to the one-dimensional case. Finally, by making simple modifications to our scheme, we show how to handle extensions proposed by Crampton [2003] of the standard hierarchies to “limited depth” and reverse inheritance.

Combinatorial group testing, given a set C of individuals ("customers"), consists of applying group tests on subsets of C for the purpose of identifying which members of C are infected (or, more generally, defective in some way). The outcome of a group test reveals only the presence or absence of infection(s) in that group, but a number of group tests exactly identifies all infected members.

We give efficient protocols for secure and private k-nearest neighbor (k-NN) search, when the data is distributed between two parties who want to cooperatively compute the answers without revealing to each other their private data. Our protocol for the single-step k-NN search is provably secure and has linear computation and communication complexity. Previous work on this problem had a quadratic complexity, and also leaked information about the parties' inputs. We adapt our techniquesto also solve the general multi-step k-NN search, and describe a specific embodiment of it for the case of sequence data. The protocols and correctness proofs can be extended to suit other privacy-preserving data mining tasks, such as classification and outlier detection.

In the third-party model for the distribution of data, the trusted data creator or owner provides an untrusted distributor D with integrity verification (IV) items that are stored at D in addition to the n data items. When a user U has a subset of n' of those n data items and needs to verify their integrity, U is provided by D with a number of IV items that U uses to verify its data's integrity. The model forbids U from receiving any information about the n-n' data items that the user is not authorized to access, and assumes that D has no signature authority (it stores only pre-signed IVs). Most of the published work in this area uses the Merkle tree or variants thereof, and typically requires D to store a linear or close to linear (in n) number s(n) of IV items that are pre-signed by the trusted authority. Moreover, most of the existing schemes impose on D a non-constant amount of computation work t(n) (typically logarithmic in n) in order to provide U with the IV items that enable U to verify the integrity of its data; we call h(n) the number of such IV items. The h(n) values found in the literature are non-constant, i.e., they actually do depend on the number of data items. The main contribution of this paper is to achieve linear s(n), constant h(n) and constant or logarithmic t(n) when the n data items are organized in a tree hierarchy T, and the user's subset of n' items form a subtree T'. The cases of T' considered are when T' is (i) rooted at a node v and of depth k below v; and (ii) reachable in k hops from v going both up and down in T.

In the third-party model for the distribution of data, the trusted data creator or owner provides an untrusted party V with data and integrity verification (IV) items for that data. When a user U gets a subset of the data at D or is already in possession of that subset, U may request from D the IV items that make it possible for U to verify the integrity of its data: D must then provide U with the (hopefully small) number of needed IVs. Most of the published work in this area uses the Merkle tree or variants thereof. For the problem of 2-dimensional range data, the best published solutions require V to store O(n log n) IV items for a database of n items, and allow a user IA to be sent only O(log n) of those IVs for the purpose of verifying the integrity of the data it receives from D (regardless of the size of lA's query rectangle). For data that is modeled as a 2-dimensional grid (such as GIS or image data), this paper shows that better bounds are possible: The number of IVs stored at D (and the time it takes to compute them) can be brought down to O(n), and the number of IVs sent to IA for verification can be brought down to a constant.

We give protocols for the secure and private outsourcing of linear algebra computations, that enable a client to securely outsource expensive algebraic computations (like the multiplication of huge matrices) to two remote servers, such that the servers learn nothing about the customer's private input or the result of the computation,and any attempted corruption of the answer by the servers is detected with high probability. The computational work done locally by the client is linear in the size of its input and does not require the client to carry out locally any expensive encryptions of such input.The computational burden on the servers is proportional to the time complexity of the current practically used algorithms for solving the algebraic problem (e.g., proportional to n3for multiplying two ntimesn matrices). If the servers were to collude against the client,then they would only find out the client's private inputs, but they would not be able to corrupt the answer without detection by the client.

This article studies the notion of quantitative policies for trust management and gives protocols for realizing them in a disclosure-minimizing fashion. Specifically, Bob values each credential with a certain number of points, and requires a minimum total threshold of points before granting Alice access to a resource. In turn, Alice values each of her credentials with a privacy score that indicates her degree of reluctance to reveal that credential. Bob's valuation of credentials and his threshold are private. Alice's privacy-valuation of her credentials is also private. Alice wants to find a subset of her credentials that achieves Bob's required threshold for access, yet is of as small a value to her as possible. We give protocols for computing such a subset of Alice's credentials without revealing any of the two parties' above-mentioned private information. Furthermore, we develop a fingerprint method that allows Alice to independently and easily recover the optimal knapsack solution, once the computed optimal value is given, but also enables verification of the integrity of the optimal value. The fingerprint method is useful beyond the specific authorization problem studied, and can be applied to any integer knapsack dynamic programming in a private setting.

The problem of key management for access control systems has been well-studied, and the literature contains several schemes for hierarchy-based and temporal-based access control. The problem of key management in such systems is how to assign keys to users such that each user is able to compute and have access to the appropriate resources while minimizing computation and storage requirements. In the current paper, we consider key management schemes for geo-spatial access control. That is, the access control policy assigns to a user a specific geographic area, and the user consequently obtains access to her area or information about it.In this work, the geography is modeled as an m × n grid of cells (let m ≥ n). Each cell has its own key associated with it, and a user who wants to access the content of a cell needs to obtain its key. Each user obtains access to a rectangular area (or a finite collection of such rectangles) and is able compute keys corresponding to the cells that comprise her area.Our main result is an efficient scheme with the following properties: (i) each user obtains a small constant number of secret keys that permit access to an arbitrary rectangular sub-grid, (ii) computation to derive the key of a specific cell in that rectangle consists of a constant number of efficient operations, and (iii) the server needs to maintain O(mn(log log m)2 log* m) public information accessible to all users. The public storage requirement is the worst-case bound and can be improved if the grid is partitioned into regions where the cells of a region share the same key.

The growth of the Internet has created tremendous opportunities for online collaborations. These often involve collaborative optimizations where the two parties are, for example, jointly minimizing costs without violating their own particular constraints (e.g., one party may have too much inventory, another too little inventory but too much production capacity, etc). Many of these optimizations can be formulated as linear programming problems, or, rather, as collaborative linear programming, in which two parties need to jointly optimize based on their own private inputs. It is often important to have online collaboration techniques and protocols that carry this out without either party revealing to the other anything about their own private inputs to the optimization (other than, unavoidably, what can be deduced from the collaboratively computed optimal solution). For example, two organizations who jointly invest in a project may want to minimize some linear objective function while satisfying both organizations' private and confidential constraints. Constraints are usually private when they reveal too much about the organizations' financial health, its future business strategy, etc. Linear programming problems have been widely studied in the literature. However, the existing solutions (e.g., the simplex method) do not extend to the above-mentioned framework in which the linear constraints are shared by the two parties, who do not want to disclose their own to the other party. In this paper, we give an efficient protocol for solving linear programming problems in the honest-but-curious model, such that neither party reveals anything about their private input to the other party (other than what can be inferred from the result). The amount of communication and computation done by our protocol is proportional to the time complexity of the simplex method, a widely used linear programming algorithm. We also provide a practical solution that prevents certain malicious behavior of the participants. The use of the known general circuit-simulation solutions to secure function evaluation is unacceptable for the simplex method, as it implies an exponential size circuit

Access hierarchies are useful in many applications and are modeled as a set of access classes organized by a partial order. A user who obtains access to a class in such a hierarchy is entitled to access objects stored at that class, as well as objects stored at its descendant classes. Efficient schemes for this framework assign only one key to a class and use key derivation to permit access to descendant classes. Ideally, the key derivation uses simple primitives such as cryptographic hash computations and modular additions. A straightforward key derivation time is then linear in the length of the path between the user's class and the class of the object that the user wants to access. Recently, work presented in [2] has given an efficient solution that significantly lowers this key derivation time, while using only hash functions and modular additions. Two fastkey-derivation techniques in that paper were given for trees, achieving O(log log n) and O(1) key derivation times, respectively, where n is the number of access classes. The present paper presents efficient key derivation techniques for hierarchies that are not trees, using a scheme that is very different from the above-mentioned paper. The construction we give in the present paper is recursive and uses the onedimensional case solution as its base. It makes a novel use of the notion of the dimension d of an access graph, and provides a solution through which no key derivation requires more than 2d+1 hash function computations, even for "unbalanced" hierarchies whose depth is linear in their number of access classes n. The significance of this result is strengthened by the fact that many access graphs have a low d value (e.g., trees correspond to the case d = 2). Our scheme has the desirable property (as did [2] for trees) that addition and deletion of edges and nodes in the access hierarchy can be "contained".

In an open environment such as the Internet, the decision to collaborate with a stranger (e.g., by granting access to a resource) is often based on the characteristics (rather than the identity) of the requester, via digital credentials: access is granted if Alice's credentials satisfy Bob's access policy. The literature contains many scenarios in which it is desirable to carry out such trust negotiations in a privacy-preserving manner, i.e., so as minimize the disclosure of credentials and/or of access policies. Elegant solutions were proposed for achieving various degrees of privacy-preservation through minimal disclosure. In this paper, we present protocols that protect both sensitive credentials and sensitive policies. That is, Alice gets the resource only if she satisfies the policy, Bob does not learn anything about Alice's credentials (not even whether Alice got access), and Alice learns neither Bob's policy structure nor which credentials caused her to gain access. Our protocols are efficient in terms of communication and in rounds of interaction

Today's world of increasingly dynamic environments naturally results in more and more data being available as fast streams. Applications such as stock market analysis, environmental sensing, Web clicks, and intrusion detection are just a few of the examples where valuable data is streamed. Often, streaming information is offered on the basis of a nonexclusive, single-use customer license. One major concern, especially given the digital nature of the valuable stream, is the ability to easily record and potentially "replay" parts of it in the future. If there is value associated with such future replays, it could constitute enough incentive for a malicious customer (Mallory) to record and duplicate data segments, subsequently reselling them for profit. Being able to protect against such infringements becomes a necessity. In this work, we introduce the issue of rights protection for discrete streaming data through watermarking. This is a novel problem with many associated challenges including: operating in a finite window, single-pass, (possibly) high-speed streaming model, and surviving natural domain specific transforms and attacks (e.g., extreme sparse sampling and summarizations), while at the same time keeping data alterations within allowable bounds. We propose a solution and analyze its resilience to various types of attacks as well as some of the important expected domain-specific transforms, such as sampling and summarization. We implement a proof of concept software (wms.*) and perform experiments on real sensor data from the NASA Infrared Telescope Facility at the University of Hawaii, to assess encoding resilience levels in practice. Our solution proves to be well suited for this new domain. For example, we can recover an over 97 percent confidence watermark from a highly down-sampled (e.g., less than 8 percent) stream or survive stream summarization (e.g., 20 percent) and random alteration attacks with very high confidence levels, often above 99 percent.

The problem of key management in an access hierarchy has elicited much interest in the literature. The hierarchy is modeled as a set of partially ordered classes (represented as a directed graph), and a user who obtains access (i.e., a key) to a certain class can also obtain access to all descendant classes of her class through key derivation. Our solution to the above problem has the following properties: (i) only hash functions are used for a node to derive a descendant's key from its own key; (ii) the space complexity of the public information is the same as that of storing the hierarchy; (iii) the private information at a class consists of a single key associated with that class; (iv) updates (revocations, additions, etc.) are handled locally in the hierarchy; (v) the scheme is provably secure against collusion; and (vi) key derivation by a node of its descendant's key is bounded by the number of bit operations linear in the length of the path between the nodes. Whereas many previous schemes had some of these properties, ours is the first that satisfies all of them. Moreover, for trees (and other recursively decomposable hierarchies), we are the first to achieve a worst- and average-case number of bit operations for key derivation that is exponentially better than the of a balanced hierarchy (double-exponentially better if the hierarchy is unbalanced, i.e., tall and skinny); this is achieved with only a constant increase in the space for the hierarchy. We also show how with simple modifications our scheme can handle extensions proposed by Crampton of the standard hierarchies to limited depth and reverse inheritance [13]. The security of our scheme relies only on the use of pseudo-random functions.

In this work we address the problem of portable and flexible privacy-preserving access rights for large online data repositories. Privacy-preserving access control means that the service provider can neither learn what access rights a customer has nor link a request to access an item to a particular customer, thus maintaining privacy of both customer activity and customer access rights. Flexible access rights allow any customer to choose any subset of items from the repository and correspondingly be charged only for the items selected. And portability of access rights means that the rights themselves can be stored on small devices of limited storage space and computational capabilities, and therefore the rights must be enforced using the limited resources available.Our main results are solutions to the problem that utilize minimal perfect hash functions and order-preserving minimal perfect hash functions. None of them use expensive cryptography, all require very little space, and they are therefore suitable for computationally weak and space-limited devices such as smartcards, sensors, etc. Performance of the schemes is measured as the probability of false positives (i.e., the probability that access to an unpurchased item will be permitted) for a given storage space bound. Using our techniques, for a data repository of size n and subscription order of m ll n items, we achieve a probability of false positives of m-c using only O(cm) bits of storage space, where c is an adjustable parameter (a constant or otherwise) that can be set to provide the desired performance. This is the first time that such provable bounds are established for this problem, and we believe the techniques we use are of more general interest through the unusual use we make of perfect hashing.

We propose a new method for a reliable identification of significant sequential episodes occurring within a window of size w in an event sequence modeled by a Markov source. As a measure of significance we use Ω∃(n, w), the number of windows containing the episode as a subsequence. We prove that Ω∃(n, w) is a sum of a φ-mixing sequence of random variables and therefore obeys the central limit theorem. This leads us to a computational formula for a threshold to identify significant episodes. The novelty of our method for Markov source stems from the fact that, instead of scoring the whole sequence using a Markov model, we compute the expected value of Ω∃(n, w) and its variance in order to estimate the threshold and compare it to the observed Ω∃(n, w). Since performance of the method critically depends on the model structure and parameters, we argue that variable-length Markov models of event streams are superior to fixed-length Markov models. We chose DNA sequences as event sources in experiments, and compared the performance of fixed-length Markov models with interpolated Markov models. This paper is an extension of our previous work in [8, 1] where we considered the problem of the reliable detection of significant episodes for memoryless sources.

Typically, when a borrower (Bob) wishes to establish a tradeline (e.g., a mortgage, an automobile loan, or a credit card) with a lender (Linda), Bob is subjected to a credit check by Linda. The credit check is done by having Linda obtain financial information about Bob in the form of a credit report. Credit reports are maintained by Credit Report Agencies, and contain a large amount of private information about individuals. Furthermore, Linda's criteria for loan qualification are also private information. We propose a "privacy-preserving" credit check scheme that allows Bob to have his credit checked without divulging private information to Linda while protecting Linda's interests. We give protocols for achieving the above while: i) protecting Bob's private information, ii) making sure that Bob cannot lie about his credit (thus Linda is assured that the information is accurate), iii) that Linda's qualification criteria are protected, and iv) that the CRA does not learn from the protocols anything other than "Bob requested a loan from Linda". What distinguishes this work from the traditional two-party privacy-preserving framework is (i) the need for secure and privacy-preserving third-party verification of the accuracy of the inputs used, and (ii) the fact that the function being computed is private to the lender and should not be revealed to either the borrower or to the above-mentioned third-party verifier. Although we choose to present the techniques of this paper for the credit checking application domain, they have much broader applicability and in fact work for any situation where there is a repository of public and private information about individuals, that is subsequently used for making decisions that impact the individuals (a credit rating agency is but one example of such a repository).

We design a tree-based forward digest protocol (TFDP) to verify data integrity in distributed media streaming for content distribution. Several challenges arise, including the timing constraint of streaming sessions, the involvement of multiple senders, and the untrustworthiness of these senders. A comprehensive comparison is presented on the performance of existing protocols and TFDP, with respect to communication and computation overhead. Both simulation and Internet-based experimental results are presented to demonstrate the effectiveness of TFDP.

A novel method of rights protection for categorical data through watermarking is introduced in this paper. New watermark embedding channels are discovered and associated novel watermark encoding algorithms are proposed. While preserving data quality requirements, the introduced solution is designed to survive important attacks, such as subset selection and random alterations. Mark detection is fully "blind" in that it doesn't require the original data, an important characteristic, especially in the case of massive data. Various improvements and alternative encoding methods are proposed and validation experiments on real-life data are performed. Important theoretical bounds including mark vulnerability are analyzed. The method is proved (experimentally and by analysis) to be extremely resilient to both alteration and data loss attacks, for example, tolerating up to 80 percent data loss with a watermark alteration of only 25 percent.

We introduce wmdb.*, a solution for numeric relational data rights protection through watermarking. Rights protection for relational data is important in areas where sensitive, valuable content is to be outsourced. A good example is a data mining application, where data is sold in pieces to parties specialized in mining it. We show how various higher level semantic constraints such as classification preservation and maximum absolute change bounds are naturally handled and how random alteration attacks are well survived.

We present a method for a reliable detection of "unusual" sets of episodes in the form of many pattern sequences, scanned simultaneously for an occurrence as a subsequence in a large event stream within a window of size w. We also investigate the important special case of all permutations of the same sequence, which models the situation where the order of events in an episode does not matter, e.g., when events correspond to purchased market basket items. In order to build a reliable monitoring system, we compare obtained measurements to a reference model which in our case is a probabilistic model (Bernoulli or Markov). We first present a precise analysis that leads to a construction of a threshold. The difficulties of carrying out a probabilistic analysis for an arbitrary set of patterns, stems from the possible simultaneous occurrence of many members of the set as subsequences in the same window, the fact that the different patterns typically do have common symbols or common subsequences or possibly common prefixes, and that they may have different lengths. We also report on extensive experimental results, carried out on the Wal-Mart transactions database, that show a remarkable agreement with our theoretical analysis. This paper is an extension of our previous work where we laid out foundation for the problem of the reliable detection of an "unusual" episodes, but did not consider more than one episode scanned simultaneously for an occurrence.

When customers need to each be given portable access rights to a subset of documents from a large universe of n available documents, it is often the case that the space available for representing each customer's access rights is limited to much less than n, say it is no more than m bits. This is the case when, e.g., limited-capacity inexpensive cards are used to store the access rights to huge multimedia document databases. How does one represent subsets of a huge set of n elements, when only m bits are available and m is much smaller than n? We use an approach reminiscent of Bloom filters, by assigning to each document a subset of the m bits: If that document is in a customer's subset then we set the corresponding bits to 1 on the customer's card. This guarantees that each customer gets the documents he paid for, but it also gives him access to documents he did not pay for ("false positives"). We want to do so in a manner that minimizes the expected total false positives under various deterministic and probabilistic models: In the former model we assume k customers whose respective subsets are known a priori, whereas in the latter we assume (more realistically) that each document has a probability of being included in a customer's subset. We cannot use randomly assigned bits for each document (in the way Bloom filters do), rather we need to consider the a priori knowledge (deterministic or probabilistic) we are given in each model in order to better assign a subset of the m available bits to each of the n documents. We analyze and give e#cient schemes for this problem.

Abstract The formidable dissemination capability allowed by the current network technology makes it increasingly important to devise new methods to ensure authenticity and integrity. Nowadays it is common practice to distribute documents in compressed form. In this paper, we propose a simple variation on the classic LZ‐77 algorithm that allows one to hide, within the compressed document, enough information to warrant its authenticity and integrity. The design is based on the unpredictability of a certain class of pseudo‐random number generators, in such a way that the hidden data cannot be retrieved in a reasonable amount of time by an attacker (unless the secret bit‐string key is known). Since it can still be decompressed by the original LZ‐77 algorithm, the embedding is completely ‘transparent’ and backward‐compatible, making it possible to deploy it without disrupting service. Experiments show that the degradation in compression due to the embedding is almost negligible. Copyright © 2004 John Wiley & Sons, Ltd.

we introduce a solution for relational database content rights protection through watermarking. Rights protection for relational data is of ever-increasing interest, especially considering areas where sensitive, valuable content is to be outsourced. A good example is a data mining application, where data is sold in pieces to parties specialized in mining it. Different avenues are available, each with its own advantages and drawbacks. Enforcement by legal means is usually ineffective in preventing theft of copyrighted works, unless augmented by a digital counterpart, for example, watermarking. While being able to handle higher level semantic constraints, such as classification preservation, our solution also addresses important attacks, such as subset selection and random and linear data changes. We introduce wmdb., a proof-of-concept implementation and its application to real-life data, namely, in watermarking the outsourced Wal-Mart sales data that we have available at our institute.

Suppose one wants to detect "bad" or "suspicious" subsequences in event sequences. Whether an observed pattern of activity (in the form of a particular subsequence) is significant and should be a cause for alarm, depends on how likely it is to occur fortuitously. A long enough sequence of observed events will almost certainly contain any subsequence, and setting thresholds for alarm is an important issue in a monitoring system that seeks to avoid false alarms. Suppose a long sequence T of observed events contains a suspicious subsequence pattern S within it, where the suspicious subsequence S consists of m events and spans a window of size w within T. We address the fundamental problem: is a certain number of occurrences of a particular subsequence unlikely to be fortuitous (i.e., indicative of suspicious activity)? If the probability of fortuitous occurrences is high and an automated monitoring system flags it as suspicious anyway, then such a system will suffer from generating too many false alarms. We quantify the probability of such an S occurring in T within a window of size w, the number of distinct windows containing S as a subsequence, the expected number of such occurrences, its variance, and establishes its limiting distribution that allows to set up an alarm threshold so that the probability of false alarms is very small. We report on experiments confirming the theory and showing that we can detect bad subsequences with low false alarm rate.

The problem of efficient data structures for IP lookups has been well studied in literature. Techniques such as LC tries and extensible hashing are commonly used. In this paper, we address the problem of generalizing LC tries and extensible hashing, based on traces of past lookups, to provide performance guarantees for memory sub-optimal structures. As a specific example, if a memory-optimal (LC) trie takes 6 MB and the total memory at the router is 8 MB, how should the trie be modified to make best use of the 2 MB of excess memory? We present a greedy algorithm for this problem and prove that, if for the optimal data structure there are b fewer memory accesses on average for each lookup compared with the original trie, the solution produced by the greedy algorithm will have 9/spl times/b/22 fewer memory accesses on average (compared to the original trie). An efficient implementation of this algorithm presents significant additional challenges. We describe an implementation with a time complexity of O(/spl xi/(d)n /spl times/ log n) and a space complexity of O(n), where n is the number of nodes of the trie and d its depth. The depth of a trie is fixed for a given version of the Internet protocol and is typically O(log n). In this case, /spl xi/(d) = O(log/sup 2/ n). We demonstrate experimentally the performance and scalability of the algorithm on actual routing data. We also show that our algorithm significantly outperforms extensible hashing for the same amount of memory.

Protecting rights over relational data is of ever increasing interest, especially considering areas where sensitive, valuable content is to be outsourced. A good example is a data mining application, where data is sold in pieces to parties specialized in mining it.Different avenues for rights protection are available, each with its own advantages and drawbacks. Enforcement by legal means is usually ineffective in preventing theft of copyrighted works, unless augmented by a digital counter-part, for example watermarking.Recent research of the authors introduces the issue of digital watermarking for generic number sets. In the present paper we expand on this foundation and introduce a solution for relational database content rights protection through watermarking.Our solution addresses important attacks, such as data re-sorting, subset selection, linear data changes (applying a linear transformation on arbitrary subsets of the data). Our watermark also survives up to 50% and above data loss.Finally we present wmdb.*, a proof-of-concept implementation of our algorithm and its application to real life data, namely in watermarking the outsourced Wal-Mart sales data that we have available at our institute.

Dot-products form the basis of various applications ranging from scientific computations to commercial applications in data mining and transaction processing. Typical scientific computations utilizing sparse iterative solvers use repeated matrix-vector products. These can be viewed as dot-products of sparse vectors. In database applications, dot-products take the form of counting operations. With widespread use of clustered and distributed platforms, these operations are increasingly being performed across networked hosts. Traditional APIs for messaging are susceptible to sniffing, and the data being transferred between hosts is often enough to compromise the entire computation. Due to the large computational requirements of underlying applications, it is highly desirable that secure protocols add minimal overhead to the original algorithm. Finally, by its very nature, dot-products leak limited amounts of information - one of the parties can detect an entry of the other party's vector by simply probing it with a vector with a I in a particular location and zeros elsewhere. We present an extremely efficient and sufficiently secure protocol for computing the dot-product of two vectors using linear algebraic techniques. Using analytical as well as experimental results, we demonstrate superior performance in terms of computational overhead, numerical stability, and security. We show that the overhead of a two-party dot-product computation using MPI as the messaging API across two high-end workstations connected via a Gigabit ethernet approaches multiple 4.69 over an unsecured dot-product. We also show that the average relative error in dot-products across a large number of random (normalized) vectors was roughly 4.5 /spl times/ 10/sup -9/.

The growth of the Internet opens up tremendous opportunities for cooperative computation, where the answer depends on the private inputs of separate entities. Sometimes these computations may occur between mutually untrusting entities. The problem is trivial if the context allows the conduct of these computations by a trusted entity that would know the inputs from all the participants; however if the context disallows this then the techniques of secure multiparty computation become very relevant and can provide useful solutions. Statistical analysis is a widely used computation in real life, but the known methods usually require one to know the whole data set; little work has been conducted to investigate how statistical analysis could be performed in a cooperative environment, where the participants want to conduct statistical analysis on the joint data set, but each participant is concerned about the confidentiality of its own data. We have developed protocols for conducting the statistical analysis in such a cooperative environment based on a data perturbation technique and cryptography primitives.

The growth of the Internet has triggered tremendous opportunities for cooperative computation, in which multiple parties need to jointly conduct computation tasks based on the private inputs they each supply. These computations could occur between mutually untrusted parties, or even between competitors. For example, two competing financial organizations might jointly invest in a project that must satisfy both organizations ’ private and valuable constraints. Today, to conduct such a computation, one must usually know the inputs from all the participants; however if nobody can be trusted enough to know all the inputs, privacy will become a primary concern. Linear systems of equations problem and linear leastsquare problem problems are two important scientific computations that involve linear equations. Solutions to these problems are widely used in many areas such as banking, manufacturing, and telecommunications. However, the existing solutions do not extend to the privacy-preserving cooperative computation situation, in which the linear equations are shared by multiple parties, who do not want to disclose their data to the other parties. In this paper, we formally define these specific privacypreserving cooperative computation problems, and present protocols to solve them. 1

The growth of the Internet has triggered tremendous opportunities for cooperative computation, where people are jointly conducting computation tasks based on the private inputs they each supplies. These computations could occur between mutually untrusted parties, or even between competitors. For example, customers might send to a remote database queries that contain private information; two competing financial organizations might jointly invest in a project that must satisfy both organizations' private and valuable constraints, and so on. Today, to conduct such computations, one entity must usually know the inputs from all the participants; however if nobody can be trusted enough to know all the inputs, privacy will become a primary concern.This problem is referred to as Secure Multi-party Computation Problem (SMC) in the literature. Research in the SMC area has been focusing on only a limited set of specific SMC problems, while privacy concerned cooperative computations call for SMC studies in a variety of computation domains. Before we can study the problems, we need to identify and define the specific SMC problems for those computation domains. We have developed a framework to facilitate this problem-discovery task. Based on our framework, we have identified and defined a number of new SMC problems for a spectrum of computation domains. Those problems include privacy-preserving database query, privacy-preserving scientific computations, privacy-preserving intrusion detection, privacy-preserving statistical analysis, privacy-preserving geometric computations, and privacy-preserving data mining.The goal of this paper is not only to present our results, but also to serve as a guideline so other people can identify useful SMC problems in their own computation domains.

We give a Monte Carlo algorithm that computes an unbiased estimate of the convolution of two vectors. The variance of our estimate is small for entries of the convolution that are large; this corresponds to the situation in which convolution is used in pattern matching or template matching, where one is only interested in the largest entries of the resulting convolution vector. Experiments performed with our algorithm confirm the theory and suggest that, in contexts where one cares about only the large entries in the convolution, the algorithm can be a faster alternative to performing an FFT-based convolution.

Given an m/spl times/m image I and a smaller n/spl times/n image P, the computation of an (m-n+1)/spl times/(m-n+1) matrix C where C(i, j) is of the form C(i,j)=/spl Sigma//sub k=0//sup n-1//spl Sigma//sub k'=0//sup n-1/f(I(i+k,j+k'), P(k,k')), 0/spl les/i, j/spl les/m-n for some function f, is often used in template matching. Frequent choices for the function f are f(x,y)=(x-y)/sup 2/ and f(x,y)=|m-y|. For the case when f(x,y)=(x-y)/sup 2/, it is well known that C is computable in O(m/sup 2/ log n) time. For the case f(x,y)=|-y|, on the other hand, the brute force O((m-n+1)/sup 2/n/sup 2/) time algorithm for computing C seems to be the best known. This paper gives an asymptotically faster algorithm for computing C when f(x,y)=|x-y|, one that runs in time O(min{s,n//spl radic/log n}m/sup 2/ log n) time, where s is the size of the alphabet, i.e., the number of distinct symbols that appear in I and P. This is achieved by combining two algorithms, one of which runs in O(sm/sup 2/ log n) time, the other in O(m/sup 2/n/spl radic/log n) time. We also give a simple Monte Carlo algorithm that runs in O(m/sup 2/ log n) time and gives unbiased estimates of C.

This research paper explores a promising interface between natural language processing (NLP) and information assurance and security (IAS). More specificall~ it is devoted to possible applications to, and further dedicated development of, the accumulated considerable resources in NLP for, IAS. The expected and partially accomplished result is in harnessing the weird, illogical ways natural languages encode meaning, the very ways that defy all the usual combinatorial approaches to mathematical--and computational--complexity and make NLP so hard, to enhance information security. The paper is of a mixed theoretical and empirical nature. Of the four possible venues of applications, (i) memorizing randomly generated passwords with the help of automatically generated funny jingles, (ii) natural language watermarking, (iii) using the available machine translation (MT) systems for (additional) encryption of text messages, and (iv) downgrading, or sanitizing classified information in networks, two venues, (i) and (iv), have been at least partially implemented and the remaining two (ii) and (iii) are being implemented to the proof-of-concept level. We must make it very clear, however, that we have done very little experimentation or evaluation at this point, though we are moving quickly in that direction. The merits of the paper, if any, are in its venture to make considerable progress achieved recently in NLE especially in knowledge representation and meaning analysis, useful for IAS needs. The NLP approach adopted here, ontological semantics, has been developed by two of the coauthors; watermarking is based on the pioneering research by another coauthor and his associates; most of the implementation of the password memorization software has been done by the fourth coauthor. All the four of us have agonized whether we should report this research now or wait till we have fully implemented all or at least some of the systems we are developing. At the end of the day, we have reached a consensus that it is important, even at this early stage, to review for the information security community what NLP can do for it and to invite feedback and further efforts and ideas on what seems likely to become a new paradigm in information security. To the body of the paper, we Mikhail J. Atallah, Craig J. McDonough, Victor Raskin Center for Education and Research in Information Assurance and Security (CERIAS, www.cerias.purdue.edu) Purdue University W. Lafayette, IN 47907 mja, raskin, [email protected] Sergei Nirenburg Computing Research Laboratory, New Mexico State University Las Cruces, NM 88003 [email protected] have added two self-contained deliberately reference-free appendices on NLP and ontological semantics, respectively, primarily for the benefit of those IAS readers, who are interested in expanding their understanding of those fields and further exploring their possible fruitful interactions with IAS.

This guarantee is true for any number of dimensions. Subsequent to this work, Bhatia et al. [4] have proved that such a performance bound is essentially optimal for this kind of scheme, and have also extended our results to the case where the number of disks is a product of the form κ1 * κ2 * … * κt where the κts need not all be 2.

We propose a non-transform image compression scheme based on approximate 1D pattern matching, called pattern matching image compression (PMIC). The main idea behind it is a lossy extension of the Lempel-Ziv data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately occurs in the already processed image. This main algorithm is enhanced with several new features such as searching for reverse approximate matching, recognizing sub-strings in images that are additively shifted versions of each other, introducing a variable and adaptive maximum distortion level D, and so forth. These enhancements are crucial to the overall quality of our scheme and their efficient implementation leads to algorithmic issues of interest in their own right. Both algorithmic and experimental results are presented. Our scheme turns out to be competitive with JPEG and wavelet compression for good quality graphical images. We also review related theoretical results.

In a computer network that consists of M subnetworks, the L-bit address of a machine consists of two parts: A prefix s/sub i/ that contains the address of the subnetwork to which the machine belongs, and a suffix (of length L-Is/sub i/I) containing the address of that particular machine within its subnetwork. In fixed-length subnetwork addressing, Is/sub i/I is independent of I, whereas, in variable length subnetwork addressing, Is/sub i/I varies from one subnetwork to another. To avoid ambiguity when decoding addresses, there is a requirement that no s/sub i/ be a prefix of another s/sub i/. The practical problem is how to find a suitable set of s/sub i/s in order to maximize the total number of addressable machines, when the ith subnetwork contains n/sub i/ machines. Not all of the n/sub i/ machines of a subnetwork i need be addressable in a solution: If n/sub i/>2(L-|s/sub i/|), then only 2(L-|s/sub j/|) machines of that subnetwork are addressable (none is addressable s/sub i/ the solution assigns no address s/sub i/ to that subnetwork). The abstract problem implied by this formulation is: Given an integer L, and given M (not necessarily distinct) positive integers n/sub 1/,...,n/sub M/, find M binary strings s/sub 1/,...,s/sub M/ (some of which may be empty) such that (1) no nonempty string s/sub i/ is prefix of another string s/sub j/, (2) no s/sub i/ is more than L bits long, and (3) the quantity /spl Sigma/(|s/sub k/|/spl ne/0) min{n/sub k/,2(L-|s/sub k/|)} is maximized. We generalize the algorithm to the case where each n/sub i/ also has a priority p/sub i/ associated with it and there is an additional constraint involving priorities: Some subnetworks are then more important than others and are treated preferentially when assigning addresses. The algorithms can be used to solve the case when L itself is a variable; that is, when the input no longer specifies L but, rather, gives a target integer /spl gamma/ for the number of addressable machines, and the goal is to find the smallest L whose corresponding optimal solution results in at least /spl gamma/ addressable machines.

We propose a non-transform image compression scheme based on approximate pattern matching, that we name pattern matching linage compression (PMIC). The main idea behind it is a lossy extension of the Lempel-Ziv data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately occurs in the already processed image. We consider both the Hamming distance and the square error distortion. The theoretical basis for such a scheme was laid out by Luczak and Szpankowski [1994, 1995]. A straightforward implementation of the basic scheme described in Luczak and Szpankowski on real images (structured data) seems not to be attractive from a practical point of view. The main algorithm is therefore enhanced with several new features such as searching for reverse approximate matching, recognizing substrings in images that are additively shifted versions of each other, introducing a variable and adaptive maximum distortion level D, and so forth. These enhancements are crucial to the overall quality of our scheme.

We propose an image compression scheme based on approximate pattern matching, that we name pattern matching image compression (PMIC). We give new, efficient algorithms for performing computations motivated by this scheme, and describe the compression ratios experimentally obtained. The main idea is a lossy extension of the Lempel-Ziv (1977) data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately occurs in the already processed image. It is enhanced with several new features such as searching for reverse approximate matching, recognizing substrings in images that are additively shifted versions of each other, introducing a variable and adaptive maximum distortion level, and so forth. Our scheme is competitive with JPEG and wavelet compression for graphical and photographical images, and it is provably suboptimal under some probabilistic assumptions concerning an image.

We present parallel techniques on hypercubes for solving optimally a class of polygon problems. We thus obtain optimal O(log n) time, n-processor hypercube algorithms for the problems of computing the portions of an n-vertex simple polygonal chain C that are visible from a given source point, computing the convex hull of C, testing an n-vertex simple polygon P for monotonicity, and other related problems as well. Previously it was not known how to achieve these complexity bounds on hypercubes, one of the main difficulties being that there is no known optimal sorting hypercube algorithm that achieves these bounds. In fact these are the first optimal geometric hypercube algorithms that do not assume that the input is given already sorted by x or y coordinates. The hypercube model we use is the standard one, with O(1) local memory per processor, and with one port communication.>

We present a method for maintaining biased search trees so as to support fast finger updates (i.e., updates in which one is given a pointer to the part of the tree being changed). We illustrate the power of such biased finger trees by showing how they can be used to derive an optimal O(nlogn) algorithm for the 3-dimensional layers-of-maxima problem and also obtain an improved method for dynamic point location.

Given an off-line sequence S of n set-manipulation operations, we investigate the parallel complexity of evaluating S (i.e., finding the response to every operation in S and returning the resulting set). We show that the problem of evaluating S is in NC for various combinations of common set-manipulation operations. Once we establish membership in NC (or, if membership in NC is obvious), we develop techniques for improving the time and/or processor complexity.

A survey of techniques for solving geometric problems in parallel is given, both for shared memory parallel machines and for networks of processors. Parallel models are reviewed, and basic subproblems that tend to arise in the solution of geometric problems on any parallel model, are discussed. PRAM techniques, techniques for mesh-connected arrays of processors, and the hybrid RAM/ARRAY model and its connection to I/O complexity are considered. Open problems are also discussed, as well as directions for future research.>

The problem of using the idle cycles of a number of high-performance workstations, interconnected by a high-speed network, for solving computationally intensive tasks is discussed. The classes of distributed applications examined require some form of synchronization among the sub-tasks, hence the need for coscheduling to guarantee that sub-tasks start at the same time and execute at the same pace on a group of workstations. A model of the system that allows the definition of an objective function to be maximized is presented. Then a quadratic time and linear space algorithm is derived for computing the optimal coscheduling.>

Abstract We give two parallel algorithms for sequence comparison on the Connection Machine 2 (CM‐2). The specific comparison measure we compute is theedit distance: given a finite alphabet ∑ and two input sequencesXϵ ∑+andYϵ ∑+the edit distanced(X,Y)is the minimum cost of transformingXintoYvia a series of weighted insertions, deletions and substitutions of characters. The edit distance comparison measure is equivalent to or subsumes a broad range of well known sequence comparison measures. The CM‐2 is very fast at performing parallel prefix operations. Our contribution consists of casting the problem in terms of these operations. Our first algorithm computesd(X,Y)usingNprocessors andO(M S)time units, whereM= min(|X|,||Y|) + 1,N= max(|X|,|Y|) + 1 andSis the time required for a parallel prefix operation. The second algorithm computesd(X,Y)usingNMprocessors andO((logNlogM)(S+R)) time units, whereRis the time for a ‘router’ communication step—one in which each processor is able to read data, in parallel, from the memory of any other processor. Our algorithms can also be applied to several variants of the problem, such as subsequence comparisons, and one—many and many‐many comparisons on 'sequence databases'.

article Free Access Share on An optimal parallel algorithm for the visibility of a simple polygon from a point Authors: Mikhail J. Atallah Purdue Univ., West Lafayette, IN Purdue Univ., West Lafayette, INView Profile , Hubert Wagener Technische Univ., Berlin, Germany Technische Univ., Berlin, GermanyView Profile , Danny Z. Chen Purdue Univ., West Lafayette, IN Purdue Univ., West Lafayette, INView Profile Authors Info & Claims Journal of the ACMVolume 38Issue 3July 1991 pp 515–532https://doi.org/10.1145/116825.116827Published:01 July 1991Publication History 19citation554DownloadsMetricsTotal Citations19Total Downloads554Last 12 Months13Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let P be a simple rectilinear convex polygon of size O(n) inside which lie n pairwise disjoint rectangular rectilinear obstacles.We provide parallel techniques for computing rectilinear shortest paths that avoid the set of obstacles in P. Specifically, we compute descriptions of shortest paths in O(log' n) time, with O(n'/ log' n) processors in the CREW-PRAM model if source and destination are on the boundary of P, with O(n'/ log n) processors if the source is an obsta-

Article P-complete geometric problems Share on Authors: M. Atallah Dept. of Computer Sciences, Purdue Univ., W. Lafayette, IN Dept. of Computer Sciences, Purdue Univ., W. Lafayette, INView Profile , P. Callahan Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MDView Profile , M. Goodrich Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MDView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 317–326https://doi.org/10.1145/97444.97699Online:01 May 1990Publication History 3citation312DownloadsMetricsTotal Citations3Total Downloads312Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We show how to extend any tree-structured dictionary machine so that it can perform order statistics robustly. In particular, we consider how to allow for redundant insertions, deletions, and updates, as well as operations based on the ranks of data items, such as Extract (j), which simultaneously selects and deletes the jth smallest data item. All these operations can be performed without ever interrupting the pipelining of responses coming from the machine, and the resulting machine has the same interval time and latency time performance as the original design, to within constant factors.

The string editing problem for input strings x and y consists of transforming x into y by performing a series of weighted edit operations on x of overall minimum cost. An edit operation on x can be the deletion of a symbol from x, the insertion of a symbol in x or the substitution of a symbol of x with another symbol. This problem has a well-known $O(|x||y|)$ time-sequential solution. Efficient PRAM parallel algorithms for the string editing problem are given. If $m = \min (|x|,|y|)$ and $n = \max (|x|,|y|)$, then the CREW bound is $O(\log m \log n)$ time with $O({{mn} / {\log m}})$ processors. The CROW bound is $O(\log n(\log \log m)^{2})$ time with $O(mn/ \log \log m)$ processors. In all algorithms, space is $O(mn)$.

We present a parallel algorithm for computing the visible portion of a simple polygonal chain with n vertices from a point in the plane. The algorithm runs in Ο(log n) time using Ο(n/ log n) processors in the CREW-PRAM computational model, and hence is asymptomatically optimal.

There is a large and growing body of literature concerning the solution of geometric problems on mesh-connected arrays of processors [5,9,14,17]. Most of these algorithms are optimal (i.e., run in time Ο(n1/d) on a d-dimensional n-processor array), and they all assume that the parallel machine is trying to solve a problem of size n on an n-processor array. What happens when we have parallel machine for efficiently solving a problem of size p, and we are interested in using it to solve a problem of size n < p? The answer to that question has to do with a fundamental, and yet (at least so far) little-studied property of geometric problems: their parallel-decomposability. More specifically, given that a problem of size p can be solved on a parallel machine P faster by a factor of (say) s(p) than on a RAM alone, then that problem is fully parallel-decomposable for P if a RAM to which the parallel machine P is attached can solve arbitrarily large problems with a speedup of also s(p) when compared to a RAM alone. The issue has been settled for the sorting problem when P is a linear systolic array [1,2,3,11]. Here we show that many geometric problems are fully parallel-decomposable for (multidimensional) mesh-connected arrays of processors.

An O(log ~ n) time, n2/logn processor as well as an O(log n) time, n3/log n processor CREW deterministic parallel algorithms are presented for constructing Huffman codes from a given list of frequences.The time can be reduced to O(log n(loglog n) 2) on an CRCW model, using only n2/(log log n) 2 processors.Also presented is an optimal O(log n) time, O(n/log n) processor EREW parallel algorithm for constructing a tree given a list of leaf depths when the depths are monotonic.An O(log 2 n) time, n processor parallel algorithm is given for the general tree construction problem.We also give an O(log 2 n) time n2/log2n processor algorithm which finds a nearly optimal binary search tree.An O(log 2 n) time n 2'36 processor algorithm for recognizing linear context free languages is given.A crucial ingredient in achieving those bounds is a formulation of these problems as multiplications of special matrices which we call concave matrices.The structure of these matrices makes their parallel multiplication dramatically more efficient than that of arbitrary matrices.

Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems. The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location. Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point. All of the algorithms presented run in $O(\log n)$ time with either a linear or a sublinear number of processors in the CREW PRAM model.

Let G and H be two mesh-connected arrays of processors, where G = g 1 , X g 2 X … X g 1 , H = h 1 x h 2 x … x h d , and g 1 … g 1 ≤ h 1 … h d . The problem of simulating G by H is considered and the best possible simulation in terms of the g i 's and h i 's is characterized by giving such a simulation and proving its optimality in the worst-case sense. Also the same bound on the average cost of encoding the edges of G as distinct paths in H is established.

We give efficient solutions to transportation problems motivated by the following robotics problem. A robot arm has the task of rearranging m objects between n stations in the plane. Each object is initially at one of these n stations and needs to be moved to another station. The robot arm consists of a single link that rotates about a fixed pivot. The link can extend in and out (like a telescope) so that its length is a variable. At the end of this “telescoping” link lies a gripper that is capable of grasping any one of the m given objects (the gripper cannot be holding more than one object at the same time). The robot arm must transport each of the m objects to its destination and come back to where it started. Since the problem of scheduling the motion of the gripper so as to minimize the total distance traveled is NP-hard, we focus on the problem of minimizing only the total angular motion (rotation of the link about the pivot), or only the telescoping motion. We give algorithms for two different modes of operation; (i) No-drops. No object can be dropped before its destination is reached. (ii) With-drops. Any object can be dropped at any number of intermediate points. Our algorithm for case (i) runs in $O(m + n\log n)$ time for angular motion and in $O(m + n\alpha (n))$ time for telescoping motion. Our algorithm for case (ii) runs in $O(m + n)$ time for angular motion and with the same time bound for telescoping motion. The most interesting problem turns out to be that of minimizing angular motion for the with-drops mode of operation.

An investigation is conducted of the relationship between a rectangular mesh and a square one. Asymptotically optimal algorithms are given for simulating one type by the other. The simulation results are useful since they permit designing algorithms on one network (e.g. the square mesh) in spite of the fact that the actual machine on which these algorithms will run is different (e.g. a rectangular mesh).>

We present techniques for parallel divide-and-conquer, resulting in improved parallel algorithms for a number of problems. The problems for which we give improved algorithms include intersection detection, trapezoidal decomposition (hence, polygon triangulation), and planar point location (hence, Voronoi diagram construction). We also give efficient parallel algorithms for fractional cascading, 3-dimensional maxima, 2-set dominance counting, and visibility from a point. All of our algorithms run in O(log n) time with either a linear or sub-linear number of processors in the CREW PRAM model.

We present techniques which result in improved parallel algorithms for a number of problems whose efficient sequential algorithms use the plane-sweeping paradigm. The problems for which we give improved algorithms include intersection detection, trapezoidal decomposition, triangulation, and planar point location. Our technique can be used to improve on the previous time bound while keeping the space and processor bounds the same, or improve on the previous space bound while keeping the time and processor bounds the same. We also give efficient parallel algorithms for visibility from a point, 3-dimensional maxima, multiple range-counting, and rectilinear segment intersection counting. We never use the AKS sorting network in any of our algorithms.

Let G and H be two mesh-connected arrays of processors, where G=glxg':!.X· .. xg, • H=h(x.h2x· .. Md.. and g 1· .. gr~ I . hd. We consider the problem of simulating G by H. and we characterize in terms of the gi'S and h j ' s the best possible simulation by giving such a simulation and proving its optimality in the worst-case sense. We also establish the same bound on the average cost of encoding the edges of G as dis· tinCt paths in H .

In the channel routing problem, a problem arising in the design of layout systems, two rows of terminals which are opposite each other, have to be connected. We study what effect the rotation of one row of terminals has on the cost measures of the routing phase. The cost measures we consider are the density, which is proportional to the width of the channel, the crossing number, which is closely related to the number of crossings between two wires in the channel, and the length of nets, which is related to the wire length needed in the routing. We present algorithms for determining the rotations which minimize each of these cost measures. The algorithms can also be used for solving optimal offset problems.

In this paper we present techniques that result in O(√n) time algorithms for computing many properties and functions of an n-node forest stored in an √n × √n mesh of processors. Our algorithms include computing simple properties like the depth, the height, the number of descendents, the preorder (resp. postorder, inorder) number of every node, and a solution to the more complex problem of computing the Minimax value of a game tree. Our algorithms are asymptotically optimal since any nontrivial computation will require Ω (√n) time on the mesh. All of our algorithms generalize to higher dimensional meshes.

A straight line is an axis ofsymmetry of a planar figure if the figure is invariant to reflection with respect to that line. The purpose of this correspondence is to describe an O( n log n) time algorithm for enumerating all the axes of symmetry of a planar figure which is made up of (possibly intersecting) segments, circles, points, etc. The solution involves a reduction of the problem to a combinatorial question on words. Our algorithm is optimal since we can establish an Ω(n log n) time lower bound for this problem.

We show that a machine in which the processors are interconnected as a binary tree can support all the dictionary and priority queue operations as well as some other data queries. Every one of the operations takes O(log n) steps where n is the number of keys present. A sequence of operations can be pipe-lined at a constant rate. In previous designs, either an operation required Ω(log N) steps where N is the total capacity of the machine, i.e., the maximum number of keys that can be stored in it, or O(log n) performance was achieved at the expense of additional wires.

Algorithms that run in O(n) steps are given for solving a number of graph problems on an n x n array of processors.The problems considered include: finding the bridges and artiedation points of an undirected graph, findmg the length of a shortest cycle, finding a minimum spanning tree, and a number of other problems.

We consider problems in computational geometry when every one of the input points is moving in a prescribed manner. We present and analyze efficient algorithms for a number of problems and prove lower bounds for some of them.

We give O(n) step algorithms for solving a number of graph problems on an n×n array of processors. The problems considered include: marking the bridges of an undirected graph, marking the articulation points of such a graph, finding the length of a shortest cycle, finding a minimum spanning tree, and a number of other problems.

The cyclic index $\delta $ of an irreducible nonnegative square matrix is the number of eigenvalues of maximum modulus of that matrix. If $\delta = 1$, the matrix is said to be primitive. The notions of primitivity and cyclic index play an important role in the theory of nonnegative matrices. In the context of discrete Markov chains, the words “period” and “aperiodic” are sometimes used in place of “cyclic index” and “primitive”, respectively. It is known how to test an irreducible nonnegative square matrix for primitivity, but there is no known practical method for finding the cyclic index $\delta $ in the general case. This paper presents a time-optimal algorithm for finding $\delta $.