Gadgetnedbrytningen i FHE || Math ∩ Programmering

På sistone har jag studerat Fully Homomorphic Encryption, vilket är den mirakulösa förmågan att utföra godtyckliga beräkningar på krypterad data utan att lära mig någon information om det underliggande meddelandet. Det är den mest omfattande privata datorlösningen som kan existera (och den finns!).

Det första FHE-schemat av Craig Gentry var baserat på idealiska galler och ansågs vara mycket komplext (jag tog mig aldrig tid att lära mig hur det fungerade). Vissa senare scheman (GSW = Gentry-Sahai-Waters) är baserade på matrismultiplikation och är begreppsmässigt mycket enklare. Ännu nyare FHE-scheman bygger på GSW eller använder det som en kärnsubrutin.

Alla dessa scheman injicerar slumpmässigt brus i chiffertexten, och varje homomorf operation ökar bruset. När bruset blir för stort kan du inte längre dekryptera meddelandet, och då och då måste du använda en process som kallas “bootstrapping” som minskar brus. Det tenderar också att vara prestandaflaskhalsen för alla FHE-scheman, och denna flaskhals är anledningen till att FHE inte anses vara praktiskt än.

För att minska bullertillväxten använder många FHE-system som GSW en teknisk konstruktion som kallas för gadgetnedbrytning. Trots det fruktansvärt vaga namnet är det en avgörande begränsning för bullertillväxt. När det dyker upp i en tidning, är det vanligtvis anmärkt som “väl känt i litteraturen”, och detaljerna du behöver för att implementera det utelämnas. Det är en av dessa ämnen.

Så jag ska ge några detaljer. Koden från det här inlägget finns på GitHub.

Binär siffra nedbrytning

För att skapa ett FHE-schema måste du tillämpa två homomorfa operationer på chiffertexter: addition och multiplikation. De flesta FHE-system tillåter en av de två operationerna trivialt. Om chiffertexterna är siffror som i RSA multiplicerar man dem som siffror och det multiplicerar de underliggande meddelandena, men addition är inte känt för att vara möjligt. Om chiffertexter är vektorer som i “Learning With Errors”-schemat (LWE) – grunden för många FHE-scheman – lägger du till dem som vektorer och det lägger till de underliggande meddelandena. (Här är “felet” i LWE synonymt med “slumpmässigt brus”, jag kommer att använda termen “brus”) I LWE och de flesta FHE-scheman döljer en chiffertext det underliggande meddelandet genom att lägga till slumpmässigt brus, och tillägg av två chiffertexter lägger till motsvarande brus. Efter för många oförminskade tillägg kommer bruset att växa så stort att det hindrar meddelandet. Så du slutar beräkna, eller så använder du en bootstrapping-operation för att minska bruset.

De flesta FHE-scheman tillåter dig också att multiplicera en chiffertext med en okrypterad konstant $ A$, men då skalas bruset med en faktor på $ A$, vilket är oönskat om $ A$ är stort. Så du måste antingen begränsa koefficienterna för dina linjära kombinationer med någon övre gräns, eller använda en version av gadgetnedbrytningen.

Den enklaste versionen av gadgetnedbrytningen fungerar så här. Istället för att kryptera ett meddelande $ m \i \mathbb{Z}$, skulle du kryptera $ m, 2m, 4m, …, 2^{k-1} m$ för ett val av $ k$, och sedan för att multiplicera $ A < 2^k$ skriver du de binära siffrorna för $ A = \sum_{i=0}^{k-2} a_ och du beräknar $k-1} a_ \sum_{i=0}^{k-1} a_i \textup{Enc}(2^im)$. Om bruset i varje kryptering är $ E$ och summering av chiffertexter summerar brus, så minskar detta trick brustillväxten från $ O(AE)$ till $ O(kE) = O(\log(A)E)$, till priset av att spåra $ k$ chiffertexter. (Att kalla bruset $ E$ är lite av ett missbruk—i verkligheten är felet samplat från en slumpmässig distribution—men förhoppningsvis förstår du min poäng).

Vissa människor kallar mappningen $ \textup{PowersOf2}(m) = m \cdot (2^0, 2^1, 2^2, \dots, 2^{k-1})$, och för den här artikelns skull låt oss kalla operationen att skriva ett tal $ A$ i termer av dess binära siffror $ \textup=(a_s,t) ={Bin}(A) a_{k-1})$ (observera att den första siffran är den minst signifikanta biten, dvs. det är en liten endian-representation). Sedan expanderar PowersOf2 och Bin en heltalsprodukt till en punktprodukt, samtidigt som potenserna 2 flyttas från den ena sidan till den andra.

$$\displaystyle A \cdot m = \langle \textup{Bin}(A), \textup{PowersOf2}(m) \rangle$$

Detta inspirerade följande “proof by meme” som jag inte kan motstå att inkludera.

Att räkna ut ett exempel, om meddelandet är $ m=7$ och $ A = 100, k=7$, då $ \textup{PowersOf2}(7) = (7, 14, 28, 56, 112, 224, 448, 896)$ och $ \textup{Bin}(A) = 0,0,$ (0,0,0,$) little-endian), och prickprodukten är

