lattice

原來 Fully Homomorphic Encryption 已經被解啦...

在 Hacker News Daily 上看到「IBM Releases Fully Homomorphic Encryption Toolkit for MacOS and iOS; Linux and Android Coming Soon」這個消息，主要是 IBM Research 要放出一些跟 Fully Homomorphic Encryption (FHE) 的 library。

Homomorphic encryption 講的是直接對密文操作：(這邊的 $\cdot$ 是操作，可能是加法，也可能是乘法，或是其他類型)

$C_1 = enc(P_1)$
$C_2 = enc(P_2)$

$enc(P_1 \cdot P_2) = enc(P_1) \cdot enc(P_2) = C_1 \cdot C_2$

也就是說，不需要把 Ciphertext 解成 Plaintext 處理完後再加密回去 (這有安全性與隱私的問題)，而是直接對兩個 Ciphertext 計算就可以了。

之前還在學校學密碼學的時候 (大概 2005 與 2006)，有翻到 Homomorphic encryption 中的 Fully Homomorphic Encryption (FHE) 是尚未被解決的問題，當時的解法都是特殊解。

剛剛因為看到上面那篇文章，查了一下發現原來在 2009 的時候 Craig Gentry 提出了一套方法，用 Lattice-based cryptogtaphy 建構出加法與乘法的操作，也就達成了 FHE 的低標。

查資料的時候發現 1) 他論文只用了十頁 2) 這是他的博班論文，解掉這個 open problem，不過看到他的博班指導教授是 Dan Boneh 好像不意外... XD

(雖然只用了十頁主要還是因為 STOC 篇幅的關係，但扣掉 circuit privacy 的部份，前面在說明建構與證明的過程只用了九頁也是很驚人)

然後接下來的幾年他又跟其他幾位學者改進了不少效能上的問題，在英文版維基百科上可以翻到有好幾個不同世代的 FHE。

Google 與 Cloudflare 測試 Post-Quantum 演算法的成果

這幾年量子電腦的進展不斷有突破，雖然到對於攻擊現有的密碼學看起來還有一段時間，但總是得先開始研究對量子電腦有抵抗性的演算法...

其中 Google Chrome 的團隊與 Cloudflare 的團隊手上都有夠大的產品，兩個團隊合作測試的結果在學界與業界都還蠻重視的：「Real-world measurements of structured-lattices and supersingular isogenies in TLS」、「The TLS Post-Quantum Experiment」。

Google Chrome 這邊是使用了 Canary 與 Dev 兩個 channel，有控制組與兩個新的演算法：

Google Chrome installs, on Dev and Canary channels, and on all platforms except iOS, were randomly assigned to one of three groups: control (30%), CECPQ2 (30%), or CECPQ2b (30%). (A random ten percent of installs did not take part in the experiment so the numbers only add up to 90.)

這兩個演算法有優點也有缺點。一個是 key 比較小，但運算起來比較慢 (SIKE，CECPQ2b)；另外一個是 key 比較大，但是運算比較快 (HRSS，CECPQ2)：

For our experiment, we chose two algorithms: isogeny-based SIKE and lattice-based HRSS. The former has short key sizes (~330 bytes) but has a high computational cost; the latter has larger key sizes (~1100 bytes), but is a few orders of magnitude faster.

We enabled both CECPQ2 (HRSS + X25519) and CECPQ2b (SIKE/p434 + X25519) key-agreement algorithms on all TLS-terminating edge servers.

感覺還是會繼續嘗試，因為這兩個演算法的缺點都還是有點致命...

所以要開始開發 CECPQ2 了...

CECPQ1 是 Google 在研究對抗量子電腦的演算法，作為測試用的演算法，曾經在 Google Chrome 的 54 beta 版 (2016 年) 存活過一段時間，最近又開始在開發新一代的演算法 CECPQ2 了，這次會是基於 TLS 1.3 上測試：「CECPQ2」。

CECPQ2 will be moving slowly: It depends on TLS 1.3 and, as mentioned, 1.3 is taking a while. The larger messages may take some time to deploy if we hit middlebox- or server-compatibility issues. Also the messages are currently too large to include in QUIC. But working though these problems now is a lot of the reason for doing CECPQ2—to ensure that post-quantum TLS remains feasible.

目前對抗量子電腦的演算法好像都跟 Lattice 有關，找時間來補一下基礎理論... @_@