密碼學趨勢：找到資訊加密安全性與運算效率的理論最佳解之後
維吉尼亞大學電腦科學院助理教授林偉楷與研究夥伴東北大學博士生Ethan Mook、東北大學電腦科學院助理教授Daniel Wichs找到資訊加密安全性與運算效率的理論最佳解，獲得2023年STOC研討會的最佳論文獎，《量子雜誌》（Quanta Magazine）訪談了他們的突破。
由於密碼學的理論研究涉及CS與數學，專業討論跟外星語沒兩樣，為了科普給一般讀者，林偉楷在登山道上向我講解，我同步進行提問，並寫下故事始末。
保障隱私權的密碼學研究
對於離不開網路的現代人，每天都將關鍵字輸入搜尋引擎，這樣做必然會暴露隱私。例如當我搜尋「搬家」，立刻就被搬家公司、家具家飾、房地產買賣租賃的廣告洗版社群，而且它們根據我的IP位置與更多關鍵字能做出精準的消費誘導，甚至掌握我搬家兵荒馬亂時無暇自炊，送上鄰近餐廳的外送折價券……便利是一體兩面的，如果經營資料庫的科技巨頭把我的住址、作息等個資拿去做不當應用或違背我意願的外洩，那該怎麼辦？
想要保障隱私，第一個解法是先下載整個資料庫，再進行離線搜尋。今天Google的資料量約有2的50次方位元，用速度最快的光纖網路下載這些資料也要耗上一個月，效率不如雇用人力備份，用目前最先進的設備儲存差不多十個貨櫃的體積後，請卡車司機或飛機空運把這十個貨櫃運到你家。
第一個解法不切實際，於是2008年出現了第二個解法－－全同態加密（Fully Homomorphic Encryption，FHE）技術。大家可以這樣理解FHE：當使用者企圖搜尋的標的是x時，FHE會把x加密成c(x)再丟給搜尋引擎。對搜尋引擎而言c(x)是一串亂碼，但它依舊能跑出使用者期待的結果，而且這個結果也受到加密保護，經過解密c(x)的程序後，便會得到搜尋x的結果。
FHE技術聽起來完全解決了隱私問題，但搜尋引擎不知道c(x)是什麼，要找到它的對應結果就要做線性運算。線性運算意味每做一次搜尋都得比對過整個資料庫，如果你用的是Google，就得戳過2的50次方位元的資料，不夠有效率。
這也是為什麼新聞常常以「問Chat GPT一個問題，耗多少度電、用多少公升水」作為標題，提醒大眾網路搜尋不是零成本，虛擬的點擊會實質造成地球環境的負荷。
提升演算法效率的兩難：安全與效率只能擇一？
十幾年來，這個困境令密碼學者絞盡腦汁思考：若不對整個資料庫開地圖砲，是否能以局部的煙霧彈來掩蓋使用者的搜尋意圖。並保證煙霧彈的投放邏輯永遠不會被識破？
為了找到安全牢靠又有效率的解方，密碼學者從兩個面向著手：
- 資料結構
圖書館會將館藏以一套編碼和流水號歸檔，同理，擁有資料庫的科技巨頭也會將它們的資訊排序。「改變資料結構」可以理解為使用者以新的、只有自己理解的編碼邏輯，把原本館藏流水號一到最後一本書重新排序，再拿走自己需要的那一本，讓圖書館的管理員不曉得哪一本書被借走了。
改變資料結構有另一種型態：拆解重組。把每一本書逐章、逐頁、逐句、逐字拆開，使用者再以新的、只有自己理解的邏輯，與其他也被拆開來的書合併，依此類推把整個圖書館的書都拆開重組。使用者拿走一本七拼八湊、內容看似亂七八糟的書，裡面藏著自己想要的篇幅，帶回家進行還原。圖書館的管理員目睹每一本書都被搞得面目全非，就更難推理出使用者的意圖了。
改變資料結構的手法繁多，重新排序和拆解重組混用，或試圖導入第三方來進行其中的步驟，讓加密程度從超簡單到夢魘級困難，但無論資料結構如何改變，沒有永遠不會被破解的方法。
當然我們可以假設「對手是傻瓜」，這顯然跟現實有出入，科技巨頭擁有豐沛的資源雇用大量聰明的腦袋來玩解密遊戲。
- 另闢蹊徑的加密
如果世界上存在絕對安全－－也就是比FHE更安全的加密技術，那只要全力解決效率問題即可。這個假設在2020年左右提出，不乏重量級學者與上古神授投入研究，但目前還無法證實這個神奇演算法存在。
使用FHE時兼顧安全與效率的問題卡關了十餘年，2023年STOC最佳論文則找到數學理論上兼顧兩者的最佳解。
數學不會就是不會！
從多項式證明找到突破口
這個突破口來自另一篇同樣發表於2008年，相較引用數迄今累計破萬的FHE，引用數是10,000開根號，也就是引用數100多次的一元N次多項式證明。
這個相較冷門的一元N次多項式證明想解決的問題大概是：有一個多項式f(X)如下，它是x的N次方加x的N-1次方加……加x的一次方加常數項（x的零次方），這些x的次方項另外乘以Cn、Cn-1、……、C1的正整數。
接著將多項式f(x)除以非常大的整數Q，Q大於N，要怎麼最有效率地求出f(x) 除以Q餘數呢？
這邊必須補充，CS理論使用的數學求的是正整數解，所以餘數可能是1到Q-1。人腦面對這個問題會直接代入數字拆解，或者放棄，畢竟數學不會就是不會。對於程式而言，要找出正確餘數有兩種方法：一是計算N次，花N單位的時間；二是花Q單位的空間建立一張表單，當得知x是多少後，就以一單位的時間查表獲得解答。
乍看之下，這個一元N次多項式只有「省空間費時」、「省時占空間」兩種極端，不過這篇論文的作者以高中程度的數學乾淨俐落地推導出「兼顧時效又省空間」的公式解，這令2022年的密碼學者們眼睛一亮，求多項式餘數的兩難有最佳解，是否意味FHE的安全性與效率兩難有解？
從理論最佳解到解決實務問題的距離
研究團隊處理一連串技術問題後，找到資訊加密安全性與運算效率的理論最佳解－－最佳抽樣數logN的10次方、最佳列表數是N的1.1次方。這個突破十餘年的瓶頸，因此獲得2023年STOC的最佳論文獎。
獲獎的三人決定申請專利開公司做技術轉移，往後打算都躺在家裡撸貓，數比貓毛還多的鈔票……以上三句純屬唬爛，為什麼最佳解不能讓他們發大財？因為他們算出來的是「數學理論的」最佳解，對照實務上Google的資料量約是2的50次方位元，把2的50次方代入N時，便會發現線性運算－－也就是一個一個戳過整個資料庫的演算法，效率沒有比較差。
當然，代入N的數值是2的1000次方時，就會產生顯著的效率差異。在目前可觀測的宇宙中，物理學家估算原子總數約是2的270次方，人類科技還沒抵達一個原子能承載一位元資訊的地步，這也意味著，2的1000次方這樣遠超過宇宙原子量的數字現在只能存在於數學中，最佳解公式尚無法實用。
科學研究的理論總是走在實務前，「相信未來會有更多人投入研究，合作優化這個成果。」林偉楷說，FHE從2008年有了理論架構，到實際且廣泛被應用不過是十幾年的事情，在集體智慧的努力下，密碼學的進步指日可待。
（本文經研究團隊成員編審，授權發布）
