Apple 拿 Live Caller ID Lookup 當作 Homomorphic Encryption 的範例

上個禮拜 Swift 的 blog 上面發表了 Homomorphic encryption 的 library (其實當作 Apple 發表的比較實際):「Announcing Swift Homomorphic Encryption」。

裡面提到了 Live Caller ID Lookup 這個功能用到了 Homomorphic encryption:

One example of how we’re using this implementation in iOS 18, is the new Live Caller ID Lookup feature, which provides caller ID and spam blocking services. Live Caller ID Lookup uses homomorphic encryption to send an encrypted query to a server that can provide information about a phone number without the server knowing the specific phone number in the request.

傳統實作 Live Caller ID Lookup 的作法是手機將號碼傳回伺服器端,然後伺服器回答相關的資訊,這樣做的缺點是伺服器端的單位就會知道誰打進來。

而以前改善的方式是類似於 k-anonymity 的方式,像是手機端只傳其中幾位數字給伺服器端 (像是收到 0912-345678 的號碼,只傳 0912-345 的部分給伺服器端),然後伺服器端針對符合的 range 給出答案,這樣可以避免伺服器端直接知道哪個號碼打來,但也透漏了比較多的資訊給手機端。

Homomorphic encryption 的重點在於可以對 ciphertext 進行運算,在手機端提供 ciphertext A 給伺服器後,伺服器端拿著 ciphertext A 與資料庫互動,最後也會得到一個 ciphertext B,然後手機端拿回 ciphertext B 後可以解回結果。

不過我沒有很買單就是了,在資料庫是 plaintext 的情況下,是否有機會從 ciphertext A 與資料庫互動的 access pattern 得知更多資訊?畢竟不能是 table scan,不然以 Apple 會拿到的查詢量來說太大了...

算是個嘗試,但是不是 snakeoil 後續可以再看看。

原來 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。