Search

The computation and communication costs of many secure multiparty protocols would benefit from a preprocessing that replaces large inputs with much smaller values without changing the outputs. This preprocessing is especially advantageous when its cost can be amortized over subsequent computations that all benefit from smaller inputs. The above holds for protocols based on garbled circuits, homomorphic encryption, or other techniques. Problems benefiting from such preprocessing include pattern matching, information retrieval, and sequence comparisons that depend on (in)equality of comparands. Motivated by this (in)equality-preservation requirement, we define the problem as follows: Alice’s and Bob’s inputs are their respective private sets S A and S B of large integers, and their private outputs are images of their sets under a function ρ that injectively maps S A ∪ S B into { 0 , 1 , … , N - 1 } for a small N ⩾ | S A | + | S B | . Alice’s (Bob’s) knowledge of this mapping on S A ( S B ) must reveal nothing about S B ( S A ). Thus, neither party should be able to learn ρ ( x ) for any x that is not in its private set; otherwise, s/he could exploit the small codomain of ρ to learn about the other party’s set. We formalize the problem, propose efficient and secure (semi-honest model) solutions to it, and discuss its use cases.

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.

Many secure protocols exist for the problem of determining occurrences of a pattern P as a substring of a text string T . That is, when Alice has T , and Bob has P , the protocol computes the answer(s) without revealing to Alice or Bob anything that cannot be deduced from the jointly computed answer. The existing protocols work for various adversarial models (some use the powerful malicious model), but they all have drawbacks that detract from practical deployment. For some, the drawback is their quadratic computation time (proportional to | T || P |), for others, it is their use of expensive cryptographic primitives such as homomorphic encryption; some have both drawbacks. Moreover, some restrict alphabet and input size to be bounded by a polynomial in a security parameter. This paper presents a scheme that overcomes these drawbacks in that it works for arbitrary alphabet and input sizes, has O ( | T | log | P | ) computational cost, does not use expensive cryptographic primitives, and has information-theoretic security (one-time pad). It can also handle single-character wildcards (symbols that match any alphabet symbol). These improvements come at the cost of using a weaker adversarial model than the malicious one (the semi-honest), and an offline helper (e.g., cloud server) that computes and provides Alice and Bob with randoms that they can subsequently use in protocols. We implemented our scheme, that we call LiLiP ( Li ghtweight, Li nearithmic & P rivate), and it performs very well in practice.

We propose a method for ensuring traceability of metal goods in an efficient and secure manner that leverages data obtained from micrographs of a part’s surface that is instance specific (i.e., different for another instance of that same part). All stakeholders in modern supply chains face a growing need to ensure quality and trust in the goods they produce. Complex supply chains open many opportunities for counterfeiters, saboteurs, or other attackers to infiltrate supply networks, and existing methods for preventing such attacks can be costly, invasive, and ineffective. The proposed method extracts discriminatory-yet-robust intrinsic strings using features extracted from the two-point autocorrelation data of surface microstructures, as well as from local volume fraction data. By using a synthetic dataset of three-phase micrographs similar to those obtained from metal alloy systems using low-cost optical microscopy techniques, we discuss tailoring the method with respect to cost and security and discuss the performance of the method in the context of anticounterfeiting and how similar methods may be evaluated for performance. Cryptographic extensions of this methodology are also discussed.

Designers need a way to overcome information-related risks, including information leakage and misuse by their own collaborators during collaborative product realization. Existing cryptographic techniques aimed at overcoming these information-related risks are computationally expensive and impractical even for moderate problem sizes, and legal approaches such as nondisclosure agreements are not effective. The computational practicality problem is particularly pronounced for computational techniques, such as the finite element analysis (FEA). In this paper, we propose a technique that enables designers to perform simulations, such as FEA computations, without the need for revealing their information to anyone, including their design collaborators. We present a new approach, the secure finite element analysis approach, which enables designers to perform FEA without having to reveal structural/material information to their counterparts even though the computed answer depends on all the collaborators' confidential information. We build secure finite element analysis (sFEA) using computationally efficient protocols implementing a secure codesign (SCD) framework. One of our findings is that the direct implementation of using SCD framework (termed as naïve sFEA) suffers from lack of scalability. To overcome these limitations, we propose hybrid sFEA that implements performance improvement strategies. We document and discuss the experiments we conducted to determine the computational overhead imposed by both naïve and hybrid sFEA. The results indicate that the computational burden imposed by hybrid sFEA makes it challenging for large-scale FEA—our scheme significantly increases the problem sizes that can be handled when compared to implementations using previous algorithms and protocols, but large enough problem sizes will swamp our scheme as well (in some sense this is unavoidable because of the cubic nature of the FEA time complexity).

