# US 11,907,380 B2 · In-memory computation in homomorphic encryption systems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,907,380 B2
- Document ID: US11907380B2
- Status: Granted
- Kind: B2
- Application number: 17/321,538
- Filed: 2021-05-17
- Published: 2022-11-17
- Granted: 2024-02-20
- Earliest claimed: 2021-05-17
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Nandakumar Sasidharan Rajalekshmi; Flavio A. Bergamaschi; Evangelos Stavros Eleftheriou
- Web page: https://patentgrep.com/patent/US11907380B2

## CPC

- G06F 21/602: {Providing cryptographic facilities or services}
- G06F 7/5443: {Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00)}
- G06F 17/141: {Discrete Fourier transforms}
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 21/79: in semiconductor storage media, e.g. directly-addressable memories
- G06N 3/065: Analogue means
- G11C 7/1006: {Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor}
- G11C 11/4085: {Word line control circuits, e.g. word line drivers, - boosters, - pull-up, - pull-down, - precharge}
- G11C 11/4094: Bit-line management or control circuits
- G11C 11/413: Auxiliary circuits, e.g. for addressing, decoding, driving, writing, sensing, timing or power reduction
- G11C 11/54: using elements simulating biological cells, e.g. neuron
- G11C 27/00: Electric analogue stores, e.g. for storing instantaneous values
- G11C 27/005: {with non-volatile charge storage, e.g. on floating gate or MNOS}
- G06F 21/107: {License processing; Key processing}
- G11C 29/028: {with adaption or trimming of parameters}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G11C: STATIC STORES (semiconductor memory devices H10B)

## Abstract

In an approach, a process stores a matrix of multibit values for a computation in an analog multiply-accumulate unit including at least one crossbar array of binary analog memory cells connected between respective pairs of word- and bit-lines of the array, where: bits of each multibit value are stored in cells connected along a word-line, and corresponding bits of values in a column of the matrix are stored in cells connected along a bit-line. In each of one or more computation stages for a cryptographic element, the process supplies a set of polynomial coefficients of an element bitwise to respective word-lines of the unit to obtain analog accumulation signals on the respective bit-lines. The process converts the analog signals to digital. The process processes the digital signals obtained from successive bits of the polynomial coefficients in each of the stages to obtain a computation result for the cryptographic element.

## Claims

### Claim 1

A computer-implemented method comprising:
storing a matrix of multibit values for a computation in an analog multiply-accumulate unit comprising at least one crossbar array of binary analog memory cells connected between respective pairs of word-lines and bit-lines of the at least one crossbar array, wherein:
bits of each multibit value are stored in cells connected along a word-line; and
corresponding bits of values in a column of the matrix are stored in cells connected along a bit-line;
in each of one or more computation stages for a cryptographic element, supplying a set of polynomial coefficients of an element bitwise to respective word-lines of the analog multiplying-accumulate unit to obtain analog accumulation signals on the respective bit-lines;
converting the analog accumulation signals to digital signals; and
processing the digital signals obtained from successive bits of the polynomial coefficients in each of the one or more computation stages to obtain a computation result for the cryptographic element.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, further comprising:
for each bit of the polynomial coefficients supplied bitwise to the word-lines, accumulating the digital signals obtained from a set of bit-lines connected to cells storing values in a column of the matrix with successive bit-shifts corresponding to successive bit-positions of the values; and
accumulating the digital signals for the successive bits of the polynomial coefficients with successive bit-shifts corresponding to successive bit-positions of the coefficients.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein the computation result for a first cryptographic element c1 is a result of a polynomial multiplication c1c2 and wherein c2 is a second cryptographic element, further comprising:
storing polynomial coefficients of the second cryptographic element c2 in the multiply-accumulate unit as respective multibit values in a first column of said matrix;
in successive computation stages, progressively shifting the polynomial coefficients of element c1 relative to a set of word-lines connected to cells storing coefficients of c2 until coefficients of c1 have been supplied bitwise to word-lines in the set of word-lines; and
processing the digital signals obtained, in each of the computation stages, from the set of bit-lines connected to cells storing the coefficients of c2 and from successive bits of the coefficients of c1 to obtain the result of the polynomial multiplication c1c2.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3, further comprising:
processing the digital signals to obtain the result of the polynomial multiplication c1c2 modulo p, wherein p is a predefined prime number for a homomorphic encryption system.

### Claim 5 (depends on 3)

