Homomorphic encryption

1. A system for homomorphic encryption via finite ring isomorphisms, comprising:

at least one processor; and

memory, operatively connected to the at least one processor and storing instructions that, when executed by the at least one processor, cause the at least one processor to:

select a polynomial f(x) of exact degree n with small coefficients in a ring F q [x];

select a polynomial h(y) of exact degree n in a ring F q [y];

construct an isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y));

construct an inverse isomorphism from the ring F q [y]/(h(y)) to the ring F q [x]/(f(x));

encrypt one or more messages using said isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y));

transmit the encrypted one or more messages to a remote computer;

receive one or more encrypted response messages from the remote computer based at least in part on the transmitted one or more messages; and

decrypt the one or more encrypted response messages.

2. The system of claim 1 , wherein to construct an isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y)) the memory further stores instructions that, when executed by the at least one processor, cause the at least one processor to determine a root ϕ(y) of the polynomial f(x) in the ring F q [y]/(h(y)), and wherein to construct an inverse isomorphism from the ring F q [y]/(h(y)) to the ring F q [x]/(f(x)) the memory further stores instructions that, when executed by the at least one processor, cause the at least one processor to determine to determine a root ψ(x) of the polynomial h(y) in a ring F q [x]/(f(x)).

3. The system of claim 2 , wherein the polynomials f(x) and h(y) are irreducible over F q .

4. The system of claim 1 , wherein to decrypt the one or more encrypted response messages, the memory further stores instructions that, when executed by the at least one processor, cause the at least one processor to:

construct a polynomial u(x) in the ring F q [x] based in part on the one or more encrypted response messages in the ring F q [y]/(h(y)) and in part on the inverse isomorphism from the ring F q [y]/(h(y)) to the ring F q [x]/(f(x)); and

construct a decrypted response message based in part on the polynomial u(x).

5. The system of claim 1 , wherein to encrypt the one or more messages, the memory further stores instructions that, when executed by the at least one processor, cause the at least one processor to:

construct a polynomial u(x) in the ring F q [x] based in part on the one or more messages; and

construct the encrypted message c(y) in the ring F q [y]/(h(y)) based in part on the polynomial u(x) and the isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y)).

6. The system of claim 5 , wherein the polynomial u(x) has small coefficients.

7. The system of claim 5 , wherein the polynomial u(x) is constructed in part from polynomials p(x), r(x), and m(x) in the ring F q [x]/(f(x)), wherein p(x), r(x), and m(x) have small coefficients.

8. The system of claim 7 , wherein the polynomial u(x) is equal to p(x)*r(x)+m(x) in the ring F q [x]/(f(x)).

9. The system of claim 8 , wherein the decrypted message is constructed in part from an image of the polynomial u(x) in a ring F q [x]/(f(x),p(x)).

10. The system of claim 1 , wherein the one or more encrypted response messages are constructed in part by the remote computer applying algebraic operations in the ring F q [y]/(h(y)) to the transmitted encrypted one or more messages.

11. A method for homomorphic encryption via finite ring isomorphisms, the method comprising:

selecting a polynomial f(x) of exact degree n with small coefficients in a ring F q [x];

selecting a polynomial h(y) of exact degree n in a ring F q [y];

constructing an isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y));

constructing an inverse isomorphism from the ring F q [y]/(h(y)) to the ring F q [x]/(f(x));

encrypting one or more messages using said isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y));

transmitting the encrypted one or more messages to a remote computer;

receiving one or more encrypted response messages from the remote computer based at least in part on the transmitted one or more messages; and

decrypting the one or more encrypted response messages.

12. The method of claim 11 , wherein constructing an isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y)) comprises determining a root ϕ(y) of the polynomial f(x) in the ring F q [y]/(h(y)), and wherein constructing an inverse isomorphism from the ring F q [y]/(h(y)) to the ring F q [x]/(f(x)) comprises determining a root ψ(x) of the polynomial h(y) in a ring F q [x]/(f(x)).

13. The method of claim 12 , wherein the polynomials f(x) and h(y) are irreducible over F q .

14. The method of claim 11 , wherein decrypting the one or more encrypted response messages comprises:

constructing a polynomial u(x) in the ring F q [x] based in part on the one or more encrypted response messages in the ring F q [y]/(h(y)) and in part on the inverse isomorphism from the ring F q [y]/(h(y)) to the ring F q [x]/(f(x)); and

constructing a decrypted response message based in part on the polynomial u(x).

15. The method of claim 11 , wherein encrypting the one or more messages comprises:

constructing a polynomial u(x) in the ring F q [x] based in part on the one or more messages; and

constructing the encrypted message c(y) in the ring F q [y]/(h(y)) based in part on the polynomial u(x) and the isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y)).

16. A computer-readable storage device having computer executable instructions stored thereon, which, when executed by a computing system, provide instructions to perform a method for homomorphic encryption via finite ring isomorphisms, the method comprising:

selecting a polynomial f(x) of exact degree n with small coefficients in a ring F q [x];

selecting a polynomial h(y) of exact degree n in a ring F q [y];

constructing an isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y));

constructing an inverse isomorphism from the ring F q [y]/(h(y)) to the ring F q [x]/(f(x));

encrypting one or more messages using said isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y));

transmitting the encrypted one or more messages to a remote computer;

receiving one or more encrypted response messages from the remote computer based at least in part on the transmitted one or more messages; and

decrypting the one or more encrypted response messages.

17. The computer-readable storage device of claim 16 , wherein constructing an isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y)) comprises determining a root ϕ(y) of the polynomial f(x) in the ring F q [y]/(h(y)), and wherein constructing an inverse isomorphism from the ring F q [y]/(h(y)) to the ring F q [x]/(f(x)) comprises determining a root ψ(x) of the polynomial h(y) in a ring F q [x]/(f(x)).

18. The computer-readable storage device of claim 17 , wherein the polynomials f(x) and h(y) are irreducible over F q .

19. The computer-readable storage device of claim 16 , wherein decrypting the one or more encrypted response messages comprises:

constructing a polynomial u(x) in the ring F q [x] based in part on the one or more encrypted response messages in the ring F q [y]/(h(y)) and in part on the inverse isomorphism from the ring F q [y]/(h(y)) to the ring F q [x]/(f(x)); and

constructing a decrypted response message based in part on the polynomial u(x).

20. The computer-readable storage device of claim 16 , wherein encrypting the one or more messages comprises:

constructing a polynomial u(x) in the ring F q [x] based in part on the one or more messages; and

constructing the encrypted message c(y) in the ring F q [y]/(h(y)) based in part on the polynomial u(x) and the isomorphism from the ring F q [x]/(f(x)) to the ring F q [y]/(h(y)).