基于模拟的安全性 | Codeboy's Blog

形式陈述

基于模拟的定义先固定协议 $\Pi$ 、理想功能 $\mathcal F$ 、安全参数 $\lambda$ 、参与方与通信调度，再明确允许的腐化集合、攻击方式、辅助输入和输出观察者。真实世界中，各方运行 $\Pi$ ，真实对手 $A$ 控制被腐化方及模型授予的网络能力；理想世界中，诚实方把输入交给可信功能 $\mathcal F$ ，理想对手或模拟器 $S$ 只能通过规定接口与 $\mathcal F$ 、被腐化方和观察环境交互。

单次执行：比较终点的联合分布

先明确一个 stand-alone 接口：输入 $\mathbf x$ 与辅助信息 $z$ 在执行前固定，外部观察者不在线改变输入、消息或并发调度。记 $\mathsf{REAL}_{\Pi,A}(1^\lambda,\mathbf x,z)$ 为真实执行后对手输出与全体诚实方输出的联合分布， $\mathsf{IDEAL}_{\mathcal F,S}(1^\lambda,\mathbf x,z)$ 为理想执行对应的联合分布。腐化方视图应包含输入、随机币、收发消息与可见状态；被动模型可以直接模拟这个完整视图，再让同一个对手作后处理。模拟器不能读取未由理想接口泄漏的诚实输入。

典型计算安全用不可区分性要求

\forall A\in\mathrm{PPT}\;\exists S\in\mathrm{PPT}:\qquad \mathsf{REAL}_{\Pi,A}\approx_c\mathsf{IDEAL}_{\mathcal F,S}.

此处 ensemble 按安全参数、允许的输入及辅助信息索引；输入长度按模型受多项式约束。终点判别器得到公开安全参数 $1^\lambda$ 。展开不可区分性，是对每个允许的 PPT 终点判别器 $D$ 存在可忽略函数，使所有允许输入及辅助信息上的接受概率差满足该界：

\left|\Pr[D(1^\lambda,\mathsf{REAL}_{\Pi,A},z)=1] -\Pr[D(1^\lambda,\mathsf{IDEAL}_{\mathcal F,S},z)=1]\right| \le\operatorname{negl}(\lambda).

