Back to results
US 11,902,414 B2Granted
Low-latency pipeline and method for use of a low latency pipeline in homomorphic encryption
AssigneeHuawei Technologies Co., Ltd.
InventorsHaohao Liao, Zhiwei Shang, Yin Tan
Life of this patent
Estimating the term…
Abstract
A low latency relinearization process can be performed in an FPGA cluster for accelerating homomorphic encryption. The low-latency process performs an early calculation of matrix rows to make the summation result available earlier in the relinearization to reduce waiting of subsequent operations.
Claims20
A low-latency relinearization method implemented by a field programmable gate array (FPGA) cluster comprising:
- receiving at the FPGA cluster a polynomial vector comprising R components;
- and
- performing modular reduction on the polynomial vector to generate a polynomial matrix comprising R+1 rows and L columns;
- multiplying the polynomial matrix by a first Keyswitch matrix to generate a first intermediate polynomial matrix;
- summing a last row of the first intermediate polynomial matrix to generate a first early-summation element and performing a modular reduction on the first early-summation element to generate a first early-summation vector;
- summing remaining rows of the first intermediate polynomial matrix to generate a first summation vector;
- subtracting the first early-summation vector from the first summation vector to generate a first subtraction-result vector;
- multiplying the first subtraction-result vector by an inverse moduli vector to generate a first result vector;
- and
- outputting from the FPGA cluster the first result vector.
7 more elements
A field programmable gate array (FPGA) cluster for use in homomorphic encryption comprising:
- a plurality of FPGAs to provide a configured to provide a pipeline for providing a low-latency relinearization method comprising:
- receiving at the FPGA cluster a polynomial vector comprising R components;
- performing modular reduction on the polynomial vector to generate a polynomial matrix comprising R+1 rows and R columns;
- multiplying the polynomial matrix by a first Keyswitch matrix to generate a first intermediate polynomial matrix;
- summing a last row of the first intermediate polynomial matrix to generate a first early-summation element and performing a modular reduction on the first early-summation element to generate a first early-summation vector;
- summing remaining rows of the first intermediate polynomial matrix to generate a first summation vector;
- subtracting the first early-summation vector from the first summation vector to generate a first subtraction-result vector;
- multiplying the first subtraction-result vector by an inverse moduli vector to generate a first result vector;
- and
- outputting from the FPGA cluster the first result vector.
7 more elements
Dependencies are inferred from the claim text.