Literatür Taraması

BGV: Brakerski-Gentry-Vaikuntanathan Şeması

Brakerski, Gentry ve Vaikuntanathan 2012 yılında “(Seviyeli) Önyüklemesiz Tam Homomorfik Şifreleme [BGV]1 makalesinde daha sonradan BGV Şeması olarak adlandırılacak bir şema önerdi. BGV bir seviyeli tamamen homomorphic şifreleme (Leveled Fully Homomorphic Encryption)(LFHE) şemasıdır, yani şemanın parametreleri şemanın değerlendirebildiği devrelerin derinliğine (polinom olarak) bağlıdır.

Güvenlik parametresi bir pozitif tam sayı \(L\) olan bir homomorfik şifreleme şemaları ailesi \( \{\varepsilon^{(L)}\; :\; L\in \mathbb{Z}^+ \} \), eğer her \(L\) için, her \(\varepsilon\) için aynı şifre çözme devresini kullanıyorsa, \(\varepsilon^{(L)}\) derinliği en fazla L olan tüm devreleri kompakt bir şekilde değerlendiyorsa ve \(\varepsilon^{(L)}\)’nin algoritmalarının hesaplama karmaşıklığı \(L\)’ye ve (değerlendirme algoritması durumunda) devre büyüklüğüne bağlı (tüm \(L\)’ler için aynı olan) bir polinom ise, bu şema ailesine \(\textbf{seviyeli tamamen homomorphic şifreleme}\) denir.

Yukarıda atıfta bulunulan derinlik, şemanın çarpımsal seviyesinden farklı bir çarpımsal derinliktir. Çarpımsal derinlik, kaç ardışık çarpmanın yapılabileceğidir; çarpımsal seviye ise bir şifreli metin üzerinde gerçekleştirilebilecek toplam çarpma miktarıdır. Mesela, \( x_1\cdot x_2 + x_2 \cdot x_3\) çarpımında çarpımsal derinlik 1, çarpımsal seviye 2’dir. Eğer \( x_1 \cdot x_2 \cdot x_3\) ifadesine bakacak olursak, burada çarpımsal derinliğin de 2 olduğunu görürüz. Çarpımsal seviye, çarpımsal derinliği aşamaz, aksi takdirde şifre çözme başarılı bir şekilde gerçekleştirilemez.

BGV, kullanıcının BGV’nin RLWE( halka hatalar ile öğrenme, Ring Learning With Error) tabanlı bir sürümünü mü yoksa düz LWE ( hatalar ile öğrenme, Learning With Error) tabanlı bir sürümünü mü istediğini seçmesine olanak tanır. RLWE veya düz LWE kullanımı arasındaki temel fark, her ikisi de aynı sonuçları elde ederken, LWE şemasının çalışma süresi RLWE’den daha kötü olduğu için LWE’nin bunu daha kötü performansla yapmasıdır. LWE üzerinden RLWE kullanmanın yanı sıra, gürültü yönetimi için Gentry’nin önyükleme prosedüründen vazgeçerler ve bunun yerine mod değiştirmeyi (modulus switching) kullanırlar.

Mod değiştirmenin arkasındaki ana fikir, özel anahtar \(\mathsf{s}\)’yi bilmeyen, bunun yerine uzunluğuna ilişkin bir sınır bilen bir değerlendiricinin, şifreli metin \(\mathsf{c}\) modulo \(q\)’yu farklı bir şifreli metin modulo \(p\)’ye dönüştürebilmesidir. Şemalarında gürültü seviyesini esasen sabit tutmak için, mod boyutundan ödün vererek ve şemanın kalan homomorfik kapasitesini kademeli olarak feda ederek modül değiştirmeyi kullanırlar.

BGV’nin ayrıntılı bir açıklaması ve tam planın nasıl uygulanacağı [BGV]’de bulunabilir. Burada, yeterli ayrıntıyı sağlayan BGV’nin temel versiyonunu anlatacağız.

