Polska społeczność Octra jest na Telegramie! · Dołącz → t.me/octrapl
octra.pl/historia
historia fhe

50 lat od marzenia
do blockchain.

Fully Homomorphic Encryption zaczęło się od pytania bez odpowiedzi.
Rivest postawił je w 1978. Gentry odpowiedział 31 lat później.

// kliknij kafelek żeby rozwinąć szczegóły

1978 pierwsze pytanie (Rivest)
31 lat otwartego problemu
2009 przełom — Craig Gentry
2024 Octra HFHE na mainnecie
oś czasu

Każde odkrycie stało na barkach poprzedniego.

1978
// punkt zerowy

Rivest, Adleman, Dertouzos — pierwsze pytanie

Trzy lata po RSA — pytanie które pozostanie otwarte przez 31 lat. Czy można obliczać na danych których się nie widzi?

Rok 1978. Ron Rivest właśnie opisał RSA — szyfrowanie które zmieniło internet. Razem z Adlemanem i Dertouzosem opublikował pracę stawiającą fundamentalne pytanie: czy możliwe są "privacy homomorphisms"? Nie wiedzieli jak tego dokonać — zdefiniowali problem i zostawili go następnym pokoleniom.
R.L. Rivest, L. Adleman, M.L. Dertouzos — "On Data Banks and Privacy Homomorphisms", Foundations of Secure Computation, 1978
↓ rozwiń szczegóły
// częściowe odpowiedzi

RSA, ElGamal, Paillier — jedna operacja na raz

Każdy schemat obsługuje albo dodawanie, albo mnożenie. Nigdy obie naraz. Pełne FHE pozostaje nieosiągalne.

RSA (1977) — homomorficzne dla mnożenia. Nie dla dodawania.

ElGamal (1985) — homomorficzne dla mnożenia w grupach cyklicznych.

Paillier (1999) — homomorficzne dla dodawania. Nie dla mnożenia.

Każdy schemat skazany na jedną operację. Pełne FHE pozostaje niedoścignione.
↓ rozwiń szczegóły
1982–2005
2009
// przełom — 31 lat oczekiwania

Craig Gentry — pierwsza pełna konstrukcja FHE

Doktorant ze Stanforda rozwiązuje otwarty problem kryptografii. Dowodzi że FHE jest możliwe. Praktycznie nieużywalne — ale matematycznie bezbłędne.

Craig Gentry, będąc doktorantem na Stanford, publikuje pracę która wstrząsa środowiskiem kryptograficznym. Pierwsza w historii działająca pełna konstrukcja FHE.

Używa krat idealnych i techniki bootstrapping — odświeżanie szumu przed przekroczeniem progu. Praktyczny problem: ~10¹²× wolniejsze od AES. Ale dowód istnienia zmienia wszystko.
C. Gentry — "A Fully Homomorphic Encryption Scheme", Stanford PhD Thesis, 2009. PDF ↗
↓ rozwiń szczegóły
// BGV — praktyczność

Brakerski-Gentry-Vaikuntanathan (BGV)

Ring-LWE zamiast krat idealnych. 1000× szybsze od Gentry. Fundament Microsoft SEAL i HElib.

BGV zastępuje kraty idealne przez Ring-LWE. Wprowadza SIMD batching — wiele wartości w jednym ciphertext. Staje się podstawą Microsoft SEAL, OpenFHE, HElib. Używany produkcyjnie w systemach bankowych i ML inference.
Z. Brakerski, C. Gentry, V. Vaikuntanathan — "(Leveled) FHE without Bootstrapping", ITCS 2012. ePrint ↗
↓ rozwiń szczegóły
2011
2012
// BFV — prostota implementacji

Fan-Vercauteren (BFV)

Uproszczona wersja BGV bez ręcznego zarządzania szumem. Domyślny schemat Microsoft SEAL.

BFV upraszcza BGV — eliminuje ręczne zarządzanie noise budget. Staje się domyślnym schematem Microsoft SEAL. Obsługuje arytmetykę liczb całkowitych z batching.
J. Fan, F. Vercauteren — "Somewhat Practical Fully Homomorphic Encryption", ePrint 2012. ePrint ↗
↓ rozwiń szczegóły
// TFHE — bramki logiczne

TFHE — bootstrapping poniżej 0.1s

Chillotti et al. osiągają ultra-szybkie bootstrapping. Fundament zama.ai i fhEVM. Sekwencyjny z natury.

TFHE działa na poziomie bramek logicznych — bootstrapping <0.1s na bramkę. Wada: sekwencyjny charakter. Aplikacje: zama.ai, Concrete, fhEVM, TFHE-rs. Najbardziej aktywny open-source ekosystem FHE.
I. Chillotti et al. — "Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds", ASIACRYPT 2016. ePrint ↗
↓ rozwiń szczegóły
2016
2017
// CKKS — ML i genomika

