问并发运行时不安全的协议示例

EN

考虑下表定义的函数f : \{L,R\} \times \{ U,D \} \to \{0,1,2\}：

`\begin{array}{c|cc}       f & L & R \\       \hline       U & 0 & 0 \\       D & 1 & 2    \end{array} #qcStackCode#`

假设Alice有来自\{L,R\}的输入(她选择了一列)，而Bob有来自\{U,D\}的输入(他选择了一行)。

f的一个简单协议如下：

1. 鲍勃清楚地宣布了他的意见。如果他的输入是U，那么各方可以停止，因为他们知道输出必须是0。
2. 如果鲍勃的输入是D，那么艾丽斯将她的输入清空。在两个输入都已知的情况下，双方可以计算输出。

在独立的安全模型中，该协议对主动对手是安全的，但是当同时执行三个实例时，该协议是不安全的。

想象一下以下场景：

• Bob是诚实的，并选择其中一个实例具有输入U，另两个实例选择输入D。有三个这样的组合(UDD, DUD, DDU)，他以一致的概率选择。
• 艾丽斯腐败。如果她能使这3个实例具有所有不同的输出，她就赢得了比赛。不难看出，她只能在鲍伯选择输入D的两个实例中使用不同的输入才能获胜。

如果各方都可以使用理想f的三个并行实例，那么很容易看出，爱丽丝只有在概率为1/3的情况下才能获胜。在这种情况下，爱丽丝对输入的选择与鲍勃的输入无关。必须(至少)有两个f-instances，其中爱丽丝使用相同的输入，而概率为1/3的情况下，鲍伯使用输入D。

但在存在并发协议实例的情况下，Alice很容易在概率1的情况下获胜，协议可以同步运行，Alice只需等待每个实例中的第一个协议消息。然后，她可以在执行步骤2的实例中发送适当的(不同的)协议消息。

由于Alice可以以某种方式影响协议，而不能影响理想的f实例，因此协议在此设置中是不安全的。

这个例子稍微简化了一些。我假设对f的理想调用是并行进行的。但要使这种榜样适应理想世界的不同要求并不难。

总体情况是，一个独立的安全协议可以在协议的早期泄露一些信息，其理由是这些信息无论如何都可以从输出中推断出来(比如Bob在本例中的输入)。但是，在并发合成的情况下，以及不同实例之间的相关输入，这种泄漏可能是不安全的。

补充其他答案的另一个例子是:基于二次残差(这里)的Goldwasser、Micali和Rackoff的经典零知识协议是完全零知识(而且它的统计可靠性可以通过顺序重复使其小得可怜)。一个长期悬而未决的问题是理解在平行组合下它是否仍然是零知识。最近的一系列论文(以本论文和本论文为高潮)表明，在标准密码假设(这里，LWE)下，在并行组合下它是不安全的。

为了补充Mikero的伟大答案，我还将尝试解释为什么在独立设置中使用的证明策略常常会在并发设置中崩溃。这提供了一个直觉，为什么证明必须完善，补充他的病态的例子。

理解独立模型和UC模型之间区别的另一种方法是:通常，安全性证明将涉及与其他各方交互的模拟器，并设法从这种交互中提取一些特定值，用于模拟协议。然而，在协议的实际运行中，通常不能提取该值，因为它会破坏协议的安全性。因此，在某种意义上，模拟器必须比普通玩家获得一些“额外的权力”，才能模拟协议(想想零知识证明:很明显，如果验证者可以在不知道证人的情况下模拟证据，那么这个验证程序就会破坏证据的可靠性)。

那么，模拟器的附加功率是多少呢？它如下:不像一个普通的玩家，模拟器是给它的对手的代码。因此，他们可以根据自己的喜好与这些代码进行交互；特别是，他们可以使用所谓的回绕策略:使用断点运行代码，并在不同的步骤分叉代码，以强制在由对手计算的值之间出现一些相关性，模拟器从这些值中提取一些值(我在这里故意模糊，但看看我对这样一种策略的这里的演练，以在一个示例零--知识证明上证明它的正确性)。

在独立设置下，回绕很好:您可以多次重新运行(多项式)代码以提取某些值。但是，想象一下，现在同一协议多次并发运行。现在，您需要分析整个协议的安全性。但是，回绕策略可能会失败:如果组合协议具有嵌套结构，则可能需要对其组件进行递归回绕，这可能会导致回绕爆炸:即使该协议仅由多个组件多项式组成，它也需要内部组件的指数倍多的回绕。因此，即使模拟器可以为内部组件的每个独立运行提取适当的值，它也无法使用回绕策略从完整组合协议中提取适当的值。

这个论点解释了为什么在使用并发组合时，在独立模型中非常好的安全证明可能会完全崩溃。有时，这只是一个安全分析的问题--也许有一种聪明的方法来避免回绕爆炸，或者一种完全不使用回绕的不同的证明策略，但有时，就像Mikero提出的病理例子一样，这种无法证明安全性的情况实际上源于组合协议的实际不安全性。

本文的定理3.2给出了关于DL问题的ZK并发合成的一个构造反例。这是一个非常有趣的建筑。

Uriel Feige，Adi Shamir证人不可分辨的和证人隐藏协议(斯托克‘90)。https://www.isical.ac.in/~rcbose/internship/lectures2016/rt02feigeshamir.pdf