函数加密体制（一）

学习函数加密的奠基论文[1]——Functional Encryption: Definitions and Challenges。

摘要：本文对函数加密形式化的研究，开始于刻画其概念和安全性的精确定义。简单来说，函数加密支持一个受限的密钥（使得密钥持有者仅可以学习加密数据的一个特定函数），而不了解关于数据的任何其他信息。例如，给一个加密的程序，密钥可以使密钥持有者学习程序一个特定输入的输出，而不可以学习这个程序的任何信息。

我们所展示的函数加密的安全性定义是很有用的。首先，我们表明对一些函数加密来说，基于游戏的安全定义是不充分的，接着我们呈现了一个基于模拟的定义并说明在标准模型下该定义不能被满足，但是在随机谕言机模型下可以被满足。我们介绍了如何将许多现有的概念映射到函数加密的形式化概念，最后总结了这个新兴领域的一系列有意思的开放问题。

Abstract.We initiate the formal study of functional encryption by giving precise definitions of the concept and its security. Roughly speaking,functional encryp- tion supports restricted secret keys that enable a key holder to learn a specific function of encrypted databut learn nothing else about the data.For example. given an encrypted program the secret key may enable the key holder to learn the output of the program on a specific input without learning anything else about the program.

We show that defining security for functional encryption is non-trivial.First. we show that a natural game-based definition is inadequate for some function- alities. We then present a natural simulation-based definition and show that it (provably) cannot be satished in the standard model, but can be satished in the random oracle model.We show how to map many existing concepts to our for- malization of functional encryption and conclude with several interesting open problems in this young area.

1 引言

加密是用户在不安全的网络或存储地方共享数据的一种方法。在公钥加密出现之前，一个广泛的观点是如果两个用户想要秘密的交流数据那么他们需要提前建立一个共同持有的密钥k 。尽管对于一些小的或是紧密结合的组织来说这个是可以接受的，但是对于像如今这样一个拥有数十亿用户的网络来说，这样的解决办法明显不可行。30年前Diffie和Hellman提出了一个全新的想法，这就是公钥加密的概念，这意味着双方不需要持有一个提前商量好的共同密钥就可以实现和对方安全通信——在当时这个想法颠覆了传统认知。

如今，公钥加密是一个非常有用的工具，它在构建安全网络通信(例如SSH、SSL)、磁盘加密和安全软件补丁分发等工具中无处不在。然而，一个根深蒂固的观点是：（1）加密是向持有密钥的单个实体发送消息或数据的方法，（2）解密数据要么全部获取要么一点也得不到——实体要么可以解密然后读取整个明文，要么除了明文长度外一点关于明文的东西都学不到。

1 Introduction

Encryption is a method for a user to securely share data over an insecure network or storage site.Before the advent of public key cryptography, a widely held view was that for two users to communicate data confidentially they would need to a priori establish a mutually held secret key k.While this might be acceptable for some small or tightly knit organizations,such a solution was clearly infeasible for larger networks such as today's Internet consisting of billions of users. Over thirty years ago, Diffie and Hell- man [DH76a.DH76b] put forth a radically new idea in the concept of public key cryp- tography, where two parties can securely communicate with each other without having an a prior mutual secret— radically challenging the conventional wisdom of the time. Today public key encryption is an invaluable tool and its use is ubiquitous in building tools from secure web communication (e.g., SSH, SSL), to disk encryption, and secure software patch distribution.However,there is an ingrained view that:(1) Encryption is α method to send α messαge or dαtα to α single entity holding α secret key, and (2)Access to the encrypted dαtα is αll or nothing - one cαn either deανyei αnd rend the entire plαintext or one leαrns nothing αt αll αbout the plαintext other thαn its length.

对于许多新兴的应用（如云服务），公钥加密不够用了。例如，通常需要在密文中指定一个解密策略，只有当个体满足所指定的策略时才能解密。更一般地说，我们可能希望仅允许访问明文的一个函数，这取决于解密者的授权。现在来举一个具体的例子，考虑在云上存储的加密图像。执法部门可能需要在云上搜索包含特定人脸的图像。因此，云需要一个受限制的密钥来解密包含目标人脸的图像，但是不可以显示任何其他图像。更一般地说，这个密钥仅可以解密明文的一个函数，例如，除目标人脸外其余地方均模糊的图像。传统的公钥加密不能帮助我们完成这项任务。

