函数加密体制（二）

4 安全定义

第2节给出了函数加密的语法定义，现在给出函数加密方案的安全定义。本节给的是基于游戏的定义，第5节讨论基于模拟的定义。

设ε 是一个函数加密方案，其功能 F 定义在 (K，X) 上。我们的目标是定义针对自适应攻击者的安全性，他会反复请求攻击者选择的密钥 skₖ ( k∈K )。正如我们将要看到的那样，定义针对此类攻击者的安全性比人们最初预期的要微妙得多。问题是如何在语义安全游戏中定义挑战密文。像往常一样，一旦攻击者获得了他想要的所有秘密钥，他将输出两个挑战消息 m₀，m₁ ∈ X ，挑战者返回从 m₀，m₁ 中随机选择的加密结果 c 。明显地，如果攻击者拥有一个密钥 skₖ (k∈K) 有 F(k，m₀) ≠ F(k，m₁)，则他很容易回答挑战密文 c 通过下式：

0 dec(skₖ，c)＝F(k，m₀)

{ 。

1 otherωise

条件1：因此，为了使（安全）定义是可满足的，我们必须严格限制攻击者对 m₀，m₁ 的选择，应该要求它们满足 F(k，m₀)＝F(k，m₁) （对于 ∀k∈K ，攻击者可能拥有的私钥 skₖ ）。

由于空密钥ϵ 会泄露明文长度，条件1中还需要确保 |m₀|＝|m₁| ，如语义安全的标准PKE定义。

This problematic system, however, would clearly not achieve the simulation-based definition of security presented in Section 5 since if x is chosen at random, the real-life adversary would be able to recover x always, while the simulator would not be able to recover a without breaking the one-wayness of the permutation π.

While the simple example above may seem to be“abusing”the role of the trivial key ϵ，it is easy to modify the functionality example F above so that there is exacty one non-trivial key k ∈ K that outputs π(x). The only difference to the construction above would be that the functional encrvption algorithm would outout a public-key encryption⁵ of either π(x) (in the “correct"implementation) or x (in the“incorrect"implementation), and the secret key for key k would be the secret key of the public-key encryption scheme. Again, it is easy to verify that the incorrect implementation satisfies the game-based definition.

Discussion. What does this separation show? While this is a subjective question, our view is that it shows that if the output of the functionality is supposed to have some

computational hiding properties – that is, security of your application is not only based on the information-theoretic properties of the function, but also on the computational properties of the function – then there is a real problem with the game-based formulation of security. The game-based formulation essentially ignores any computational hiding properties of the function, and therefore offers no security guaraicus that could be meaningfully combined with such computational considerations.

安全定义：有了条件1的要求，我们可以很自然的得到函数加密方案ε 的基于游戏的安全定义。对敌手 A 定义实验 b(b＝0，1) 如下：

• 初始化：运行 (pp，mk) ← setup(1λ) ，并将 pp 发送给 A ;

• 询问： A 适应性地提交请求 kᵢ ( kᵢ∈K，i＝1，2，. . . )，然后收到skᵢ ← Keygen(mk，kᵢ) ；

• 挑战： A 提交两个消息 m₀，m₁ ∈ X（要满足条件1），然后收到 enc(pp，mb) ;

• A 继续进行密钥查询且要服从条件1，最终输出 {0，1} 中的一个值。

设Wb ( b＝0，1 )表示事件：在实验 b 中敌手输出为 1 ，定义敌手优势为： FEαdυ[ε，A](λ)：＝|Pr[W₀] – Pr[W₁]|

定义3：一个函数加密方案 ε 是安全的当且仅当对于任意PPT敌手 A 函数 FEαdυ[ε，A](λ)是可忽略的。

定义3是论文[BW07，KSW08]中相关定义的一个概括。

Security definition. With requirement (1) in place we obtain a natural game for defining security of an FE scheme ε.For b＝0，1 define experiment b for an adversary A as follows：

– Setup: run (pp，mk) ← setup(1λ) and give pp to .A.

– Query：A adaptively submits queries kᵢ in K for i＝1，2，. . . and is given skᵢ ← keygen(mk，kᵢ).

– Challenge： A submits two messages m₀，m₁ ∈ X satisfying (1) and is given

enc(pp，mb).

– A continues to issue key queries as before subject to (1) and eventually outputs a bit in {0，1}.

For b＝0，1 let Wb be the event that the adversary outputs 1 in Experiment b and define

FEadv[ε，A](λ)：＝丨Pr[W₀] – Pr[W₁]丨

Definition 3. An FE scheme ε is secure if for αll PPT A the function FEαdv[ε , A](λ) is negligible.

Definition 3 is a generalization of related definitions from [BW07，KSW08].

4.1 “蛮力法”构造

简单的展示一下多项式大小的密钥空间K 的任意功能 F 都可以很容易的实现。记 s＝|K| – 1 且 K＝{s，k₁，. . .，kₛ} 。蛮力构造的方案中，公共参数、秘密钥、密文的大小均和 s 成比例。[BW07]中给出一个密切相关的构造。

蛮力构造的函数加密方案实现功能F 使用到一个语义安全的公钥加密方案 (G，E，D) ，具体如下：

初始化 (1λ) ：对于 i＝1，. . .，s 运行 (ppᵢ，mkᵢ) ← G(1λ)，输出 pp：＝(pp₁，. . .，ppₛ)，mk：＝(mk₁，. . .，mkₛ) ；

• 密钥生成 (mk，kᵢ) ：输出 skᵢ＝mkᵢ ；

加密 (pp，x) ：输出密文 c：(F(ϵ，x)，E(pp₁，F(k₁，x))，. . .，E(ppₛ，F(kₛ，x)) ;

• 解密 (skᵢ，c) ：若 skᵢ＝ϵ ，则输出 c₀ ；否则输出 D(skᵢ，cᵢ) 。

明显地，密文c 泄露了 F(kᵢ，x)，i＝1，. . .，s 的比特长度。因此为了保证这个结构的安全性，我们必须假定空功能 F(ϵ，·) 已经泄露了这个信息，也就是说 |F(kᵢ，x)|，i＝1，. . .，s 包含在了 F(ϵ，x) 内。我们说 F 泄露了功能的比特长度。

定理1：设 F 是一个泄露功能比特长度的函数。若 (G，E，D) 是语义安全的公钥加密方案，则实现功能 F 蛮力构造的函数方案是安全的。

证明（证明框架）：证明方法是对挑战密文的s 个部分进行标准混合论证。

We briefly show that any functionality F where the key space K has polynomial size can be easily realized. Write s＝|K| – 1 and K＝{ϵ，k₁，. . .，kₛ). In this brute force construction, the size of public parameters, secret key,and ciphertext are all propor- tional to s. A closely related construction is given in [BW07].

The brute force FE scheme realizing F uses a semantically secure public-key en-cryption scheme (G，E，D) and works as follows：

– setup(1λ)：for i＝1，. . .，s run (pp，mkᵢ) ← G(1λ).

output：pp：＝(ppᵢ，. . .，ppₛ) and mk：＝(mk₁，. . .，mkₛ)

– keygen(mk，kᵢ)：output skᵢ：＝mkᵢ.

– enc(pp，x)：output c：=，＝(F(ϵ，x)，E(pp，F(kᵢ，x))，. . .，E(ppₛ，F(kₛ，x))).

– dec(skᵢ，c):output c₀ if skᵢ＝ϵ，and output D(skᵢ，cᵢ) otherwise.

Clearly, a ciphertext c leaks the bit lengths of F(kᵢ，x) for i＝1，. . .，s. Therefore，for this construction to be secure we must assume that this information is already leaked by the empty functionality F(ϵ，·)，namely that |F(kᵢ， x)| for i＝1，. . .，s is contained in F(ϵ，x). If so then we say that F'reveals functional bit lengths.

Theorem 1.Let F be α functionαlity thαt reνeαls functionαl bit lengths. If (G，E，D) is α semαnticαlly secure public-key encryption scheme then the brute force FE system implementing F is secure.

Proof (Proof Sketch).The proof is by a standard hybrid argument acrosethe s compe-nents of the challenge ciphertext.

4.2 基于游戏安全定义的不充分性

现在来展示一下，对于某一个复杂的功能（这里理解成函数比较恰当）来说定义3太弱了。对于这些函数我们构造一个满足定义3安全性的系统，但实际并不安全。不过，对于像第5节展示的带有公开索引的谓词加密中的功能（函数）来说定义3足够了。

给出基于游戏的定义3的不充分性的一个简单的功能例子。设π 是一个单向置换，考虑仅接受平凡密钥ϵ 的功能 F ，定义为： F(ϵ，x)＝π(x) 。很明显，对这个简单的功能来说正确的实现函数加密的方法是：有一个函数加密算法在输入 x 时输出 π(x) ，即 enc(pp，x)＝π(x) 。这个方案明显需要第5节提出的基于模拟的安全定义。

然而，考虑该功能一个“不正确”的实现，其中函数加密算法输入x 时输出 x ，即 enc(pp，x)＝x 。明显这个系统泄露了比所需更多的明文信息。不过，很容易能证明该方案满足第4节基于游戏的安全定义。这是因为，任取两个值 x 和 y ， F(ϵ，x)＝F(ϵ，y) 当且仅当 x＝y 。因此攻击者只能对 m₀＝m₁ 的明文消息发起挑战。

We will now show that for certain complex functionalities Definition 3 is too weak.For these functionalities we construct systems that are secure under Definition 3 but should not be considered secure. Nevertheless, for functionalities such as predicate encryption with public index we show in Section 5 that Definition 3 is adequate.

We give a simple example of a functionality for which the game-based Definition 3 is insufficient.Let π be a one-way permutation and consider the functionality F that only admits the trivial key ϵ，defined as follows：

F(ϵ，x)＝π(x)

It is clear that the “right”way to achieve functional encryption for this very simple functionality is to have the functional encryption algorithm itself simply output π(x) on input x， namely enc(pp，x)＝π(x). This scheme would also clearly achieve the simulation-based definition of security presented in Section 5

However, consider an “incorrect"realization of this functionality where the func-tional encryption algorithm outputs x on input x，namely enc(pp，x)＝x. Clearly this system leaks more information about the plaintext than needed. Nevertheless,it is easy to verify that this construction satisfies the game-based definition from Section 4 This is because for any two values x and y，it is the case that F(ϵ，x)＝F(ϵ，y) if and only if x＝y and therefore the attacker can only issue challenge messagee m₀，m₁ where m₀＝m₁.

然而，这是一个有问题的系统，不能实现第5节提出的基于模拟的安全定义，因为x 是可以随机选择的，因为真实世界的敌手可能会一直恢复 x ，而在模拟世界中若不打破 π 的单向性就无法恢复 x 。

尽管上述这个简单的例子“滥用了”平凡密钥ϵ 的作用，但是很容易可以修正上述功能 F （有一个非平凡的密钥 k∈K ，让它输出 π(x) ）。与上述构造的不同在于：函数加密算法输出一个公钥加密结果 π(x) (正确执行)或 x (非正确执行)， k 的秘密钥是公钥加密方案中的密钥。在这个例子中，仍然很容易证明非正确执行的时候是满足基于游戏的定义的。

讨论：这种分离说明了什么？这是一个主观的问题，我们认为这表明了若功能（函数）的输出具有一些计算隐藏性——即方案的安全性不仅仅基于函数的信息论性质——则基于游戏的安全形式就有问题。基于游戏的形式必须忽略函数的计算隐藏性，因此，没有提供与这种计算考虑相结合的有意义地安全保证。

This problematic system, however, would clearly not achieve the simulation-based definition of security presented in Section 5 since if x is chosen at random, the real-life adversary would be able to recover x always, while the simulator would not be able to recover x without breaking the one-wayness of the permutation π.

While the simple example above may seem to be“abusing”the role of the trivial key ϵ，it is easy to modify the functionality example F above so that there is exacty one non-trivial key k∈K that outputs π(x). The only difference to the construction above would be that the functional encrvption algorithm would outout a public-key encryptior⁵ of either π(x) (in the “correct”implementation) or x (in the“incorrect"implementation), and the secret key for key k would be the secret key of the public-key encryption scheme. Again, it is easy to verify that the incorrect implementation satisfies the game-based definition.

Discussion. What does this separation show? While this is a subjective question, our view is that it shows that if the output of the functionality is supposed to have some

computational hiding properties – that is, security of your application is not only based on the information-theoretic properties of the function, but also on the computational properties of the function – then there is a real problem with the game-based formulation of security. The game-based formulation essentially ignores any computational hiding properties of the function, and therefore offers no security guaraices that could be meaningfully combined with such computational considerations.

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。