固定会话下的安全组合

形式陈述

固定两个会话的交互接口

组合安全要保证：把协议内部的理想服务换成安全实现后，外部系统仍满足相应的真实—理想比较。下面证明一个固定两个会话的替换引理。它保留通用可组合安全中的在线环境和统一模拟器，但不重证完整 UC 机器模型的组合定理。[1]

固定父协议 $R$ 、两个公开会话标识 $s_1,s_2$ 、固定参与方身份，以及执行前选定的腐化集合 $C$ 。第 $i$ 个子程序槽位可运行真实协议 $\pi_i$ ，或具有同样诚实输入／输出接口的理想功能 $F_i$ 。所有实验共同使用下列模型：

每个机器均为严格概率多项式时间；整个执行的总步数、激活次数、消息总长度和辅助输入长度都有多项式上界，不能只限制一次激活。
各槽位私有存储分离，随机带独立。父协议可通过接口传入相关输入，也可把前一次输出作为后一次输入；隔离不要求输入独立。
消息只经过带会话名与类型的端口。诚实输入不通过对手转交；对手只能使用声明的腐化、泄漏、调度和中止接口。两世界保持同一权限。
不存在共享秘密状态、共享可变全局量、会话标识碰撞、偷读诚实内存或辨认挑战实现代码的接口。不创建新会话，不包含递归调用。
在线环境 $Z$ 可以在执行中提供输入、读取允许输出并与对手通信；调度可依赖已经看到的记录。所有世界使用相同的路由和调度语义。
允许的环境类对下文的局部包装封闭：可在内部运行 $R$ 、对手、另一个槽位及已选定的模拟器，并将剩余槽位接到挑战接口；包装后的总资源仍在假设覆盖范围内。

最后一项是归约能成立的实际条件。若环境类禁止运行其中某台机器，就不能把“其余系统”自动当成合法判别环境。

子程序假设：先固定模拟器，再量化环境

令 $D_i$ 是第 $i$ 个槽位的固定对手转发器：原样转交允许的对手消息和泄漏，不增加权限。假设存在在线模拟器 $S_i$ ，使每个允许的周围环境 $W$ 、辅助输入 $z$ 都满足

\left| \Pr[\operatorname{Exec}(\pi_i,D_i,W;1^\lambda,z)=1] -\Pr[\operatorname{Exec}(F_i,S_i,W;1^\lambda,z)=1] \right| \le\varepsilon_i(\lambda;t_W). \tag{1}

$\operatorname{Exec}$ 表示该环境最终输出的接受位。 $\varepsilon_i(\lambda;t_W)$ 是已证明覆盖相应资源界的优势上界；若只作渐近陈述，也可对每个固定 $W$ 使用其自身的可忽略界，不需要凭空假设一个支配所有 PPT 环境的统一函数。

$S_i$ 必须独立于 $W,z$ 选定，且只能从理想功能获准的接口取信息。这个假设可由在线模拟定义中的 $\forall A_i\exists S_i\forall W$ 取 $A_i=D_i$ 得到；本页不需要另证一般的 dummy-adversary 等价定理。只对执行终点样本成立的 stand-alone 模拟，不能直接充当式 (1)。

两子程序替换引理。 在这些条件下，对每个整体真实对手 $A$ ，存在一个不依赖于 $Z,z$ 的严格 PPT 理想对手 $S^A$ ，使同时替换两个槽位后的接受概率差至多

\varepsilon_1(\lambda;T_1)+\varepsilon_2(\lambda;T_2), \tag{2}

其中 $T_1,T_2$ 是下文实际包装环境的资源界。若两项在这些包装环境下可忽略，则组合差也可忽略。

直觉

把一个子程序替换掉时，外部看见的不只是它最后返回的字符串。外部可能先发一条消息、根据响应安排另一会话，再回到原会话。式 (1) 要求同一个模拟器应对整个过程，因而“其余系统作为环境”才是合法归约。

两个替换不是同时跳到终点。先把第一个真实槽位换成理想功能及其模拟器；第二步必须在这个已经改变的世界中替换第二个槽位。否则两个局部比较可能根本没有共同的中间实验。

例子与边界

三个实验与同一个整体对手

先固定任意 $A$ ，再固定由式 (1) 给出的 $S_1,S_2$ 。保持 $R,Z,z,C$ 和调度接口不变，定义

实验	会话 $s_1$	会话 $s_2$
$H_0$	$\pi_1$	$\pi_2$
$H_1$	$F_1$ 与 $S_1$	$\pi_2$
$H_2$	$F_1$ 与 $S_1$	$F_2$ 与 $S_2$

这里“与 $S_i$ ”表示理想侧对手适配器，诚实调用仍直接通向 $F_i$ 的规定端口。整体对手 $A$ 仍按自己的代码行动，它在该槽位看到的对手记录由 $S_i$ 产生。

若已经证明两个相邻差分别至多 $2^{-\lambda}$ 与 $3\cdot2^{-\lambda}$ ，式 (2) 给出 $4\cdot2^{-\lambda}$ 。在 $\lambda=8$ 时为 $1/64$ 。这只是给定局部界的预算示例，不是某份未说明协议的测量结果。采用接受概率差时没有额外的二倍因子；若改用猜测成功率减 $1/2$ ，则必须整体转换优势规范。

同一份掩码为何破坏隔离

考虑两个仅向被动观察者显示一次一密密文的子程序。第 $i$ 个诚实输入为 $m_i\in\{0,1\}^\lambda$ ，显示 $c_i=m_i\oplus K_i$ ，理想泄漏只有长度。独立均匀 $K_i$ 时，显示内容可以由独立均匀字符串完美模拟。