CKKS — przybliżona arytmetyka zmiennoprzecinkowa

Akceptowalny błąd jak float64. Idealny dla neural networks i genomiki. Google, IBM, Microsoft.

CKKS akceptuje przybliżone wyniki (jak float64) — idealny dla ML i genomiki. Google do prywatnych obliczeń statystycznych, IBM i Microsoft w systemach enterprise. Podstawa zastosowania FHE w AI.
J.H. Cheon et al. — "Homomorphic Encryption for Arithmetic of Approximate Numbers", ASIACRYPT 2017. ePrint ↗
↓ rozwiń szczegóły
// sprzęt i standaryzacja

HomomorphicEncryption.org, GPU, ASIC

Branżowa standaryzacja. Intel, AMD, NVIDIA pracują nad akceleratorami FHE. FHE zaczyna być realne dla przemysłu.

HomomorphicEncryption.org standaryzuje parametry BGV/BFV/CKKS/TFHE. Intel HEXL (AVX-512), NVIDIA CUDA kernels, dedykowane ASIC. Przejście od badań do enterprise.
↓ rozwiń szczegóły
2019–2022
2024
// HFHE — FHE na blockchainie

Octra HFHE — Hypergraph FHE na mainnecie

Octra zastępuje sekwencyjne kraty strukturą hipergrafu. 17 000 TPS na testnecie. Pierwszy blockchain zaprojektowany od zera pod FHE.

Octra Labs przedstawia HFHE — schemat oparty na hipergrafie zamiast sekwencyjnych kratach. Masowa równoległość. Testnet: 17 000 TPS (nieweryfikowalne zewnętrznie).

Impl: C++ / libpvac (zamknięty kod). Peer review w toku — brak publikacji IACR. Ops: ct_add, ct_sub, ct_gte, ct_and, ct_or, ct_not. Brak ct_mul.
mainnet alpha ⚠ peer review w toku
↓ rozwiń szczegóły
schematy FHE

Cztery schematy. Cztery kompromisy.

Nie ma jednego "FHE" — to rodzina schematów. Każdy optymalizuje inny typ danych i zastosowanie.

BGV

Brakerski, Gentry, Vaikuntanathan · 2011
daneliczby całkowite
błądbrak (dokładne)
batchingSIMD (wektory)
zastosowaniebazy danych, ML inference
impl.Microsoft SEAL, OpenFHE
peer review✓ IACR

CKKS

Cheon, Kim, Kim, Song · 2017
daneliczby zmiennoprzecinkowe
błądakceptowalny (jak float)
batchingSIMD (wektory)
zastosowanieML, genomika, statystyki
impl.Google, IBM, Microsoft
peer review✓ IACR

TFHE

Chillotti, Gama, Georgieva · 2016
danebity / bramki logiczne
błądbrak (dokładne)
bootstrap~0.1s / bit
zastosowanieEVM, smart kontrakty
impl.zama.ai, Concrete, TFHE-rs
peer review✓ IACR

HFHE

Octra Labs · 2024
danect_int, ct_bool
błądbrak (dokładne)
równoległośćmasowa (hipergraf)
zastosowanienative Octra
impl.C++ / libpvac (zamknięty)
peer review⚠ w toku
literatura źródłowa

Cytowane prace naukowe.

Wszystkie kluczowe prace FHE dostępne w repozytorium IACR ePrint lub Stanford Digital Library.

[1]
Rivest, Adleman, Dertouzos (1978) — "On Data Banks and Privacy Homomorphisms", Foundations of Secure Computation. Pierwsze sformułowanie problemu privacy homomorphism.
[2]
Gentry (2009) — "A Fully Homomorphic Encryption Scheme", Stanford PhD Thesis. Pierwsza pełna konstrukcja FHE. PDF ↗
[3]
Brakerski, Gentry, Vaikuntanathan (2011) — "(Leveled) FHE without Bootstrapping", ITCS 2012. Schemat BGV, Ring-LWE, SIMD batching. ePrint ↗
[4]
Fan, Vercauteren (2012) — "Somewhat Practical Fully Homomorphic Encryption". Schemat BFV, podstawa Microsoft SEAL. ePrint ↗
[5]
Chillotti et al. (2016) — "Faster FHE: Bootstrapping in Less Than 0.1 Seconds", ASIACRYPT 2016. Schemat TFHE, bramki logiczne. ePrint ↗
[6]
Cheon, Kim, Kim, Song (2017) — "Homomorphic Encryption for Arithmetic of Approximate Numbers", ASIACRYPT 2017. Schemat CKKS, arytmetyka przybliżona. ePrint ↗
[7]
Octra Labs (2024) — "Hypergraph FHE (HFHE)" — dokumentacja techniczna. Zamknięty kod libpvac. docs.octra.org ↗ (brak niezależnej publikacji IACR)