我们认为，现在是时候采用加密系统的一个新的广阔视野。为此，我们探讨了函数加密（功能加密）的概念。在一个函数加密系统内，解密密钥允许用户学习到加密数据的一个函数。简而言之，在函数加密系统中对于一个功能F(·，·) （模拟为一个图灵机），一个持有主密钥的权威机构可以生成一个私钥 skₖ ，这个私钥有能力在加密数据上计算出函数值 F(k，·) 。更准确的来说，解密者使用私钥 skₖ 可以从 x 的密文中计算出函数值 F(k，x) 。直观来看，该系统的安全性是保证不可以学习到关于 x 更多的东西。但是正如我们将要看到的那样，严格的刻画这个安全是非常具有挑战的。

For many emerging applications such as “cloud"services this notion of public-key encryption is insufficient. For example, there is often a need to specify a decryption policy in the ciphertext and only individuals who satisfy the policy can decrypt.More generally, we may want to only give access to a function of the plaintext,depending on the decryptor's authorization. As a concreteexample,consider a cloudservice stor- ing encrypted images.Law enforcement may require the cloud to search for images containing a particular face.Thus, the cloud needs a restricted secret key that decrypts images that contain the target face, but reveals nothing about other images. More gen- erally,the secret key may only reveal a function of the plaintext image,for example an image that is blurred everywhere except for the target face. Traditional public-key cryptography cannot help with such tasks.

We believe that it is time to adopt a new broad vision of encryption systems. To this

end,we explore the concept of functionαl encryption.In a functional encryption sys-tem, a decryption key allows a user to learn a function of the encrypted data. Briefly, in a functional encryption system for functionality F(·，·)(modeled as a Turing Ma- chine) an authority holding a master secret key can generate a key skₖ that enables the computation of the functionF(k，·)on encrypted data. More precisely,using skk the decryptor can computeF(k，x) from an encryption of x.Intuitively,the security of the system guarantees that one cannot learn anything more about x，inas we shall aee capturing this rigorously is quite challenging.

现在已经可以知道函数加密的能力了吧。再让我们考虑一下如果对于任意多项式时间的图灵机F(·，·) 可以实现函数加密的话，可以实现什么呢？在访问控制方面的应用中，可以设置 x＝(ind，m) 编码一个消息 m 以及一个任意复杂的访问控制程序 ind （作用是对用户凭证的描述）。函数 F 解释了程序 ind 在 k 上的作用，当且仅当 ind 接受 k 时输出消息 m 。此外， ind 还应该被隐藏起来，则人们不一定知道为什么成功解密或者那种密钥满足 ind 。在第3节中，我们给出了更多其他的例子。

We can now see the power of functional encryption.Let us consider what can be achieved if we could realize functional encryption for any polynomial-time Turing Ma- chine F(·，·).In applications of access control,one could let x= (ind，m) encode a message m as well as an arbitraly complex access control program ind that will act over the description of a user's credentials.The functionality F would interpret the program ind over k and output the message m if and only if ind accepts on input k. Moreover, the program ind would be hidden and thus one would not necessarily know why decryption was successful or what other keys would satisfy ind. We give many more examples in Section 3

论文贡献：最近，有多种系统超出传统加密的边界。比如，身份基加密、可搜索加密、属性基加密。它们以及一些相关的研究（例如[BW07]，[KSW08]）提出了特定的新系统，用于解决从表达访问控制到搜索加密数据等问题。在过去的几年里，术语(函数加密！)被用来形容这个新领域。

尽管这些成果包含着函数加密的特殊案例，一般性的概念还从来没有被形式化的定义或研究。本篇文章我们正式地提出这个课题一个形式化的处理，并讨论了许多尚存的挑战。从函数加密的一般框架和语法开始，展示如何将现有的加密概念(如基于属性的加密和许多其他概念)优雅地表示为函数加密的特定功能。

