当前位置：首页 > news >正文

函数加密（Functional Encryption）简介

news 来源：原创 2025/7/5 22:58:48

1. 引言

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

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

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

而在函数加密中：

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

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

初始化阶段会生成一个主私钥 $\mathit{msk}$ ，
在密钥生成阶段，可以利用该主私钥针对特定函数 $f$ 派生出函数私钥 $\mathit{sk_f}$ 。
加密算法的逻辑相同，而解密操作则需要函数私钥 $\mathit{sk_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$ 创建对应的函数私钥 $\mathit{sk_{f_1}}, \dots, \mathit{sk_{f_i}}, \dots, \mathit{sk_{f_n}}$ ，其中每个函数 $f_i$ 表示对病历数据的一种特定访问策略。随后，管理方将各个函数私钥分发给相应类别的专业人员。

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

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

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

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

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

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

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

1）可应用于加密数据上的函数 $f$ 的差别：
- 在全同态加密（FHE）中，被应用于加密数据上的函数 $f$ （即评估阶段）是任意的：
  - Bob 可以在密文 $\mathit{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 ()$ 生成密钥对 $(\mathit{pk}, \mathit{sk})$ ，并将 $\mathit{pk}$ 提供给对手 $\mathcal{A}$
$\mathcal{A}$ 得到公钥 $\mathit{pk}$
$\mathcal{A}$ 选择两条等长的消息 $m_0$ 和 $m_1$ ，并将它们发送给挑战者
挑战者使用公钥加密消息 $m_b$ （其中 $\in \{0,1\}$ ，但 $\mathcal{A}$ 并不知道 $b$ 的值）： $\mathit{c} \leftarrow E(\mathit{pk}, m_b)$
$\mathcal{A}$ 得到密文 $\mathit{c}$ 并输出一个猜测值 $\in {0,1}$

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

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

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

正如 Morrolan 所指出的：

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

也就是说：

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

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

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

对手可以使用其函数私钥对密文 $\mathit{c}$ 解密并得到 $f(m_b)$ ，但与之前类似，无法判断密文 $\mathit{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