| Texto completo | |
| Autor(es): |
Guimaraes, Antonio
;
Pereira, Hilder V. L.
;
van Leeuwen, Barry
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ADVANCES IN CRYPTOLOGY, ASIACRYPT 2023, PART VI; v. 14443, p. 33-pg., 2023-01-01. |
| Resumo | |
Micciancio and Sorrel (ICALP 2018) proposed a bootstrapping algorithm that can refresh many messages at once with sublinearly many homomorphic operations per message. However, despite the attractive asymptotic cost, it is unclear if their algorithm could ever be practical, which reduces the impact of their results. In this work, we follow their general framework, but propose an amortized bootstrapping procedure that is conceptually simpler and asymptotically cheaper. We reduce the number of homomorphic multiplications per refreshed message from O(3(rho) center dot n(1/rho) center dot log n) to O(rho center dot n(1/rho)), and the noise overhead from (O) over tilde (n(2+3 center dot rho)) to (O) over tilde (n(1+rho)), where n is the security level and rho >= 1 is a free parameter. We also make it more general, by handling non-binary messages and applying programmable bootstrapping. To obtain a concrete instantiation of our bootstrapping algorithm, we describe a double-CRT (aka RNS) version of the GSW scheme, including a new operation, called shrinking, used to speed-up homomorphic operations by reducing the dimension and ciphertext modulus of the ciphertexts. We also provide a C++ implementation of our algorithm, thus showing for the first time the practicability of the amortized bootstrapping. Moreover, it is competitive with existing bootstrapping algorithms, being even around 3.4 times faster than an equivalent non-amortized version of our bootstrapping. (AU) | |
| Processo FAPESP: | 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais |
| Beneficiário: | Munir Salomao Skaf |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |
| Processo FAPESP: | 21/09849-5 - Avaliação homomórfica eficiente com múltiplas chaves para aplicações em genômica |
| Beneficiário: | Antonio Carlos Guimarães Junior |
| Modalidade de apoio: | Bolsas no Exterior - Estágio de Pesquisa - Doutorado |
| Processo FAPESP: | 19/12783-6 - Migração eficiente de aplicações científicas e de engenharia de alto desempenho para a nuvem |
| Beneficiário: | Antonio Carlos Guimarães Junior |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |