Kryptografia II stopień

Od definicji bezpieczeństwa do konstrukcji, redukcji i publikacji naukowych.

W15. Kryptografia kwantowa i postkwantowa

QKD używa kanału kwantowego do uzgadniania materiału kluczowego, ale wymaga uwierzytelnionego kanału klasycznego. Nie rozwiązuje samo problemu tożsamości ani ochrony urządzeń końcowych.

QKD: Quantum Key Distribution. Kwantowa dystrybucja klucza. To inna technologia niż kryptografia postkwantowa.

W idei BB84 nadawca koduje losowe bity w losowo wybieranych bazach, a odbiorca mierzy w swoich losowych bazach. Publicznie porównują bazy i zachowują pozycje, w których były zgodne. Próbka służy do oszacowania błędów. Następnie potrzebne są uzgadnianie informacji i wzmacnianie prywatności. Informacja ujawniona przy korekcji musi wejść do rachunku końcowego klucza. Nie wystarczy powiedzieć, że podsłuch „zawsze zostanie wykryty”. Twierdzenie zależy od oszacowań, modelu urządzeń i skończonej liczby próbek.

Kryptografia postkwantowa działa na zwykłych komputerach i uwzględnia przeciwnika kwantowego. Algorytm Shora podważa faktoryzację i DL, także na krzywych. Grover przyspiesza ogólne przeszukiwanie kwadratowo. Koszty realnego ataku nie sprowadzają się jednak do mechanicznego dzielenia każdej tabeli parametrów przez dwa.

Mechanizm	Funkcja	Dokument
ML-KEM	Enkapsulacja klucza	FIPS 203
ML-DSA	Podpis oparty na modułowych kratach	FIPS 204
SLH-DSA	Bezstanowy podpis oparty na haszach	FIPS 205

ML-KEM: Module-Lattice-Based Key-Encapsulation Mechanism. Mechanizm enkapsulacji klucza oparty na kratach modułowych. ML oznacza tu kraty modułowe, a nie uczenie maszynowe.
ML-DSA: Module-Lattice-Based Digital Signature Algorithm. Algorytm podpisu cyfrowego oparty na kratach modułowych.
SLH-DSA: Stateless Hash-Based Digital Signature Algorithm. Bezstanowy algorytm podpisu cyfrowego oparty na funkcjach haszujących.

Intuicja LWE

LWE: Learning With Errors. Problem uczenia z błędami, związany z równaniami zaburzonymi szumem.

LWE rozwijamy jako Learning With Errors, czyli uczenie się z błędami. Publiczna macierz $A$ opisuje współczynniki wielu równań, $s$ jest kolumną tajnych niewiadomych, a $e$ kolumną niewielkich losowych błędów. Obserwujemy $(A,b)$ , gdzie $b=A\cdot s+e$ modulo $q$ . Bez błędu odpowiednio wiele niezależnych równań pozwala odzyskać $s$ przez algebrę liniową. Z błędem powstaje problem zależny od parametrów i rozkładów. To intuicja, nie specyfikacja ML-KEM. Dokładne wymiary i mały rachunek podajemy poniżej.

Klasyczny dowód cofający stan przeciwnika nie przenosi się automatycznie do kwantowej wyroczni losowej. Nie można swobodnie kopiować nieznanego stanu kwantowego.

Zadanie przekrojowe: wybierz standard, wypisz typy i założenie. Oddziel KEM od szyfrowania danych i podpisu. Wskaż, co można zachować podczas migracji.

Źródło historycznego protokołu: Bennett–Brassard, BB84. Standardy w tabeli opisują konkretne algorytmy postkwantowe, nie realizację QKD.

KEM nie jest podpisem ani szyfrem pliku

KEM, czyli mechanizm enkapsulacji klucza, ma trzy algorytmy. Odbiorca tworzy parę $(ek,dk)$ . Nadawca wykonuje $(K,C)\leftarrow\mathsf{Encaps}(ek)$ i wysyła $C$ . Odbiorca wykonuje $K'\leftarrow\mathsf{Decaps}(dk,C)$ . Dla uczciwego szyfrogramu klucze powinny być równe, z błędem określonym przez konstrukcję. Dane użytkownika szyfrujemy osobno przez AEAD, po odpowiednim wyprowadzeniu klucza i związaniu kontekstu.

Klucz sesji nie płynie po strzałce. Jest obliczany po obu stronach. AEAD chroni późniejsze dane. Uwierzytelnianie klucza publicznego pozostaje zadaniem protokołu.

ML-KEM nie uwierzytelnia sam nadawcy ani źródła klucza publicznego. Zastąpienie publicznego klucza napastnika nadal jest możliwe bez ochrony protokołu nadrzędnego. IND-CCA modeluje odporność klucza wyzwania na dozwolone zapytania o inne szyfrogramy. Nie oznacza „wszystkie problemy bezpiecznego połączenia zostały rozwiązane”.

Jak niewielki błąd może chronić, ale nie niszczyć wyniku

LWE (Learning With Errors) dotyczy równań liniowych z niewielkim losowym błędem. W uproszczonym szyfrowaniu pracujemy modulo $q$ . Niech publiczna macierz $A$ ma $m$ wierszy i $n$ kolumn. Sekret $s$ ma $n$ współrzędnych, wektor błędu $e$ ma $m$ , a publiczne $b=A\cdot s+e$ ma $m$ . Symbole oznaczają tu kolumny. Transpozycja $\mathsf T$ zamienia kolumnę w wiersz i odwrotnie. Iloczyn wiersza i kolumny jest sumą iloczynów odpowiadających sobie współrzędnych.

Szyfrując bit $\mu$ , losujemy $r\in\mathbb Z_q^m$ , $e_1\in\mathbb Z_q^n$ i $e_2\in\mathbb Z_q$ z rozkładów małych wartości przewidzianych przez konstrukcję. „Mała” dotyczy reprezentanta całkowitego wokół zera. Symbol $\lfloor q/2\rfloor$ oznacza zaokrąglenie w dół. Bezpieczny dobór rozkładów i wymiarów wymaga osobnej analizy. Poniższe równania ilustrują poprawność. Tworzymy wektor $u$ o $n$ współrzędnych i skalar $v$ :

u=A^\mathsf{T}\cdot r+e_1,\qquad v=b^\mathsf{T}\cdot r+e_2+\lfloor q/2\rfloor\cdot\mu.

Odbiorca odejmuje $s^\mathsf{T}\cdot u$ . Znosi się duży składnik liniowy i pozostaje zakodowany bit z błędem:

v-s^\mathsf{T}\cdot u =\lfloor q/2\rfloor\cdot\mu+e^\mathsf{T}\cdot r+e_2-s^\mathsf{T}\cdot e_1\pmod q.

Dekodujemy według bliższego środka, 0 albo $\lfloor q/2\rfloor$ , z odległością liczoną cyklicznie modulo $q$ . Dla parzystego $q$ błąd o wartości bezwzględnej mniejszej niż $q/4$ wystarcza do rozdzielenia tych dwóch obszarów. Dla nieparzystego modułu uwzględniamy zaokrąglenia. Za mały błąd może osłabić założenie, za duży może powodować błędy deszyfrowania. Parametry dobiera się wspólnie, nie na podstawie samej poprawności kilku przykładów.

Policzmy mały przykład, który nie zapewnia bezpieczeństwa: $q=23$ , $m=n=2$ , $s=(2,1)^{\mathsf T}$ , $e=(1,-1)^{\mathsf T}$ oraz

A=\begin{pmatrix}3&5\\7&2\end{pmatrix},\quad b=\begin{pmatrix}12\\15\end{pmatrix},\quad r=\begin{pmatrix}1\\1\end{pmatrix},\quad e_1=\begin{pmatrix}1\\0\end{pmatrix},\quad e_2=1.

Dostajemy $u=(11,7)^{\mathsf T}$ i $s^{\mathsf T}\cdot u=29\equiv6\pmod{23}$ . Pozostały błąd wynosi $e^{\mathsf T}\cdot r+e_2-s^{\mathsf T}\cdot e_1=-1$ . Ten sam rachunek sprawdza oba możliwe bity:

Bit $\mu$	$v$ modulo 23	$v-s^{\mathsf T}\cdot u$ modulo 23	Bliższy środek
0	5	22	0, odległość cykliczna 1
1	16	10	11, odległość 1

Liczba 22 leży blisko zera na okręgu reszt modulo 23. Zwykła odległość na prostej dawałaby tu błędną intuicję. Sprawdzenie dwóch bitów pokazuje poprawność tego przykładu, nie trudność odtworzenia małego sekretu.

