學習同態加密

Ⅰ 區塊鏈中現代密碼學

1983年 - David Chaum描述的盲簽
1997年 - Adam Back發明的HashCash（工作證明制度的一個例子）
2001年 - Ron Rivest，Adi Shamir和Yael Tauman向加密社區提出了環簽名
2004年 - Patrick P. Tsang和Victor K.提出使用環簽名系統進行投票和電子現金;
2008年 - 由Satoshi Nakamoto出版的Bitcoin白皮書
2011年 - 比特幣系統中的匿名分析，Fergal Reid和Martin Harrigan
2012 - 目的地址比特幣匿名（CryptoNote中的一次性地址）。

安全多方計算起源於1982年姚期智的百萬富翁問題。後來Oded Goldreich有比較細致系統的論述。

姚氏百萬富翁問題是由華裔計算機科學家、圖靈獎獲得者姚啟智教授首先提出的。該問題表述為：兩個百萬富翁Alice和Bob想知道他們兩個誰更富有，但他們都不想讓對方知道自己財富的任何信息。該問題有一些實際應用：假設Alice希望向Bob購買一些商品，但她願意支付的最高金額為x元；Bob希望的最低賣出價為y元。Alice和Bob都非常希望知道x與y哪個大。如果x>y，他們都可以開始討價還價；如果z<y，他們就不用浪費口舌。但他們都不想告訴對方自己的出價，以免自己在討價還價中處於不利地位。

該方案用於對兩個數進行比較，以確定哪一個較大。Alice知道一個整數i；Bob知道一個整數j, Alice與B0b希望知道究竟i>=j還是j>i，但都不想讓對方知道自己的數。為簡單起見，假設j與i的范圍為[1，100】。Bob有一個公開密鑰Eb和私有密鑰Db。

安全多方計算（Secure Multi-Party Computation）的研究主要是針對無可信第三方的情況下, 如何安全地計算一個約定函數的問題. 安全多方計算在電子選舉、電子投票、電子拍賣、秘密共享、門限簽名等場景中有著重要的作用。

同態加密（Homomorphic Encryption）是很久以前密碼學界就提出來的一個Open Problem。早在1978年，Ron Rivest, Leonard Adleman, 以及Michael L. Dertouzos就以銀行為應用背景提出了這個概念[RAD78]。對，你沒有看錯，Ron Rivest和Leonard Adleman分別就是著名的RSA演算法中的R和A。

什麼是同態加密？提出第一個構造出全同態加密（Fully Homomorphic Encryption）[Gen09]的Craig Gentry給出的直觀定義最好：A way to delegate processing of your data, without giving away access to it.

這是什麼意思呢？一般的加密方案關注的都是數據存儲安全。即，我要給其他人發個加密的東西，或者要在計算機或者其他伺服器上存一個東西，我要對數據進行加密後在發送或者存儲。沒有密鑰的用戶，不可能從加密結果中得到有關原始數據的任何信息。只有擁有密鑰的用戶才能夠正確解密，得到原始的內容。我們注意到，這個過程中用戶是不能對加密結果做任何操作的，只能進行存儲、傳輸。對加密結果做任何操作，都將會導致錯誤的解密，甚至解密失敗。

同態加密方案最有趣的地方在於，其關注的是數據處理安全。同態加密提供了一種對加密數據進行處理的功能。也就是說，其他人可以對加密數據進行處理，但是處理過程不會泄露任何原始內容。同時，擁有密鑰的用戶對處理過的數據進行解密後，得到的正好是處理後的結果。

有點抽象？我們舉個實際生活中的例子。有個叫Alice的用戶買到了一大塊金子，她想讓工人把這塊金子打造成一個項鏈。但是工人在打造的過程中有可能會偷金子啊，畢竟就是一克金子也值很多錢的說… 因此能不能有一種方法，讓工人可以對金塊進行加工（delegate processing of your data），但是不能得到任何金子（without giving away access to it）？當然有辦法啦，Alice可以這么做：Alice將金子鎖在一個密閉的盒子裡面，這個盒子安裝了一個手套。工人可以帶著這個手套，對盒子內部的金子進行處理。但是盒子是鎖著的，所以工人不僅拿不到金塊，連處理過程中掉下的任何金子都拿不到。加工完成後。Alice拿回這個盒子，把鎖打開，就得到了金子。

這裡面的對應關系是：盒子：加密演算法盒子上的鎖：用戶密鑰將金塊放在盒子裡面並且用鎖鎖上：將數據用同態加密方案進行加密加工：應用同態特性，在無法取得數據的條件下直接對加密結果進行處理開鎖：對結果進行解密，直接得到處理後的結果同態加密哪裡能用？這幾年不是提了個雲計算的概念嘛。同態加密幾乎就是為雲計算而量身打造的！我們考慮下面的情景：一個用戶想要處理一個數據，但是他的計算機計算能力較弱。這個用戶可以使用雲計算的概念，讓雲來幫助他進行處理而得到結果。但是如果直接將數據交給雲，無法保證安全性啊！於是，他可以使用同態加密，然後讓雲來對加密數據進行直接處理，並將處理結果返回給他。這樣一來：用戶向雲服務商付款，得到了處理的結果；雲服務商掙到了費用，並在不知道用戶數據的前提下正確處理了數據；

聚合簽名由Boneh等人提出，主要是通過聚合多個簽名為一個簽名，來提高簽名與驗證的效率。要對多個用戶的數據進行簽名，聚合簽名能夠極大地降低簽名計算復雜度。CL就是聚合簽名。

零知識證明過程有兩個參與方，一方叫證明者，一方叫驗證者。證明者掌握著某個秘密，他想讓驗證者相信他掌握著秘密，但是又不想泄漏這個秘密給驗證者。

雙方按照一個協議，通過一系列交互，最終驗證者會得出一個明確的結論，證明者是或不掌握這個秘密。

對於比特幣的例子，一筆轉帳交易合法與否，其實只要證明三件事：

發送的錢屬於發送交易的人
發送者發送的金額等於接收者收到金額
發送者的錢確實被銷毀了
整個證明過程中，礦工其實並不關心具體花掉了多少錢，發送者具體是誰，接受者具體是誰。礦工只關心系統的錢是不是守恆的。

zcash 就是用這個思路實現了隱私交易。

零知識證明的三條性質對應：

（1）完備性。如果證明方和驗證方都是誠實的，並遵循證明過程的每一步，進行正確的計算，那麼這個證明一定是成功的，驗證方一定能夠接受證明方。
（2）合理性。沒有人能夠假冒證明方，使這個證明成功。
（3）零知識性。證明過程執行完之後，驗證方只獲得了「證明方擁有這個知識」這條信息，而沒有獲得關於這個知識本身的任何一點信息。

只有環成員，沒有管理者，不需要環成員之間的合作，簽名者利用自己的私鑰和集合中其他成員的公鑰就能獨立的進行簽名，不需要其他人的幫助，集合中的其他成員可能不知道自己被包含在了其中。
環簽名可以被用作成一種泄露秘密的方式，例如，可以使用環形簽名來提供來自「白宮高級官員」的匿名簽名，而不會透露哪個官員簽署了該消息。 環簽名適用於此應用程序，因為環簽名的匿名性不能被撤銷，並且因為用於環簽名的組可以被即興創建。

1）密鑰生成。為環中每個成員產生一個密鑰對（公鑰PKi，私鑰SKi)
2）簽名。簽名者用自己的私鑰和任意n個環成員的公鑰為消息m生成簽名a
3）簽名驗證。簽名者根據環簽名和消息m，驗證簽名是否是環中成員所簽。如果有效就接收，如果無效就丟棄。

