Recursive algorithms with delayed computations performed in a homomorphically encrypted space
US11616635B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 26, 2020 |
| Grant date | Mar 28, 2023 |
| Priority date | — |
| Expiry date | Jun 12, 2041 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L2209/125
- WIPO fieldControl
- WIPO sectorInstruments
Abstract
A device, system and method for securely executing recursive computations over encrypted data in a homomorphically encrypted (HE) space. For a recursive algorithm with sequentially dependent recursive iterations, executing the recursive algorithm in parallel by computing multiple recursive iterations simultaneously over multiple parallel execution iterations and not in sequential order. Each parallel execution iteration may compute a partial HE solution of multiple sequential recursive iterations comprising a known HE part and leaves empty a placeholder call slot for an unknown HE part. Placeholder call slots remain empty and are filled at delayed times at a later parallel execution iteration from when the known part of the same HE computation is computed. A final HE solution is computed in fewer multiple parallel execution iterations than the number of sequential recursive iterations, thereby accelerating the recursive algorithm in HE space.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.