格密碼學進階05：從IBE出發到內積ABE（AFV11）

寫在前面

越往後面寫，筆者發現隨著難度的進階，很多內容並不是可以全部塞在一篇文章中一起發出來的了。每一篇文章的內容都有太多細節的地方需要滿滿的思考。

從這一期開始，為了方便閱讀，我們縮短每一期的篇幅，每一期就詳細的介紹一篇或者幾篇有關的paper。這樣可以方便我們充分的理解體系的構造以及安全性的證明。

在之前的文章中，我們已經充分的瞭解了IBE加密在格中的實現方法。IBE其實並不是一個什麼大難題，因為我們已經有基於雙線性配對（Bilinear Maps）的非常好的IBE系統了。

真正讓Lattice突出它的強大的地方在於，我們可以從類似ABB10的IBE架構出發，逐步新增新的功能，最後就可以實現傳說中的

ABE

（

Attribute-based Encryption

），即

屬性加密

了。

這一期，我們來看一看從IBE開始向ABE跨越的第一步：

支援內積運算

。

ABE簡介

乍一看

支援內積運算

這個詞，大家都會感覺一頭霧水。想要了解它是什麼意思的話，我們需要了解一下ABE問題的具體定義。

想必現在網上已經有許多關於屬性加密（ABE）的介紹了。我們在這裡就不多說整個問題的背景知識了，而是直接給出大概的定義。

首先，整個系統和IBE是一樣的，需要一組由管理員生成的MPK與MSK。擁有了MSK的管理員，就可以基於任何

屬性函式

$f(\cdot)$

簽發對應的私鑰

。什麼是屬性函式呢？屬性函式其實就是一個讀取一個

屬性輸入

的函式，如果

通過了函式的驗證，那麼這個函式就會輸出1，反之就會輸出0。（反過來也可以，如果通過了輸出0，沒有就輸出1也是一樣的。）

這樣的話，如果Alice要傳送一封訊息，她可以根據MPK與自己選擇的一個屬性輸入

建立一個特殊的公鑰，進而加密她的訊息

。這個時候，和IBE不同的是，這個訊息並不是指向某個

的，而是任何人，只要擁有管理員簽發的金鑰

，並且

的話，那就可以解密這條訊息。

不僅如此，管理員也可以簽發多個

的私鑰

，並且分發給不同的人。這樣就可以確保一條訊息對應的屬性

只會有一部分人對應的函式

可以驗證透過。這樣的構造對於人數眾多的

ACL

（

Access Control List

）使用場景下非常有用。即如果我想要一條訊息只讓某個分組的人可以解密，就可以透過ABE系統來高效地實現。

對於這一類把屬性函式存放在金鑰sk中，然而把屬性本身放在密文中的構造，我們一般都稱之為

KP-ABE

（

Key Policy ABE

）。反之，如果我們把驗證的函式放在密文中，然而把屬性放在金鑰中的話，這種構造被叫做

CP-ABE

（

Ciphertext Policy ABE

）。

一般來說，CP-ABE更加貼合我們實際的使用邏輯一點——我們在創造密文的時候，可以決定驗證的屬性函式

，就可以很輕鬆的選擇到底誰能看到誰不能看到。每個人所擁有的屬性金鑰，就可以是他們的名字或者是身份證號。然而，現在

最常見的構造仍然是KP-ABE的結構

，因為CP-ABE的構造會更復雜一點（需要能夠把函式嵌入在密文中並且可以快速驗證屬性輸入）。

如果我們不需要高效這一點，我們可以

把任意的KP-ABE結構轉換成CP-ABE結構

，即對調加密方和解密方的角色。假如我們擁有一個可以支援任意複雜度電路的屬性函式的KP-ABE結構，這個時候，我們只需要生成一個對應於

Universal Circuit

（

全能電路

）

$U(\cdot, x)$

的金鑰

，就足夠了。

Universal Circuit

是一個萬能的電路，其功能如下：我們輸入一個電路

的描述，與

的輸入

，然後全能電路就可以計算這個輸入的電路在

上的值

隨後輸出。在KP-ABE的場景中，我們想要透過Key中的函式

來驗證金鑰中的輸入

。當Key中的函式是

$U(\cdot, x)$

，即內嵌了輸入

的Universal Circuit的時候，這個時候金鑰中的輸入就變成了CP-ABE中的屬性函式

