# US 2020/0403781 A1 · Compressible (F)HE with Applications to PIR

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

- Number: US 2020/0403781 A1
- Document ID: US20200403781A1
- Status: Published application
- Kind: A1
- Application number: 16/444,540
- Filed: 2019-06-18
- Published: 2020-12-24
- Earliest claimed: 2019-06-18
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Craig B. Gentry; Shai Halevi
- Web page: https://patentgrep.com/patent/US20200403781A1

## CPC

- H04L 9/008: {involving homomorphic encryption}
- G06F 21/602: {Providing cryptographic facilities or services}
- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- H04L 9/0618: {Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04N 21/2353: {specifically adapted to content descriptors, e.g. coding, compressing or processing of metadata}
- G06N 20/00: Machine learning
- H04L 9/088: {Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms (network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A request is received for specific information that can be determined using data in a database on a first computer system. Either at least some of the data is encrypted or the request is encrypted. The first computer system does not have a decryption key to decrypt the encrypted data or request. The first computer system performs compressible HE operations on the data to determine compressed ciphertext(s) that correspond to the specific information. The operations include using a first uncompressed HE scheme and a second compressed HEscheme. The first HE scheme is used on the data to create other multiple ciphertexts and the second HE scheme is used on the other multiple ciphertexts to pack the other multiple ciphertexts into fewer ciphertexts that are compressed. Both the HE schemes use a same secret key. The first computer system sends a response including compressed ciphertext(s) corresponding to the specific information.

## Claims

### Claim at position 1

-16. (canceled)

### Claim at position 2

-24. (canceled)

### Claim 25

A method, comprising:
encrypting an index i, to be sent to a first computer system and by a second computer system, of an entry into a database stored by the first computer system, wherein the index i is represented in a mixed radix of ND bases and the database also has ND bases;
requesting by the second computer system retrieval of an item from the first computer system using the encrypted index;
receiving, by the second computer system and from the first computer system, a response to the request, the response comprising an encrypted answer, comprising one or more compressed ciphertexts, corresponding to an entry in the database that was requested using the encrypted index; and
decrypting by the second computer system the one or more compressed ciphertexts into corresponding plaintext.

### Claim 26 (depends on 25)

The method of claim 25, wherein the mixed radix ND bases has index elements (i1, i2, . . . , iD), wherein the database has N dimensions, N=A×B×B× . . . ×B, with ii∈[A] and ij∈[B] for all j>1, and encrypting an index i comprises encrypting scalars q′·π0,1 and σ1, 1, . . . , σ1,7 wherein σ1,0, . . . , σ1,7 are the bits of i1, and for j=2, . . . , D encrypting ciphertexts to encrypt bits of a unit vector eij, which is one in position ij and zero elsewhere, and where a ciphertext modulus of a ciphertext is a composite Q=q·q′, with q≈246 and q′≈260.

### Claim 27 (depends on 26)

The method of claim 26, wherein encrypting an index i comprises the following:
for a least significant bit, σ1,0, of i1 using an identity to multiple the least significant bit, and also multiplying the bit σ1,0 by q′;
for the other bits of i1, using a wide and short gadget matrix to multiply the other bits; and
for the bits encoding the unary representation of the other ij's for j>1, using a somewhat rectangular gadget matrix to multiply the bits encoding the unary representation.

### Claim 28 (depends on 25)

The method of claim 25, wherein the decrypting comprises decrypting using a secret key the response comprising the one or more compressed ciphertexts to obtain a matrix comprising a redundant encoding of the plaintext corresponding to the one or more compressed ciphertexts and additional noise, and using redundancy of the encoding to eliminate the noise and recover the plaintext corresponding to the one or more compressed ciphertexts.

### Claim 29 (depends on 28)

The method of claim 28, wherein the redundant encoding of the plaintext comprises some matrix that includes the plaintext, multiplied by a nearly square gadget matrix.

### Claim 30 (depends on 29)

The method of claim 29, where for the nearly square gadget matrix, H, there exists another matrix F where F has full rank and entries much smaller than q, where q is a learning with errors modulus, and where H×F=0 mod q, where the entries of matrix F are small enough so that after the entries get multiplied by noise from ciphertext, a result is still smaller than q.

### Claim 31 (depends on 29)

The method of claim 29, wherein:
the secret key is a matrix of a form S=[S′|I], where S′ is a learning with errors (LWE) secret;
the some matrix that includes the plaintext is a matrix
M
′
=
[
0
M
]
where M is the plaintext, so as to get SM′=M.

### Claim 32 (depends on 31)

The method of claim 31, wherein the plaintext is an n0×n0 matrix M, and where the matrix M′ is obtained from M by adding as many zero rows as a dimension of the learning with errors (LWE) secret, the dimension denoted by k, wherein, denoting n1=n0+k, the padded matrix M′ has dimension n1×n0.

### Claim 33 (depends on 32)

The method of claim 32, where the redundant encoding comprises multiplying M′ on the right with the gadget matrix H of dimension n0×n2 results in a final dimension of a matrix of ciphertexts of n1×n2.

### Claim 34 (depends on 28)

The method of claim 28, wherein the redundant encoding of the plaintext comprises some matrix that includes the plaintext, multiplied by an integer greater than one.

### Claim 35 (depends on 34)

The method of claim 34, wherein:
the secret key is a matrix of a form S=[S′|I], where S′ is a learning with errors (LWE) secret;
the some matrix that includes the plaintext is a matrix
M
′
=
[
0
M
]
where M is the plaintext, so as to get SM′=M.

### Claim 36 (depends on 35)

The method of claim 35, wherein the plaintext is an n0×n0 matrix M, and where the matrix M′ is obtained from M by adding as many zero rows as a dimension of the learning with errors (LWE) secret, the dimension denoted by k, wherein, denoting n1=n0+k, the padded matrix M′ has dimension n1×n0.

### Claim 37

An apparatus, comprising:
one or more memories having computer-readable code thereon; and
one or more processors, the one or more processors, in response to retrieval and execution of the computer-readable code, causing the computer system to perform operations comprising:
encrypting an index i, to be sent to a first computer system and by a second computer system, of an entry into a database stored by the first computer system, wherein the index i is represented in a mixed radix of ND bases and the database also has ND bases;
requesting by the second computer system retrieval of an item from the first computer system using the encrypted index;
receiving, by the second computer system and from the first computer system, a response to the request, the response comprising an encrypted answer, comprising one or more compressed ciphertexts, corresponding to an entry in the database that was requested using the encrypted index; and
decrypting by the second computer system the one or more compressed ciphertexts into corresponding plaintext.

### Claim 38 (depends on 37)

The apparatus of claim 37, wherein the mixed radix ND bases has index elements (i1, i2, . . . , iD), wherein the database has N dimensions, N=A×B×B× . . . ×B, with ii∈[A] and ij∈[B] for all j>1, and encrypting an index i comprises encrypting scalars q′·σ1,0 and σ1,1, . . . , σ1,7 wherein σ1,0, . . . σ1,7 are the bits of i1, and for j=2, . . . , D encrypting ciphertexts to encrypt bits of a unit vector eij, which is one in position ij and zero elsewhere, and where a ciphertext modulus of a ciphertext is a composite Q=q·q′, with q≈246 and q′≈260.

### Claim 39 (depends on 38)

The apparatus of claim 38, wherein encrypting an index i comprises the following:
for a least significant bit, σ1,0, of i1 using an identity to multiple the least significant bit, and also multiplying the bit σ1,0 by q′;
for the other bits of i1, using a wide and short gadget matrix to multiply the other bits; and
for the bits encoding the unary representation of the other ij's for j>1, using a somewhat rectangular gadget matrix to multiply the bits encoding the unary representation.

### Claim 40 (depends on 37)

The apparatus of claim 37, wherein the decrypting comprises decrypting using a secret key the response comprising the one or more compressed ciphertexts to obtain a matrix comprising a redundant encoding of the plaintext corresponding to the one or more compressed ciphertexts and additional noise, and using redundancy of the encoding to eliminate the noise and recover the plaintext corresponding to the one or more compressed ciphertexts.

### Claim 41 (depends on 40)

The apparatus of claim 40, wherein the redundant encoding of the plaintext comprises some matrix that includes the plaintext, multiplied by a nearly square gadget matrix.

### Claim 42 (depends on 41)

The apparatus of claim 41, where for the nearly square gadget matrix, H, there exists another matrix F where F has full rank and entries much smaller than q, where q is a learning with errors modulus, and where H×F=0 mod q, where the entries of matrix F are small enough so that after the entries get multiplied by noise from ciphertext, a result is still smaller than q.

### Claim 43 (depends on 41)

The apparatus of claim 41, wherein:
the secret key is a matrix of a form S=[S′|I], where S′ is a learning with errors (LWE) secret;
the some matrix that includes the plaintext is a matrix
M
′
=
[
0
M
]
where M is the plaintext, so as to get SM′=M.

### Claim 44 (depends on 43)

The apparatus of claim 43, wherein the plaintext is an n0×n0 matrix M, and where the matrix M′ is obtained from M by adding as many zero rows as a dimension of the learning with errors (LWE) secret, the dimension denoted by k, wherein, denoting n1=n0+k, the padded matrix M′ has dimension n1×n0.

### Claim 45 (depends on 40)

The apparatus of claim 40, wherein the redundant encoding of the plaintext comprises some matrix that includes the plaintext, multiplied by an integer greater than one.

### Claim 46 (depends on 35)

The apparatus of claim 35, wherein:
the secret key is a matrix of a form S=[S′|I], where S′ is a learning with errors (LWE) secret;
the some matrix that includes the plaintext is a matrix
M
′
=
[
0
M
]
where M is the plaintext, so as to get SM′=M.