Temel BGV şeması 7 ayrı işleve ayrılabilir:

  1. \(\textbf{ParamGen}(\lambda, \mu, b)\): Girdi olarak güvenlik parametreleri \(\lambda\) ve \(\mu\) ve de bir bit \(b\in \{0,1\}\) alır. Eğer \(b=0\) ise RLWE, \(b=1\) ise LWE versiyonunu kullanır. Çıktı olarak \( params = (q,d,n,\chi) \) listesini verir. Burada \(q=q(\lambda) \) bir tek sayı şifreli metin modu, \(d=d(\lambda) \) 2’nin bir kuvveti, \(n=n(\lambda) \) sistemin boyutu, ve \(\chi\) hata örnekleme için kullanılan ayrık Gauss dağılımıdır. RLWE varyantında kullanılan halka, \(R = \mathbb{Z}[x]/(x^d+1)\) yani derecesi \(d\) ve daha düşük olan polinom halkasıdır.
  2. \(\textbf{SecKeyGen}(params)\): Girdi olarak parametre listesi \(params\)’ı alır. Temel şemada gizli anahtar \(\mathsf{sk}\), hata dağılımı \(\chi\)’den örneklenir ve \(R\) halkasına aittir. Yani, \( \mathsf{s}’\leftarrow \chi^n \) ve \( \mathsf{s}'[i] \), \(\mathsf{s}’\)’ın \(i\)’inci katsayısı olmak üzere $$\mathsf{sk} = \mathsf{s} = (1,\mathsf{s}'[1], \dots , \mathsf{s}'[n]) \in R_q^{n+1} .$$
  3. \(\textbf{PubKeyGen}(params,\mathsf{sk} )\): Girdi olarak parametre listesi \(params\) ve \(\mathsf{sk}\) alır. \(\mathsf{sk}\) içerisinden \(\mathsf{s}’\) alınır. \(N = \lceil(2n+1)\;\log{q} \rceil\) olmak üzere, \(R_q\) halkasından tek düze rastgele !!!uniformly random!!! \(N\times n\) boyutunda \(\mathbf{A’}\) matrisi ve \(\mathbf{e} \leftarrow \chi^n\) hata vektörü üretilir. \(\mathbf{b} \leftarrow \mathbf{A’} \mathbf{s’} + 2\mathbf{e} \) alındıktan sonra \(n+1\) sütunlu \( \mathbf{A} \) matrisi, birinci sütunu \(\mathbf{b} \) ve kalan sütünları \(-\mathbf{A’}\) matrisinin sütunları olacak şekilde atanır. \(\textbf{PubKeyGen}\) çıktı olarak \(\textsf{pk} = \mathbf{A} \) verir.
  4. \(\textbf{Enc}(params,\mathsf{pk},m )\): Girdi olarak parametre listesi \(params\), açık anahtar \(\mathsf{pk}\), ve açık metin \(m\in \{0,1\}\) alır. İlk olarak \( m \) \( \mathsf{m} \leftarrow (m,0, \ldots, 0) \in R_q^{n+1} \) şeklinde halkaya gömülür. Daha sonra, rastgele \(\mathsf{r} \leftarrow R_2^{N} \) alınır, ve çıktı olarak şifreli metin \(\mathsf{c} = \mathsf{m} +\mathbf{A}^T \mathsf{r} \in R_q^{n+1} \) verir.
  5. \(\textbf{Dec}(params,\mathsf{sk}, \mathsf{c} )\): Girdi olarak parametre listesi \(params\), gizli anahtar \(\mathsf{sk}\), ve şifreli metin \(\mathsf{c}\) alır. Çıktı olarak \( m \leftarrow \left[[\langle \mathsf{c},\mathsf{s} \rangle]_q\right]_2 \) verir.
  6. \(\textbf{EvalAdd}(\mathsf{c_1} ,\mathsf{c_2})\): Girdi olarak aynı gizli anahtar \(\mathsf{sk}\) kullanılarak şifrelenmiş \(\mathsf{c_1}\) ve \(\mathsf{c_2}\) şifreli metinlerini alır. Çıktı olarak \(\mathsf{c_3} \leftarrow (\mathsf{c_1} +\mathsf{c_2}) \mod q \) verir.
  7. \(\textbf{EvalMult}(\mathsf{c_1} ,\mathsf{c_2})\): Girdi olarak aynı gizli anahtar \(\mathsf{sk}\) kullanılarak şifrelenmiş \(\mathsf{c_1}\) ve \(\mathsf{c_2}\) şifreli metinlerini alır. Çıktı olarak \(\mathsf{c_3} \leftarrow (\mathsf{c_1} \times \mathsf{c_2}) \mod q \) verir.

Temel BGV şemasında, şifreli metinler \(\textbf{EvalMult}\)’un bir sonucu olarak büyür. BGV’de bir düz metin üzerinde derecesi \(d\) olan polinom çarpması gerçekleştirirken, elde edilen şifreli metin \(d + 1\) halka elemanına sahiptir. Bu sorun, şifreli metnin yeniden doğrusallaştırılmasıyla hafifletilir.

Yukarıda açıklanan şemayı FHE şemasına çevirmek için şifreli metin üzerinde istenen toplama ve çarpma işlemleri yapıldıktan sonra \(\textbf{Refresh}\) isimli fonksiyon çağrılır. \(\textbf{Refresh}\), esas olarak, mod değiştiren ve ardından ortaya çıkan şifreli metnin şifrelendiği anahtarı değiştiren bir ölçeklendirme fonksiyonu çağırır. Yenilemeyi önyükleme prosedürüyle birleştirerek bir FHE şeması elde edilebilir.

BGV, harmanlama (batching) konseptiyle şemanın güzel bir optimizasyonunu sunar. Harmanlama işleminin arkasındaki ana fikir, her bir şifreli metne birden çok düz metni paketlemektir, böylece bir fonksiyon homomorfik olarak bir girdi üzerinde homomorfik olarak değerlendirilirken hemen hemen aynı verimlilikle birden çok girdi üzerinde değerlendirilebilir.

Bu bölümde bahsedilen üç şemadan BGV’nin, harmanlama prosedürleri nedeniyle aynı işlemi birden fazla şifreli metin üzerinde aynı anda gerçekleştirirken en etkili şema olduğunu eklemeliyiz. Öte yandan, üçü arasında BGV, kullanımı ve doğru şekilde uygulanması en zor olanıdır. Ek olarak, karmaşık tam sayılar veya gerçel sayılar üzerinde değil, yalnızca tam sayılar üzerinde hesaplamalar yapabilir. Bu olumsuz yönlerine rağmen BGV, 2018’de düzenlenen Homomorfik Şifreleme Standardizasyon Çalıştayı sırasında homomorfik şifreleme için önerilen bir şema olarak seçilmiştir.

BFV: Brakerski-Fan-Vercauteren Şeması

2012’de Fan ve Vercauteren [FV]2, Brakerski’nin [B]3 LWE’ye dayalı tamamen homomorfik şifreleme şemasını RLWE’nin güvenlik varsayımı altında çalışacak şekilde değiştirdi. Hem 2’de hem de 3’de, yeniden doğrusallaştırmadan yararlanılır, ancak BFV’nin daha verimli bir yaklaşımı vardır. Ayrıca, 3 ‘in sahip olmadığı bir mod değiştime hilesi sunarak önyükleme prosedürünü basitleştirirler. Bu iyileştirmeler bu bölümün geri kalanında açıklanacaktır.

BFV’deki açık metin uzayı, \(R_t = \mathbb{Z}_t[x]/(x^d+1)\) şeklindedir; burada \(t\), düz metin katsayı modu ve \(d\) açık metin polinom modülüdür. BFV’de bir açık metnin şifrelenmesi, aynı polinom modu \(d\)’ye, ancak farklı bir katsayı modu \(q \gg t\)’ye, yani \(R_q = \mathbb{Z}_q[x]/(x^d+1)\) halkasından iki polinomla temsil edilen bir şifreli metin üretir. BGV şemasındakine benzer bir şekilde, bu şifreli metinlerin boyutu, homomorfik çarpma gerçekleştirildiğinde büyür. Şifreli metnin şemanın destekleyebileceğini aşmasını önlemek için, bir \(n + 1\) derece polinomu \(n\) derecesine geri getirmek için bir yeniden doğrusallaştırma prosedürü kullanılır. Tamamen homomorfik hesaplamalar, BFV tarzında aşağıdaki şekilde gerçekleştirilebilir:

\(\lambda\) bir güvenlik parametresi, \(q\) bir tam sayı polinom modu, \( d=2^n \) bir derece, \(t\), \(1 < t < q\) olacak şekilde bir tam sayı polinom katsayısı modu olsun. Bunların üzerine, \( \delta = \lfloor q/t \rfloor \), \(T\) yeniden doğrusallaştırma prosedüründe kullanılacak anahtarın üretiminde kullanılacak pozitif bir tam sayı, \( l= \lfloor \log_T(q) \rfloor \), \(R_2\) katsayıları \( \{ -1,0,1 \}\) kümesinde olan bir polinom halkası, ve \(\chi\) hata örneklemesi için kullanılacak tam sayılar üzerinde standart sapması \(\sigma\) olan bir ayrık Gauss dağılımı olsun.

BFV şeması 8 ayrı fonksiyona ayrılabilir:

  1. \(\textbf{PrivateKeyGen}(\lambda)\): Girdi olarak güvenlik parametresi \(\lambda\) ve rastgele örneklenen \(\mathbf{s}\leftarrow R_2 \) alır. Çıktı olarak gizli anahtar \( \mathsf{sk} = \mathbf{s} \) verir.
  2. \(\textbf{PublicKeyGen}(\mathsf{sk} )\): Girdi olarak gizli anahtar \(\mathsf{sk}\)’yı alır. \( \mathbf{s} \leftarrow \mathsf{sk} \) atamasını yaptıktan sonra \(\mathbf{a} \leftarrow R_q\) ve \(\mathbf{e} \leftarrow \chi\) örneklemeleri alınır. Çıktı olarak açık anahtar olarak \( \mathsf{pk} \leftarrow ([-\mathbf{a} \cdot \mathbf{s} + \mathbf{e}]_q, \mathbf{a} ) \) ikilisini verir.
  3. \(\textbf{EvaluationKeyGen}(\mathsf{sk} ,T )\): Girdi olarak gizli anahtar \(\mathsf{sk}\)’yı ve yukarıda belirtilen \(T\) sayısını alır. \( \mathbf{s} \leftarrow \mathsf{sk} \) atamasını yaptıktan sonra, \(i= 0, \dots, l\) için \( \mathbf{a_i}\leftarrow R_q\) ve \(\mathbf{e_i} \leftarrow \chi\) örneklenir. Çıktı olarak \(i= 0, \dots, l\) için değerlendirme anahtarları \( \mathsf{evk} \leftarrow ([-(\mathbf{a_i} \cdot \mathbf{s} + \mathbf{e_i}) + T^i\cdot \mathbf{s}^2]_q, \mathbf{a_i} ) \) ikililerini verir.
  4. \(\textbf{Encrypt}(\mathsf{pk} ,\mathbf{m} )\): Girdi olarak açık anahtar \( \mathsf{pk} \) ve bir ileti \( \mathbf{m} \in R_t \) alır. Önce, \( \mathbf{p_0} \leftarrow \mathsf{pk}[0] \) ve \( \mathbf{p_1} \leftarrow \mathsf{pk}[1] \) olarak açık anahtar ikiye bölünür. Daha sonra rastgele olarak \(\mathbf{u},\mathbf{e_1}, \mathbf{e_2} \leftarrow \chi\) örneklenir. Çıktı olarak aşağıdaki şifreli metini verir. \[ \mathbf{ct} = \left( [\delta \cdot \mathbf{m}+\mathbf{p_0} \mathbf{u} + \mathbf{e_1}]_q , [\mathbf{p_1} \mathbf{u} + \mathbf{e_2}]_q \right) \]
  5. \(\textbf{Decrypt}(\mathsf{sk} ,\mathbf{ct} )\): Girdi olarak gizli anahtar \( \mathsf{sk} \) ve bir şifreli metin \( \mathbf{ct}\) alır. Önce, \( \mathbf{s} \leftarrow \mathsf{sk} \), \( \mathbf{c_0} \leftarrow \mathbf{ct}[0] \) ve \( \mathbf{c_1} \leftarrow \mathbf{ct}[1] \) atamaları yapılır. Daha sonra, açık metin aşağıdaki gibi hesaplanır ve döndürülür. \[ \mathbf{m’} = \left[ \left\lfloor \frac{t\cdot [\mathbf{c_0} + \mathbf{c_1}\cdot \mathbf{s}]_q }{q} \right\rceil \right]_t \]
  6. \(\textbf{Add}(\mathbf{ct_0} ,\mathbf{ct_0} )\): Girdi olarak iki adet şifreli metin \( \mathbf{ct_0}, \mathbf{ct_1} \) alır. Çıktı olarak aşağıdaki toplam şifreli metnini verir. \[ \mathbf{ct’} = ( \mathbf{ct_0}[0] + \mathbf{ct_1}[0] , \mathbf{ct_0}[1] + \mathbf{ct_1}[1] ) \]
  7. \(\textbf{Multiply}(\mathbf{ct_0} ,\mathbf{ct_0} )\): Girdi olarak iki adet şifreli metin \( \mathbf{ct_0}, \mathbf{ct_1} \) alır. Çıktı olarak aşağıdaki işlemlerden sonra çarpım şifreli metni \(\mathbf{ct’}\) verir. \[ \mathbf{c_0} = \left[ \left\lfloor \frac{t\cdot \mathbf{ct_0}[0] \cdot \mathbf{ct_1}[0] }{q} \right\rceil \right]_q \] \[ \mathbf{c_1} = \left[ \left\lfloor \frac{t\cdot \left( \mathbf{ct_0}[0] \cdot \mathbf{ct_1}[1] + \mathbf{ct_0}[1] \cdot \mathbf{ct_1}[0] \right)}{q} \right\rceil \right]_q \] \[ \mathbf{c_2} = \left[ \left\lfloor \frac{t\cdot \mathbf{ct_0}[1] \cdot \mathbf{ct_1}[1] }{q} \right\rceil \right]_q \] \[ \mathbf{ct} = \left( \mathbf{c_0} + \sum_{i=0}^{l} \mathsf{evk}[i][0] \mathbf{c_2}^{(i)} \; , \; \mathbf{c_1} + \sum_{i=0}^{l} \mathsf{evk}[i][1] \mathbf{c_2}^{(i)} \right) \]
  8. \(\textbf{Relinearization} \): Relinearization’ın (Yeniden Doğrusallaştırma) asıl amacı, çarpımdan sonra dereceyi tekrar 2’ye düşürmektir. Varsayalım bir çarpım boyutu 3 olan \( (\mathbf{c_0}, \mathbf{c_1}, \mathbf{c_2} )\) şifreli metnini üretti. Bunu, aynı sonuca çözümlenecek boyutu 2 olan şifreli metin \( (\mathbf{c’_0}, \mathbf{c’_1} )\)’e çevirmek için, \(\textbf{EvaluationKeyGen}\) fonksiyonunda yaratılan yeniden doğrusallaştırma anahtarını kullanacağız. İlk akla gelen hesap \[ \mathbf{c’_0} = [ \mathbf{c_0} + \mathsf{evk}[0] \mathbf{c_2} ]_q \textrm{ ve } \mathbf{c’_1} = [ \mathbf{c_1} + \mathsf{evk}[1] \mathbf{c_2} ]_q \] olacaktır. Ne yazık ki, \( \mathbf{c_2}\)’nin katsayıları en fazla \(q\) olabileceği için şifre çözme başarısız olacaktır. Bunun yerine, \( \mathbf{c_2}\)’yi yukarıdaki denklemlerde kullanmadan önce, aşağıdaki gibi daha küçük bir moda çevirmektir. \[ \mathbf{c_2} = \sum_{i=0}^{l} \mathbf{c_2}^{i} T^i \]

CKKS: Cheon-Kim-Kim-Song Şeması

Hem BGV hem de BFV Şemalarının, yalnızca tam sayılar üzerinde hesaplamalar gerçekleştirebilmeleri veya başka bir deyişle, yalnızca boolean, tam sayı veya mod işlemler gibi ayrık hesaplamaları destekleyebilmeleri gibi bir dezavantajı vardır. Çoğu gerçek dünya verisi \( \mathbb{R}\) veya \( \mathbb{C}\) gibi sürekli bir alana ait olduğundan, bu BGV ve BFV şemalarının gerçek dünya uygulamalarının çoğu için pek pratik yapmaz. CKKS Şeması, şifreleme gürültüsünü yaklaşık hesaplamalar sırasında doğal olarak oluşan hatanın bir parçası olarak ele alarak sınırlı hassasiyetle karmaşık sayılar üzerinde hesaplamaya izin vererek bu sorunu çözer.

CKKS Şeması, Cheon, Kim, Kim ve Song tarafından 2017’de yayınlanan “Homorphic Encryption for Aritmetic of Approximate Numbers” makalesinde önerildi [CKKS]4. Şema başlangıçta HEAAN diye adlandırılıyordu, ancak şemayı homomorfik şifreleme kütüphanesi HEAAN’dan (CKKS/HEAAN uygulayan bir kitaplık) ayırt etmek için, şemanın ismi yazarlarının isminden yola çıkarak CKKS olarak değiştirildi. Homomorfik şifreleme yöntemleri arasında, CKKS şeması, yaklaşık sayılar üzerinde işlem yapmak için daha doğal bir ortam sağladığından dolayı özellikle, tahmin ve makine öğrenimi yöntemlerini uygulamak için çok uygundur.

2017’de ortaya çıkmasından bu yana, kalan sayılar sistemini Residue Number System, RNS) kullanarak CKKS-RNS 5 algoritması ve genelleştirilmiş versiyonu tam CKKS-RNS 6 algoritması literatüre sunulmuştur.

