Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but problem as a whole has not received theoretical treatment it deserves. In this paper, we provide software protection. We reduce to efficient simulation on oblivious RAM. A machine if thhe sequence in which accesses memory locations equivalent any two inputs with same running time. For example, an Turing Machine movement heads tapes identical...

We provide formal definitions and efficient secure techniques for turning noisy information into keys usable any cryptographic application, and, in particular, reliably securely authenticating biometric data. Our apply not just to information, but keying material that, unlike traditional keys, is (1) reproducible precisely (2) distributed uniformly. propose two primitives: a fuzzy extractor extracts nearly uniform randomness R from its input; the extraction error-tolerant sense that will be...

Searchable symmetric encryption (SSE) allows a party to outsource the storage of its data another (a server) in private manner, while maintaining ability selectively search over it. This problem has been focus active research recent years. In this paper we show two solutions SSE that simultaneously enjoy following properties:

We construct an Attribute-Based Encryption (ABE) scheme that allows a user's private key to be expressed in terms of any access formula over attributes. Previous ABE schemes were limited expressing only monotonic structures. provide proof security for our based on the Decisional Bilinear Diffie-Hellman (BDH) assumption. Furthermore, performance new compares favorably with existing, less-expressive schemes.

We establish the following, quite unexpected, result: replication of data for computational private information retrieval problem is not necessary. More specifically, based on quadratic residuosity assumption, we present a single database, computationally scheme with O(n/sup /spl epsiv//) communication complexity any epsiv/>0.

Searchable symmetric encryption (SSE) allows a party to outsource the storage of his data another in private manner, while maintaining ability selectively search over it. This problem has been focus active research and severa

We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number corrupted participants. That is, we consider network with open communication and an adversary that can adaptively corrupt as many parties it wishes. In this setting, our protocols allow subset (with pairs being special case) desired their local inputs, be guaranteed security is preserved activity rest network. This implies under concurrent composition unbounded protocol...

Article Free Access Share on How to withstand mobile virus attacks (extended abstract) Authors: Rafail Ostrovsky MIT Laboratory for Computer Science, 545 Technology Sq., Cambridge MA MAView Profile , Moti Yung IBM Research, T.J, Watson Center, Yorktown, NY NYView Authors Info & Claims PODC '91: Proceedings of the tenth annual ACM symposium Principles distributed computingJuly 1991 Pages 51–59https://doi.org/10.1145/112600.112605Online:01 July 1991Publication History...

We present a general construction of zero-knowledge proof for an NP relation R(x,w) which only makes black-box use secure protocol related multi-partyfunctionality f. The latter is required to be against small number "honest but curious" players. As application, we can translate previous results on the efficiency multiparty computation domain zero-knowledge, improving over constructions efficient proofs. In particular, if verifying R witness length m done by circuit C size s, and assuming...

With the gaining popularity of remote storage (e.g. in Cloud), we consider setting where a small, protected local machine wishes to access data on large, untrusted machine. This was introduced RAM model context software protection by Goldreich and Ostrovsky. A secure Oblivious simulation allows for client, with small (e.g., constant size) memory, hide not only but also sequence locations it accesses (both reads writes) unprotected memory size n.Our main results are as follows:• We analyze...

We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after introduction) among practitioners, and order suggest improvements application. propose justify a clusterability criterion sets. present that quickly lead provably near-optimal solutions when applied well-clusterable instances. This is the first performance guarantee variant heuristic. The provision on output quality does not come at expense speed:...

Article Free Access Share on Efficient search for approximate nearest neighbor in high dimensional spaces Authors: Eyal Kushilevitz Computer Science Department, Technion IIT, Haifa 32000, Israel IsraelView Profile , Rafail Ostrovsky Bell Communications Research, MCC-1C365B, 445 South Street, Morristown, NJ NJView Yuval Rabani Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium Theory computingMay 1998 Pages 614–623https://doi.org/10.1145/276698.276877Online:23...

We address the problem of designing data structures that allow efficient search for approximate nearest neighbors. More specifically, given a database consisting set vectors in some high dimensional Euclidean space, we want to construct space-efficient structure would us search, query vector, closest or nearly vector database. also this when distances are measured by L1 norm and Hamming cube. Significantly improving extending recent results Kleinberg, whose size is polynomial algorithms run...

Article Free AccessEfficient computation on oblivious RAMs Author: R. Ostrovsky Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA MAView Profile Authors Info & Claims STOC '90: Proceedings the twenty-second annual ACM symposium Theory ComputingApril 1990 Pages 514–523https://doi.org/10.1145/100216.100289Published:01 April 1990Publication History 159citation944DownloadsMetricsTotal Citations159Total Downloads944Last 12 Months101Last 6 weeks41 Get Citation...