定义抽象函数加密的安全性是非常有意义的。自然地，从基于游戏的不可区分性定义开始(基于[lBW07],[KSW08]中安全谓词加密的定义)。不幸的是，我们表明这个简单的定义对于某些函数是不够的（因为存在满足这个安全定义的平凡结构是不安全的）。

Our Contributions. Recently, there have been multiple systems that suggest moving beyond the traditional boundaries of encryption. Some examples include Identity-BasedEncryption[Sha84,BF03.CocO1],searchableencryption [BCOP04] and Attribute-Based Encryption [SW05].These and other related works such as [BW0Z,KSW08] propose specific new systems for problems ranging from expressive access control to searching on encrypted data. In the last few years, the term "functional encryptiorˡ”was adopted to describe this new area [LOS ⁺10.OT10.AL101.

While these results contain special cases of functional encryption,the general con- cept has never been formally defined or studied.In this paper we put forth a formal treatment of the subject and discuss many of the remaining challenges. We begin with a general framework and syntax for functional encryption and show how existing encryption concepts, such as attribute based encryption and many others,can be ele- gantly expressed as particular functionalities of functional encryption.

Defining security of abstract functional encryption turns out to be highly non-trivial We begin with a natural indistinguishability game-based definition (based on a defini- tion of secure predicate encryption from |BW07.KSW081). Unfortunately, we show that this simple definition is inadeguate for certain functionalities since trivially inse- cure constructions may satisfy it.