\(N\) tam sayısı 2’nin bir kuvveti, \(M=N/2\) ve \(\Phi_N(x)= x^M+1\) olmak üzere, \( \mathbb{Q}[x]/\left(\Phi_N(x) \right) \) cisminin (N-th cyclotomic field) tam sayılar halkası \(R= \mathbb{Z}[x]/\left(\Phi_N(x)\right) \) olsun.

Bir CKKS şifreli metni ile \( l=2^k \leq M \) uzunluğundaki bir kompleks vektör şifrelenebilir:
\( \zeta = e^{\pi i /{2l}} \) ve \( m(Y) \in \mathbb{R}[Y]/\left( Y^{2l} +1\right) \) olmak üzere, \( \mathbb{R}[Y]/\left( Y^{2l} +1\right) \) ile \( \mathbb{C}^l \) karmaşık vektörler cismi arasındaki \( \mathbf{Decode} \) halka homomorfizması aşağıdaki gibi tanımlanır.

\[ \mathbf{Decode}(m) = \left( m(\zeta) , m(\zeta^5), \dots , m(\zeta^{4l-3}) \right) \]

\( m(Y) =\mathbf{m} = \left( m_0, \dots , m_{2l-1} \right) \) ve \[ M_l = \begin{bmatrix} 1 & \zeta & \zeta^2 & \cdots & \zeta^{2l-1}\\ 1 & \zeta^5 & \zeta^{5\cdot 2} &\cdots & \zeta^{5\cdot (2l-1)}\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ 1 & \zeta^{4l-3} & \zeta^{(4l-3)\cdot 2} &\cdots & \zeta^{(4l-3)\cdot (2l-1)} \end{bmatrix} \] olarak alınırsa \( \mathbf{Decode}(m) =M_l \cdot \mathbf{m} \) eşitliği elde edilir.

