函数加密（Functional Encryption）简介

1. 引言

函数加密（FE）可以被看作是公钥加密（PKE）的一种推广，它允许对第三方的解密能力进行更细粒度的控制。

在公钥加密中，公钥 $pk$ 用于将某个值 $x$ 加密为密文 $ct$（通过加密算法），而私钥 $sk$ 用于从密文 $ct$ 中恢复出 $x$（通过解密算法）。公钥加密强制执行一种“全有或全无”的访问规则：

• 要么能够解密并读取完整明文，
• 要么完全无法获得任何关于明文的信息。

而在函数加密中：

• 私钥 $s{k}_f$ 与某个特定的函数 $f$ 相关联，使得解密函数返回的是 $f(x)$。
  • 可注意到，通过将 $f$ 设置为恒等函数（即$f(x)=x$），公钥加密就可以被看作是函数加密的一个特例。

更明确地说，如下图所示是 公钥加密 和 函数加密 这两种加密协议的不同“API”接口。函数加密：

• 初始化阶段会生成一个主私钥 $msk$，
• 在密钥生成阶段，可以利用该主私钥针对特定函数 $f$ 派生出函数私钥 $s{k}_f$。
• 加密算法的逻辑相同，而解密操作则需要函数私钥 $s{k}_f$ 来得到 $f(x)$。
  

非正式地说，一个函数加密方案的安全性要求对手除了 $f(x)$ 所泄露的信息外，无法从密文中获得关于 $x$ 的任何其他信息。BSW10——2010年Dan Boneh等人 Functional Encryption: Definitions and Challenges论文 中提供了对此类方案更正式的安全性定义。稍后会尝试更详细地解释它。现在，先通过一个示例应用来巩固对该加密方案的理解。

2. FE（函数加密）应用示例

来看一个医院的例子：医院保管着大量病人的记录，并且存在 $n$ 类具有不同访问权限的专业人员。在这种场景下，医院管理方首先执行初始化阶段（setup），然后为每一个函数 $f_1,\dots ,f_i,\dots ,f_n$ 创建对应的函数私钥 $s{k}_{f_1},\dots ,s{k}_{f_i},\dots ,s{k}_{f_n}$，其中每个函数 $f_i$ 表示对病历数据的一种特定访问策略。随后，管理方将各个函数私钥分发给相应类别的专业人员。

病人的记录通过 $pk$ 加密后，每位专业人员都只能通过解密函数获得其权限范围内的信息，而无法访问其他内容。

在这种设置中，医院只需生成一份加密的病历记录，便可支持多种访问级别。这比传统的对称加密或非对称加密方式更加高效——后者通常需要为每一类用户执行 $n$ 次加密操作。

3. 函数加密与全同态加密的区别

如果熟悉全同态加密（FHE），那么分析FHE与函数加密（FE）之间的异同会非常有趣。这两种密码学原语都支持在加密数据上执行函数，但它们的设置方式和应用场景完全不同。

典型的 FHE 应用场景适用于计算外包，其流程如下：

• Alice 执行初始化并将她的数据 $x$ 加密为密文 $ct$，然后将该密文发送给 Bob
• Bob 在密文 $ct$ 上计算函数 $f$，得到新的密文 $c{t}^{\prime }$，并将其结果返回给 Alice
• Alice 解密密文，得到 $f(x)$
  

函数加密与全同态加密的区别有：

• 1）可应用于加密数据上的函数 $f$ 的差别：
  • 在全同态加密（FHE）中，被应用于加密数据上的函数 $f$（即评估阶段）是任意的：
    • Bob 可以在密文 $ct$ 上执行任意算术函数，这个函数也可以是 Alice 私有的。
  • 相比之下，在函数加密（FE）中，可在密文上执行的函数集受限于主私钥生成的函数私钥。
• 2）评估与解密阶段的差别：
  • FHE 的评估函数返回的是另一个密文，需要 Alice 进一步参与解密。
  • 而在 FE 中，评估和解密是同时进行的，不需要进一步的交互即可获得 $f(x)$。

简而言之：

• FHE：始终需要与密钥持有者交互才能获得 $f(x)$，但函数 $f$ 是任意的（甚至可以是私密的）
• FE：不需要与密钥持有者交互就能获得 $f(x)$，但可执行的函数 $f$ 是受限的

4. FE 的安全性定义