群簽名的一般流程

盲數字簽名（Blind Signature）簡稱盲簽名——是一種數字簽名的方式，在消息內容被簽名之前，對於簽名者來說消息內容是不可見的。1982年大衛·喬姆首先提出了盲簽名的概念。盲簽名因為具有盲性這一特點，可以有效保護所簽署消息的具體內容，所以在電子商務和電子選舉等領域有著廣泛的應用。

類比例子：對文件簽名就是通過在信封里放一張復寫紙，簽名者在信封上簽名時，他的簽名便透過復寫紙簽到文件上。

所謂盲簽名，就是先將隱蔽的文件放進信封里，而除去盲因子的過程就是打開這個信封，當文件在一個信封中時，任何人不能讀它。對文件簽名就是通過在信封里放一張復寫紙，簽名者在信封上簽名時，他的簽名便透過復寫紙簽到文件上。

一般來說，一個好的盲簽名應該具有以下的性質：

不可偽造性。除了簽名者本人外，任何人都不能以他的名義生成有效的盲簽名。這是一條最基本的性質。
不可抵賴性。簽名者一旦簽署了某個消息，他無法否認自己對消息的簽名。
盲性。簽名者雖然對某個消息進行了簽名，但他不可能得到消息的具體內容。
不可跟蹤性。一旦消息的簽名公開後，簽名者不能確定自己何時簽署的這條消息。
滿足上面幾條性質的盲簽名，被認為是安全的。這四條性質既是我們設計盲簽名所應遵循的標准，又是我們判斷盲簽名性能優劣的根據。

另外，方案的可操作性和實現的效率也是我們設計盲簽名時必須考慮的重要

因素。一個盲簽名的可操作性和實現速度取決於以下幾個方面：

1,密鑰的長度；
2,盲簽名的長度；
3,盲簽名的演算法和驗證演算法。
盲簽名具體步驟
1,接收者首先將待簽數據進行盲變換，把變換後的盲數據發給簽名者。
2,經簽名者簽名後再發給接收者。
3,接收者對簽名再作去盲變換，得出的便是簽名者對原數據的盲簽名。
4,這樣便滿足了條件①。要滿足條件②，必須使簽名者事後看到盲簽名時不能與盲數據聯系起來，這通常是依靠某種協議來實現的。

Ⅱ 零知識證明

https://arxiv.org/abs/1906.07221

零知識簡潔的非交互知識論證（zk SNARK）是一種真正巧妙的方法，可以在不透露任何其他信息的情況下證明某件事是真的，然而，為什凱談么它盯叢碰首先是有用的呢？

