# US 2025/0167976 A1 · Method for accelerating bootstrapping in a cryptographic application

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

- Number: US 2025/0167976 A1
- Document ID: US20250167976A1
- Status: Published application
- Kind: A1
- Application number: 18/515,914
- Filed: 2023-11-21
- Published: 2025-05-22
- Earliest claimed: 2023-11-21
- Assignees: Katholieke Universiteit Leuven
- Applicants: Katholieke Universiteit Leuven
- Inventors: Michiel VAN BEIRENDONCK
- Web page: https://patentgrep.com/patent/US20250167976A1

## CPC

- H04L 9/008: {involving homomorphic encryption}
- H04L 9/0877: {using additional device, e.g. trusted platform module [TPM], smartcard, USB or hardware security module [HSM]}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method for performing a bootstrapping operation in cryptographic application, includes receiving in an accelerator one or more input ciphertexts used in the cryptographic application to be bootstrapped and iteratively processing one or more accumulator variables in function of portions of the input ciphertexts; multiplying, within each iteration, the processed accumulator variables with a bootstrapping key element belonging to a bootstrapping key comprising a plurality of bootstrapping key elements, said bootstrapping key element taken from a bootstrapping cache memory in the accelerator; while performing the multiplying for each of the one or more accumulator variables in turn, loading into the bootstrapping cache memory from an external memory a next bootstrapping key element of the plurality of bootstrapping key elements to be used in a next iteration of the bootstrapping operation.

## Claims

### Claim 1

A method for performing a bootstrapping operation in a cryptographic application, comprising
receiving in an accelerator one or more input ciphertexts used in the cryptographic application to be bootstrapped and iteratively processing one or more accumulator variables in function of portions of the input ciphertexts, whereby each accumulator variable is linked to one input ciphertext and each iteration step is performed for each of the one or more accumulator variables in turn;
multiplying, within each iteration, the processed accumulator variables with a bootstrapping key element belonging to a bootstrapping key comprising a plurality of bootstrapping key elements, said bootstrapping key element taken from a bootstrapping cache memory in the accelerator,
while performing said multiplying for each of the one or more accumulator variables in turn, loading into the bootstrapping cache memory from an external memory a next bootstrapping key element of the plurality of bootstrapping key elements to be used in a next iteration of the bootstrapping operation.

### Claim 2 (depends on 1)

The method for performing a bootstrapping operation as in claim 1, where the bootstrapping cache memory is a SRAM memory.

### Claim 3 (depends on 1)

The method for performing a bootstrapping operation as in claim 1, wherein said one or more input ciphertexts are supplied from a further memory in the accelerator.

### Claim 4 (depends on 1)

The method for performing a bootstrapping operation as in claim 1, wherein said one or more input ciphertexts are supplied from an external memory.

### Claim 5 (depends on 1)

The method for performing a bootstrapping operation as in claim 1, wherein the vector elements and/or the bootstrapping key elements and/or said accumulator variables are represented in fixed point.

### Claim 6 (depends on 1)

The method for performing a bootstrapping operation as in claim 1, wherein the cryptographic application is a torus fully homomorphic encryption scheme.

### Claim 7 (depends on 1)

A program, executable on a programmable device containing instructions which, when executed, perform the method as in claim 1.

### Claim 8

An accelerator for performing a bootstrapping operation in cryptographic application, the accelerator comprising
a preprocessing block configured to receive one or more input ciphertexts to be bootstrapped and to iteratively process one or more accumulator variables in function of portions of the input ciphertexts, whereby each accumulator variable is linked to one input ciphertext and each iteration step is performed for each of the one or more accumulator variables in turn;
an arithmetic unit configured to multiply, within each iteration, the processed accumulator variables with a bootstrapping key element belonging to a bootstrapping key comprising a plurality of bootstrapping key elements,
wherein the accelerator further comprises a bootstrapping cache memory for storing the bootstrapping key element to be multiplied and adapted for loading into the bootstrapping cache memory a next bootstrapping key element of said plurality of bootstrapping key elements to be used in a next iteration of the bootstrapping operation, while performing the multiplying operation for each of the one or more accumulator variables in turn.

### Claim 9 (depends on 8)

The accelerator as in claim 8, wherein the arithmetic unit comprises a plurality of cascaded computational stages, where each computational stage is operating on different parts of said one or more accumulator variables.

### Claim 10 (depends on 8)

The accelerator as in claim 8, wherein the plurality of cascaded computational stages forms a pipeline.

### Claim 11 (depends on 8)

The accelerator as in claim 8, comprising a memory for storing said one or more input ciphertexts.

### Claim 12 (depends on 8)

The accelerator as in claim 8, wherein a fixed point representation is used for the one or more input ciphertexts and/or the bootstrapping key element and/or the accumulator variables.

### Claim 13 (depends on 8)

The accelerator as in claim 8, wherein the bootstrapping cache memory is arranged for storing more than one next bootstrapping key element to be used.

### Claim 14 (depends on 8)

The accelerator as in claim 8, implemented on a Field Programmable Gate Array or in an application specific integrated circuit.

### Claim 15 (depends on 8)

The accelerator as in claim 8, wherein the arithmetic unit has forward and inverse FFT or NTT computational stages, with the forward FFT or NTT having a higher throughput than the inverse FFT or NTT.

### Claim 16 (depends on 8)

A computing system comprising an accelerator as in claim 8 and a memory external to the accelerator, said memory arranged to store one or more bootstrapping keys for use in the bootstrapping operation.

### Claim 17 (depends on 14)

Use of an accelerator as in claim 14 in a cloud computing service.