Given the inadequacy of game-based definitions we move to simulation-based def- initions in the spirit of the original notion of semantic security of Goldwasser and Micali [GM84].The goal is to capture the notion that the adversary learns nothing about the plaintext other than functions F(k，·) of the plaintext for which he has a secret key. Somewhat surprisingly, we show a connection to non-committing encryp- tion [CFGN96，Nie02] which proves that our definition cannot be satisfied for the same reason that non-interactive non-committing encryption is impossible. However, we show that our definition can be satisfied in the random oracle model,and we ex- hibit constructions for interesting functionalities that can be shown to be secure.(Inde- pendently, O'Neill[ON10]also observed a gap between simulation and game-based definitions and a connection to non-committing encryption.)

Functional encryption is still in its infancy and many fascinating open problems re- main. We conclude with several directions for future work.The key challenge is the construction of functional encryption for more general functionalities.Another impor- tant question is understanding the relative power of functionalities: vheedoes one fuec-tionality imply another and when can functionalities be black-box separated?

鉴于基于游戏的定义的不足，我们根据Goldwasser和Micali的原始语义安全概念的精神转向基于模拟的定义。目标是捕获这样一种概念，即攻击者除了拥有秘密密钥的明文函数F(k，·) 之外，对明文一无所知。有些令人惊讶的是，我们展示了一个与非承诺加密的连接，它证明了我们的定义不能被满足，原因与非交互式非承诺加密是不可能的相同（应该是在标准模型下不可能被满足吧）。然而，我们的定义在随机谕言机下是可以被满足的，并展示了可证明安全的有趣函数的构造（另外，O'neill也观察到了基于模拟和基于游戏的定义之间的差距，以及与非承诺加密的联系）。

函数加密仍处于起步阶段，仍然存在许多令人着迷的开放问题。我们总结了未来工作的几个方向，关键的挑战是构建更通用的功能的函数加密。另一个重要的问题是理解功能的相对力量:什么时候一个功能意味着另一个功能，什么时候功能可以被黑盒分离?

2 函数加密语法

我们首先解释函数加密的句法定义（对于一个功能F 来说）。功能 F 描述了可以从密文中学到的明文函数。准确来说，一个功能的定义如Definition 1 所示。

Definition 1 ：一个功能 F 是定义在 (K，X) 上的一个函数 F：K × X → {0，1}* ，可以被一个确定的图灵机描述。集合 K 称作密钥空间，集合 X 称作明文空间，我们要求密钥空间包含一个特殊的空密钥 ϵ 。

We begin by describing the syntactic definition of functional encryption (FE) for a func- tionality F.The functionality F describes the functions of a plaintext that can be learned from the ciphertext.More precisely, a functionality is defined as follows.

Definition 1.A functionαlity F defined oνer (K，X)is α function F：K × X → {0，1}* described αs α (deterministic) Turing Mαchine.The set K is cαlled the key space αnd the set X is cαlled the plaintext space. We require thαt the key spαce K cnαin α speαiαl key cαlled the empty key denoted ϵ.

对于功能F，在已知 x 的密文和 k 的密钥 skₖ 时，函数加密方案要有能力计算 F(k，x) 。使用 skₖ 计算 F(k，x) 的算法叫做解密。更准确地说，一个函数加密方案的定义如Definition 2 所示。

Definition 2：对于一个定义在 (K，X) 上的功能 F 来说，函数加密方案(FE)是包含四个PPT算法（初始化，密钥生成，加密，解密）的元组，且对于 ∀k ∈ K，∀x ∈ X 要满足下述相关条件：

• (pp，mk) ← setup(1λ) （产生公开参数和主密钥对）；

• sk ← keygen(mk，k) （产生关于 k 的密钥）；

• c ← enc(pp，x) (生成密文消息 c )；

• y ← dec(sk，c) (使用 sk 从密文 c 中计算 F(k，x) )。

要求y＝F(k，x) 的概率为 1 。

A functional encryption scheme for the functionality F enables one to evaluate F(k，x) given the encrvption of x and a secret key skₖ for k. The algonthm for evaluation

F(k，x) using skₖ is called decrypt.More precisely， a functional encryption scheme is defined as follows.

Definition 2. A functionαl encryption scheme (FE) for α functionαlity F defined oνer (K，X) is α tuple of four PPT αlgorithms (setup，keygen，enc，dec) sαtisfying the fol-lowing correctness condition for αll k ∈ K αnd x ∈ X ：

(pp，mk) ← setup(1λ) ( generαte a public αnd mαster secret key pαir)

sk ← keygen(mk，k) ( generαte secret key for k)

c ← enc(pp，r) (encrypt messαge x)

y ← dec(sk，c) (use sk to compute F(k，x)from c)

then we re quire thαt y＝F(k，x) with probαbility 1.

在第4节我们会定义函数加密方案的安全性。现在，简要的展示一下：标准公钥加密是函数加密的一个简单的例子。设密钥空间K：＝{1，ϵ} ，考虑下述定义在 (K，Ⅹ) （对于一些明文空间 X ）上的功能 F ：

{m k＝1

F(k，x)：＝ 。

{len(m) k＝ϵ

对于k＝1 的密钥可以完全解密有效密文，而空密钥 k＝ϵ 只是返回明文的位长度。因此，该功能在语法上定义了标准的公钥加密。

空密钥 ϵ：密钥空间 K 中空密钥 ϵ 刻画了有意从密文中泄露的明文的所有信息，例如加密明文的长度。 ϵ 的密钥为空也用 ϵ 表示。因此，任何人都可以在密文

ʀ

c ← enc(pp，x)上运行解密算法 dec(ϵ，c) ，然后获得 c 有意泄露的关于 x 的所有信息。

进一步参数化：在某些情况下，密钥空间 K 和明文空间 X 通过初始化算法的生成数量被进一步参数化。例如，初始化可能输出一个 RSA 模 N ，在这种情况下集合 K 和 X 以及功能 F 定义为 ℤɴ 上的元组。更一般地说，我们允许初始化输出第三个参数 π ，通过 Kπ 和 Xπ 定义密钥空间和明文空间。功能 F 定义为： Fπ：Kπ × Xπ → {0，1}* 。其中 π 在文中是明确的，避免把它写成一个明确的下标。

We define security of a functional encryption scheme in Section 4 For now,we briefly show that standard public-key encryption is a simple example of functional encryption.

Let K：＝{1，ϵ} 1.c and consider the following functionality F defined over (K，X) for some plaintext space X：

x if k＝1

F(k，x)：{＝

len(x) if k＝ϵ

A secret key for k＝1 fully decrypts valid ciphertexts, while the empty key k＝ϵ simply retums the bit length of the plaintext.Hence,this functionality syntactically defines standard public-key encryption.

The empty key ϵ：The special key ϵ in K captures all the information about the plaintext that intentionally leaks from the ciphertext, such as the length of the encrypted plaintext. The secret key for ϵ is empty and also denoted by ϵ. Thus, anyone can run dec(ϵ，c)

ʀ

on a ciphertext c ← enc(pp，x) and obtain all the information about x that intentionally leaks from c.

Further parametrization.In some cases the key space K and plaintext space X are further parametrized by quantities generated by the setup algorithm.Forexample, setup may output an RSA modulus N in which case the sets K and X and the functionality F are defined as tuples over ℤɴ. More generally, we allow setup to output a third parameter π and we denote the key and plaintext space by Kπ and Xπ .The functionality F is the defined as

Fπ：Kπ × Xπ → {0，1}*.

When π is clear from context, we avoid writing it as an explicit subscript.

2.1 函数加密的子类

到目前为止，我们为函数加密方案定义了最通用的语法。来看看我们想到的应用，可以很方便的定义函数加密的两个子类，其中明文空间X 具有额外的结构。

谓词加密：在许多应用中，明文 x∈Ⅹ 本身是一个对 (ind，m) ∈ l × M ，其中 ind 称作索引， m 称作有效载荷消息。例如，一个电子邮件系统内，索引可能是发送者的姓名而有效载荷是邮件内容。

在这种情况下，一个函数加密方案可以被定义为一个多项式时间的谓词 P：K × l → {0，1}， 其中 K 是密钥空间。更准确地说，在 (K∪{ϵ}，(l × M)) 上的功能 F 定义为：

F(k ∈ K，(ind，m) ∈ X)↓

m P(k，ind)＝1

：＝{ ←

⊥ P(k，ind)＝0

。

紧接着，设c 是 (ind，m) 的加密结果，设 skₖ 是 k ∈ K 的密钥。则解密过程 dec(skₖ，c) 在 P(k，ind)＝1 时显示 c 中的有效载荷，其他情况不显示关于 m 的任何东西。

So far we defined the most general syntax for a functional encryption scheme. For th|e applications we have in mind it is convenient to define two sub-classes of functional encryption where the plaintext space Xhas additional structure.

Predicate encryption [BW07，KSW08]. In many applications a plaintext x ∈ X is itself a pair (ind，m) ∈ I × M where ind is called an index and m is called the payload message. For example, in an email system the index might be the sender's name while the payload is the email contents.

In this context, an FE scheme is defined in terms of a polvnomial-time predicate P：K × l → {0，1} where K is the key space. More precisely, the FE functionality over (K∪{ϵ}， (I × M)) is defined as

F(k E K， (ind，m) ∈ X)↓

m if P(k，ind)＝1，and

：＝{ ←

⊥ if P(k，ind)＝0

Consequently，let c be an encryption of (ind，m) and let skₖ be a secret key for k ∈ K. Then dec(skₖ，c) reveals the payload in c when P(k，ind)＝1 and roueals aothing new about m otherwise.

带有公开索引的谓词加密：谓词加密的一个子类是从密文中可以很容易的获得明文索引。特别地，在函数加密的这种类型中，空密钥 ϵ 明确显示了索引 ind ，即 F(ϵ，(ind m))＝(ind，len(m)) 。因此，解密过程 dec(ϵ，c) 让任何人都可以获得明文 m 的索引以及比特长度。

Predicate encryption with public index.A sub-class of predicate encryption makes the plaintext index easily readable from the ciphertext.In particular,in this type of FE the empty key ϵ explicitly reveals the index ind, namely

F(ϵ，(ind，m)) ＝ (ind， len(m) )

Hence, dec(ϵ，c) gives anyone the index component of the plaintext an well as the bit length of m.

参考

1. Boneh, D., Sahai, A., Waters, B. (2011). Functional Encryption: Definitions and Challenges. In: Ishai, Y. (eds) Theory of Cryptography. TCC 2011. Lecture Notes in Computer Science, vol 6597. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19571-6_16

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