\( \mathbf{Encode} \) fonksiyonu ise \( \mathbf{Decode} \) fonksiyonunun tersi olarak tanımlanır ve \( M_l\) matrisinin tersi ile çarpmaya karşı gelir. \( m(Y) \in \mathbb{R}[Y]/\left( Y^{2l} +1\right) \) şeklindeki açık metin polinomları, \(Y \mapsto X^{M/l} \) dönüşümü ile \(\mathbb{R}[x]/\left(\Phi_N(x)\right) \) bölüm halkasına gömülebilirler.

CKKS şeması 7 ayrı fonksiyona ayrılabilir:

  1. \(\textbf{Setup}(\lambda, \mu, b)\): Girdi olarak güvenlik parametresi \(\lambda\) ve \(2\)’nin tam kuvveti olacak şekilde \( N \) alınır. \( R \) üzerinde, anahtar \( (\chi_{key}) \), hata \( (\chi_{err}) \) ve şifreleme \( (\chi_{enc}) \) için dağılımlar belirlenir. Bu dağılımlar düzgün (uniform) dağılım olarak alınabilir. Taban mod değeri \(p \) ve seviye sayısı \(L\) olmak üzere, şifreli metin mod değerleri \( q_k = p^k\;(1\leq k\leq L) \) belirlenir ve bir \( P \) tam sayısı seçilir.
  2. \(\textbf{KeyGen}()\): Önce, \( \mathbf{s} \in \chi_{key} \) seçilir ve gizli anahtar \(\mathsf{sk} = (1,\mathbf{s} ) \) olarak alınır. Daha sonra \( a \in R_{q_L} = \mathbb{Z}_{q_L} / \left( \Phi_N(x) \right) \) ve \( e \in \chi_{err} \) seçilerek, \( b = -as + e \mod q_L \) işlemi yapılır ve açık anahtar \(\mathsf{pk} = (b,a ) \) olarak belirlenir. Aynı işlemler yapılarak, benzer şekilde \(\mathsf{evk} \) anahtarı (evaluation key, değerlendirme anahtarı) belirlenir.
  3. \(\textbf{Enc}(m)\): Girdi olarak açık metin \( m\) alır. \( r \in \chi_{enc} \) ve \( e_0, e_1 \chi_{err} \) olmak üzere şifreli metin aşağıdaki şekilde verilir.
  4. \(\textbf{Dec}(ct)\): Girdi olarak şifreli metin \( ct\) alır. \( k \) seviyesindeki bir şifreli metin \( ct \) için açık metin \( m= \langle ct , \mathsf{sk} \rangle \mod q_k \) iç çarpımı olarak döndürülür.
  5. \(\textbf{Add}( {ct_1} ,{ct_2} )\): Girdi olarak \( k \) seviyesindeki iki adet şifreli metin \( {ct_1}, {ct_2} \) alır. Çıktı olarak aşağıdaki toplam şifreli metnini verir. \[ {ct_{add}} = {ct_1} + {ct_2} \mod q_k \]
  6. \(\textbf{Mult}( {ct_1} ,{ct_2} )\): Girdi olarak \( k \) seviyesindeki iki adet şifreli metin \( {ct_1}, {ct_2} \) alır. Şifreli metinleri \( {ct_1} = (c_0, c_1) \) ve \( {ct_2} = (c_0′, c_1′) \) diye ayırdıktan sonra \[ (d_0,d_1,d_2) = (c_0 c_0′, c_0 c_1′ + c_0′ c_1, c_1 c_1′) \mod q_k \] hesaplanır ve çıktı olarak aşağıdaki çarpım şifreli metnini verir. \[ {ct_{mult}} = (d_0,d_1) + \lfloor P^{-1} \cdot d_2 \cdot \mathsf{evk} \rceil \mod q_k \]
  7. \(\textbf{RS}(ct) \): Rescale (Yeniden Ölçekleme) fonksiyonu girdi olarak \( k \) seviyesindeki bir şifreli metin \( ct \) alır. Çıktı olarak aşağıda hesaplanan yeniden ölçeklenmiş şifreli metin verilir. \[ ct’ = \lfloor p^{k’-k} \cdot ct \rceil \mod q_{k’} \]

