Patent ID: 8891762

Claim:
A method for selecting an encrypted element in an encrypted vector according to an order of the encrypted element in the encrypted vector using a secure communication between a first processor and a second processor, wherein the second processor stores a pair of keys for a semantically secure additively homomorphic cryptosystem, the pair includes a private decryption key and a public encryption key, wherein the encrypted vector is encrypted with the public key and stored at the first processor, and wherein the first processor operates only in an encrypted domain, comprising the steps of: scaling values of the elements of the encrypted vector, such that the order of the elements in the encrypted vector is preserved, wherein the scaling further comprises: constructing an order preserving matrix; and multiplying the encrypted vector by the order preserving matrix; permuting the order of the elements of the encrypted vector to produce a scaled permuted vector; providing information in the encrypted domain to the second processor, wherein the information in an underlying unencrypted domain is indicative of an order of elements in the scaled permuted vector; obtaining an encrypted index of the encrypted element in the scaled permuted vector; and selecting the encrypted element based on the encrypted index; selecting an integer g>0; and determining the order preserving matrix GεZ N×N according to G = [ g + g 1 g 2 g 3 … g N g 1 g + g 2 g 3 … g N g 1 g 2 g + g 3 … g N ⋮ ⋮ ⋮ ⋱ ⋮ g 1 g 2 g 3 … g + g N ] . , wherein Z is the set of integers and N is the number of elements in the encrypted vector, and elements g i are integers, wherein the steps of the method are performed by the first processor.