In this work, we present a simple, yet effective and practical scheme to improve the security of stored password hashes, increasing the difficulty to crack passwords and exposing cracking attempts. We utilize a hardware-dependent function (HDF), such as a physically unclonable function (PUF) or a hardware security module (HSM), at the authentication server to inhibit offline password discovery. Additionally, a deception mechanism is incorporated to alert administrators of cracking attempts. Using an HDF to generate password hashes hinders attackers from recovering the true passwords without constant access to the HDF. Our scheme can integrate with legacy systems without needing additional servers, changing the structure of the hashed password file, nor modifying client machines. When using our scheme, the structure of the hashed passwords file, e.g., etc/shadow or etc/master.passwd , will appear no different than traditional hashed password files. 1 However, when attackers exfiltrate the hashed password file and attempt to crack it, the passwords they will receive are ErsatzPasswords—“fake passwords.” The ErsatzPasswords scheme is flexible by design, enabling it to be integrated into existing authentication systems without changes to user experience. The proposed scheme is integrated into the pam_unix module as well as two client/server authentication schemes: Lightweight Directory Access Protocol (LDAP) authentication and the Pythia pseudorandom function (PRF) Service [Everspaugh et al. 2015]. The core library to support ErsatzPasswords written in C and Python consists of 255 and 103 lines of code, respectively. The integration of ErsatzPasswords into each explored authentication system required less than 100 lines of additional code. Experimental evaluation of ErsatzPasswords shows an increase in authentication latency on the order of 100ms, which maybe acceptable for real world systems. We also describe a framework for implementing ErsatzPasswords using a Trusted Platform Module (TPM).

Designers need a way to overcome information related risks, including information leakage and misuse from their own collaborators during a collaborative product realization process. Existing cryptographic techniques aimed at overcoming these information related risks are computationally expensive and slow even for moderate problem sizes, and legal approaches (e.g., the use of non-disclosure agreements) are not effective. The computational practicality problem is particularly pronounced for simulation computations like finite element analysis (FEA), that involve both a geometric partitioning (meshing) and computations of cubic time complexity. In this paper, we propose a technological approach that enables designers to perform simulations, such as FEA computations, without the need for revealing their information to anyone, including their design collaborators. We demonstrate our approach using secure finite element analysis (sFEA) which enables designers to perform FEA without having to reveal structural/material information to their counterparts even though the computed answer depends on all the collaborators’ confidential information. We build sFEA using computationally efficient protocols implementing a secure co-design framework. One of our findings is that the most natural implementations of sFEA, using existing protocols, suffer from limited scalability. To overcome these limitations, we propose strategies that help improve the scalability of sFEA. We document and discuss the experiments we conducted to determine the computational overhead imposed by sFEA. The results indicate that the computational burden imposed by sFEA makes it challenging for large-scale FEA — our scheme significantly increases the problem sizes that can be handled when compared to implementations using previous algorithms and protocols, but large enough problem sizes will swamp our scheme as well (in some sense this is unavoidable because of the cubic nature of the FEA time complexity). This work is another step towards opening up new avenues for improving the way information is exchanged in collaborative simulation computations such as FEA.

In the context of globalized supply chains, counterfeiting of manufactured goods is a growing problem. The financial, legal, and reputational costs that counterfeit goods impose on legitimate enterprises have spurred investigation into efficient and robust anti-counterfeiting methodologies. In particular, physically unclonable functions (PUFs) have been applied effectively in several manufacturing areas, especially electronics. However, anti-counterfeiting solutions for generic manufactured goods are often expensive to make and implement, or not robust to minor damage that the goods may sustain during transport and use. In this paper, a framework for developing robust, efficient, and cost-effective optical PUFs for anti-counterfeiting of manufactured metallic goods is proposed, along with an example implementation for 4140-steel parts according to standard ASTM A29. For an input library of 50 steel micrographs, the proposed example PUF is shown to have good robustness to simulated part damage and an estimated classification error rate of less than 1%.

