Patent ID: 8281121

Claim:
A method comprising: receiving a query sequence that includes a plurality of queries at a user computing device from a requestor; determining an answer sequence that includes a plurality of answers that corresponds to the plurality of respective queries; transforming a first representation of the answer sequence in a first domain to a second representation of the answer sequence in a second domain, the first representation including a plurality of first coefficients that corresponds to the plurality of respective answers, the second representation including a plurality of second coefficients, a number of the second coefficients in the plurality of second coefficients being less than a number of the first coefficients in the plurality of first coefficients; adding noise to the plurality of second coefficients to provide a noisy representation of the plurality of second coefficients in the second domain; encrypting the noisy representation in accordance with a homomorphic encryption technique to provide an encrypted representation of the plurality of second coefficients to the requestor; receiving an encrypted summation sequence that includes a plurality of summations from the requestor, each of the plurality of summations incorporating a respective second coefficient of the noisy representation of the plurality of second coefficients; determining a decryption share of the user based on the encrypted summation sequence; and providing the decryption share of the user to the requestor to be combined with at least one decryption share of at least one other respective user for decryption of the encrypted summation sequence.