Schemă aritmetică rapidă complet homomorfă? BFV = bootstrapping lentă, TFHE = aritmetică lentă

Schema BFV este bună pentru a reprezenta o mulțime de numere întregi în interiorul unui polinom și chiar putem opera pe ele individual relativ rapid. Cu toate acestea, bootstrapping-ul pe BFV este imposibil, astfel încât nicio bibliotecă nu îl implementează.

Pe de altă parte, scheme precum TFHE au bootstrapping foarte rapid, dar funcționează pe porți. Această lucrare este cea mai nouă pe care am putut găsi o modalitate de a codifica numerele întregi pe torus: https://www.mdpi.com/2078-2489/12/8/297 dar este nevoie de 0,9 secunde pentru a multiplica un număr întreg de 4 biți, ceea ce este prea mult.Pe BFV, nu pot doar să înmulțesc loturi în același timp, dar înmulțirea durează mult mai puțin (aproximativ 80ms single-core) și valoarea coeficientului (modulul text în clar) poate ajunge la mai mult de 1 milion. Pot chiar să codific un număr de 64 de biți în formă RNS și să-l înmulțesc în BFV pe această multiplicare polinomială de 80 ms.

Deci, există o schemă mai bună care face un bootstrapping rapid și funcționează peste reprezentări de dimensiunea unui cuvânt ale numerelor întregi, nu binare? (sau poate unul care codifică în binar, dar face artihmetic rapid cumva).

Există implementări mai eficiente ale TFHE decât cea pe care o citați. În special, compania Zama are o implementare pe care o numesc Beton, care include

• cod sursă deschisă Rust, care este de asemenea, ambalat ca o "ladă" de rugină, și
• un integrare cu (parte din) Numpy.

Sunt cateva repere ale codului Rust de acum ~ 2 ani, unde pretind ~30ms pentru înmulțiri. Din păcate, nu îmi este clar din acel document câți biți de mesaj pretind pentru benchmark. Eu cred că este $\geq 5$, dar poate fi doar $5$. Oricum, acest lucru este, desigur, mult mai rapid decât ~.9s pentru înmulțiri pe 4 biți.

Rețineți că veți pierde în continuare calitățile de tip SIMD ale BFV. În ciuda acestui fapt, s-ar putea să ajungeți (practic) mai repede, deoarece se pare că Concrete are un backend accelerat de GPU (respectele de referință menționate mai sus au fost înainte de a exista acest backend), astfel încât s-ar putea obține, în mod plauzibil, un grad similar de paralelism prin apelarea la acesta.

Totuși, cu condiția să interpretez corect benchmark-urile, aceasta este o accelerare > 30x față de ceea ce citați (înainte de a face ceva legat de GPU, care este acum o opțiune), deci este plauzibil de interes.

În ceea ce privește bootstrapping-ul BFV, criptosistemul BGV are caracteristici similare cu BFV (ambele sunt scheme „aritmetică rapidă cu SIMD + bootstrapping lentă”) și Reperele HElib conține cod exemplu pentru bootstrapping BGV, care poate fi de interes pentru dvs.