Developments in digital technology and manufacturing processes have expanded the horizon of designer innovation in creating products. In addition to this, real-time collaborative platforms help designers shorten the product development cycle by enabling collaborations with domain experts from concept generation to product realization and after-market. These collaborations are extending beyond enterprise and national boundaries, contributing to a growing concern among designers regarding the security of their sensitive information such as intellectual property (IP) and trade secrets. The source of such sensitive information leaks could be external (e.g., hacker) or internal (e.g., disgruntled employee) to the collaboration. From a designer's perspective, this fear can inhibit participation in a collaboration even though it might result in better products or services. In this paper, we aim to contextualize this evolving security space by discussing various security practices in digital domains, such as encryption and secret sharing, as well as manufacturing domains, such as physically unclonable function (PUF) and physical part watermarking for anticounterfeiting and tamper evidence purposes. Further, we classify these practices with respect to their performance against different adversarial models for different stages in product development. Such a classification can help designers to make informed decisions regarding security practices during the product realization process.

Information leakage can lead to loss of intellectual property and competitive edge. One of the primary sources of information leakage in collaborative design is sharing confidential information with collaborators, who may be also collaborating with competitors. Hiding information from collaborators is challenging in codesign because it can lead to inferior and suboptimal solutions. Therefore, there is a need for techniques that enable designers to protect confidential information from their collaborators while achieving solutions that are as good as those obtained when full information is shared. To address this need, we propose a secure codesign (SCD) framework that enables designers to achieve optimal solutions without sharing confidential information. It is built on two principles: adding/multiplying a parameter with a large random number hides the value of the parameter, and adding/multiplying a large number is orders of magnitude faster than using existing cryptographic techniques. Building on the protocols for basic arithmetic computations, developed in our earlier work, we establish protocols for higher order computations involved in design problems. The framework is demonstrated using three codesign scenarios: requirements-driven codesign, objective-driven codesign, and Nash noncooperation. We show that the proposed SCD framework enables designers to achieve optimal solutions in all three scenarios. The proposed framework is orders of magnitude faster than competing (but impractical for engineering design) cryptographic methods such as homomorphic encryption, without compromising on precision in computations. Hence, the proposed SCD framework is a practical approach for maintaining confidentiality of information during codesign.

The SQL group-by operator plays an important role in summarizing and aggregating large datasets in a data analytic 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 materialize this approximate semantics, they primarily focus on one-dimensional attributes and treat multidimensional attributes independently. However, correlated attributes, such as in spatial data, are processed independently, and hence, groups in the multidimensional space are not detected properly. To address this problem, we introduce two new SGB operators for multidimensional 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. 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., submit to TKDE

Most research today in electronic communications focuses on developing new technologies and “best practices” to enhance security and privacy. However, these technologies and best-practice codes are all too often not used, and in this failure the users are often their own worst enemies. It is thus important to develop an enhanced understanding of why users indicate concern about security and privacy, but when given the opportunity act contrary to their stated intention. We collect data from 435 participants about 24 electronic activities with a survey and a mixed effects model. We find a significant inverse relationship between their assessed risk and benefit (recognizing that the particular technology matters where some technologies are inherently perceived as more risky than others). This significant inverse relationship represents a departure from decision theories that assume purely cognitive information processing, and the separation of the probabilities and the utilities. We shed light on the role of affect, which commonly competes with cognition, and works as an orienting mechanism in security and privacy behaviors, and discuss business and policy implications of our findings.

The goal in this paper is to enable collaboration in the codesign of engineering artifacts when participants are reluctant to share their design-related confidential and proprietary information with other codesigners, even though such information is needed to analyze and validate the overall design. We demonstrate the viability of codesign by multiple entities who view the parameters of their contributions to the joint design to be confidential. In addition to satisfying this confidentiality requirement, an online codesign process must result in a design that is of the same quality as if full sharing of information had taken place between the codesigners. We present online codesign protocols that satisfy both requirements and demonstrate their practicality using a simple example of codesign of an automotive suspension system and the tires. Our protocols do not use any cryptographic primitives—they only use the kinds of mathematical operations that are currently used in single-designer situations. The participants in the online design protocols include the codesigners, and a cloud server that facilitates the process while learning nothing about the participants' confidential information or about the characteristics of the codesigned system. The only assumption made about this cloud server is that it does not collude with some participants against other participants. We do not assume that the server does not, on its own, attempt to compute as much information as it can about the confidential inputs and outputs of the codesign process: It can make a transcript of the protocol and later attempt to infer all possible information from it, so it is a feature of our protocols the cloud server can infer nothing from such a transcript.