零知識證明在無數應用中是有利的，包括:

關於私人數據的證明聲明:

匿名授權：

匿名付款：

外包計算：

盡管表面上聽起來很棒，但底層方法是數學和密碼學的「奇跡」，自 1985 年在主要著作「互動式證明系統的知識復雜性中引入以來，已經進行了第四個十年的研究 隨後引入了非互動式證明，這在區塊鏈的背景下尤為重要。

在任何零知識證明系統中，都有一個驗證人想要說服驗證人某些陳述是真實的，而不披露任何其他信息，例如，驗證人了解到驗證人的銀行賬戶中有X多個，但沒有其他信息（即，未披露實際金額）。協議應滿足三個屬性：

讓我們從簡單開始，並嘗試證明某些東西，而不必擔心零知識，非交互性，其形式和適用性。

想像一下，我們有一個長度為 10 數組，我們想向驗證者（例如程序）證明所有這些位都設置為 1，即我們知道一個數組，使得每個元素都等於 1。

驗證者一次只能檢查 (即讀取) 一個元素。為了驗證語句，可以通過以某種任意順序讀取元素，並檢查它是否真正等於1，如果是，則在第一次檢查後該語句的置信度為10%，或者如果該位不等於1，則語句完全無效。驗證者必須進入下一輪，直到他獲得足夠的信心。在一些情況下，可以信任證明者並且只需要50% 置信度，在需要95% 置信度的其他情況下，必須檢查所有單元。很明顯，這種證明協議的缺點是，必須進行與元素數量成比例的檢查數量，如果我們考慮數百萬個元素的數組，這是不切實際的。

讓我們考慮多項式，有一個曲線對應於多項式： 。多鄭蠢項式有一個有利的性質，即如果我們有兩個不相等的次數最多為 d 的多項式，它們相交的點不超過 d。 例如，讓我們稍微修改原始多項式 。如果我們想找到兩個多項式的交點，我們需要將它們等同起來。例如，要找到多項式與x軸相交的位置 (即 )，我們將 等同，並且此類方程的解將是那些共享點: ， 和 。

同樣，我們可以將多項式的原始版本和修改版本等同起來，以找到它們的交點。所得的多項式為1，且有明顯的解 。因此只有一個交點。

對於任意次數為 d 的多項式，任何此類方程的結果始終是另一個次數最多為 d 的多項式，因為沒有乘法可以產生更高的次數。 示例： ，簡化為 。代數基本定理告訴我們，d 次多項式最多可以有 d 個解。因此，我們可以得出結論，任意點處的任何多項式的求值類似於其唯一身份的表示。讓我們在x = 10處評估我們的示例多項式。

事實上，在所有要計算的x選項中，最多隻有3個選項在這些多項式中具有相同的計算，而所有其他選項都會不同。這就是為什麼如果證明者聲稱知道一些多項式 (無論其次數有多大)，他們可以遵循一個簡單的協議來驗證語句:

例如，如果我們考慮 x 從 1 到 的整數范圍，則評估不同的點數為 。 此後，x 意外「擊中」任何 個共享點的概率等於 ，這被認為可以忽略不計。

注意：與無效位檢查協議相比，新協議只需要一輪，並且在聲明中給出了壓倒性的信心（假設 d 充分小於范圍的上限，幾乎 100%）。

這就是為什麼多項式是zk-SNARK的核心，盡管也可能存在其他證明介質。

我們從證明多項式知識的問題開始，然後採用通用方法。 在此過程中，我們將發現多項式的許多其他性質。 到目前為止的討論集中，關注一個弱的證明概念上，即各方必須相互信任，因為還沒有措施來執行協議的規則。 例如，證明者不需要知道多項式，他可以使用任何其他可用的方法來得出正確的結果。 此外，如果驗證者的多項式評估的幅度不大，比如說 10，驗證者可以猜測一個數字，並且它被接受的概率是不可忽略的。 我們必須解決協議的這種弱點，但首先知道多項式意味著什麼？ 多項式可以表示為以下形式（其中 n 是多項式的次數）：

如果有人說他知道一個 1 次多項式（即 ），那意味著他真正知道的是系數 。 此外，系數可以有任何值，包括 0。讓我們說，證明者聲稱知道3次多項式，使得x = 1和x = 2是所有可能解中的兩個。這樣的有效多項式之一是 。

代數的基本定理指出，只要多項式是可解的，任何多項式都可以分解為線性多項式 (即代表直線的1次多項式)。因此，我們可以將任何有效多項式表示為其因子的乘積:

同樣，如果這些因子中的任何一個為零，則整個方程為零，因此，所有 都是唯一的解。我們的示例可以分解為以下多項式:

x的值是：0，1，2，你可以很容易地在多項式的任一形式上檢查這一點。

回到證明者聲稱他知道根為 1 和 2 的 3 次多項式，這意味著他的多項式具有以下形式：

換句話說，(x − 1) 和 (x − 2) 是所討論的多項式的余因子。因此，如果證明者想要證明他的多項式確實具有這些根而不公開多項式本身，則他需要證明他的多項式p(x) 是那些協因子 的乘法，稱為目標多項式，和一些任意多項式h(x) ，即:

換句話說，p(x) 具有t(x) 的所有根。找到h(x) 的自然方法是通過除法 。如果證明者找不到這樣的h(x)，這意味著p(x) 沒有必要的協因子t(x)，在這種情況下，多項式除法將具有餘數。在我們的示例中，如果我們將 除以 。我們得到了無余數的結果 。

使用我們的多項式身份檢查協議，我們可以比較多項式 和 ：

為了將其付諸實踐，讓我們在示例中執行此協議:

相反，如果證明者使用不同的 ，它沒有正確的輔因子，例如 ，那麼：

我們將得到 ，余數為 ，即: 。這意味著證明者必須將余數除以 才能評估 。因此，由於驗證者對x的隨機選擇，因此對於余數 被t(x) 整除的概率很低，因此，如果驗證者將檢查p和h補是整數，這樣的證明將被拒絕。但是，該檢查要求多項式系數也必須是整數。

現在，我們可以在不學習多項式本身的情況下檢查多項式的特定屬性，因此這已經為我們提供了某種形式的零知識和簡潔。盡管如此，此構造仍存在多個問題:

我們將在以下部分解決所有問題。

在上文中，如果將 和 不是明文給出，而是作為黑匣子給出，那將是理想的選擇，因此人們無法篡改協議，但仍然能夠計算對這些模糊值。類似於哈希函數，因此在計算時很難返回到原始輸入。

這正是同態加密的目的。也就是說，它允許對一個值進行加密，並能夠對這種加密應用算術運算。有多種方法可以實現加密的同態特性，我們將簡要介紹一種簡單的方法。

一般的想法是，我們選擇一個基數的自然數g（比如5），然後對一個值進行加密，我們將g乘以該值的冪。例如，如果我們想要加密數字3：

其中125是3的加密。如果要將這個加密的數字乘以2，則將其提高為2的指數:

我們能夠將未知值乘以2，並對其進行加密。我們還可以通過乘法添加兩個加密值，例如3+2：

同樣，我們可以通過除法減去加密的數字，例如5 − 3:

但是，由於基數5是公共的，因此很容易回到秘密數字，將加密的數字除以5，直到結果為1。除法的次數即為明文。

這就是模演算法發揮作用的地方。模運算的思想如下：我們聲明只選擇前n個自然數，即0，1，…，n-1而不是擁有一個無限的數字集。如果任何給定的整數不在這個范圍內，我們將其「環繞」。例如，讓我們先選擇六個數字。為了說明這一點，請考慮一個具有六個相等單位刻度的圓；這是我們的射程。

現在讓我們看看數字8將落在哪裡。 打個比方，我們可以把它想像成一根繩子，它的長度是八個單位。如果我們把繩子連接到圓圈的開頭並開始將繩子纏繞在它周圍，旋轉一圈後，我們還剩下一部分繩子.因此，如果我們繼續這個過程，繩子將在2處結束。

它是模運算的結果。 不管繩子有多長，它總是會停在圓圈的刻度之一處。 因此，模運算將使其保持在一定范圍內。 15 個單位的繩索將在 3 處停止，即 6 + 6 + 3（兩個完整的圓圈，剩餘 3 個單位）。 負數的工作方式相同，唯一的區別是我們將其包裝在相反的方向，對於 -8，結果將是 4。

而且，我們可以進行算術運算，結果總是在n個數的范圍內。 我們現在將使用符號「mod 」來表示數字的范圍。 例如：3 × 5 = 3 (mod 6); 5 + 2 = 1 (mod 6).

此外，最重要的特性是運算順序無關緊要，例如，我們可以先執行所有運算，然後在每次運算後應用模或應用模。例如: 相當於：2 × 4 = 2 (mod 6); 2 − 1 = 1 (mod 6); 1 × 3 = 3 (mod 6).

那到底為什麼有幫助呢？事實證明，如果我們使用模算術，則具有運算結果，回到原始數字是不平凡的，因為許多不同的組合將具有相同的結果: 5 × 4 = 2 (mod 6); 4 × 2 = 2 (mod 6); 2 × 1 = 2 (mod 6).

如果沒有模算術，結果的大小為它的解決方案提供了線索。 否則，這條信息會被隱藏，而常見的算術屬性會被保留。

如果我們回到同態加密並使用模運算，例如模 7，我們將得到：

和不同的指數會有相同的結果:

這是很難找到指數的地方。 事實上，如果模數足夠大，這樣做就變得不可行，而現代密碼學的很大一部分是基於這個問題的「難度」。該方案的所有同態屬性都保留在模領域中：

encryption:
multiplication:
addition:

讓我們明確說明加密函數： ，其中 v 是我們要加密的值。

這種同態加密方案存在局限性，盡管我們可以將加密值乘以未加密值，但我們不能將兩個加密值乘以 (和除以)，也不能對加密值求冪。雖然從第一印象來看是不幸的，但這些屬性將成為zk-SNARK的基石。

有了這樣的工具，我們現在可以評估一個加密隨機值為x的多項式，並相應地修改零知識協議。