ML-KEM używa struktur modułowych nad pierścieniem wielomianów oraz kompresji. Operacje NTT przyspieszają mnożenie wielomianów. Pełny standard zawiera również transformację do KEM, sprawdzenia wejść i regułę niejawnego odrzucenia niepoprawnego szyfrogramu. Powyższy rachunek wyjaśnia znoszenie składników, ale nie jest implementacją ML-KEM. Specyfikacja: FIPS 203.

NTT: Number-Theoretic Transform. Transformata teorioliczbowa.

Dwie drogi do podpisu postkwantowego

ML-DSA: relacja liniowa jest sprawdzana w strukturze modułowej. Odpowiedź musi mieć właściwe ograniczenia normy. Odrzucanie niektórych kandydatów podczas podpisywania kontroluje rozkład odpowiedzi, aby nie zdradzał sekretu. Nie wolno „przyspieszyć” algorytmu przez usunięcie odrzucania. To nie jest klasyczny Schnorr z podmienioną grupą. FIPS 204 definiuje również kodowanie, zaokrąglanie i informacje pomocnicze.

SLH-DSA: bezpieczeństwo opiera się na funkcjach haszujących. Podpisy jednorazowe i podpisy dla ograniczonej liczby użyć są uwierzytelniane przez strukturę drzew. Ścieżka uwierzytelnienia pozwala przejść od danego liścia do publicznego korzenia. „Bezstanowy” nie oznacza, że pojedynczego klucza jednorazowego można bez ograniczeń używać ponownie. Cała konstrukcja kontroluje wybór i użycie jej składowych. Ceną są inne rozmiary podpisu i koszty niż w rodzinie kratowej. FIPS 205 precyzuje ten podział.

Migracja to także model czasu

Dane o długim okresie poufności mogą być przechwycone dzisiaj i analizowane w przyszłości. Dlatego termin wdrożenia zależy nie tylko od przewidywanej dostępności komputera kwantowego, lecz także od czasu ochrony danych i kosztu zmiany infrastruktury. Dobór profilu hybrydowego wymaga bezpiecznego łączenia sekretów i ochrony negocjacji przed wymuszeniem słabszej wersji. Samo doklejenie dwóch szyfrogramów nie tworzy dowodu bezpieczeństwa. Klasyczne pairingi, BLS i Schnorr z tego kursu nie są postkwantowe.

W16. Szyfrowanie homomorficzne: suma i iloczyn bez klucza

Interfejs szyfrowania z obliczaniem

Do znanego interfejsu szyfrowania dodajemy algorytm oceny funkcji: $\Pi_{\mathrm{HE}}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Eval},\mathsf{Dec})$ . W ogólnym wariancie KeyGen zwraca $(pk,sk,evk)$ , gdzie $evk$ jest jawnym kluczem pomocniczym do obliczeń. W prostych przykładach poniżej osobny $evk$ nie jest potrzebny, więc Eval korzysta z $pk$ i parametrów. W innych systemach ten dodatkowy materiał może być istotny.

Właściciel wykonuje Enc ze swoim kluczem publicznym. Wykonawca otrzymuje szyfrogramy i opis dozwolonej funkcji, wywołuje Eval i zwraca szyfrogram wyniku. Dopiero właściciel uruchamia Dec z $sk$ . Trzeba określić typy szyfrogramów wejściowych i wynikowych oraz klasę dopuszczalnych funkcji. Dodatkowe Eval nie oznacza możliwości wykonania dowolnego programu bez ograniczeń.

Cel. Właściciel szyfruje liczby. Wykonawca oblicza dopuszczalną funkcję na szyfrogramach. Właściciel odczytuje wynik, nie wykonując sam całej funkcji na jawnych danych. Nie chodzi tu o uczenie maszynowe, lecz o podstawowy kontrakt obliczeniowy:

\mathsf{Dec}_{sk}(\mathsf{Eval}_{pk}(f,C_1,\ldots,C_n)) =f(m_1,\ldots,m_n),\qquad C_i=\mathsf{Enc}_{pk}(m_i).

Równość obowiązuje w określonej przestrzeni wiadomości i dla dozwolonej klasy obwodów. W systemach przybliżonych zastępuje ją określone ograniczenie błędu. Poufność wejść nie zmusza wykonawcy do policzenia właściwej funkcji. Szyfrogram zera może być poprawnym szyfrogramem, ale błędną odpowiedzią.

