Do not claim, show me the proof：記一個困擾了我小一年的問題

01-31

題注

更新：密碼學交流群的朋友們說，更快速的方法是利用FFT，而且還可以並行加速。因為本質上我們計算的是卷積結果，FFT後到做乘法即可。才疏學淺，拜服！

Do not claim, show me the proof.

這是我和知乎密碼學交流群共同的群主@玄星同學日常交流時，他常常提到的一句話。在本篇專欄中，我也想把這句話送給所有做密碼學，乃至其他數學或計算機科學相關的朋友們。很多時候，所看到的問題並沒有想像的那麼簡單。

當然了，我這個問題可能根本就不難，可能好多人都知道，我比較白痴了？但我確實是不知道… 而且我諮詢了很多周圍的人，大家也都不知道。因此，看起來這確實是一個似乎很簡單，但解決起來卻沒那麼輕鬆的問題，特別適合證明@玄星同學態度的好問題。因此我這裡也想把這個問題分享給大家。

本篇專欄還要特別感謝一個人，就是我實驗室的師弟海文同學。我是在一次很偶然的機會中和他討論了這個問題，當時我們也都沒有想到一個比較好的解決方法。不曾想，海文同學把這個問題一直留在了腦海中，並在閱讀論文的過程中不斷尋找問題的答案。直到上周五，海文同學終於興高采烈的告訴我，他在一個論文中找到了這個問題的解決方法！至此，這個困擾了我將近一年的問題終於在海文同學的幫助下得到了解決~ 特別感謝海文同學長時間以來的努力。因此，我也希望在我的專欄中向關注我動向的朋友們推薦這個將要入學讀研究生，來自數學學院的小夥子，未來主要做Lattice-Based Cryptography以及Fully Homomorphic Encryption。相信經過未來幾年的錘鍊，他一定至少可以超過我，成為年輕一代應用密碼學的傑出人才。各位業界的大佬們，求關注他哈~

本專欄文章的相關代碼已經同步到我的CloudCrypto密碼學函數庫中：GitHub - liuweiran900217/CloudCrypto: A library for cryptographic primitive implementations for Cloud Storage applications.。相關代數問題解決方法的核心代碼位於：

src/main/java/cn/edu/buaa/crypto/algebra/HornerRule.javan

對應密碼學原語實現的核心代碼位於：

src/main/java/cn/edu/buaa/crypto/encryption/ibbe/del07n

對應密碼學原語的使用例子位於：

src/test/java/com/example/encryption/ibben

如果有需要代碼的朋友，請自行瀏覽或下載上述代碼。如果覺得我寫的能讀，懇請留個star，讓更多需要的朋友們看見，沒準可以幫助他們解決更多的問題呢？

題圖來自：http://pic.baike.soso.com/p/20140430/20140430141100-761898745.jpg。其他圖片為本人自繪。

背景

先來回顧一下所遇到問題的背景。這部分屬於現代密碼學的科普，如果覺得不太好理解的話可以跳過… 如果試著理解一下的話，有助於了解問題是如何引入的。不過，這部分內容不可避免地有不少公式，看著會令人頭大…

早在2014年，我在導師的指導下開始著手構造一個被稱為分層基於身份的廣播加密（Hierarchical Identity-Based Broadcast Encryption，HIBBE）[1,2]。從這個密碼學原語的名字上就可以看出，想構造這個密碼學原語，肯定要參考諸如基於身份的加密（Identity-Based Encryption，IBE）[3,4]、廣播加密（Broadcast Encryption，BE）[5,6]、分層基於身份的加密（Hierarchical Identity-Based Encryption，HIBE）[7,8]，以及基於身份的廣播加密（Identity-Based Broadcast Encryption，IBBE）[9]。

前面所有的密碼學原語都還好說，但這最後一個IBBE理解起來可是讓我犯了難，因為這個方案的構造中用到了一個看起來特別簡單，但是細想起來缺覺得無從下手的問題。而正是這個問題，使得我一直無法正確實現IBBE方案。無法實現IBBE的話，那我的Crypto庫豈不是有很多遺憾了…