The computer-implemented method of claim 3, further comprising:
for at least one further cryptographic element c:
storing polynomial coefficients of element c, as respective multibit values in a further column of said matrix, in cells connected to the set of word-lines; and
processing the digital signals obtained, in each of said the computation stages, from the set of bit-lines connected to cells storing the coefficients of c and from successive bits of the coefficients of c1 to obtain a further result of the further polynomial multiplication c1c.

### Claim 6 (depends on 3)

The computer-implemented method of claim 3, wherein:
the second cryptographic element c2 is an elements of a secret key (1, s) of a homomorphic encryption system;
the first cryptographic element c1 is an element of a cyphertext (c0, c1) encrypted under a corresponding public key;
c0 is another cryptographic element; and
further comprising, subsequent to obtaining a result of a polynomial multiplication c1s, computing a sum of c1s and c0 to obtain a decryption m=c0+c1s modulo p of the cyphertext, wherein p is a predefined prime number for the homomorphic encryption system.

### Claim 7 (depends on 6)

The computer-implemented method of claim 6, further comprising:
computing the sum in an in-memory logic array.

### Claim 8 (depends on 3)

The computer-implemented method of claim 3, wherein:
encrypted weights w of a neural network inference model comprise respective cryptographic elements cw and polynomial coefficients of each element cw are stored in the multiply-accumulate unit as respective multibit values in a column of the matrix;
encrypted data values d to be weighted and propagated through the network in an inference operation comprise respective cryptographic elements cd for which polynomial multiplication cdcw is required to weight a data value d by a weight w;
further comprising:
performing each polynomial multiplication cdcw in the inference operation, wherein cd corresponds to the first cryptographic element c1 and cw corresponds to the second cryptographic element c2; and
processing the results of polynomial multiplications cdcw as encrypted data values are propagated through the network to obtain an encrypted inference result from the model.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, wherein:
for an encrypted data value d to be weighted by a plurality of weights wj=1 to L for propagation through the neural network, requiring a corresponding plurality of polynomial multiplications cdcwj, the coefficients of each element cwj stored in a respective column of said matrix in cells connected to a common set of word-lines for the elements cwj; and
the results of polynomial multiplications cdcwj are obtained by progressively shifting the coefficients of element cd relative to that set of word-lines until coefficients of cd have been supplied bitwise to word-lines in the set.

### Claim 10 (depends on 1)

The computer-implemented method of claim 1, further comprising:
for computing a polynomial multiplication c1c2 of first cryptographic element c1 and a second cryptographic element c2, each having n polynomial coefficients, wherein said matrix of multibit values comprises a Discrete Fourier Transform matrix M1 with values ei,j, i=0 to (n−1), j=0 to (n−1), given by ei,j=ki×j modulo p, wherein kN=1 modulo p, N≥n and p is a predefined prime number for a homomorphic encryption system, comprising:
storing an Inverse Discrete Fourier Transform matrix M2 corresponding to M1 as a further matrix of multibit values in a further crossbar array of the multiply-accumulate unit;
supplying n coefficients of element c1 bitwise to respective word-lines connected to cells storing values in M1, and processing the digital signals obtained from successive bits of the coefficients to obtain a Discrete Fourier Transform T(c1) of the coefficients of element c1;
supplying n coefficients of element c2 bitwise to respective word-lines connected to cells storing values in M1, and processing the digital signals obtained from successive bits of the coefficients to obtain a Discrete Fourier Transform T(c2) of the coefficients of element c2;
performing component-wise multiplication of corresponding components of T(c1) and T(c2) to obtain another Discrete Fourier Transform T(c3) of the coefficients of a cryptographic element c3; and
supplying the components of T(c3) bitwise to respective word-lines connected to cells storing values in M2 to obtain analog accumulation signals on the bit-lines, converting the analog accumulation signals to digital signals and processing the digital signals obtained from successive bits of the components to obtain a result of the polynomial multiplication c3=c1c2.

### Claim 11 (depends on 10)

The computer-implemented method of claim 10, further comprising:
processing the digital signals to obtain the result of the polynomial multiplication c1c2 modulo p, where p is a predefined prime number for the homomorphic encryption system.

### Claim 12 (depends on 1)

The computer-implemented method of claim 1, further comprising:
performing an operation selected from the group consisting of: (i) addition, (ii) subtraction, (iii) scaling, and (iv) component-wise multiplication, of cryptographic elements required for a the computation using an in-memory logic array.

### Claim 13 (depends on 1)

The computer-implemented method of claim 1, wherein the binary analog memory cells comprise analog static random access memory (SRAM) cells.

### Claim 14