讓我們看看如何評估多項式 。正如我們以前建立的那樣，多項式就是知道它的系數，在這種情況下，它們是: 1,-3,2。因為同態加密不允許對加密值求冪，所以我們必須得到從1到3的x冪的加密值: ， ， ，這樣我們可以對加密多項式求值如下:

作為這些操作的結果，我們在我們未知的某個 x 處對我們的多項式進行了加密。 這是一個非常強大的機制，並且由於同態特性，相同多項式的加密計算在加密空間中總是相同的。我們現在可以更新協議的先前版本，對於d次多項式:

Verifier:

Prover:

Verifier:

由於證明者對s一無所知，因此很難提出不合法但仍匹配的評估。

雖然在這樣的協議中，證明者的敏捷性是有限的，但他仍然可以使用任何其他方法來偽造證明，而無需實際使用所提供的 s 冪的加密，例如，如果證明者聲稱僅使用 2 次冪 和 有一個令人滿意的多項式 ，這在當前協議中無法驗證。

多項式的知識是其系數 。 我們在協議中「分配」這些系數的方式是通過對秘密值 s 的相應加密冪求冪（即 ）。 我們已經在選擇 s 的加密冪時限制了證明者，但這種限制並未強制執行，例如，可以使用任何可能的方法來找到滿足方程 的任意值 和 並將它們提供給驗證者而不是 和 。 例如，對於一些隨機 ， 和 ，其中 可以從提供的 s 的加密冪計算。 這就是為什麼驗證者需要證明僅使用 s 的冪的加密來計算 和 而沒有別的。

讓我們考慮一個1次多項式的基本例子，該多項式具有一個變數和一個系數 ，相應地，s的加密 。我們正在尋找的是確保只有s的加密，即 ，被一些任意系數c同態「乘以」，而不是其他任何東西。所以對於任意的c，結果必須是 形式。

一種方法是要求對另一個移位的加密值與原始值一起執行相同的操作，充當「校驗和」的算術模擬，確保結果是原始值的取冪。這是通過引入的指數知識假設Knowledge-of-Exponent Assumption (或KEA) 來實現的，更確切地說:

Alice有一個值a，她希望Bob指數到任何冪，唯一的要求是只有這個a可以指數，沒有別的，以確保她：

因為 Bob 無法從元組 中提取 ，因此推測 Bob 可以產生有效響應的唯一方法是通過以下過程：

最終，這樣的協議向Alice提供了一個證據，證明Bob確實將a乘以他已知的某個值，並且他不能進行任何其他操作，例如乘法、加法，因為這將消除 移位關系。

在同態加密上下文中，冪運算是加密值的乘法。我們可以在簡單的單系數多項式 的情況下應用相同的構造：

這種結構限制證明者僅使用提供的加密 s，因此證明者可以僅將系數 c 分配給驗證者提供的多項式。 我們現在可以將這種單項多項式方法縮放為多項多項式，因為每個項的系數分配是單獨計算的，然後同態地「相加」在一起。 因此，如果向證明者提供 s 的加密冪以及它們的移位值，他可以評估原始多項式和移位多項式，其中必須進行相同的檢查。 特別是對於 d 次多項式：

對於我們之前的示例多項式 ，這將是：

現在我們可以確定，驗證程序除了使用驗證程序提供的多項式外，沒有使用任何其他方法，因為沒有其他方法來保持 移位。此外，如果驗證者希望確保在驗證者的多項式中排除一些s的冪，例如j，他將不提供加密 及其移位 。

與我們一開始的相比，我們現在有了一個健壯的協議。 然而，無論加密如何，零知識屬性仍然存在一個明顯的缺點：雖然理論上多項式系數 可以有很大范圍的值，但實際上它可能非常有限（上例中為 6），這意味著 驗證者可以暴力破解有限范圍的系數組合，直到結果等於證明者的答案。 例如，如果我們考慮每個系數的 100 個值的范圍，則 2 次多項式將總共有 100 萬個不同的組合，考慮到蠻力將需要不到 100 萬次迭代。 此外，即使在只有一個系數且其值為 1 的情況下，安全協議也應該是安全的。

因為驗證器只能從驗證器發送的數據中提取關於未知多項式p（x）的知識，所以讓我們考慮那些提供的值（證明）： 。他們參與以下檢查：

gp=gh（多項式p（x）有t（x）的根）

（gp）α=gp′t（s）（使用正確形式的多項式）

問題是我們如何改變證據，使支票仍然有效，但無法提取任何知識？從上一節可以得出一個答案：我們可以用一些隨機數δ（δ）來「移位」這些值，例如（gp）δ。現在，為了提取知識，首先需要找到被認為不可行的δ。此外，這種隨機化在統計學上與隨機性是無法區分的。

為了保持關系，讓我們檢查驗證者的檢查。證明者的值之一位於方程式的每一側。因此，如果我們用相同的 δ 「移動」 它們中的每一個，方程必須保持平衡。

具體地，證明者對隨機 δ 進行采樣，並用g α p(s) δ gh(s) δ 對其證明值求冪，並提供給驗證者進行驗證:

(gp)δ = gh δ t(s) (gp)δ α = gp′ δ

合並後，我們可以觀察到支票仍然有效：