的電路描述

。換句話說，我們可以把對於屬性函式電路的描述存放在金鑰中，然後透過Key中嵌入的全能電路和輸入

來進行計算，最後得到

的值。

關於Universal Circuit的適用方法，還有很多很多，這裡就不多描述了。但是

的最大弊端在於這麼一個全能的電路的體積是非常龐大的。如果我們把

作為

嵌入在

中，首先能否實現巨大的複雜度先不說，就算可以實現，整體的效率也會非常低。

IBE是ABE的一種簡化版本

瞭解完ABE是什麼之後，我們回頭看IBE的時候就會發現，其實IBE就是一種非常簡化版本的ABE了。

IBE的問題在於，在一個系統中，每一個人都擁有屬於自己的一個任意選擇的“身份”，即

。然後如果我想給某人發訊息，我就需要基於那個人的

來作為公鑰進行加密。那個人會從系統管理員那裡拿到屬於自己的

的金鑰

$\mathbf{e}_{ID}$

，從而就可以解開所有對著他的

加密的密文了。

如果套用ABE的構造的話，那麼“身份”即

，就是ABE系統中的屬性輸入

，然後驗證身份所用的屬性函式也很簡單：

$f(x) = \begin{cases}0 & x = ID^*,\\ 1 & \text{otherwise}.\end{cases} \\$

之前我們描述的ABE的屬性函式對於透過的屬性會輸出1，這裡我們為了方便後續的構造，我們顛倒一下1與0的定義，如果屬性透過驗證，

會輸出0。（這一點並不影響ABE的實現，非常的trivial。）

在ABE中，IBE只是一種非常簡單的屬性函式。我們觀察

的定義可以發現，這其實就是一個

Point Function

。也就是說，在整個函式的輸入空間中，只有一個點（即

）上對應的輸出是0，其餘都是1。

Point Function在所有可能的屬性函式的集合中，屬於最簡單的一類。之前我們說到的CHKP10與ABB10這兩種IBE構造都是變相的實現了Point Function ABE。

寫到這裡，我們不禁開始思考：我們知道ABE最後的終點就是可以實現任意複雜度的函式，但是我們目前只知道怎麼實現Point Function而已。我們能不能循序漸進繼續摸索下一個複雜度的函式類別呢？

內積函式

如果要超出Point Function的範疇，進入下一階段的話，一個比較有意義的方向就是線性函式（Linear Function）了，即對於屬性

$\mathbf{x}$

（可以是一個向量）的任意線性組合。我們在表達

$\mathbf{x}$

中的元素的線性組合的時候，就可以使用

$\langle \mathbf{x}, \mathbf{y} \rangle$

的內積形式來表述。舉個例子：

$\mathbf{x} = [x_0,x_1,x_2]\\ \mathbf{y} = [1, -1, 2]\\ \langle \mathbf{x}, \mathbf{y} \rangle = x_0 - x_1 + 2x_2 \\$

在2011年的時候，Agrawal，Freeman與Vaikuntanathan在【

AFV11

】這篇paper中介紹了一種新的ABE構造，可以實現屬性向量

$\mathbf{x}$

與金鑰中的一個向量

$\mathbf{y}$

的內積。這裡的屬性函式為：

$f(\mathbf{x}) = \begin{cases} 0 & \text{if } \langle \mathbf{x}, \mathbf{y} \rangle = 0,\\ 1 & \text{otherwise.} \end{cases} \\$

AFV11同樣也是一個KP-ABE架構。這也就是說，在這個構造中，我們在金鑰

中嵌入一個計算與

$\mathbf{y}$

向量內積的函式

$f(\cdot)$

。然後我們在加密的過程中在密文中嵌入屬性向量

$\mathbf{x}$

。這樣，如果解密方的金鑰中的

$\mathbf{y}$

與密文中的

$\mathbf{x}$

的內積為0的時候，解密方就可以成功解密這個密文啦。

即然Point Function ABE就等於IBE，那麼基於內積函式的ABE可以實現什麼不同的功能呢？如果仔細觀察的話，我們可以把一組有限長度的

布林邏輯表示式

（CNF/DNF）嵌入在這個裡面。這樣的話，

$\mathbf{x}$

向量的每一位就代表一個boolean bit，然後

$\mathbf{y}$

中就是對應的約束。只要內積等於0，那就代表布林邏輯驗證通過了。

光是基於內積，就已經可以實現很多有限約束的邏輯了。是不是感覺很強大？

AFV11的具體構造

接下來，我們來詳細的看一下AFV11 ABE是如何構造的。

內積ABE這個概念在【

KSW08

】中被第一次提出。其大致形式和我們之前描述的相同：在金鑰中嵌入一個

$\mathbf{y}$

向量，在密文中嵌入一個

$\mathbf{x}$

向量。最後如果兩者的內積為0，則擁有

$\mathbf{y}$

的金鑰就可以解開攜帶

$\mathbf{x}$

屬性的密文。

為了方便我們表述AFV11的具體結構，我們假設進行內積運算的向量

$\mathbf{x, y}$

的長度為4，即

$\lvert \mathbf{x} \rvert = \lvert \mathbf{y} \rvert = 4$

。

公共引數

AFV11 ABE系統的公共引數和之前介紹的CHKP10系統大致相似。首先，我們需要一個透過MP12 Trapdoor演算法生成的隨機平均分佈的矩陣

$\mathbf{A}$

，與一個任意選擇的SIS問題向量

$\mathbf{u}$

。

其次，因為我們這裡的內積向量長度為4，所以我們需要額外的生成4個隨機平均分佈的（沒有Trapdoor的）矩陣

$\mathbf{A}_1, \mathbf{A}_2, \mathbf{A}_3, \mathbf{A}_4$

。

這個系統的MSK就是矩陣

$\mathbf{A}$

的Trapdoor

$\mathbf{R}$

。

加密矩陣與金鑰生成

熟悉基於Lattice的ABE之後，想必我們都知道下一步是什麼了：根據一個約束向量

$\mathbf{y}$

，如何構造ABE矩陣

$\mathbf{F_y}$

。AFV11中的

$\mathbf{F}$

矩陣很簡單：

$\mathbf{y} = (y_1, y_2, y_3, y_4)\\ \mathbf{F_y} = [\mathbf{A} \vert \sum_i y_i \mathbf{A}_i] \\$

AFV11真正不一樣的地方在於右側，把

$\mathbf{y}$

的每一項乘以對應的

$\mathbf{A}_i$

矩陣，然後把結果加起來得到一個新的組合矩陣。因為基於格的方案基本上都是針對於一個bit來進行操作的，所以我們這裡也額外的約束這個ABE中的

$\mathbf{x, y}$

向量都為二進位制向量。當

$y_i \in \{0, 1\}$

的時候，

$\sum_i y_i \mathbf{A}_i$

就等於

$\mathbf{A}_i$

的一個subset sum。

$\mathbf{F_y}$

矩陣的左側和往常一樣，就是帶有Trapdoor的

$\mathbf{A}$

矩陣，這確保了擁有MSK的管理員可以生成任何

$\mathbf{F_y}$

對應的金鑰。對應

$\mathbf{F_y}$

的金鑰

$\mathbf{e_y}$

就是其SIS問題的解：

$\mathbf{F_y e_y} = \mathbf{u} \text{ mod }q \\$

加密演算法Enc

我們知道如何根據

$\mathbf{y}$

約束向量生成

$\mathbf{F_y}$

和對應的金鑰

$\mathbf{e_y}$

之後，下一步就是根據屬性

$\mathbf{x}$

開始加密一段密文了。

首先，我們要做的事情是和普通的Dual Regev一樣，把需要加密的原文

$\mu \in \{0, 1\}$

嵌入在密文中：

$C = \mathbf{u}^t \mathbf{s} + noise + \lfloor q/2 \rfloor \mu \\$

其中

$\mathbf{s}$

為隨機選擇的一個向量，

為噪音。

我們知道，光有

還是不夠的，我們還需要一個輔助的密文

：

其中

$\mathbf{x}$

為噪音向量，

$\mathbf{noise}$

為噪音向量。

在普通的Dual Regev中，我們只需要知道一個對應了

$\mathbf{A e = u} \text{ mod }q$

SIS問題中的解

$\mathbf{e}$

，就可以把

轉換成一個近似

$\mathbf{u}^t \mathbf{x}$

的值，隨後就可以把這一部分從

中移除，從而還原出

$\mu$

的值來。

但是在這裡，我們不能輕易的給出這個