$$\displaystyle 28 \cdot 1 + 224 \cdot 1 + 448 \cdot 1 = 700 = 7 \cdot 2^2 + 7 \cdot 2^5 + 7 \cdot 2^6$$

En generaliserad prylkonstruktion

Man kan generalisera den binära siffrans uppdelning till olika baser, eller till vektorer av meddelanden istället för ett enda meddelande, eller att inkludera en delmängd av siffrorna för varierande approximationer. Jag har funderat över ett FHE-schema som klarar alla tre. I mitt sökande efter klarhet stötte jag på en trevlig artikel av Genise, Micciancio och Polyakov som heter “Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More”, där de anger en bra allmän definition.

Definition: För varje ändlig additiv grupp $ A$, en $ A$-grej av storlek $ w$ och kvalitet $ \beta$ är en vektor $ \mathbf{g} \in A^w$ så att vilket gruppelement som helst $ u \in A$ kan skrivas som en heltalskombination $ u = \sum_{i=1}^w g_i x_i$ där $ \mathbf{x} = (x_1, \dots , x_w)$ har norm som mest.

De huvudsakliga grupperna i mitt fall är $ A = (\mathbb{Z}/q\mathbb{Z})^n$, där $ q$ vanligtvis är $ 2^{32}$ eller $ 2^{64}$, dvs osignerade int-storlekar på datorer för vilka vi får gratis moduloperationer. I det här fallet är en $ (\mathbb{Z}/q\mathbb{Z})^n$-gadget en matris $ G \in (\mathbb{Z}/q\mathbb{Z})^{n \times w}$ och representationen $ x \in \mathbb{Z}^w$ av $ u \in (\/mathbb{mathbb{Z})^s $ u \in (\/mathbb)\{th{th} $ s $ Gx = u$.

Här är $ n$ och $ q$ fixerade, och $ w, \beta$ växlas bort för att göra det valda gadgetschemat mer effektivt (mindre $ w$) eller bättre på att minska brus (mindre $ \beta$). Ett exempel på hur detta skulle kunna fungera visas i nästa avsnitt genom att generalisera den binära siffrans uppdelning till en godtycklig bas $ B$. Detta gör att du kan använda färre siffror för att representera talet $ A$, men varje siffra kan vara så stor som $ B$ och därför är kvaliteten $ \beta = O(B\sqrt{w})$.

En vanlig konstruktion är att konvertera en $ A$-gadget till en $ A^n$-gadget med hjälp av Kronecker-produkten. Låt $ g \in A^w$ vara en $ A$-gadget av kvalitet $ \beta$. Då är följande matris en $ A^n$-gadget av storlek $ nw$ och kvalitet $ \sqrt{n} \beta$:

$$\displaystyle G = I_n \times \mathbf{g}^\top = \begin{pmatrix} g_1 & \dots & g_w & & & & & & & & \\\ & & & g_1 & \dots & g_w & & & & \\\ & & & & & & & \ddots & \dots & & & & & & &_&} &&$

Tomma mellanslag representerar nollor, för tydlighetens skull.

Ett exempel med $ A = (\mathbb{Z}/16\mathbb{Z})$. $ A$-gadgeten är $ \mathbf{g} = (1,2,4,8)$. Denna har storlek $ 4 = \log(q)$ och kvalitet $ \beta = 2 = \sqrt{1+1+1+1}$. Sedan bygger vi för en $ A^3$-gadget

\( G = I_3 \times \mathbf{g}^\top = \begin{pmatrix} 1&2&4&8&&&&&&&&& \\ &&&&1&2&4&8&&&& \\ &&&&&&&&&&&2&2&4&8 \end{pmatrix} \)

Nu givet en vektor $ (15, 4, 7) \in \mathbb{A}^3$ skriver vi den på följande sätt, där varje liten endian-representation är sammanlänkade i en enda vektor.

$$\displaystyle \mathbf{x} = \begin{pmatrix} 1\\ 1\\ 1\\ 1\\ 0\\ 0\\ 1\\ 0\\ 1\\ 1\\ 1\\ 0 \end{pmatrix}$$

Och slutligen,

\( (15, 4, 7) = G \mathbf{x} = \begin{pmatrix} 1 & 2 & 4 & 8 & & & & & & & & \\ & & & & 1 & 2 & 4 & 8 & & & & & \\ & & & & & & & & & & 1 & 2 & 4 & 8}{ pmatrix}{ 1\\1\\1\\1\\0\\0\\\1\\0\\1\\1\\1\\0 \end{pmatrix}\)

För att använda definitionen mer rigoröst, om vi var tvungna att skriva matrisen ovan som en gadget “vektor”, skulle den vara i kolumnordning från vänster till höger, $ \mathbf{g} = ((1,0,0), (2,0,0), \dots, (0,0,8)) \in A^{wn}$. Eftersom vektorn $ \mathbf{x}$ i värsta fall kan vara alla 1:or, är dess norm högst $ \sqrt{12} = \sqrt{nw} = \sqrt{n} \beta = 2 \sqrt{3}$, som påståtts ovan.

En signerad representation i bas B

Som vi har sett byter gadgetnedbrytningen reducering av brus mot en större chiffertextstorlek. Med heltal modulo $ q = 2^{32}$ kan detta finjusteras lite mer genom att använda en större bas. Istället för PowersOf2 skulle vi kunna definiera PowersOfB, där $ B = 2^b$, så att $ B$ delar $ 2^{32}$. Till exempel, med $ b = 8, B = 256$, skulle vi bara behöva spåra 4 chiffertexter. Och gadgetnedbrytningen av talet vi multiplicerar med skulle vara små siffrorna i dess bas-$ B$-representation. Kostnaden här är att den maximala posten för den sönderdelade representationen är 255.

Vi kan finjustera detta lite mer genom att använda en signerad bas-$ B$ representation. Såvitt jag vet är detta inte samma sak som vad datorprogrammerare normalt kallar ett signerat heltal, och det har inte heller något att göra med tvås komplement representation av negativa tal. I stället för de normala bas-$ B$ siffrorna $ n_i \in \{ 0, 1, \dots, B-1 \}$ för ett tal $ N = \sum_{i=0}^k n_i B^i$, väljer den signerade representationen $ n_i \in \{ -B/2, -B/2 + 1, B, s, 1, B, s, 1, B, s, 1, – 1 \}$.

Att beräkna siffrorna är något mer involverat, och det fungerar genom att förskjuta stora koefficienter med $ -B/2$, och “absorbera” effekten av den förändringen till nästa mer signifikanta siffra. T.ex. om $ B = 256$ och $ N = 2^{11} – 1$ (alla 1:or upp till den 10:e siffran), då är den osignerade little-endian bas-$ B$ representationen av $ N$ $ (255, 7) = 255 + 7 \cdot 256$. Motsvarande signerad bas-$ B$ representation subtraherar $ B$ från den första siffran och adderar 1 till den andra siffran, vilket resulterar i $ (-1, 8) = -1 + 8 \cdot 256$. Detta fungerar generellt på grund av följande “lägg till noll”-identitet, där $ p$ och $ q$ är två på varandra följande osignerade siffror i den osignerade bas-$ B$-representationen av ett tal.

$$\displaystyle \begin{align} pB^{k-1} + qB^k &= pB^{k-1} – B^k + qB^k + B^k \\\ &= (pB)B^{k-1} + (q+1)B^k \end{align}$$

Sedan om $ q+1 \geq B/2$, skulle du upprepa och föra 1:an till nästa högre koefficient.

Resultatet av allt detta är att det maximala absoluta värdet av en koefficient för den signerade representationen halveras från den osignerade representationen, vilket minskar brustillväxten till priset av en något mer komplex representation (ur implementeringssynpunkt). En annan bieffekt är att det största representativa antalet är mindre än $2^{32}-1$. Om du försöker tillämpa den här algoritmen på ett så stort antal, skulle den största siffran behöva flyttas, men det finns ingen efterföljare att bära till. Snarare, om det finns $ k$-siffror i den osignerade bas-$ B$-representationen, har det maximala antalet som kan representeras i den signerade versionen alla siffror satta till $ B/2 – 1$. I vårt exempel med $ B=256$ och 32 bitar är den största siffran 127. Formeln för det maximala representerbara heltal är $ \sum_{i=0}^{k-1} (B/2 – 1) B^i = (B/2 – 1)\frac{B^k – 1}{B-1}$.

max_digit = base // 2 - 1
max_representable = (max_digit
    * (base ** (num_bits // base_log) - 1) // (base - 1)
)

En enkel python-implementering beräknar den signerade representationen, med kod kopierad nedan, där $ B=2^b$ är baseoch $ b = \log_2(B)$ är base_log.

def signed_decomposition(
  x: int, base_log: int, total_num_bits=32) -> List(int):
    result = ()
    base = 1 << base_log
    digit_mask = (1 << base_log) - 1
    base_over_2_threshold = 1 << (base_log - 1)
    carry = 0

    for i in range(total_num_bits // base_log):
        unsigned_digit = (x >> (i * base_log)) & digit_mask
        if carry:
            unsigned_digit += carry
            carry = 0

        signed_digit = unsigned_digit
        if signed_digit >= base_over_2_threshold:
            signed_digit -= base
            carry = 1
        result.append(signed_digit)

    return result

I en framtida artikel visar jag hur gadgetnedbrytningen fungerar i en praktisk miljö som kallas nyckelbytevilket gör att man kan konvertera en LWE-chiffertext krypterad med nyckel $ s_1$ till en LWE-chiffertext krypterad med en annan nyckel $ s_2$. Denna operation ökar bruset, och därför används gadgetnedbrytningen för att minska brustillväxten. Nyckelbyte används i FHE eftersom vissa operationer (som bootstrapping) har bieffekten av att byta krypteringsnyckel.

Tills dess!