在闡述遇到的核心問題之前，我們先來簡單聊聊什麼叫做IBBE。朋友們最熟知的公鑰加密體制是RSA了。RSA允許接收方運行密鑰生成演算法（Key Generation，KeyGen）生成一個公鑰（Public Key，PK）和一個私鑰（Secret Key，SK）。接收方把公鑰公開，這樣任何人都可以用公鑰加密（Encrypt），只有擁有私鑰的接收方才能夠解密（Decrypt）。現在我們把這個問題擴展一下：如果接收方不止有1個人，而是有好多好多人，如何同時給他們發送加密信息呢？

最簡單的方法是按照下圖所示，每個人都公開自己的公鑰，加密時候用不同的公鑰給不同的人加密。這種方法最大的缺點是，加密結果的長度，也就是密文（Ciphertext，CT）長度和接收者人數相關，接收者人數越多，密文長度越長。如果團體人數過多的話，這種方法的效率就不太高了。

解決這個問題的方法是引入BE的概念。在BE中，接收方組成一個小群體。我們找一個可信第三方（一般叫做Dealer），由它來生成公鑰，並且給小群體中的每個人發送不同的私鑰。發送方此時只運行一次加密演算法，然後把這一份密文同時發送給所有人。如果密文長度和接收者人數數量無關，或者說密文長度為常數的話，就可以一次給很多很多人發送加密信息，大大降低通信的開銷。同時，廣播加密進一步可以選擇接收者人數。比如我的加密信息可以只允許編號為1、3、5的用戶解密，那麼編號為2、4等的其他用戶雖然也有自己的私鑰，但即使它們聯合起來也無法解密信息。這種加密方法在有線電視信號、音視頻信息訂閱中有著廣泛的應用。

BE看起來已經足夠好了，但是還有問題：因為群體中每個人有一個編號，發送者進行加密時需要知道群體中每個人的編號對應的是多少。但用編號標示一個人多麼不方便啊。最好的方法是，每個人的編號是一個有意義的字元串，比如這個人的名字，這個人的郵箱什麼的。不過，有意義的字元串的情況個數太多了，我們這時候讓Dealer事先執行Setup演算法，產生公鑰和一個稱為主私鑰（Master Secret Key，MSK）的東西。每一個用戶加入群體的時候，就用自己的名字什麼的向Dealer申請私鑰。這時候，Dealer運行KeyGen演算法，用主私鑰生成各個用戶對應的私鑰。加密的時候，發送方利用公鑰，和每個人的名字作為參數運行加密演算法。這就是IBBE的概念了。有關IBBE的具體內容，可以看看我在《密碼學報》灌水的一篇論文《選擇密文安全的基於身份的廣播加密方案》（http://www.jcr.cacrnet.org.cn:8080/mmxb/EN/article/downloadArticleFile.do?attachType=PDF&id=74），這是個中文論文，寫的更系統一些。

由於我們可以在有意義的字元串中增加諸如時間信息、次數信息等等有意義的信息，因此IBBE天生也帶有撤銷的功能。舉個例子，Dealer可以要求每個申請私鑰的人拿到的都是「姓名+日期」所對應的私鑰，比如Alice拿到的是"Alice20160805"所對應的私鑰。第二天，加密所用的信息統一變成"Alice20160806"，這樣一來，前面一天的私鑰就作廢了。

這麼一看，IBBE的功能簡直強大的不要不要的。2007年，Cécile Delerablée基於雙線性群（Bilinear Group）構造了第一個IBBE方案。朋友們也不用太糾結雙線性群是什麼，簡單來說就是，這個東西涉及到3個代數群： $mathbb{G}_1,mathbb{G}_2,mathbb{G}_T$ ，還有一個函數 $e(cdot,cdot):mathbb{G}_1 times mathbb{G}_2 rightarrow mathbb{G}_T$ 就好了。我們著重來看看這個方案的構造。這裡我們只回顧Setup演算法和Encrypt演算法就夠了。方案的構造沿用我自己《密碼學報》論文的描述。

