Telcordia Technologies, Inc.

University of California

Stealth Software Technologies, Inc.

Johns Hopkins University

Massachusetts Institute of Technology

Technion Research & Development Foundation Ltd

The Trdf Research & Development Foundation Ltd

Rafail Ostrovsky

Yuval Ishai

Giovanni Di-Crescenzo

Brett Hemenway Falk

Yuval Rabani

William E Skeith, Iii

Steve Naichia Lu

William A Aiello

Giovanni Di Crescenzo

Yair Amir

Vladimir Braverman

Eyal Kushilevitz

Oded Goldreich

Rohit Nema

Sivaramakris Rajagopalan

Sachin Lodha

Quinn Grier

Paul Bunn

Non-transitory computer readable storage mediums have instructions executed by processors to convert a first list at a first server into a first encrypted, permuted list with first dummy data elements and form a first encrypted linked list of pointers to locations in the first encrypted, permuted list. A second list at a second server is converted into a second encrypted, permuted list with second dummy data elements and a second encrypted linked list is formed of pointers to locations in the second encrypted, permuted list. Elements of the first encrypted, permuted list are combined with elements of the second encrypted, permuted list into a merged, sorted list of secret sharings, where the merged, sorted list of secret sharings is formed solely utilizing local computations at the first server, local computations at the second server and communications solely between the first server and the second server.

Apparatus and method for secure merging of lists using only local computations at each of two machines and communications solely between the two machines

A hardware module has a plug to interface with an audio channel of a speech communication device. A scrambler connected to the plug is configured to receive a local audio input signal and form an encrypted audio output signal in a human audible range that is applied to the audio channel of the speech communication device. The scrambler also receives a remote encrypted audio input signal in a human audible range and forms a remote audio output signal corresponding to the remote encrypted audio input signal.

Apparatus and method for forming a voice encrypted signal in the hearing range

A database system includes an input to a database server configured to deliver a data stream formed of a sequence of elements, D={p, p, . . . , p} of size m of numbers from {1, . . . , n} to the database server. The system further includes a computer program that causes a processor to approximate frequency moments (F) in the data stream, such that a frequency of an element (i) is defined as f=|{j:p=i}| and a k-th frequency moment of D is defined as single pass through the data stream. The processor is caused to carry out the steps of locating elements (i) with a frequency &#x3a9;Fin the data stream as heavy elements and approximating fas &#x2267; a fraction of fto limit memory resources used by the processor to estimate Fto O(nlog(n)) bits.

System and method for pick-and-drop sampling

In one embodiment, a non-transitory computer readable storage medium includes executable instructions to perform a series of operations represented by a first garbled program received from a client on garbled data received from the client. A second garbled program is obtained as a result of execution of the first garbled program. The second garbled program includes a first garbled portion and a second garbled portion. The second garbled portion includes a third garbled portion generated through execution of the first garbled portion, such that the series of operations can be performed without interaction with the client and while maintaining as hidden the underlying content of the first garbled program and the garbled data.

Apparatus, system, and method to garble programs

A routing protocol is used to transmit messages from a sender to a receiver over a network of nodes, where adversaries can control links between the nodes and can also control the behavior of a large number of nodes. Various techniques can be used, along or in combination, to combat these effects. In one approach, certain trigger conditions are identified, the occurrence of which signals malicious behavior within the network. When signaled, the sender requests status reports from the intermediate nodes in an effort to determine which nodes are malicious. The information for the status reports is generated by nodes as packets are passed from one node to the next.

Authenticated adversarial routing

instructions to: (1) process first data by encrypting based on a first key and re-arranging based on a first mapping to obtain second data, where a first element included in the first data is associated with a first index corresponding to a location in a first memory; (2) request to store the second data in a second memory at locations determined based on the first mapping; (3) in response to determining that the first element is not stored in the first memory, request a second element from the second memory; and (4) in response to determining that the first element is stored in the first memory: (a) retrieve the first element from the first memory; and (b) request a third element from the second memory that has not been previously requested, without requesting the second element from the second memory.

Apparatus, system, and method to efficiently search and modify information stored on remote servers, while hiding access patterns

A method for private keyword searching on streaming data such that the searching does not reveal what keywords are being searched for and does not reveal whether any such keywords have been located nor which documents in the data stream are saved.

