Patent ID: 7290150

Claim:
A computer-implemented method for processing an intersection type query spanning separate databases while revealing only minimal information beyond a query answer, comprising: (a) sender S and receiver R each apply a hash function h to their respective attribute value sets, X S =h(V S ) and X R =h(V R ); (b) sender S and receiver R each choose a random secret key, es εr KeyF for S and er εr KeyF for R; (c) sender S and receiver R each encrypt their respective hashed sets, Y S =f eS (X S )=f eS (h(V S )) and Y R =f eR (X R )=f eR (h)(V R )); (d) receiver R sends to sender S its encrypted set Y R =f eR (h(V R )), reordered lexicographically; (e) sender S sends to receiver R its set Y S =f eS (h(V S )), reordered lexicographically; (f) sender S encrypts each yεY R with key es and sends back to R pairs <y,f eS (y)>=<f eR (h(v)),f eS (f eR (h(v)))>; (g) receiver R encrypts each yεY S with er, obtaining Z S =f eR (f eS (h(V S ))) and from pairs <f eR (h(v)),f eS (f eR (h(v)))> obtained in Step (f) for vεV R , receiver R creates pairs <v,f eS (f eR (h(v)))> by replacing f eR (h(v)) with the corresponding v; and (h) receiver R selects all V E V R for which (f eS (f eR (h(v)))εZ S to form V S ∩V R .