Patent Document ID: 10089487
Application ID: 15476058

Base Claim:
1. A method for searching in an encrypted database, comprising: formulating a search as a conjunct of two or more atomic search queries; selecting one of the conjuncts as a primary atomic search query; and generating search capabilities for a secondary atomic search query using the primary atomic search query and the secondary atomic search query; wherein the encrypted database comprises a first data structure associated with the primary atomic search query and a second data structure associated with the secondary atomic search query; wherein the first data structure and the second data structure are generated from a raw database comprising a plurality of records, and wherein each record of the plurality of records comprises a corresponding record index value and a plurality of attribute values; wherein the first data structure is generated from the raw database by: computing a first entry for each attribute value of the plurality of attribute values; wherein the first entry comprises an encrypted tuple list and a search tag, the search tag being obtained by applying a pseudorandom function to the attribute value of the first entry; wherein the encrypted tuple list comprises a plurality of tuple list values obtained based on a randomized index value the randomized index value being obtained by applying a random permutation to the record index value; and wherein the plurality of tuple list values comprises a first tuple value obtained by encrypted the randomized index value with a key; wherein the plurality of tuple list values further comprises a second tuple value obtained by: applying a first pseudorandom function to the randomized index value to create a first intermediate tuple value, wherein the first pseudorandom function takes a first key; applying a second pseudorandom function to the attribute value and a current count associated with the attribute value to create a second intermediate tuple value, wherein the second pseudorandom function takes a second key; and dividing the first intermediate tuple value by the second intermediate tuple value; and wherein the formulating, selecting and generating steps are performed in accordance with one or more processing devices.

---

Claim 3:
3. The method of claim 1 , wherein generating the search capabilities for the secondary atomic search query comprises performing an exponentiation in algebraic groups.