A computer system comprising:
a homomorphic encryption system in which cryptographic elements are represented by polynomials with multibit coefficients, comprising an analog multiply-accumulate unit having at least one crossbar array of binary analog memory cells connected between respective pairs of word-lines and bit-lines of the at least one crossbar array, one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media for execution, the program instructions comprising:
program instructions to store a matrix of multibit values for a computation in an analog multiply-accumulate unit comprising at least one crossbar array of binary analog memory cells connected between respective pairs of word-lines and bit-lines of the at least one crossbar array, wherein:
bits of each multibit value are stored in cells connected along a word-line; and
corresponding bits of values in a column of the matrix are stored in cells connected along a bit-line;
program instructions to, in each of one or more computation stages for a cryptographic element, supply a set of polynomial coefficients of an element bitwise to respective word-lines of the analog multiplying-accumulate unit to obtain analog accumulation signals on the respective bit-lines;
program instructions to convert the analog accumulation signals to digital signals; and
program instructions to process the digital signals obtained from successive bits of the polynomial coefficients in each of the one or more computation stages to obtain a computation result for the cryptographic element.

### Claim 15 (depends on 14)

The computer system of claim 14, further comprising:
program instructions to, for each bit of the polynomial coefficients supplied bitwise to the word-lines, accumulate the digital signals obtained from a set of bit-lines connected to cells storing values in a column of the matrix with successive bit-shifts corresponding to successive bit-positions of the values; and
program instructions to accumulate the digital signals for the successive bits of the polynomial coefficients with successive bit-shifts corresponding to successive bit-positions of the coefficients.

### Claim 16 (depends on 14)

The computer system of claim 14, wherein the computation result for a first cryptographic element c1 is a result of a polynomial multiplication c1c2 and wherein c2 is a second cryptographic element, further comprising:
program instructions to store polynomial coefficients of the second cryptographic element c2 in the multiply-accumulate unit as respective multibit values in a first column of said matrix;
program instructions to, in successive computation stages, progressively shift the polynomial coefficients of element c1 relative to a set of word-lines connected to cells storing coefficients of c2 until coefficients of c1 have been supplied bitwise to word-lines in the set of word-lines; and
program instructions to process the digital signals obtained, in each of the computation stages, from the set of bit-lines connected to cells storing the coefficients of c2 and from successive bits of the coefficients of c1 to obtain the result of the polynomial multiplication c1c2.

### Claim 17 (depends on 16)

The computer system of claim 16, further comprising:
program instructions to process the digital signals to obtain the result of the polynomial multiplication c1c2 modulo p, wherein p is a predefined prime number for a homomorphic encryption system.

### Claim 18 (depends on 16)

The computer system of claim 16, further comprising:
program instructions to, for at least one further cryptographic element c:
store polynomial coefficients of element c, as respective multibit values in a further column of said matrix, in cells connected to the set of word-lines; and
process the digital signals obtained, in each of said the computation stages, from the set of bit-lines connected to cells storing the coefficients of c and from successive bits of the coefficients of c1 to obtain a further result of the further polynomial multiplication c1c.

### Claim 19 (depends on 16)

The computer system of claim 16, wherein:
the second cryptographic element c2 is an elements of a secret key (1, s) of a homomorphic encryption system;
the first cryptographic element c1 is an element of a cyphertext (c0, c1) encrypted under a corresponding public key;
c0 is another cryptographic element; and
further comprising program instructions to, subsequent to obtaining a result of a polynomial multiplication c1s, compute a sum of c1s and c0 to obtain a decryption m=c0+c1s modulo p of the cyphertext, wherein p is a predefined prime number for the homomorphic encryption system.

### Claim 20

A computer program product comprising:
one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions comprising:
program instructions to store a matrix of multibit values for a computation in an analog multiply-accumulate unit comprising at least one crossbar array of binary analog memory cells connected between respective pairs of word-lines and bit-lines of the at least one crossbar array, wherein:
bits of each multibit value are stored in cells connected along a word-line; and
corresponding bits of values in a column of the matrix are stored in cells connected along a bit-line;
program instructions to, in each of one or more computation stages for a cryptographic element, supply a set of polynomial coefficients of an element bitwise to respective word-lines of the analog multiplying-accumulate unit to obtain analog accumulation signals on the respective bit-lines;
program instructions to convert the analog accumulation signals to digital signals; and
program instructions to process the digital signals obtained from successive bits of the polynomial coefficients in each of the one or more computation stages to obtain a computation result for the cryptographic element.