operațiuni cu un singur slot pe polinom complet homomorf SIMD

Conform https://eprint.iacr.org/2011/133.pdf și multe alte lucrări, există un izomorfism între spațiul polinoamelor și coeficienții săi. Deci, cel puțin în schema BFV, putem face:

$$p(x) = [a_1, a_2, ..., a_3]$$ $$\phi(p(x)) = [\phi(a_1), \phi(a_2), ..., \phi(a_3)]$$

Așadar, aplicarea unei operații la polinom este aceeași cu aplicarea tuturor elementelor, un fel ca SIMD funcționează pe procesoare. Acest lucru este, de asemenea, galizat automorfismul Galois pe unele scheme.

Acum, să presupunem că vreau să operez doar pe al doilea element, așa că găsesc cumva o modalitate de a-l extrage cu o mască de bit și astfel obțin:

$$p_2(x) = [0, \phi(a_2), ..., 0]$$

Acum pot opera $p_2(x)$ a modifica $\phi(a_2)$ oricum vreau eu. Există vreo modalitate de a-l pune înapoi pe $p(x)$ cu modificarile mele? De asemenea, cred că unele operații pe care le fac p_2(x) ar putea face ca celelalte elemente să fie diferite de zero, ceea ce este, de asemenea, o provocare.

Există o modalitate simplă de a face acest lucru. Mai exact, ați menționat deja că aveți o procedură de extragere a mascai de bit. Prin urmare, dat $p(x)$, $p_2(x)$, și $p_2'(x)$ (operațiile dvs. homomorfe aplicate la $p_2$), lăsa $p_3(x)$ fi rezultatul aplicării aceleiași mască de biți la $p_2'$. Apoi, este simplu să verifici asta

$$p(x) - p_2(x) + p_3(x)$$

iti ofera rezultatul dorit.

Acest lucru reduce totul la două proceduri de „extracție cu masca de bit”, evaluarea homomorfă (care pare inevitabil) și câteva completări (care ar trebui să fie ieftine). Apoi, există întrebări firești:

• poate fi suficientă o extracție de masca de bit?
• Cum se poate aplica eficient extracția bitmask?

Dacă slotul pe care doriți să calculați este public, ar trebui să fie suficient să se înmulțească cu o constantă adecvată (cu coeficienți 0/1) polinom, dând o suprasarcină multiplicativă de 1 pentru fiecare extracție de mască de biți. Bitmask-urile private par mai puțin eficiente --- Mă pot gândi la ceva care folosește $O(n)$ înmulțiri (dar cel puțin are adâncimea 1), în esență prin calculul unei înmulțiri a unui boolean 0/1 (criptat) pentru fiecare index pentru a „selecta” indicii potriviți, apoi adăugând totul la final.

Totuși, nu știu cum se compară cele de mai sus cu cele de ultimă generație.

De asemenea, merită menționat că, dacă operațiunile dvs $p_2(x)$ do nu depind de celelalte coordonate $\phi(a_i)$ (dar poate pur și simplu să le „suprascrie”), se poate elimina una dintre (și anume prima) operațiuni de extragere a mască de biți. Totuși, aceasta depinde de funcția specială pe care o evaluați.