Method for private keyword search on streaming data

A method of embedding the edit distance metric into the Hamming distance metric with low distortion. In other words, two input character strings are mapped to two corresponding output bit strings such that the Hamming distance between the output strings is approximately proportional to the edit distance between the two corresponding input strings.

Method for low distortion embedding of edit distance to Hamming distance

A method and system are provided for timed-release cryptography. A sender encrypts data in a timed-release fashion such that a receiver based on information exchanged with a server decrypts the encrypted data at or after a release time without revealing to the server any information about the sender, the data, and the release time. In one embodiment, the sender encrypts a key and a release time based on a public key of the receiver and encrypts the data based on the encrypted key. The server determines a condition, which is a function of the encrypted key, the encrypted release time, and a current time. The server then sends the condition to the receiver using a conditional oblivious transfer method. If the current time as determined by the server is greater than or equal to the release time, the receiver determines the encrypted key based on the condition. The receiver then uses the encrypted key to decrypt the encrypted data. However, if the current time is less than the release time, the receiver fails to determine the encrypted key based on the condition, and thus, fails to decrypt the encrypted data.

Method and system for timed-release cryptosystems

A method and system for privately retrieving selected information from a database. The method includes determining, at a server, a first commodity and a second commodity, communicating the first commodity to an inquiring processor and the second commodity to the database, and retrieving the selected information from the database based on the first commodity and the second commodity such that the selected information is not revealed to the database. The first and second commodities may, for example, include a random address in the database and a private information retrieval query for encoding the random address, respectively. The inquiring processor determines an address offset based on the random address and the address of selected information in the database, and sends the address offset to the database. The database cyclically shift its contents according the address offset, and executes the query on the cyclically shifted contents. The database then sends the result of the query to the inquiring processor, which extracts from the result the selected information in the database.

System and method for private information retrieval from a single electronic storage device using verifiable commodities

Method for efficiently revoking digital identities

A method and system perform non-malleable and non-interactive commitment of data, which is communicated by a sender to a receiver. At a commitment phase, the sender selects a first string having a first portion and a second portion, and based on the first portion of the first string, establishes a first commitment to an authentication key. The sender divides the second portion of the first string into a set of segments each including two or more sub-segments, and based on the first commitment, selects one of the subsegments in each of the segments. The sender combines the selected sub-segments together, and establishes a second commitment to the data based on the combined selected sub-segments such that the second commitment is equivocable. The sender authenticates the second commitment by using the authenticating key. At a de-commitment phase, the sender de-commits the data and the authentication key.

Method and system for non-malleable and non-interactive cryptographic commitment in a network

A method and system identify in a database one or more data entries that are the nearest neighbors of a query. The database prebuilds a first set of strings by probabilistically selecting values of respective bits in each of the first set of strings based on a probability that depends on a first hamming distance. Based on the first set of strings, the database predetermines the trace values of each data entry in the database, respectively, and stores the predetermined trace values as entries in a trace table. For each trace value entry, the database identifies the data entries whose trace values are within a second hamming distance of the trace value entry, and stores the addresses of the identified data entries in the trace value entry. When the database receives a query, by identifying the trace value entry in the trace table that match the trace value of the query, the database identifies the data entries that are within the first hamming distance of the query. In addition, a method and system estimate the hamming distance between two strings in a network.

Method for determining approximate hamming distance and approximate nearest neighbors of a query

System and method for private information retrieval from a single electronic storage device using commodities

A method and apparatus for privately retrieving information from a single electronic storage device (e.g., a database) is described. An inquiring processor identifies a portion of a database memory with information for retrieval and encodes address of the information into a preselected mathematical function that conceals the identity of the selected information from the database. The inquiring processor transmits the encoded function to the database. The database cooperates by executing the encoded function on the database and transmits an encoded result that represents an evaluation of the encoded function to the inquiring processor. The inquiring processor, having knowledge of the selected mathematical function, decodes the encoded result to generate the information from the selected memory section of the database. The inquiry can be repeated until the inquiring processor can retrieve the selected information. The process minimizes the exchange of information between the database and the inquiring processor that is necessary to privately retrieve information.

Growing community of inventors

Los Angeles, CA, United States of America

Rafail Ostrovsky