Erratum to: M.J. Atallah and N. Hopper (Eds.) Privacy Enhancing Technologies DOI: 10.1007/978-3-642-14527-8

Record linkage is used to associate entities from multiple data sources. For example, two organizations contemplating a merger may want to know how common their customer bases are so that they may better assess the benefits of the merger. Another example is a database of people who are forbidden from a certain activity by regulators, may need to be compared to a list of people engaged in that activity. The autonomous entities who wish to carry out the record matching computation are often reluctant to fully share their data; they fear losing control over its subsequent dissemination and usage, or they want to insure privacy because the data is proprietary or confidential, and/or they are cautious simply because privacy laws forbid its disclosure or regulate the form of that disclosure. In such cases, 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 (1) our techniques make no use of a third party, and (2) they achieve much better performance than previous schemes in terms of their execution time while maintaining acceptable quality of output compared to nonprivacy settings. Our protocol consists of two phases. The first phase primarily produces candidate record pairs for matching, by carrying out a very fast (but not accurate) matching between such pairs of records. The second phase is a novel protocol for efficiently computing distances between each candidate pair (without any expensive cryptographic operations such as modular exponentiations). Our experimental evaluation of our approach validates these claims.

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.

D computer graphics models and digitally-controlled manufacturing have come together to enable the design, visualiza- tion, 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 coun- terfeit 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 genuini- ty of the object. The signature is detectable by a signature-reading device, based on methods in computer graphics and com- puter 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 proto- type of our scheme end-to-end, including the production of the physical object and the genuinity-testing device. Categories and Subject Descriptors (according to ACM CCS): I.3 (Computer Graphics), I.3.3 (Picture/Image Gen- eration), I.3.7 (Three-dimensional Graphics and Realism), I.4.1 (Digitization and Image Capture).

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 handledlocallyin 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 asO(log*n) for ann-node hierarchy. For more general access hierarchies of dimensiond, we use a technique that consists of adding dummy nodes and dimension reduction. The key derivation work for such graphs is then linear indand the increase in the number of edges is by the factorO(logd − 1n) 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.

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.

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.

We adress in this paper the security issues that arise when outsourcing business processes in the BPaaS (Business Process as a Service). In particular when sharing and reusing process fragments coming from different organizations for faster and easier development of process-based applications (PBA). The goal is twofold, to preserve the process fragment provenance, i.e., the companies's business activities which provide the reused fragments in order to avoid the competition, and to guarantee the end-to-end availability of PBA to fragment's consumers. We formally define the problem, and offer an efficient anonymization-based protocol. Experiments have been conducted to show the effectiveness of the proposed solution. We address the security issues that arise when outsourcing business processes in the cloud as BPaaS (Business Process as a Service).We formally define the concept of sharing and reusing process fragments for faster and easier development of process-based applications.We provide an efficient anonymization-based protocol to preserve the process fragment provenance, and to guarantee the end-to-end availability of process-based applications.We evaluate the performance of the proposed approach on real datasets.

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

Reconstructing the sequence of computer events that led to a particular event is an essential part of the digital investigation process. The ability to quantify the accuracy of automatic event reconstruction systems is an essential step in standardizing the digital investigation process thereby making it resilient to tactics such as the Trojan horse defense. In this paper, we present findings from an empirical study to measure and compare the accuracy and effectiveness of a suite of such event reconstruction techniques. We quantify (as applicable) the rates of false positives and false negatives, and scalability in terms of both computational burden and memory-usage. Some of our findings are quite surprising in the sense of not matching a priori expectations, and whereas other findings qualitatively match the a priori expectations they were never before quantitatively put to the test to determine the boundaries of their applicability. For example, our results show that automatic event reconstruction systems proposed in literature have very high false-positive rates (up to 96%).