$(PK,MSK) leftarrow textsf{Setup}(lambda, m)$ 。首先生成一個滿足安全常數 $lambda in mathbb{N}$ 的雙線性群 $(p, mathbb{G}_1, mathbb{G}_2, mathbb{G}_T, e)$ 。隨後，演算法隨機選擇元素 $g overset{R}{leftarrow} mathbb{G}_1$ ， $hoverset{R}{leftarrow} mathbb{G}_2$ ， $gamma overset{R}{leftarrow} mathbb{Z}_p$ ，並選擇一個安全的哈希函數 $H:{0,1}^* rightarrow mathbb{Z}_p$ 。主私鑰為 $MSK=(g,gamma)$ ，公鑰為 $PK=left(w,v,h,h^{gamma}, ldots, h^{gamma^m}right)=left(g^{gamma}, e(g, h), h,h^{gamma}, ldots, h^{gamma^m}right)$ 。
$(CT,K)leftarrow textsf{Encrypt}(PK,S)$ 。給定公鑰PK以及廣播身份集合 $S={ID_1, cdots, ID_s}$ ，其中 $s leq m$ ,加密演算法隨機選擇 $koverset{R}{leftarrow}mathbb{Z}_p$ ，計算密文為 $C_1 = w^{-k}$ ， $C_2=h^{k cdot prod_{i=1}^{s}(gamma + H(ID_i))}$ 。封裝的會話密鑰為 $K=v^k$ 。

好了，看到這裡我想問個問題： $C_2$ 怎麼求？這裡面有兩個比較坑的地方。

有的朋友說了，這不簡單嘛，所有的參數都給出了，直接求就可以了啊。這就是第一個比較坑的地方。在加密演算法中，我們是不知道 $gamma$ 具體值的。因此，h指數上面的東西似乎求不了？怎麼辦呢？

如果你看到這裡沒有想明白這個問題，請暫停一下，想明白以後再繼續往下看。

如果你想明白了這個問題，那麼你一定會為 $prod_{i=1}^{s}(gamma + H(ID_i))$ 的展開式發愁了。而一直困擾我的也就是這個問題了。

問題

我們把這個問題再一般化一點。實際上，我們要解決的問題是這個：

$x^n+a_{n-1}x^{n-1}+cdots+a_1x+a_0 = prod_{i=1}^{n}(x + b_i)$ ，給定所有的 $b_i$ ，求每一個 $a_i$ 。這個問題看上去特別的簡單，很像二項式展開啊有沒有？的確， $a_1$ 和 $a_{n-1}$ 的計算非常簡單。然而，其他的似乎就沒那麼直觀了，我們有：

$a_0=b_1b_2cdots b_n=prod_{i=1}^{n}b_i$ ，

$a_1=b_2b_3 ldots b_n + b_1b_3 ldots b_n + cdots + b_1b_2ldots b_{n-1}$

...

$a_{n-1}=b_1 + b_2 + cdots + b_n = sum_{i=1}^{n}{b_i}$ 。

實際上，上述這些多項式還有個名字，叫做基本對稱多項式（Elementary Symmetric Polynomials，ESP）。基本對稱多項式後在數學中的很多領域都得到了應用。然而，即使是維基百科（Elementary symmetric polynomial）也沒有提到這個多項式求值的方法。我們先不談具體的演算法。我們來分析一下：如果硬算的話，需要多少次加法運算和多少次乘法運算。

加法運算次數很容易得到。

$a_0$ 需要 $C_n^n-1=0$ 次加法；
$a_1$ 需要 $C_n^{n-1}-1=n-1$ 次加法；
...
$a_i$ 需要 $C_n^{n-i}-1$ 次加法；

因此加法運算總次數為： $sum_{i=0}^{n-1}{(C_n^{n-i}-1)}=2^{n} -n-1$ 。