顺序 $\forall A\exists S\forall D$ 要求先针对 $A$ 选定一个 $S$ ，再用它应对所有终点测试； $S$ 的可用信息是 $A$ 的代码及理想接口提供的内容。额外保留与输入相关的 $z$ ，使结论覆盖带有先验知识的观察者。概率覆盖两个执行中模型规定的全部随机币。采用均匀隐藏世界位的猜测实验时， $|2\Pr[b'=b]-1|$ 与接受概率差同规范，而成功率减 $1/2$ 少一个因子 $2$ 。

在线环境：额外的交互责任

另一类定义让环境 $Z$ 在执行过程中提供输入、读取输出并与对手交互。此时比较的是 $\mathsf{EXEC}_{\Pi,A,Z}(1^\lambda,z)$ 与 $\mathsf{EXEC}_{\mathcal F,S,Z}(1^\lambda,z)$ 的环境输出，量词通常写成 $\forall A\exists S\forall Z$ ，并须同时指定机器模型、激活与调度规则、会话及子程序接口。与终点判别器相比，关键变化是观察者获得了执行中的交互接口。

同一个模拟器须在环境接下来的行为尚未发生时，就按理想权限回应交互。环境能并发组织其他执行时，终点分布的单次证明未必足够；通用可组合安全及其组合定理处理的是明确模型下的这项更强责任。

统计模拟把两个输出 ensemble 的总变差要求为可忽略，从而允许计算无界 distinguisher；完美模拟要求分布逐参数完全相同。模拟器通常仍要求高效，否则它可能靠穷举获得现实中不应存在的解释。采用哪一层安全性、模拟器是严格 PPT 还是期望 PPT，都应在定理中写明。

腐化和执行模型是定义的一部分。静态腐化在协议开始前选定被腐化方；自适应腐化允许执行中改变集合，并要求处理已使用随机币与内部状态。半诚实对手按协议运行但观察全部内部信息，恶意对手可任意偏离；同步、异步、认证信道、可信设置、允许 abort、公平性和输出交付都会改变 $\mathcal F$ 及可模拟能力。

直觉

理想功能是一份安全规格：它明确攻击者在最理想实现中仍能知道什么、改变什么、延迟什么。若现实攻击者制造的每一种可观察结果，都能由只使用这些理想权限的模拟器复现到不可区分，那么现实协议没有额外泄漏信息，也没有赋予攻击者规格之外的能力。

模拟器是证明中的解释器。它用真实对手的代码和理想接口合成一个看似真实的视图；观察者若无法判断自己身处哪一边，现实行为的攻击收益就受到理想规格的约束。

例子与边界

零知识提供最小例子。真实 verifier 与知道 witness 的 prover 交互并得到完整 view；理想侧的 simulator 不知道 witness，却仅凭公开语句生成不可区分的 verifier view。这说明 verifier 从 transcript 中获得的内容可以不依赖 witness 重建，但不说明语句为假时 prover 不能欺骗，后者由 soundness 单独保证。

多方计算中，理想功能像可信方：收集各方输入、计算 $f(\mathbf x)$ ，再按规格发送输出或允许特定 abort。现实协议若安全，恶意参与者在消息调度、输入选择与中途退出中造成的全部影响，都应能由 $S$ 在理想接口内重现。若理想功能允许对手看见输出后再阻止诚实方收到结果，所得结论只有 security with abort，不能描述成完全公平。

模拟任务覆盖所有允许的输入、辅助信息和相应观察者，并比较完整联合分布。因而模拟器要同时复现腐化方内部状态、可见消息时序和输出相关性；联合测试可以检查字段间的约束，单个字段的边缘分布只描述其中一部分。

三方求和的完整模拟例把这种要求变成逐点计数：模拟器只取腐化方输入和总和，生成完整发送行、接收列和公开列和，并证明每个合法视图在两侧的概率都是 $q^{-5}$ 。该等式连同全部输出及辅助信息成立；即使输出反推出某个输入，也不表示协议产生了额外泄漏。

Stand-alone 模型通常分析一份协议与外部执行隔离的情形，证明可使用 rewinding 等技术。通用可组合模型允许环境并发运行其他协议并在执行间传递消息，要求同一个模拟器在定义允许的上下文中维持不可区分。相应组合定理在其机器模型、会话及子程序条件下，将这种交互保证用于组合后的系统。

自适应腐化还带来状态一致性任务：环境在看见消息后腐化发送者时，模拟器须使此前消息与新暴露的随机币相符。可擦除状态、非承诺加密等技术各自在适用模型中帮助完成这一任务；静态证明则只处理执行前已选定的腐化集合。

推论与应用

基于模拟的安全性统一了零知识、秘密共享、安全多方计算和可组合协议的证明语言。它把“安全”拆成一份理想功能与一项不可区分结论，使泄漏、abort、腐化、调度和设置假设都能在规格层接受审查，而不埋进证明叙述。

实际证明常用混合论证在真实执行与理想执行之间逐步替换组件。每一步都要保持接口一致并记录优势和运行时间损失；最终结论只覆盖定义允许的环境。侧信道、实现错误或模型外协议组合若未进入所选观察接口，就不会由抽象模拟定理自动处理。

固定两会话组合把在线定义落实为两次环境包装、一个统一模拟器和完整优势／资源账本；理想OT下的两门混淆电路则给出双方静态半诚实的完美单次模拟，明确两种保证的接口不同。

参考资料

Yehuda Lindell, “How to Simulate It — A Tutorial on the Simulation Proof Technique”, in Tutorials on the Foundations of Cryptography, Springer, 2017, Chapter 6，§6.4.2，Definition 6.4.1，pp. 283–285；§6.10.1，p. 341：终点联合分布与交互环境的区别。
Shafi Goldwasser, Silvio Micali, and Charles Rackoff, “The Knowledge Complexity of Interactive Proof Systems,” SIAM Journal on Computing 18(1), 1989。
Oded Goldreich, Silvio Micali, and Avi Wigderson, “How to Play Any Mental Game,” STOC 1987，simulation for secure computation。
Ran Canetti, “Universally Composable Security: A New Paradigm for Cryptographic Protocols,” FOCS 2001; Journal of the ACM 2020 version。

形式陈述 ​

单次执行：比较终点的联合分布 ​

在线环境：额外的交互责任 ​

反向链接

形式陈述

单次执行：比较终点的联合分布

在线环境：额外的交互责任