Mikhail J. Atallah

Security concerns are a substantial impediment to the wider deployment of cloud storage. There are two main concerns on the confidentiality of outsourced data: i) protecting the data, and ii) protecting the access pattern (i.e., which data is being accessed). To mitigate these concerns, schemes for Oblivious Storage (OS) have been proposed. In OS, the data owner outsources a key-value store to a cloud server, and then can later execute get, put, and remove queries, by collaboration with the server; furthermore, both the data and the access pattern are hidden from the server. In this paper, we extend the semantics of OS by proposing an oblivious index that supports nearest neighbor queries. That is, finding the nearest keys to the query in the key-value store. Our proposed index structure for supporting nearest-neighbor has similar performance bounds to previous OS schemes that did not support nearest-neighbor, in terms of client storage, server storage and rounds of communication

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

This paper develops and tests a privacy‐preserving business process that supports the selection of a contract manufacturer by an original equipment manufacturer (OEM), and the determination of whether the OEM or the chosen contract manufacturer will procure each of the components to be used in the manufacture of the OEM's branded product. Our “secure price‐masking (SPM)” technology contributes to procurement theory and practice in four significant ways: First, it preserves the privacy of every party's individual component prices. Second, SPM assures that the contract manufacturers will bid their own private purchase cost (i.e., not add a margin to their cost). Third, SPM is not invertible; i.e., none of the participants can “solve” for the private inputs of any other participant based on its own inputs and the outputs provided to it by SPM. Fourth, the posterior distribution of any other participant's private inputs is practically indistinguishable from its prior distribution. We also describe the results of a proof‐of‐concept implementation.

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 texts and avoiding transmission of the original source for stego objects. Because the inherent redundancy of natural language creates plenty of room for variation in translation, machine translation is ideal for steganographic applications. We describe the design and implementation of a scheme for hiding information in translated natural language text and present experimental results using the implemented system. While the initial work in this vein required the presence of both the source and the translation, the system detailed in this paper requires only the translated text for recovering the hidden message, increasing security and improving resource usage. These improvements occur not only because the source text is no longer available to the adversary, but also because a broader repertoire of defenses (such as mixing human and machine translation) can now be used.

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.

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