函数加密的安全性是在可选择明文攻击下的不可区分性（IND-CPA）概念下定义的。这个安全性通过一个对手 $\mathcal{A}$ 和挑战者之间的博弈进行证明。该博弈的逻辑类似于用于证明公钥加密方案语义安全性的方式，如下所示：

先分析 PKE 的情形。对于 $b=0,1$，实验 $\mathsf{Exp}(b)$ 的流程如下：

• 挑战者使用函数 $G()$ 生成密钥对 $(pk,sk)$，并将 $pk$ 提供给对手 $\mathcal{A}$
• $\mathcal{A}$ 得到公钥 $pk$
• $\mathcal{A}$ 选择两条等长的消息 $m_0$ 和 $m_1$，并将它们发送给挑战者
• 挑战者使用公钥加密消息 $m_b$（其中 b ∈ { 0 , 1 } b \in \{0,1\} b∈{0,1}，但 $\mathcal{A}$ 并不知道 $b$ 的值）：$c\leftarrow E(pk,m_b)$
• $\mathcal{A}$ 得到密文 $c$ 并输出一个猜测值 $b^{\prime }\in 0,1$

如果没有任何高效（多项式时间）对手 $\mathcal{A}$ 能够区分 $m_0$ 和 $m_1$ 的加密密文，则该加密方案 $\mathcal{E}$（由其函数 $(G,E,D)$ 定义）在语义安全意义下是安全的。数学上，这被表示为：
$$\left|\mathrm{Pr}[\mathsf{EXP}(0)=1]-\mathrm{Pr}[\mathsf{EXP}(1)=1]\right|<\text{negligible}$$

其中，$\mathrm{Pr}[\mathsf{EXP}(0)=1]$ 表示对手在实验 0 中输出 1 的概率（即错误地猜测加密的是 $m_1$），而 $\mathrm{Pr}[\mathsf{EXP}(1)=1]$ 表示对手在实验 1 中正确输出 1 的概率。

换句话说，对手正确猜出被加密消息的概率应该非常接近于随机猜测的概率。实际中，这确保了对手即使能选择被加密的消息，也无法通过观察密文来获取关于明文的任何信息。

正如 Morrolan 所指出的：

• 当且仅当加密方案是非确定性的，这种安全属性才成立。

也就是说：

• 在同一个公钥下，对相同明文的两次加密操作应该以压倒性概率产生不同的密文。

在函数加密（FE）中，博弈仅有些许不同。对于 $b=0,1$，实验 $\mathsf{EXP}(b)$ 的过程如下：

• 挑战者生成密钥对 $(pk,msk)$ 并将其交给对手 $\mathcal{A}$
• $\mathcal{A}$ 可自适应地向挑战者提交不同的函数 $f_1,f_2,\dots ,f_i$，并接收相应的函数私钥 $s{k}_{f_1},s{k}_{f_2},\dots ,s{k}_{f_i}$
• 然后，$\mathcal{A}$ 选择两个消息 $m_1$ 和 $m_2$，满足对于所有已查询的函数 $f_i$，都有 $f_i(m_1)=f_i(m_2)$，并将它们提供给挑战者
• 挑战者用公钥加密消息 $m_b$（其中 $b\in 0,1$，但 $\mathcal{A}$ 并不知道 $b$ 的值）：$c\leftarrow E(pk,m_b)$
• $\mathcal{A}$ 得到密文 $c$，并输出一个猜测 $b^{\prime }\in 0,1$

对手可以使用其函数私钥对密文 $c$ 解密并得到 $f(m_b)$，但与之前类似，无法判断密文 $c$ 是对 $m_1$ 还是 $m_2$ 的加密 。这正是所描述的安全性定义的体现。

更进一步地，BSW10——2010年Dan Boneh等人 Functional Encryption: Definitions and Challenges论文 中指出：

• 上述安全定义对于某些特定函数 $f$ 是不充分的，并在论文中提出了更为严格的安全性定义。

5. 总结

除了在实际应用中对加密数据进行计算的显著作用，正如本文所描述的那样，函数加密在密码学理论中也已成为一种强有力的工具。它可用于构建更高级的密码原语，如 不可区分混淆（iO），iO被认为是“密码学完备”的：

• 几乎可以实现所有已知的密码原语。

特别地，根据 Sora 的 Introduction to Indistinguishability/Ideal Obfuscation(iO)可知：

• iO 可以通过递归函数加密（recursive FE）来构建。

参考资料

[1] Leku 2024年11月25日博客 A gentle introduction to functional encryption