乘法運算次數也是類似的。

$a_0$ 需要 $C_n^0(n-1)=n-1$ 次乘法；
$a_1$ 需要 $C_n^1(n-2)=n(n-2)$ 次乘法；
...
$a_i$ 需要 $C_n^i(n-1-i)$ 次乘法；

因此乘法運算總次數為： $sum_{i=0}^{n-1}{C_n^{i}(n-1-i)}$ 。

可以看到，即使是加法運算也已經是指數級的了，乘法運算次數甚至比加法運算還要多。如果這是真的，就意味著IBBE方案隨著廣播用戶數量的增加，演算法的複雜度也將以指數級增長，因此這根本就不是一個高效的演算法。難道，AISACRYPT上的論文有這麼明顯的錯誤嗎？是否存在一種高效的演算法，可以讓我們快速求解 $a_0,ldots,a_{n-1}$ 呢？

解決

這個問題我一直都沒有找到有效的演算法，直到上周五，海文師弟說他在PKC 2010上的一篇論文的附錄部分找到了這個演算法[10]。由於師弟是做Fully Homomorphic Encryption（FHE）的，因此他會時常閱讀相關的論文。一看論文的名字《Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Size》就知道，這也是個FHE的論文了。

在論文[10]的第20頁，作者提到了一句話：

To compute the $S$ symmetric polynomials on (the encryptions of) $s_1$ bits we proceed in a recursive manner, essentially using Horner』s Rule to compute the last $S+1$ coefficients of the product $prod_{i=1}^{s_1}{(b_icdot x + 1)}$ 。

這不正是我們要解決的問題嗎！不過，所謂的Horners Rule又是什麼呢？這個所謂的Horners Rule，又叫做秦九昭演算法，是幾百年前中國數學家秦九昭提出的一種多項式快速求值方法。19世紀，英國數學家William George Horner重新發現並提出了這個演算法，所以才叫Horners Rule。

Horners Rule解決的問題是求解高次多項式 $f(x)=a_nx^n + a_{n-1}x^{n-1}+cdots+a_1x+a_0$ 在某個點 $x=x_0$ 處值的快速演算法。如果直接從多項式本身求 $x=x_0$ 處值的話，很顯然需要 $O(n)$ 次加法和 $O(n^2)$ 次乘法，速度很慢。Horners Rule的方法利用了一個迭代關係：

$f(x)=a_0+x(a_1+x(a_2+cdots+x(a_{n-1}+a_nx)))$

因此，我們可以依次可以從括弧最裡面開始進行迭代求值，即依次求

$c_{n-1}=a_{n-1}+a_nx_0$

$c_{n-2}=a_{n-2}+a_{n-1}c_{n-1}$

$c_{1}=a_{1}+a_2c_2$

$c_{0}=a_{0}+a_1c_1$

最後的 $c_0$ 就是我們要求的 $f(x_0)$ 。如果按照這種方式計算，只需要進行 $O(n)$ 次加法和 $O(n)$ 次乘法即可，大大降低了計算量。

Horners Rule能夠降低求解高次多項式的計算量的原因在於充分利用了迭代關係，那麼，能否找到類似的迭代關係，從而解決我們的問題呢？實際上，基本對稱多項式也有類似的關係。很容易可以看出， $a_i$ 是從n個 $b_j$ 中依次保留n-i個 $b_j$ 後相乘再相加的結果，因此我們稱 $a_i$ 是n元n-i次基本對稱多項式，記為 $ESP(n, n-i)$ 。對於n元k次基本對稱多項式，其迭代關係如下：