Najpierw dodawanie: ElGamal z wiadomością w wykładniku

Zacznijmy od generatora $g$ grupy rzędu $q$ , sekretu $k\in\mathbb Z_q^*$ i klucza publicznego $K=g^k$ .

ElGamal z wiadomością w wykładniku: algorytmy i przepływ

Ustalamy mały zakres odczytu B. Liczby dodajemy modulo q, ale interpretacja całkowita wymaga braku zawinięcia i wyniku w B. Publiczny klucz K=g^k nie jest tajnym skalarem k.

\Pi=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{EvalAdd},\mathsf{Dec})

\mathsf{Setup}(1^\lambda)

\longrightarrow pp

pp=(G,q,g)

|G|=q,\quad G=\langle g\rangle

Rząd q jest liczbą pierwszą. Ustal kodowania i działania grupy. Dodatkowe funkcje wskazano przy konstrukcji.

\mathsf{KeyGen}(pp)

\longrightarrow (K,k)

k\overset{\$}{\leftarrow}\mathbb Z_q^*,\quad K=g^k

\mathsf{Enc}(pp,K,m)

\longrightarrow (S,T)

r\overset{\$}{\leftarrow}\mathbb Z_q

S=g^m\cdot K^r,\quad T=g^r

\mathsf{EvalAdd}(pp,(S,T),(S\prime,T\prime))

\longrightarrow C_+

C_+=(S\cdot S\prime,T\cdot T\prime)

\mathsf{Dec}(pp,k,(S,T),B)

\longrightarrow m\text{ albo }\bot

Q=S\cdot(T^k)^{-1}

\text{znajdź }m\in B:\ g^m=Q

Jednoznacznie ograniczony logarytm, nie efektywny odczyt dowolnej liczby.

ElGamal z wiadomością w wykładniku

Właściciel danych: $pp,K,k,m,m\prime$

Wykonawca: $pp,K$

Właściciel danych, Enc: dwa wejścia: $C\leftarrow\mathsf{Enc}(K,m)$ $C\prime\leftarrow\mathsf{Enc}(K,m\prime)$
Właściciel danych → Wykonawca: $(C,C\prime)$ Dwa szyfrogramy
Wykonawca, EvalAdd: $C_+=(S\cdot S\prime,T\cdot T\prime)$
Wykonawca → Właściciel danych: $C_+$ Szyfrogram sumy
Właściciel danych, Dec: usuń maskę i odczytaj: $Q=g^{m+m\prime}$ Znajdź wynik w ograniczonym zakresie B.

Wykonawca nie dostaje k. Poufność nie wymusza poprawnego wykonania zleconej funkcji.

Dla małej liczby całkowitej $m$ i świeżego skalaru $r\in\mathbb Z_q$ szyfrogram to $C=(S,T)=(g^m\cdot K^r,g^r)$ . Właściciel usuwa maskę przez $S\cdot(T^k)^{-1}=g^m$ . Wynikiem jest na razie obraz wiadomości w grupie, nie sama liczba $m$ .

Gdy pomnożymy po składowych dwa szyfrogramy $C,C'$ dla $m,m'$ i losowości $r,r'$ , otrzymamy:

(S\cdot S',T\cdot T') =\bigl(g^{m+m'}\cdot K^{r+r'},g^{r+r'}\bigr).

Mnożenie elementów grupy dodaje wiadomości w wykładniku. W punkcie krzywej ta sama operacja będzie dodawaniem. Nie mylmy działania na szyfrogramach z działaniem na ukrytych liczbach.

W zapisie addytywnym niech $K=k\cdot P$ . Dla małej liczby całkowitej $m$ i świeżego skalaru $r$ szyfrujemy:

C=(S,T)=(m\cdot P+r\cdot K,\ r\cdot P).

Posiadacz $k$ oblicza $S-k\cdot T=m\cdot P$ . Aby odzyskać liczbę $m$ , trzeba jeszcze rozwiązać logarytm dyskretny w ograniczonym, małym zakresie. To nie jest metoda odczytywania dowolnego skalaru w dużej grupie. Wykonawca dodaje składowe szyfrogramów i otrzymuje szyfrogram sumy. Mnożenie szyfrogramu przez jawną stałą również jest możliwe. Nie jest tym samym co mnożenie dwóch zaszyfrowanych liczb.

Pairing dodaje jeden poziom mnożenia

Używamy dwóch kluczy $K_1=k_1\cdot P_1$ , $K_2=k_2\cdot P_2$ . Szyfrogram $C_1=(S_1,T_1)$ należy do $G_1^2$ , a $C_2=(S_2,T_2)$ do $G_2^2$ .

Dwa poziomy obliczeń homomorficznych: algorytmy i przepływ

Instancja dydaktyczna z tego rozdziału. Setup wybiera pairing typu 3, generatory P₁,P₂ i ograniczony zakres odczytu. KeyGen losuje niezależne niezerowe k₁,k₂ i publikuje K_i=k_i·P_i. Indeksy Enc oznaczają grupę źródłową, nie liczbę rund.

\Pi=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc_1},\mathsf{Enc_2},\mathsf{EvalMul},\mathsf{Dec_T})