注意: 零知識是多麼容易被編織到建築中，這通常被稱為 「免費」 零知識。

到目前為止，我們有一個互動式零知識方案。為什麼會這樣？由於該證明僅對原始驗證者有效，其他任何人（其他驗證者）都不能信任同一證明，因為：

因此，為了證明語句（在這種情況下是多項式的知識），需要與每個驗證者進行單獨的交互。

雖然互動式證明系統有其使用案例，例如，當證明人只想說服一個專用的驗證人（稱為指定驗證人），這樣證明就不能再用於向其他人證明同一陳述時，當一個人需要同時（例如，在區塊鏈等分布式系統中）或永久地說服多方時，這是非常有效的。驗證方需要始終保持在線，並對每個驗證方執行相同的計算。

因此，我們需要的秘密參數是可重用的，公開的，可信的和不可濫用的。

讓我們首先考慮在秘密 (t(s)，α) 產生後如何保護它們。我們可以像驗證者在發送給證明者之前對s的指數進行加密一樣對它們進行加密。然而，我們使用的同態加密不支持兩個加密值的乘法，這對於驗證檢查以使t(s) 和h以及p和 α 的加密相乘都是必需的。這就是密碼配對的地方。

密碼配對（雙線性映射）是一種數學構造，用函數 , 給定來自一組數字的兩個加密輸入（例如， ，允許將它們確定地映射到不同數字輸出集中的乘法表示，即， 。

由於源和輸出編號集合不同，因此配對的結果不能用作另一個配對操作的輸入。我們可以將輸出集 (也稱為 「目標集」) 視為來自 「不同的宇宙」。因此，我們不能將結果乘以另一個加密值，並通過名稱本身建議我們一次只能乘以兩個加密值。在某種意義上，它類似於一個散列函數，它將所有可能的輸入值映射到一組可能的輸出值中的一個元素，並且它不是平凡可逆的。

注意: 乍一看，這種限制只能阻礙依賴的功能，具有諷刺意味的是，在zk-SNARK情況下，它是該方案的安全性所擁有的最重要的屬性。

配對函數 的一個基本（技術上不正確）的數學類比是說明有一種方法可以「交換」每個輸入的基數和指數，這樣基數 在轉換過程中會被修改成指數，例如 。 然後將兩個「交換的」輸入相乘，使得原始 a 和 b 值在相同的指數下相乘，例如：

因此，由於在「交換」期間使用結果 在另一個配對（例如， ）中改變了鹼基，因此不會產生所需的加密乘法 。配對的核心屬性可以用等式表示：

e(ga, gb) = e(gb, ga) = e(gab, g1) = e(g1, gab) = e(g1, ga)b= e(g1, g1) ab= . . .

從技術上講，配對的結果是目標集不同生成器g下原始值的加密產物，即 。因此，它具有同態加密的特性，例如，我們可以將多對的加密產物添加到一起：

注意：加密配對利用橢圓曲線來實現這些屬性，因此從現在起，符號 將表示曲線上的生成器點，該點將被添加到自身 次，而不是我們在前面部分中使用的乘法群生成器。

有了加密配對，我們現在可以設置安全的公共和可重用參數。讓我們假設我們信任一個誠實的一方來生成秘密 s 和 α。一旦 α 和具有相應 α 位移的 s 的所有必要冪被加密（gα, gsi , gαsi for i in 0, 1, ..., d），必須刪除原始值。

這些參數通常被稱為公共參考字元串common reference string或CRS。CRS生成後，任何prover和verifier都可以使用它來執行非互動式零知識證明協議。雖然不重要，但CRS的優化版本將包括對目標多項式target polynomial 的加密評估。

此外，CRS分為兩組（對於 中的 ）：

由於能夠乘以加密值，verifier可以在協議的最後一步檢查多項式，讓verification key verifier進程從證明者那裡接收到加密多項式評估 gp、gh、gp'：

雖然可信設置是有效的，但它並不有效，因為 CRS 的多個用戶將不得不相信一個刪除的 和 ，因為目前沒有辦法證明這一點。 因此，有必要最小化或消除這種信任。 否則，不誠實的一方將能夠在不被發現的情況下製作假證據。

實現這一點的一種方法是由多方使用前面部分中介紹的數學工具生成復合 CRS，這樣這些方都不知道秘密。這是一種方法，讓我們考慮三個參與者 Alice、Bob 和 Carol，對應的索引為 A、B 和 C，對於 i 在 1、2、...中。 . . , d:

作為這種協議的結果，我們有復合 和 並且沒有參與者知道其他參與者的秘密參數，除非他們串通。事實上，為了學習 和 ，必須與其他所有參與者串通一氣。因此，即使一個人是誠實的，也無法提供假證明。

注意：此過程可以根據需要對盡可能多的參與者重復。

可能存在的問題是如何驗證參與者是否與 CRS 的每個值一致，因為對手可以采樣多個不同的 s1、s2、...。 . . 和α1, α2, . . .，並將它們隨機用於 s 的不同冪（或提供隨機數作為增強的公共參考字元串），從而使 CRS 無效且不可用。