We explore the problem of portable and flexible privacy preserving access rights that permit access to a large collection of digital goods. 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 a customer to choose a subset of items or groups of items from the repository, obtain access to and 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 such as smartcards or sensors, and therefore the rights must be enforced using the limited resources available. In this paper, we present and compare two schemes that address the problem of such access rights. We show that much can be achieved if one allows for even a negligible amount of false positives – items that were not requested by the customer, but inadvertently were included in the customer access right representation due to constrained space resources. But minimizing false positives is one of many other desiderata that include protection against sharing of false positives information by unscrupulous users, providing the users with transaction untraceability and unlinkability, and forward compatibility of the scheme. Our first scheme does not place any constraints on the amount of space available on the limited-capacity storage device, and searches for the best representation that meets the requirements. The second scheme, on the other hand, has (modest) requirements on the storage space available, but guarantees a low rate of false positives: with O(mc) storage space available on the smartcard (where m is the number of items or groups of items included in the subscription and c is a selectable parameter), it achieves a rate of false positives of m −c .

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.

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.

Internet computing technologies, like grid computing, enable a weak computational device connected to such a grid to be less limited by its inadequate local computational, storage, and bandwidth resources. However, such a weak computational device (PDA, smartcard, sensor, etc.) often cannot avail itself of the abundant resources available on the network because its data are sensitive. This motivates the design of techniques for computational outsourcing in a privacy-preserving manner, i.e., without revealing to the remote agents whose computational power is being used either one’s data or the outcome of the computation. This paper investigates such secure outsourcing for widely applicable sequence comparison problems and gives an efficient protocol for a customer to securely outsource sequence comparisons to two remote agents. The local computations done by the customer are linear in the size of the sequences, and the computational cost and amount of communication done by the external agents are close to the time complexity of the best known algorithm for solving the problem on a single machine.

The use of deception to enhance security has shown promising results as a defensive technique. In this paper we present an authentication scheme that better protects users’ passwords than in currently deployed password-based schemes, without taxing the users’ memory or damaging the user-friendliness of the login process. Our scheme maintains comparability with traditional password-based authentication, without any additional storage requirements, giving service providers the ability to selectively enroll users and fall-back to traditional methods if needed. The scheme utilizes the ubiquity of smartphones; however, unlike previous proposals it does not require registration or connectivity of the phones used. In addition, no long-term secrets are stored in any user’s phone, mitigating the consequences of losing it. Our design significantly increases the difficulty of launching a phishing attack by automating the decisions of whether a website should be trusted and introducing additional risk at the adversary side of being detected and deceived. In addition, the scheme is resilient against Man-in-the-Browser (MitB) attacks and compromised client machines. We also introduce a covert communication mechanism between the user’s client and the service provider. This can be used to covertly and securely communicate the user’s context that comes with the use of this mechanism. The scheme also incorporates the use of deception that makes it possible to dismantle a large-scale attack infrastructure before it succeeds. As an added feature, the scheme gives service providers the ability to have full-transaction authentication.

The goal in this paper is to enable collaboration in the co-design of engineering artifacts when participants are reluctant to share their design-related confidential and proprietary information with other co-designers, even though such information is needed to analyze and validate the overall design. We demonstrate the practicality of co-design by multiple entities who view the parameters of their contributions to the joint design to be confidential. In addition to satisfying this confidentiality requirement, an online co-design process must result in a design that is of the same quality as if full sharing of information had taken place between the co-designers. We present online co-design protocols that satisfy both requirements, and demonstrate their practicality using a simple example of co-design of an automotive suspension system and the tires. Our protocols do not use any cryptographic primitives — they only use the kinds of mathematical operations that are currently used in single-designer situations. The participants in the online design protocols include the co-designers, and a cloud server that facilitates the process while learning nothing about the participants’ confidential information or about the characteristics of the co-designed system. The only assumption made about this cloud server is that it does not collude with some participants against other participants. We do not assume that the server does not, on its own, attempt to compute as much information as it can about the confidential inputs and outputs of the co-design process: It can make a transcript of the protocol and later attempt to infer all possible information from it, so it is a feature of our protocols the cloud server can infer nothing from such a transcript.

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.

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.

Techniques were developed that make it possible to use remote servers without having to reveal to them either (i) the confidential inputs and outputs of computations; or (in the case of information storage and retrieval) the confidential data and queries thereupon. The techniques also make cheating by the remote untrusted servers detectable; here cheating mean s not carrying out the expected computational and storage duties. Significant progress was also made in the direction of hiding from the remote servers the access patterns to the encrypted data that they store, a potentially important consideration in situations where it is not enough to hide the data (e.g., when the access patterns reveal too much about the nature of how the data is being used). The progress in this area brings closer the day when remote cloud servers can be used for the most confidential tasks, without worry about confidentiality being compromised by security breaches occurring at the cloud service providers.