\mathsf{Enc}_i(pp,K_i,m_i)

\longrightarrow C_i\in G_i^2

r_i\overset{\$}{\leftarrow}\mathbb Z_q

S_i=m_i\cdot P_i+r_i\cdot K_i,\quad T_i=r_i\cdot P_i

\mathsf{EvalMul}(pp,C_1,C_2)

\longrightarrow D\in G_T^4

d_{SS}=e(S_1,S_2),\quad d_{ST}=e(S_1,T_2)

d_{TS}=e(T_1,S_2),\quad d_{TT}=e(T_1,T_2)

\mathsf{Dec}_T(pp,k_1,k_2,D,B)

\longrightarrow z\text{ albo }\bot

Q=(d_{SS}\cdot d_{TT}^{k_1\cdot k_2})\cdot(d_{ST}^{k_2}\cdot d_{TS}^{k_1})^{-1}

\text{znajdź }z\in B:\ e(P_1,P_2)^z=Q

Wynik z jest liczbą w małym zakresie, nie dowolnym logarytmem dyskretnym.

Dwa poziomy obliczeń homomorficznych

Właściciel danych: $pp,k_1,k_2,m_1,m_2$

Wykonawca: $pp$

Właściciel danych, Enc₁ i Enc₂: $C_1\in G_1^2,\quad C_2\in G_2^2$
Właściciel danych → Wykonawca: $(C_1,C_2)$ Różne grupy źródłowe
Wykonawca, EvalMul: cztery pairingi: $d_{SS}=e(S_1,S_2),\quad d_{ST}=e(S_1,T_2)$ $d_{TS}=e(T_1,S_2),\quad d_{TT}=e(T_1,T_2)$
Wykonawca → Właściciel danych: $D\in G_T^4$ Wynik w grupie docelowej
Właściciel danych, Dec: zdejmij maski: $Q=(d_{SS}\cdot d_{TT}^{k_1\cdot k_2})$ $\phantom{Q=}\cdot(d_{ST}^{k_2}\cdot d_{TS}^{k_1})^{-1}$
Właściciel danych, Dec: ograniczony odczyt: $e(P_1,P_2)^z=Q$ Szukaj z w ustalonym małym zakresie.

Wykonawca używa tylko szyfrogramów. Wyników

G_{T}

nie podajemy ponownie do pairingu. To obliczanie jednego poziomu iloczynów, nie dowolnego obwodu.

Wykonawca tworzy cztery elementy grupy docelowej:

D=(d_{SS},d_{ST},d_{TS},d_{TT}) =\bigl(e(S_1,S_2),e(S_1,T_2),e(T_1,S_2),e(T_1,T_2)\bigr).

Właściciel znający oba skalary usuwa maski:

Z=\frac{d_{SS}\cdot d_{TT}^{k_1\cdot k_2}} {d_{ST}^{k_2}\cdot d_{TS}^{k_1}} =e(P_1,P_2)^{m_1\cdot m_2}.

Typy argumentów są istotne: $e:G_1\times G_2\to G_T$ . Nie obliczamy $e(D,C_2)$ , ponieważ $D$ nie jest elementem $G_1$ . Komponentowe mnożenie dwóch krotek docelowych dodaje ich ukryte wiadomości. Możemy więc liczyć wiele iloczynów pierwszego poziomu i sumować je, np. $z=x_1\cdot y_1+x_2\cdot y_2$ . Nie możemy dowolnie mnożyć wyników takich iloczynów.

