Homomorphic processing unit (HPU) for accelerating secure computations under homomorphic encryption

Patent metadata

Field	Value
Publication number	US-10298385-B2
Application number	US-201715674864-A
Country	US
Kind code	B2
Filing date	Aug 11, 2017
Priority date	Apr 11, 2017
Publication date	May 21, 2019
Grant date	May 21, 2019

Abstract

Fully homomorphic encryption integrated circuit (IC) chips, systems and associated methods are disclosed. In one embodiment, an integrated circuit (IC) homomorphic processor chip is disclosed. The IC homomorphic processor chip includes at least one processor slice. Each processor slice includes local control circuitry, a numeric theoretic transform (NTT) butterfly unit, and on-chip memory. The NTT butterfly unit is responsive to the local control circuitry to operate in multiple modes for performing operations on encrypted data using homomorphic encryption. Each mode is associated with a different configuration of the NTT butterfly unit.

First claim

We claim:

1. An integrated circuit (IC) homomorphic processor chip comprising:
at least one processor slice, the slice including
local control circuitry;
a numeric theoretic transform (NTT) butterfly unit responsive to the local control circuitry to operate in multiple modes for performing operations on encrypted data using homomorphic encryption, each mode associated with a different configuration of the NTT butterfly unit;
on-chip memory coupled to the control circuitry and the NTT butterfly unit; and
wherein a given NTT transformation operation involves an initial NTT step followed by log 2 (n)−1 stages of evaluation by the NTT butterfly unit, where “n” represents a degree of a polynomial associated with a set of ciphertext (C txt ) coefficient values.

2. The IC homomorphic processor chip of claim 1 , wherein the NTT butterfly unit is responsive to the local control circuitry to operate in multiple modes for operations involving fully homomorphic encryption.

3. The IC homomorphic processor chip of claim 1 , wherein the NTT butterfly unit is responsive to the local control circuitry to operate in multiple modes for operations involving partially homomorphic encryption.

4. The IC homomorphic processor chip of claim 1 , wherein:
a first configuration for the NTT butterfly unit employs first circuitry to carry out a first ciphertext (C txt ) function; and
a second configuration for the NTT butterfly unit reuses at least a portion of the first circuitry to carry out a second C txt function.

5. The IC homomorphic processor chip of claim 4 , wherein:
the first circuitry carries out a ciphertext (C txt ) addition function; and
the second C txt function comprises a C txt multiplication function.

6. The IC homomorphic processor chip of claim 5 , wherein:
the first circuitry includes a modular adder.

7. The IC homomorphic processor chip of claim 6 , wherein:
the modular adder comprises a combinational modular adder.

8. The IC homomorphic processor chip of claim 6 , wherein:
the modular adder comprises a sequential modular adder.

9. The IC homomorphic processor chip of claim 5 , wherein:
the second configuration includes second circuitry comprising a modular multiplier.

10. The IC homomorphic processor chip of claim 9 , wherein the modular multiplier comprises a parallel integer multiplier.

11. The IC homomorphic processor chip of claim 10 , wherein the modular multiplier further comprises:
a modular reduction unit.

12. The IC homomorphic processor chip of claim 1 , wherein the IC homomorphic processor includes multiple processor slices, and wherein the IC homomorphic processor further comprises:
master control circuitry to interface the multiple processor slices with external memory via an external processor interface.

13. The IC homomorphic processor chip of claim 12 , wherein the local control circuitry receives instructions from the master control circuitry to:
retrieve the set of C txt coefficient values from the external memory;
load the set of values into a processing pipeline;
perform at least one Ctxt operation to generate transformed values; and
store the transformed values to a destination memory location.

14. The IC homomorphic processor chip of claim 13 , wherein the instructions from the master control circuitry further comprises instructions to:
perform NTT transformations on the loaded set of C txt coefficient values to generate corresponding transformed values in the NTT domain.

15. The IC homomorphic processor chip of claim 14 , wherein the instructions from the master control circuitry to perform at least one Ctxt operation comprises instructions to:
perform at least one Ctxt operation from the group consisting of addition operation, subtraction operation, multiplication operation, XOR operation, XNOR operation, AND operation, equality operation, smaller than operation, larger than operation, entity operation, copy operation and negation operation.

16. The IC homomorphic processor chip of claim 1 , wherein:
the NTT butterfly unit is realized as a single-stage unit.

17. A homomorphic encryption system, comprising:
an integrated circuit (IC) homomorphic processor chip;
main memory external to the IC homomorphic processor chip;
a data path for transferring data between the main memory and the IC homomorphic processor chip;
a control path to control the transfers between the main memory and the IC homomorphic processor chip; and
wherein the IC homomorphic processor chip comprises
master control circuitry to control the transfers of data between the main memory and the IC homomorphic processor chip via the control path; and
multiple processor slices corresponding to a pipeline depth, each of the multiple processor slices including
local control circuitry;
a numeric theoretic transform (NTT) butterfly unit responsive to the local control circuitry to operate in multiple modes for performing operations on encrypted data using homomorphic encryption, each mode associated with a different configuration of the NTT butterfly unit; and
on-chip memory coupled to the local control circuitry and the NTT butterfly unit; and
wherein a given NTT transformation operation involves an initial NTT step followed by log 2 (n)−1 stages of evaluation by the NTT butterfly unit, where “n” represents a degree of a polynomial associated with a set of ciphertext (C txt ) coefficient values.

18. The homomorphic encryption system of claim 17 , wherein the homomorphic encryption comprises fully homomorphic encryption.

19. The homomorphic encryption system of claim 17 , wherein the homomorphic encryption comprises partially homomorphic encryption.

20. The homomorphic encryption system of claim 17 , wherein the master control circuitry schedules operations for each of the multiple processor slices to:
retrieve the set of C txt coefficient values from the main memory;
load the set of values into a processing pipeline;
perform at least one Ctxt operation; and
store the transformed values to a destination memory location.

21. The homomorphic encryption system of claim 20 , wherein the scheduled operations from the master control circuitry further comprises scheduled operations for each of the multiple processor slices to:
perform NTT transformation operations on the loaded set of values to generate corresponding transformed values in the NTT domain.

22. The homomorphic encryption system of claim 21 , wherein the scheduled operations from the master control circuitry further comprises scheduled operations for each of the multiple processor slices to:
perform at least one Ctxt operation from the group consisting of addition operation, subtraction operation, multiplication operation, XOR operation, XNOR operation, AND operation, equality operation, smaller than operation, larger than operation, entity operation, copy operation and negation operation.

23. The homomorphic encryption system of claim 21 , wherein:
each of the NTT butterfly units comprises a single-stage butterfly.

Assignees

• Governing Council Univ Toronto

Inventors

• KHEDR Alhassan
• Gulak Glenn

Classifications

• G06F9/30029

  Logical and Boolean instructions, e.g. XOR, NOT · CPC title

• H04L2209/12

  Details relating to cryptographic hardware or logic circuitry · CPC title

• G09C1/00 Primary

  Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00) · CPC title

• H04L9/0618

  Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation · CPC title

• H04L9/008 Primary

  involving homomorphic encryption · CPC title