There has been much recent work on secure storage outsourcing, where an organization wants to store its data at untrusted remote cloud servers in an encrypted form, such that its own employees can query the encrypted data using weak devices (both computationally and storage-wise). Or a weak client wants to outsource an expensive computational task without revealing to the servers either the inputs or the computed outputs. The framework requires that the bulk of the computational burden of query-processing be placed on the remote servers, without revealing to these servers anything about the data. Most of the existing work in this area deals with non-image data that is keyword based, and the present paper is to deal with raw image data (without any keyword annotations). We demonstrate that shape-based image feature extraction, a particularly computationally intensive task, can be carried out within this framework, by presenting two schemes for doing so, and demonstrating their viability by experimentally evaluating them. Our results can be used in a number of practical situations. In one scenario the client has images and wants to securely outsource shape-based feature extraction on them, in another the server has encrypted images and the client wants a feature-extracted representation of those that are feature-rich.

This paper argues the need for providing a covert back-channel communication mechanism in authentication protocols, discusses various practical uses for such a channel, and desirable features for its design and deployment. Such a mechanism would leverage the current authentication channel to carry out the covert communication rather than introducing a separate one. The communication would need to be oblivious to an adversary observing it, possibly as a man-in-the-middle. We discuss the properties that such channels would need to have for the various scenarios in which they would be used. Also, we show their potential for mitigating the effects of a number of security breaches currently occurring in these scenarios.

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

This article presents a new algorithm for finding oligonucleotide signatures that are specific and sensitive for organisms or groups of organisms in large-scale sequence datasets. We assume that the organisms have been organized in a hierarchy, for example, a phylogenetic tree. The resulting signatures, binding sites for primers and probes, match the maximum possible number of organisms in the target group while having at most k matches outside of the target group. The key step in the algorithm is the use of the lowest common ancestor (LCA) to search the organism hierarchy; this allows the combinatorial problem in almost linear time (empirically observed) to be solved. The presented algorithm improves performance by several orders of magnitude in terms of both memory consumption and runtime when compared to the best-known previous algorithms while giving identical, exact solutions. This article gives a formal description of the algorithm, discusses details of our concrete, publicly available implementation, and presents the results from our performance evaluation.

International audience; 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.

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.

We treat the problem of secure outsourcing of sequence comparisons by a client to remote servers, which given two strings λ and μ of respective lengths n and m, consists of finding a minimum-cost sequence of insertions, deletions, and substitutions (also called an edit script) that transform λ into μ. In our setting a client owns λ and μ and outsources the computation to two servers without revealing to them information about either the input strings or the output sequence. Our solution is non-interactive for the client (who only sends information about the inputs and receives the output) and the client’s work is linear in its input/output. The servers’ performance is O(σmn) computation (which is optimal) and communication, where σ is the alphabet size, and the solution is designed to work when the servers have only O(σ(m + n)) memory. By utilizing garbled circuit evaluation in a novel way, we completely avoid public-key cryptography, which makes our solution particularly efficient.

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.

One of the challenges for parallel compilers and compiler-related tools is, given a machine-independent parallel language, to generate executable code for a variety of computational models, and to identify those specific parallel modes for which a program is well-suited. One portion of this problem, developing a method for estimating the relative execution time of a data-parallel algorithm in an environment capable of the SIMD and SPMD (MIMD) modes of parallelism, is presented. Given a data-parallel program in a language whose syntax is mode-independent and empirical information about instruction execution time characteristics, the goal is to use static source-code analysis to determine an implementation that results in an optimal execution time for a mixed-mode machine capable of SIMD and SPMD parallelism. Statistical information about individual operation execution times and paths of execution through a parallel program is assumed. A secondary goal of this study is to indicate language, algorithm, and machine characteristics that must be researched to learn how to provide the information needed to obtain an optimal assignment of parallel modes to program segments.