Zaszyfrowany iloczyn skalarny

MCL WebAssembly, BLS12-381. Jedna warstwa iloczynów. Odczyt przez ograniczony logarytm dyskretny.

Pierwszy wektor · x₁Pierwszy wektor · x₂Drugi wektor · y₁Drugi wektor · y₂

Etap	Wynik
Jawny punkt odniesienia	2
Odczyt szyfrogramu	Jeszcze nie wykonano
Testy typów	Jeszcze nie wykonano

Gotowe do rozpoczęcia.

Demonstrator wykonuje powyższą algebrę w lokalnym MCL WebAssembly, BLS12-381. Funkcja wykonawcy otrzymuje tylko szyfrogramy. Klucz jest używany przy odczycie. Jedna strona zna jednak cały stan, więc podział ról jest dydaktyczny, a nie izolowany sprzętowo. Zakres wejść $[-5,5]$ gwarantuje $|z|\le50$ . Odczyt przeszukuje ten ograniczony zakres. Używa porównań elementów grupy, nie odczytu zapamiętanego jawnego wyniku. Rachunek w grupie jest rzeczywisty, lecz ta niewielka implementacja nie jest audytowanym systemem produkcyjnym.

Dlaczego to może być poufne

W źródłowej grupie jest to wariant ElGamala. W typie 3 nie ma efektywnego izomorfizmu pozwalającego swobodnie przenieść każdy punkt między grupami. Odpowiednie założenia DDH w grupach źródłowych umożliwiają argument CPA. Nie należy ujawniać dodatkowego obrazu tego samego sekretu w drugiej grupie bez analizy. Taki obraz może pozwolić pairingiem sprawdzać kandydatów wiadomości. Założenia i publikowane parametry są częścią schematu.

Pairing wyjaśnia poprawność iloczynu. Poufność kompletnego systemu i dozwolonych wyników wymaga osobnego dowodu, uwzględniającego wszystkie udostępnione typy szyfrogramów. Nie jest to IND-CCA szyfrowanie z nieograniczoną usługą deszyfrowania: homomorfizm celowo pozwala modyfikować szyfrogramy.

Herumi i źródła. She-wasm realizuje dwupoziomowe szyfrowanie w WebAssembly. Dostępny jest działający przykład obliczania tabeli krzyżowej i opis interfejsu SHE. Podstawa badawcza to Attrapadung i współautorzy, Efficient Two-level Homomorphic Encryption in Prime-order Bilinear Groups and A Fast Implementation in WebAssembly, ASIACCS 2018. Powyższe demo prezentuje rachunek na szyfrogramach, nie kopię całego API ani profilu parametrów she-wasm. Historyczna konstrukcja Boneha–Goha–Nissima używa innego, złożonego rzędu grup.

SHE: Somewhat Homomorphic Encryption. Szyfrowanie homomorficzne pozwalające wykonać ograniczony zakres obliczeń.
ASIACCS: Asia Conference on Computer and Communications Security. Azjatycka konferencja ACM o bezpieczeństwie komputerów i komunikacji.

Od dwóch poziomów do większej głębokości

W rodzinie BGV wiadomości i błędy są przenoszone przez działania na szyfrogramach. Mnożenie zwiększa złożoność reprezentacji i zużywa budżet błędu. Dobór parametrów, reliniaryzacja i przełączanie modułów umożliwiają ocenę obwodu o zadanej głębokości. Bootstrapping homomorficznie wykonuje odpowiednio przygotowane deszyfrowanie, odświeżając szyfrogram. Wymaga to dodatkowych kluczy ewaluacyjnych i założeń, nie dostępu wykonawcy do jawnego sekretu. Brakerski–Gentry–Vaikuntanathan pokazują konstrukcje poziomowane.

CKKS projektuje się dla obliczeń przybliżonych. Kodowanie, skala i reskalowanie są częścią znaczenia wyniku. Nie można przedstawiać takiego wyniku jako dokładnej arytmetyki całkowitoliczbowej. Cheon–Kim–Kim–Song formalizują tę funkcjonalność. Większa ogólność nie zawsze pomaga: dla samej sumy lub iloczynu skalarnego prostszy mechanizm może realizować dokładnie potrzebny cel.

Powiązania: C14, L8.