若实现擅自让两会话共享同一个隐藏 $K$ ，便有

c_1\oplus c_2=m_1\oplus m_2.

固定一个判别环境：私下均匀独立选 $m_1,m_2$ ，通过诚实端口送入；不向对手泄漏它们，按固定时间表请求两份密文，再检查上述等式。缺少任何输出就拒绝。共享掩码的真实侧总被接受；只得到两个长度的理想模拟器，其输出对与均匀的秘密异或无关，接受概率至多 $2^{-\lambda}$ 。因此区分差至少为

1-2^{-\lambda}.

$\lambda=2$ 时有 16 对消息。固定任意两份模拟密文，其异或只对应其中四对消息，接受概率为 $1/4$ ；真实侧全部 16 对通过，差为 $3/4$ 。这不是替换引理的反例：共享密钥已经违反槽位私有状态与随机性的隔离。

终点安全不足以启动哪一步

若只知道每个 $\pi_i$ 的最终视图可由单次执行模拟器重建，下面的 $W_1$ 仍可能在拿到一条响应后调用另一个槽位，再根据其输出发送下一条消息。这样的 $W_1$ 是在线交互环境，未必属于终点安全假设的量词范围。缺口在于局部假设不能应用，而非三角不等式失效。

同样，共享 CRS、随机预言机、密钥服务或外部账户若要进入组合模型，必须显式规定共同接口与安全保证。本页的隔离条件排除了这些共享设置；更广的 UC 定理可以处理其规定的模型，不能仅凭本页引理省略它们。

推论与应用

第一次替换的环境包装

构造 $W_1$ ，在内部运行 $Z,R,A,\pi_2$ 及路由／调度器，只把会话 $s_1$ 留给外部挑战。 $A$ 发给该会话的对手操作经转发器送出，响应原样交还；诚实调用从 $R$ 的对应端口送到挑战诚实接口。

挑战为 $(\pi_1,D_1)$ 时，包装执行就是 $H_0$ ；挑战为 $(F_1,S_1)$ 时，就是 $H_1$ 。把相同局部机器的随机带耦合为相同值，按激活步数归纳：下一条路由消息、接收机器的状态转移和可见输出均与相应实验一致。封装隔离保证没有遗漏一条绕过端口的通信。因此式 (1) 给出

|\Pr[H_0=1]-\Pr[H_1=1]| \le\varepsilon_1(\lambda;T_1).

这是实验的精确实现关系，并不声称真实协议与理想功能的每次运行逐点相等。

第二次替换与总模拟器

构造 $W_2$ ，内部运行 $Z,R,A,F_1,S_1$ 及同一个路由规则，只把 $s_2$ 留给挑战。第一次已经替换的 $F_1,S_1$ 必须保留在包装内。于是两种挑战分别精确实现 $H_1,H_2$ ，同样得到

|\Pr[H_1=1]-\Pr[H_2=1]| \le\varepsilon_2(\lambda;T_2).

将两式按混合论证相加，得到式 (2)。最终理想对手是

S^A=\operatorname{Router}[A,S_1,S_2].

它在本地运行 $A$ ，将两个槽位的对手操作分别交给 $S_1,S_2$ ，其余获准操作照常转发。最终对手不包含 $Z,R$ 或诚实组件；它们只在证明用的判别包装中被局部运行。 $A$ 先固定， $S_1,S_2$ 与环境无关，所以得到所需量词 $\forall A\exists S^A\forall Z,z$ 。

资源账本与适用终点

令 $t_X$ 为机器 $X$ 在整个允许执行中的总工作上界， $r$ 为路由和调度开销。把具体解释器的模拟慢化计入这些预算，可取

\begin{aligned} T_1&\le t_Z+t_R+t_A+t_{\pi_2}+r,\\ T_2&\le t_Z+t_R+t_A+t_{F_1}+t_{S_1}+r,\\ t_{S^A}&\le t_A+t_{S_1}+t_{S_2}+r. \end{aligned}

各项都是固定多项式，故模拟器高效。组件定理必须覆盖 $T_1,T_2$ ，仅覆盖原来的 $t_Z$ 不够。若声称“每步至多一微秒”，却允许不受限的激活次数，整个包装就未必是 PPT。

本页完成的是两个固定、隔离会话的在线替换。推广到多项式个会话需要统一索引和资源／误差界；推广到动态创建、嵌套会话、自适应腐化或共享设置，还需相应机器模型。Canetti 的完整 UC 定理还包含调用方合规、subroutine-respecting、subroutine-exposing 等条件，[1] 它们由原文处理，不由这张三行混合表替代。

参考资料

[1] Ran Canetti, Universally Composable Security, JACM 67(5), Article 28, 2020，§4.2 Definition 9，p. 28:42：在线模拟量词；§5.2 Definition 19，p. 28:52：子程序隔离；§6.1 Theorem 22，p. 28:58：完整组合定理及条件。链接为 NSF 保存的作者论文。本文两会话引理和数值例子在上述简化接口内独立展开，未复述完整 UC 定理证明。

形式陈述 ​

固定两个会话的交互接口 ​

子程序假设：先固定模拟器，再量化环境 ​

三个实验与同一个整体对手 ​

同一份掩码为何破坏隔离 ​

终点安全不足以启动哪一步 ​

第一次替换的环境包装 ​

第二次替换与总模拟器 ​

资源账本与适用终点 ​

反向链接