The multisearch problem is defined as follows. Given a data structure D modeled as a graph with n constant-degree nodes, perform O(n) searches on D. Let r be the length of the longest search path associated with a search process, and assume that the paths are determined "on-line." That is, the search paths may overlap arbitrarily. In this paper, we solve the multisearch problem for certain classes of graphs in O([formula] + r ([formula]/log n)) time on a [formula] × [formula]n mesh-connected computer. For many data structures, the search path traversed when answering one search query has length r = O(log n). For these cases, our algorithm processes O(n) such queries in asymptotically optimal Θ([formula]) time. The classes of graphs we consider contain many of the important data structures that arise in practice, ranging from simple trees to Kirkpatrick hierarchical search DAGs. Multisearch is a useful abstraction that can be used to implement parallel versions of standard sequential data structures on a mesh. As example applications, we consider a variety of parallel on-line tree traversals, as well as hierarchical representations of polyhedra and its myriad of applications (line-polyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and three-dimensional convex hull).

In the third-party model for the distribution of data, the data owner provides a third party (referred to as the dealer) with data as well as integrity verification information for that data, in the form of digital signatures that the dealer can use to convince a user of the data's integrity (the dealer is not trusted with the owner's signature keys, which is why it receives pre-signed items). The user's interactions are with the dealer, who is in charge of enforcing access control and confidentiality for the data (i.e., no user should learn more than the outcome of their authorized query). This kind of outsourcing is becoming increasingly important because of its advantageous economics - a dealer who acts as a repository for many owners can achieve economies of scale that are not feasible for the individual owners, and the model allows the data owners to focus on what they do best (the creation and/or acquisition of high-quality data). A problem that arises in the context of outsourced databases (particularly for XML data) is the following: There is a total order Π on n items stored with the dealer, and a user query consists of a pair of items whose relative ordering should be revealed along with a proof that the result is correct. The proof is generated using the dealer's local data (i.e., without bothering the data owner). The main difficulty is achieving efficient storage and query-processing while achieving the desiderata (that the user should learn nothing other than the answer to their query, and that a misbehaving dealer should not be able to convince a user of a wrong ordering). This paper gives a solution that is provably secure under a new assumption and can efficiently generate a very short proof. Furthermore, this scheme is generalized to partial orders that can be decomposed into d total orders. In this case, a user either learns the ordering of the queried items, or learns that they are incomparable.

We give an improved parallel algorithm for the problem of computing the tube minima of a totally monotonen ×n ×n matrix, an important matrix searching problem that was formalized by Aggarwal and Park and has many applications. Our algorithm runs inO(log logn) time withO(n2/log logn) processors in theCRCW-PRAM model, whereas the previous best ran inO((log logn)2) time withO(n2/(log logn)2 processors, also in theCRCW-PRAM model. Thus we improve the speed without any deterioration in thetime ×processors product. Our improved bound immediately translates into improvedCRCW-PRAM bounds for the numerous applications of this problem, including string editing, construction of Huffmann codes and other coding trees, and many other combinatorial and geometric problems.

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.

Significant research efforts have recently been dedicated to modeling and querying uncertain data. In this paper, we focus on skyline analysis of uncertain data, modeled as uncertain objects with probability distributions over a set of possible values called instances. Computing the exact skyline probabilities of instances is expensive, and unnecessary when the user is only interested in instances with skyline probabilities over a certain threshold. We propose two filtering schemes for this case: a preliminary scheme that bounds an instance's skyline probability for filtering, and an elaborate scheme that uses an instance's bounds to filter other instances based on the dominance relationship. We experimentally demonstrate the effectiveness of our filtering schemes on both real and synthetic data sets and show the efficiency of our schemes compared with other algorithms.

The talk will review recent results and algorithmic challenges for computational geometry problems in the context of uncertain data. This is an active area of investigation in the database community, and we introduce it through the specifics of the maximal elements problem (called the skyline problem in the database community): Rather than being a point, an uncertain object is a set of points called instances, each with an associated probability; instances of the same uncertain object can be geometrically far from each other, and are mutually exclusive (i.e., at most one of them can occur). For this version of the maximal elements problem, the input is a collection of m uncertain objects, whose total number of instances is n, and the problem is to compute for each of these n instances the probability that it is a maximal point, i.e., that it occurs for its own object and is not dominated by any occurring instance from another object.

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 subtasks, hence the need for coscheduling to guarantee that subtasks start at the same time and execute at the same pace on a group of workstations. A model of the system is presented that allows the definition of an objective function to be maximized. Then a quadratic time and linear space algorithm is derived for computing the optimal coschedule, for the given model and class of applications addressed.