幸運的是，因為我們可以使用配對來乘以加密值，所以我們能夠執行一致性檢查，從第一個參數開始，並確保每個下一個參數都是從它派生的。參與者發布的每個 CRS 都可以檢查如下：

請注意，雖然我們驗證每個參與者都與他們的秘密參數一致，但使用先前發布的 CRS 的要求並未對每個下一個參與者強制執行（在我們的示例中為 Bob 和 Carol）。因此，如果對手是鏈中的最後一個，他可以忽略先前的 CRS 並從頭開始構造有效參數，就好像他是鏈中的第一個，因此是唯一知道秘密 s 和 α 的人。

我們可以通過額外要求除第一個參與者之外的每個參與者加密和發布他的秘密參數來解決這個問題，例如，Bob 還發布：

這允許驗證 Bob 的 CRS 是 Alice 參數的適當倍數，因為 i in 1, 2, . . . , d:

同樣，Carol必須證明她的CRS是Alice-Bob的CRS的適當倍數。

這是一個強大的CRS設置方案，不完全依賴任何一方。實際上，即使只有一方是誠實的，並且刪除並且從不共享其秘密參數，即使所有其他各方都合謀，它也是非常明智的。因此，CRS 設置中不相關的參與者越多，偽造證據的可能性就越小，如果競爭方參與，其可能性就可以忽略不計。該方案允許涉及對設置的易讀性有疑問的其他不受信任的各方，因為驗證步驟確保他們不會破壞最終的公共參考字元串 (也包括使用弱 α 和s)。

我們現在准備鞏固進化的zk-SNARKOP協議。形式上，為簡潔起見，我們將使用大括弧來表示由其旁邊的下標填充的一組元素，例如si i ∈[d] 表示集合s1，s2，...，sd。

已商定目標多項式t（x）和校準儀多項式的d次：

Setup：

Ⅲ 同態加密聯邦學習前景薪資高嗎

前景好，薪資高。
1、同態加密的應用非常廣泛，可以老緩用於保護金融機構的數據，保護政府機構的數據，保護企業的數據，以及保護個中緩人的數據，信息化網路時代離不開隱私保護，同態加密聯邦學習前景很高高。
2、同態加密聯邦學習的技術工作人員薪酬范圍：40k-70k/月，屬於高薪侍培模。

Ⅳ 隱私計算-密碼學-同態加密

近年來，隨著大數據與人工智慧的盛行，針對個人的個性化的推薦技術的不斷發展，人們在享受便利的同時，也深深的感覺到無處不在的監控與監事，比如剛剛瀏覽了一個網站的商品，當去其他網站訪問的時候就會推薦類似的產品；剛剛搜索了某件商品，在很多其他的場景中都會給你推薦。這種體驗，談不上不好，也談不上多壞，但是如果仔細想想，就感覺自己的網上進行裸奔，個人隱私，一清二楚，毫無隱私可言，細思極恐。

不過隨著廣大用戶對於個人隱私的重視程度不斷加強，以及法律法規的不斷完善，針對個人隱私的保護提出了更高的要求，什麼樣的數據可以採集、收集與使用，如何使用都是一個比較敏感的問題。十三屆全國人大常委會第三十次會議表決通過了《 中華人民共和國個人信息保護法 》，並與2021年11月1日起施行。確立個人信息保護原則、規范處理活動保障權益、禁止「大數據殺熟」規范自動化決策、嚴格保護敏感個人信息、賦予個人充分權利等。新規施行後，違法的主體將 最高可處五千萬以下或者上一年度營業額百分之五 以下的罰款。

鑒於上述情況，近年來隱私計算技術被不斷的提及，源於其有優秀的數據保護作用，使得 「數據不出域、數據可用不可見、數據可算不可見」 ，限定了數據的使用場景，防止了數據的泄露，而引起了業界的熱捧。

隱私計算技術的演進歷程如下圖描述，以下是楊強教授在KDD 2021中國區的分享材料：

可以看到，隱私計算技術從1979年就開始了，最開始是安全多方計算、到差分隱私、到TEE， 再到最近火的不能再火的聯邦學習 ，一系列的技術應運而生。那為啥現在隱私計算這么火呢。

註：隱私計算技術成熟度曲線

但是這些技術本身的安全加密都是採用共同的方法與策略，下面講述下隱私計算的加密技術。

本文主要介紹同態加密，

眾所周知，優秀的程序員需要 嚴謹的邏輯思維與具象能力 ，當然在材料的時候，可能需要適當的渲染。但是對於技術的理解，對技術的探索，嚴謹的邏輯與堅實的推理是非常重要的。所以，對於「數據加密」這個命題，需要進行一番探索。

如此三態合一，即可保障數據的全鏈路的生命周期安全 。

那麼有沒有辦法解決數據計算的安全問題呢？答案就是 同態加密技術 。保障數據的運行態的安全，那麼同態加密技術具體是如何實現，如何應用，並且有哪些限制呢？

什麼是同態加密？ ，引用Gentry大佬的原話：

同態加密（Homomorphic Encryption, HE），指滿足密文同態運算性質的加密演算法，即數據經過同態加密之後，對密文進行某些特定的計算，得到的密文計算結果在進行對應的同態解密後的明文等同於對明文數據直接進行相同的計算， 實現數據的「可算不可見」 。同態加密的實現效果如圖所示。