$\mathbf{e}$

來，而是要巧妙的設計一個結構，使得如果

$\langle \mathbf{x, y} \rangle = 0$

的時候，我們就可以得到一個近似

$\mathbf{u}^t \mathbf{s}$

的值，幫助我們解密。

AFV11中，這個體系的具體實現方式是這樣的，我們根據

$\mathbf{x} = (x_1, x_2, x_3, x_4)$

這個屬性向量的每一個值，分別構造出四個密文矩陣：

$C_i = (\mathbf{A}_i + x_i \times \mathbf{G})^t \mathbf{s} + \mathbf{noise} \\$

如果我們仔細觀察這個密文矩陣的構造的話，我們會發現因為

$\mathbf{A}_i$

是隨機選擇的，所以可以當作一個完美的One-Time Pad來完全的隱藏所有的

屬性。

總結一下，我們的加密演算法

一共會生成普通的Dual Regev密文

，還會額外的生成4個對應了

約束的密文

。

解密演算法Dec

現在，我們來看看最重要的環節——解密是如何進行的。

總結一下，作為一個解密方，我們會擁有一個屬於自己的約束向量

$\mathbf{y}$

和對應的金鑰

$\mathbf{e_y}$

。我們看到的密文由三部分組成：

Dual Regev中蘊涵了真正的加密內容的密文

$C = \mathbf{u}^t \mathbf{s} + noise + \lfloor q/2 \rfloor \mu$

。

為了方便我們解開第一部分而存在的一段補充的密文

。

根據加密方選擇的屬性向量生成的一組密文

$C_i = (\mathbf{A}_i + x_i \times \mathbf{G})^t \mathbf{s} + \mathbf{noise}$

。

AFV11 ABE的精髓在於，已知

$\mathbf{y}, \mathbf{e_y}, C$

，我們可以巧妙的組合這些資訊，計算並移除密文

中的One-Time Pad

$\mathbf{u}^t \mathbf{s}$

，從而還原出原文

$\mu$

來。

我們知道這些資訊中，最方便我們解密的應該是我們所擁有的金鑰

$\mathbf{e_y}$

，因為它滿足瞭如下的等式：

$\mathbf{F_y e_y} = [\mathbf{A} \vert \sum_i y_i \mathbf{A}_i] \mathbf{e_y} = \mathbf{u} \text{ mod }q \\$

接下來就是想辦法構造出這個結構，從而讓這個金鑰發揮用武之地了。

首先，我們把

$\mathbf{y}$

的資訊疊加到

$\{C_i\}$

密文上，構成新的組合密文

：

$\begin{align*} C_y &= \sum_i y_i C_i\\ &= (\sum_i y_i \mathbf{A}_i + \underbrace{\sum_i y_i x_i \mathbf{G}}_\text{0 if $\langle \mathbf{x, y} \rangle = 0$})^t \mathbf{s} + \underbrace{\sum_i y_i \cdot noise}_\text{small if $y_i$ is binary} \end{align*} \\$

如果我們展開

的表示式，我們會發現其中帶有

$\mathbf{G}$

的一項，如果

$\mathbf{x, y}$

的內積為0的話，就可以被完美的消除。這樣一來，整個表示式就變成了純粹的

$\sum_i y_i \mathbf{A}_i$

，這也就是我們前面

$\mathbf{e_y}$

用到的矩陣的一部分！

接下來，最後一步我們就是要正確的使用金鑰

$\mathbf{e_y}$

來解密。我們拼接

與

，並且乘上

$\mathbf{e_y}$

，就可以得到：