CKKS türü algoritmalarda, şifreli metin mod değeri \( q \) her homomorfik çarpmadan sonra azalır. Dolayısıyla, şifre çözme işlemi mesajın büyüklüğü \( q \) değerinden küçük olduğunda doğru sonucu vermektedir. Bu nedenle, \( q \) değeri bir sonraki çarpma için çok düşük olmadan önce yalnızca belirli sayıda ardışık homomorfik çarpma işlemi yapılabilir.

  1. Brakerski, Zvika & Gentry, Craig & Vaikuntanathan, Vinod. (2011). (Leveled) Fully Homomorphic Encryption without Bootstrapping. Electronic Colloquium on Computational Complexity (ECCC). 18. 111. 10.1145/2090236.2090262. []
  2. Fan, Junfeng & Vercauteren, Frederik. (2012). Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144. https://eprint.iacr.org/2012/144. 2012. [] []
  3. Brakerski, Zvika. (2012). Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. Proceedings of Advances in Cryptology-Crypto. 7417. 10.1007/978-3-642-32009-5_50. [] [] []
  4. Cheon, Jung & Kim, Andrey & Kim, Miran & Song, Yongsoo. (2017). Homomorphic Encryption for Arithmetic of Approximate Numbers. 409-437. 10.1007/978-3-319-70694-8_15. []
  5. Cheon, Jung & Kyoohyung, Han & Kim, Andrey & Kim, Miran & Song, Yongsoo. (2019). A Full RNS Variant of Approximate Homomorphic Encryption: 25th International Conference, Calgary, AB, Canada, August 15–17, 2018, Revised Selected Papers. 10.1007/978-3-030-10970-7_16. []
  6. Kyoohyung, Han & Ki, Dohyeong. (2020). Better Bootstrapping for Approximate Homomorphic Encryption. 10.1007/978-3-030-40186-3_16. []