舉個例子： 國內某家大型的三甲醫院，由於歷史悠久，並且醫術精湛，歷史遺留了大量的用戶病例數據 。如今思考基於這些病例數據進行建模分析。但是由於數據量特別巨大，醫院本身的IT資源有限，計算能力不足。

這個時候，雲廠商找了過來。但是對於醫院來說，這些數據本身是用戶的隱私信息，並且也是醫院的核心價值，所以盡管雲廠商再三保證數據安全， 但是醫院還是不能夠放心的將數據上傳到雲廠商進行計算 。

正當這個事情推進不下去的時候，雲廠商從密碼行業花大價錢招來某個大牛，大牛提出一個方案，這樣吧，我們現在有 這樣一門技術，不需要傳輸明文數據，只需要傳輸密文就好，而且加密秘鑰由醫院自己保存，我們基於上傳的密文數據做不解密的密態運算（ 並計算函數醫院提供就好），這樣數據不會泄露，雲廠商對數據無感知，之後傳回密文結果，醫院自己解密就好 。醫院一聽非常高興，那就這么辦吧。

下面將核心流程描述下。

這里，大家可能有個問題，這個f應該是什麼樣的函數，有什麼樣的限制條件？HE方案是支持任意的數據處理方法f，還是說只支持滿足一定條件的f呢？根據f的限制條件不同，HE方案實際上分為了兩類：

Paillier加密演算法是Pascal paillier[1]在1999年發明的概率公鑰加密演算法，該演算法 基於復合剩餘類的困難問題，是一種滿足加法的同態加密演算法 ，已經廣泛應用在加密信號處理或第三方數據處理領域。

前面我們分析過 同態加密的核心流程 ，大家可以一起回憶一下。核心的函數包括：秘鑰生成、明文加密、密文解密，下面我們來一步一步的分析，並且描述下，

秘鑰的生成主要有如下的步驟，

下面介紹一個完整的同態運算，m由 組成，介紹下同態加密的是如何使用密文計算的。

Ⅳ 信息安全安全前沿技術有哪些

信息安全基本上都是都是攻與防的對抗，正是這種對抗促使了信息安全的發展，因此攻也屬於信息安全非常重要的一塊。因而前沿的東西都在攻防這一塊兒，這也是為什麼各大安全公司都有攻防實驗室的原因。由於種種原因，攻擊技術遠遠超前於防護技術，最近幾年流行的威脅情報也是為了解決如何更快的發現攻擊並做情報共享，堵住同類型攻擊。

把信息安全劃分為北向和南向，北向偏理論，務虛；南向偏技術，務實。當然本人屬於南向。

北向前沿：機器學習和深度學習在信息安全中的運用，威脅情報的識別，大數據和雲技術在信息安全領域的運用等。
南向前沿：關注blackhat吧，目前都在研究智能硬體設備的安全，物聯網安全，智能家居安全，車聯網安全，工控安全等等。這些領域目前還都處於攻擊技術領先的狀態。
至於代表人物，沒有，誰敢來代表一個方向的前沿，有也是吹牛瞎忽悠的人。

Ⅵ 同態加密簡介

同態加密是數據加密方式的一種，特點是允許數據在加密情況下實現數學或邏輯運算。

同態加密通常為非對稱性加密。因此在介紹同態加密之前，簡單介紹一下非對稱性加密。非對稱性加密分為三個步驟：

1. 生成一對鑰匙，一個公鑰pub和一個密鑰priv；

2. 使用公鑰pub加密原始數據，得到加密數據，公式：pub(原始數據）= 加密數據 ；

3. 使用密鑰priv解密加密數據，得到原始數據，公式：priv( 加密數據 ）= 原始數據 ；

同態加密允許對 加密數據 進行處理，得到的解密結果等價於在原始數據下做運算。以聯邦學慣用到的Paillier演算法舉例，假設我有兩個數 和 ，我希望把它們扔給第三方做加法運算，即 + 。同時不希望第三方知道 、 及它們之和的具體值，同態加密可以派上用場，具體步驟如下：

1. （本地）生成一對鑰匙，公鑰pub和密鑰priv，公鑰用於加密，密鑰用於解密；

2. （本地）使用公鑰pub分別加密 和 ，得到 ( )和 ( )；

3. （第三方）使用 函數處理 和 ，即 ；

4. （本地）使用密鑰priv解密 ，即 ；

4中  =  + 。第三方通過上述步驟3實現了 和 在加密狀態下做加法的操作。

為了更直觀認識上述步驟，假設 =100， =200，步驟就變成：

1. （本地）生成一對鑰匙，公鑰pub和密鑰priv，公鑰用於加密，密鑰用於解密；

2. （本地）使用公鑰pub分別加密 和 ，得到 =1234， =4321 (舉例）；

3.（第三方） 使用 函數處理 和 ，即 =12345678;

4. （本地）使用解密priv解密 ，得到  = 300。

第三方在不知道 =100和 =200，但是通過 函數依然可以在加密情況下實現相加運算。