$[{ESP(n,k) = }left{ {begin{array}{*{20}{c}}n {ESP(n - 1,k) + {b_n}}&{k = 1} n {{b_n}ESP(n - 1,k - 1)}&{n = k} n {ESP(n - 1,k) + {b_n}ESP(n - 1,k - 1)}&{n > k} nend{array}} right.]$

看起來有點麻煩？我們用下面的圖來描述就好了：

每一個豎線代表一次加法，每一個斜線代表一次乘法，所乘的內容就是 $b_i$ 了。而最後一行就是我們想得到的結果。圖中可以清晰的看出，所需要的運算量為 $O(n^2)$ 次加法和 $O(n^2)$ 次乘法。原來，論文沒有騙我們…

實現

有了迭代關係，代碼的實現異常簡單，直接看圖說話即可：

/**n * Created by Weiran Liu on 2016/8/22.n *n * Given coefficients of n fundamental polynomials, computes the coefficients of the extended n-degree polynomial.n *n * The algorithm is called Horners Rule, or Qin Jiu Zhao algorithm.n * The detailed algorithm is shown in the paper:n * Nigel P. Smart, Frederik Vercauteren. Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes.n * PKC 2010, pp. 420 - 443, 2010.n *n * @author Hanwen Feng <A HREF="mailto:feng_hanwen@buaa.edu.cn"> (feng_hanwen@buaa.edu.cn) </A> andn * Weiran Liun */npublic class HornerRule {n /**n * Compute n coefficients for n-degree polynomials by given n elementary coefficientsn * @param elementaryCoefficientn * @return n coefficientsn */n public static Element[] ComputeEfficients(Pairing pairing, Element[] elementaryCoefficient) {n int n = elementaryCoefficient.length;n Element[] allCoefficients = new Element[n+1];n //set a_{n} to be 1n allCoefficients[n] = pairing.getZr().newOneElement().getImmutable();n //set all other efficients to be initially zeron for (int i = 0; i < n; i++) {n allCoefficients[i] = pairing.getZr().newZeroElement().getImmutable();n }n for (int k = 0; k < n; k++) {n for (int i = n - k - 1; i < n - 1; i++) {n allCoefficients[i] = allCoefficients[i].add(allCoefficients[i + 1].mulZn(elementaryCoefficient[k])).getImmutable();n }n allCoefficients[n-1] = allCoefficients[n-1].add(elementaryCoefficient[k]).getImmutable();n }n return allCoefficients;n }n}n

總結

很多看起來很顯然的東西，可能都經不起推敲。看似我們懂了，其實還是有很多不懂，甚至根本沒有理解的地方。學習也好，工作也罷，還是知其然又知其所以然比較好。開始的時候真的要做到刨根問底，不要以訛傳訛哦！

參考文獻

[1] Weiran Liu, Jianwei Liu, Qianhong Wu, Bo Qin. Hierarchical Identity-Based Broadcast Encryption. ACISP 2014, pp. 242-257, 2014.

[2] Weiran Liu, Jianwei Liu, Qianhong Wu, Bo Qin, Yan Li. Practical Chosen-Ciphertext Secure Hierarchical Identity-Based Broadcast Encryption. International Journal of Information Security, 2016, 15(1): 35-50.

[3] Adi Shamir. Identity-Based Cryptosystems and Signature Schemes. CRYPTO 1984, pp. 47-53, 1984.

[4] Dan Boneh, Matt Franklin. Identity-Based Encryption from the Weil Pairing. CRYPTO 2001, pp. 213-229, 2001.

[5] Amos Fiat, Moni Naor. Broadcast Encryption. CRYPTO 1993, pp. 480-491, 1993.

[6] Dan Boneh, Craig Gentry, Brent Waters. Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys. CRYPTO 2005, pp. 258-275, 2005.

[7] Jeremy Horwitz, Ben Lynn. Towards Hierarchical Identity-Based Encryption. EUROCRYPT 2002, pp. 466-481, 2002.

[8] Craig Gentry, Alice Silverberg. Hierarchical ID-Based Cryptography. ASIACRYPT 2002, pp. 548-566, 2002.

[9] Cécile Delerablée. Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys. ASIACRYPT 2007, pp. 200-215, 2007.

[10] Nigel P. Smart, Frederik Vercauteren. Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Size. PKC 2010, pp. 420-443, 2010.