$\begin{align*} \mathbf{e_y}^t [C$

得到這個結果之後，我們就可以從

中減去這一項，就可以得到密文啦！

$C - \mathbf{e_y}^t [C$

AFV11的深入理解

由於篇幅原因，這裡就不給出AFV11的安全論證了。不過大致的方案和之前相同，我們需要能夠在不知道MSK和對應的任何約束

$\mathbf{y} : \langle \mathbf{x,y} \rangle = 0$

情況下的金鑰的條件下，可以生成任何

$\mathbf{y}$

的金鑰並且符合AFV11的正確性要求。

如果我們仔細的品味一下AFV11的結構的話，我們會發現其實它在解密的時候根據

$\mathbf{y}$

的值組合

$\{C_i\}$

這些密文的過程，和FHE同態加密運算非常的神似。就好比是我們收到了一段對於秘密屬性向量

$\mathbf{x}$

的加密，然後我們同態的把

$\mathbf{y}$

的值疊加上去，得到一個新的密文。

然而這裡解密的精髓非常的耐人尋味：我們事先透過MSK生成了在

$\langle \mathbf{x, y} \rangle = 0$

的情況下對應密文的一個金鑰

$\mathbf{e_y}$

。因為解密者並不知道

$\mathbf{x}$

或者

$\mathbf{s}$

的值，所以他只能同態的計算他的

$\mathbf{y}$

與帶有

$\mathbf{x}$

的密文的內積，得到一個新的密文。如果恰巧兩者的內積是0的話，那麼他手中的金鑰就可以巧妙的“解開”新的密文，拿到幫助我們解密的

$\mathbf{u}^t \mathbf{s}$

。

如果我們換一種方法來理解

的話，我們可以把它理解為同態計算了

$\mathbf{x, y}$

內積的密文

$C_{\langle \mathbf{x, y} \rangle}$

：

$C_{\langle \mathbf{x, y} \rangle} = (\mathbf{A_y} + \langle \mathbf{x, y} \rangle \cdot \mathbf{G})^t\mathbf{s} + \mathbf{noise} \\$

這裡的

$\mathbf{A_y}$

即基於了

$\mathbf{y}$

的值生成的

$\sum_i y_i \mathbf{A}_i$

。

當

$\mathbf{G}$

項為0之後，我們會發現整個密文失去了任何有關

$\mathbf{x}$

的資訊，這也就是為什麼一開始我們可以在不知道

$\mathbf{x}$

的情況下只通過MSK就能生成解開這個密文的金鑰。

歸納到ABE

如果我們再進一步的觀察這個結構的話，我們可以把這個結構進一步的generalize一下：

$C_{f(x)} = (\mathbf{A}_f + f(x) \cdot \mathbf{G})^t \mathbf{s} + \mathbf{noise} \\$

這裡的

$\mathbf{A}_f$

就是嵌入了

屬性函式的矩陣

$\mathbf{A}$

。

在AFV11中，我們的屬性函式就是與

$\mathbf{y}$

的內積操作，即：

$f(\cdot) = \langle \cdot, \mathbf{y} \rangle \\$

這裡的

$\mathbf{y}$

我們可以理解為嵌入在

中的一個constant。

用這種角度來看的話，我們發現，只要我們能夠把

的複雜度範圍擴大（目前AFV11只給了我們線性內積的

），那就可以用這種模式來實現任何屬性函式的ABE了！

我們來嘗試總結一下這種結構的ABE的大致結構：

首先使用Dual Regev來加密密文

$\mu$

，使其隱藏在

$\mathbf{u}^t \mathbf{s}$

構成的的One-Time Pad中。

隨後我們使用MSK生成關於

$f(\cdot)$

本身組成的

$\mathbf{A}_f$

所對應的金鑰

$\mathbf{e}_f$

。

加密方把自己的屬性輸入

嵌入在

$\{C_i\}$

中，隨後解密方同態的在

$\{C_i\}$

上計算

$f(\cdot)$

。

如果

，密文中帶有

的項全部都會歸零，然後我們只會剩下描述

的

$\mathbf{A}_f$

。隨即我們就可以使用

$\mathbf{e}_f$

來得到

$\mathbf{u}^t \mathbf{s}$

並且還原出原文

$\mu$

。

這樣的結構，正是Boneh et al。提出的【

BGG+14

】的ABE結構！由於現在我們只解決了線性函式的計算，距離真正的ABE還差了一點距離。這一部分正是BGG+14所解決的。

寫在最後

下一期，我們就來深入的瞭解一下BGG+14是如何構造的，以及我們如何證明齊安全性。

小蜜蜂問答

小蜜蜂問答

格密碼學進階05：從IBE出發到內積ABE（AFV11）

推薦文章

小蜜蜂問答

小蜜蜂問答

格密碼學進階05：從IBE出發到內積ABE（AFV11）

相關文章

六一非洲鼓表演報幕詞？

量子雷達？哪位大神科普一下？

玫瑰小鎮的主線任務合成鑰匙失敗了，該怎麼辦？

不小心開發票時壓線了嗚

推薦文章