随机Oracle模型证明和可编程性

#1 楼

您的第二个问题是关于可编程性。托马斯（Thomas）的回答或评论还没有直接解决这个问题，因此我将仅关注该问题。不幸的是，我不知道一个简单的原语在需要编程的随机oracle模型中是安全的，但是一旦我解释了背景，我将使用一个很清楚的原语。这就是所谓的菲亚特-沙米尔（Fiat-Shamir）启发式算法；制作非交互式零知识证明是一个不错的技巧。
在进入菲亚特·沙米尔之前，请考虑一下您最喜欢的基本零知识证明是如何工作的。由于这是Crypto SE，而不是CSTheory SE，因此希望您正在考虑证明离散对数和二次残差的知识，而不是图同构或3色图。 ;）
[此外：从技术上讲，这些都不是真正的零知识证明，它们是诚实验证者的零知识证明（有时称为$ \ Sigma $ -protocols，但我们不在乎这种区别）
Schnorr对离散对数的知识证明
$ P $（对于证明者）伴随着两个值$ g $和$ y $在某些组$ \ mathbb {G} _q $中，其中离散对数是硬。她声称：我知道$ x $的价值，因此$ y = g ^ x $。由于$ x $是$ y $基元$ g $的离散对数，直接计算$ x $是不可行的，因此$ V $（验证者）最初不能确定她是否真的知道$ x $。
Schnorr协议允许$ P $以不透露任何有关$ x $的方式证明$ x $到$ V $的知识。它如下：


$ P $生成一个随机值$ a $，计算$ b = g ^ a $，然后将$ b $发送到$ V $


$ V $生成一个随机值$ c $并将$ c $发送回$ P $


$ P $计算$ d = a + cx $并将$ d $发送到$ V $


$ V $接受$ \ langle b，c，d \ rangle $作为$ \ langle g，y \ rangle $ iff的证明$ g ^ d = by ^ c $


安全分析
我们可以自问，从这样的协议的安全性方面，您想要什么？ $ V $担心来回发送一堆数字实际上可能不会构成证明$ P $知道这样的$ x $的证明。如果他实际上可以得出结论，则$ P $必须知道$ x $，如果$ P $可以产生许多接受的$ \ langle b，c，d \ rangle $成绩单，那么证明就是正确的证明。
$ P $可能担心$ V $可能会通过看到一个或多个接受的笔录来了解有关$ x $的一些信息。这被认为是泄漏有关$ x $的零信息（诚实验证者技术的光泽度）的证明。如果它泄漏零信息，则称其为零知识。
声音（通过提取）
为了证明Schnorr协议是正确的，我们实际上将间接地做到这一点。我们首先要证明它是“可提取的”，然后证明可萃取性意味着稳健性。我不会给出实际的定义或证明，而只是给出正在发生的事情的草图。
Schnorr协议具有一个特殊的健全性（您猜对了，它具有特殊的健全性）：如果有两个接受的笔录$ t_1 = \ langle b，c，d \ rangle $和$ t_2 = \ langle b，c'，d'\ rangle $其中$ t_1 $与$ t_2 $共享相同的$ b $值，但$ c $（和因此$ d $）不同，则可以计算$ x $的值：$ x =（d-d'）/（c-c'）$。如果$ P $可以可靠地生成接受成绩单，则没有理由假设她无法生成$ t_1 $。同样$ t_2 $。而且，如果她能同时产生两者，那么她“知道” $ x $，就意味着产生$ t_1 $和$ t_2 $所需的知识足以产生$ x $本身。
当我们最终到达菲亚特·沙米尔（Fiat-Shamir）时，将“可扩展性”这一概念正式化一点很重要。考虑一下$ P $是一个编译的二进制程序而不是一个人的情况。您可以运行$ P $来执行协议，并且可以将$ P $倒带到先前的内部状态，但是您不能对其进行反编译或查看内部状态（这称为可倒带黑盒访问；为什么要使用这些特殊功能证明可提取性被允许是另一回事了。
我们说，如果您可以从与这样的黑匣子的交互中获得$ x $，则可以提取协议。而且我们说协议可以通过这种方式提取（您可以倒带的黑匣子）就是好的。这两个命题在文献中都有证据，我遗漏了很多精美的文字。请注意，除了可提取性以外，您还可以通过其他方式证明其稳健性，而不是黑盒子可重绕的可提取性（可提取性足够，但不是必需的）来证明其稳定性。 >
让$ P $输出$ b $

给$ P $一个随机$ c $作为输入
让$ P $输出$ d $

将$ P $倒退到步骤1和步骤2之前
给$ P $一个不同的随机$ c'$作为输入
让$ P $输出$ d'$

/>从$ \ langle b，c，d \ rangle $和$ \ langle b，c'，d'\ rangle $计算$ x $


零知识（通过Simulation ）
同样，我们可以通过证明协议具有不同的属性（即可仿真性）来间接证明该协议为零知识。在这种情况下，我们得到一个已编译的$ V $二进制文件，并且必须可靠地为其提供给我们的$ c $可接受的$ b $和$ d $值。但是，该协议用于了解我们实际上不知道的$ x $！如果我们可以在不知道$ x $的情况下模拟可接受的协议运行，则协议中的值一定不能真正泄漏有关$ x $的任何信息。因此，如果协议在这方面是可仿真的，那么它就是零知识。
我之前提到Schnorr实际上不是零知识协议。这会产生一些模拟Schnorr成绩单的问题，当我们在Fiat-Shamir中使用随机预言时，这些问题会得到解决。要模拟Schnorr协议，请执行以下操作：

生成随机值$ d $

猜测$ c $的值

供应$ b = g ^ dy ^ {-c} $作为$ V $的输入

如果$ V $输出$ c'$

如果$ c'\ neq c $（如果您猜错了），请返回第2步。否则继续
将$ d $提供给$ V $，如果$ c $的值确实很短（请稍作说明），则可以接受$ br $ ，那么模拟器是有效的。对于更长的值，您无法使用此方法证明Schnorr的零知识。有很多技巧可将Schnorr转换为真正的零知识。如果脚本接受$ x $，则必须知道$ x $；另一方面，您可以生成无需$ x $即可接受的脚本：这有什么用？如果仔细观察，您会发现模拟成绩单是按顺序生成的，而可提取的成绩单是按顺序生成的。实际上，由于生成乱序，我们无法生成$ \ langle b，c，d \ rangle $和$ \ langle b，c'，d'\ rangle $成绩单，因为不再选择$ b $的值：由$ d $和$ c $决定。
Fiat-Shamir的想法是使Schnorr（及相关）协议不交互。这意味着$ P $可以产生所有三个值$ \ langle b，c，d \ rangle $而不是依靠$ V $来提供$ c $。此外，由于我们知道成绩单是可模拟的，因此$ P $可以生成必须在值$ b $之后生成的$ c $值，因此排除了任何模拟。怎么样？实际上，这真的很容易：设置$ c = \ mathcal {H}（b）$。验证者还检查$ c = \ mathcal {H}（b）$。 [另外：实际上，这里有一个整洁的优化，您完全不必发送$ b $的值，而将其放在一边]。
最后，我们可以引入随机预言。事实证明，如果您使用常规哈希函数，则无法在协议之外进行可提取性或仿真的角力。我们将尝试，但是最终我们将需要一个可以编程的随机oracle。
通过Fiat-Shamir启发式提取
回想一下，提取依赖于$ \ langle b，c，d \ rangle之类的成对的转录本$和$ \ langle b，c'，d'\ rangle $。对于菲亚特·沙米尔（Fiat-Shamir），$ c = \ mathcal {H}（b）$，因此，如果两个副本之间的$ b $值相同，则$ c $以及$ d $也将相同。因此，我们无法使用常规的确定性哈希函数获得两个这样的成绩单。但是，如果$ \ mathcal {H} $是可编程的随机预言机，我们可以使它为相同的输入产生不同的值。再次，我们玩向$ P $具有可倒退的黑盒访问的游戏，但是这次我们也得到了随机的oracle：请参阅$ P $查询$ O $和$ b $来计算$ \ mathcal {H}（b）$

生成随机$ c $并编程$ c = \ mathcal {H}（b）$在$ O $

中让$ O $回答查询
让$ P $计算$ d $

让$ P $输出$ \ langle b，c， d \ rangle $

后退至步骤2的结尾
生成随机$ c'$并将$ c'= \ mathcal {H}（b）$编程为$ O $

继续操作，最终让$ P $输出$ \ langle b，c'，d'\ rangle $


一些注意事项：（1）因为这是非交互性的，所以$ P $在步骤1之后不会输出$ b $，因此我们依赖于查看对随机oracle的查询的能力； （2）如果oracle生成“即时”答案（而不是使用所有查询/响应的密码本输入协议），则实际上我们不必使用$ c $的不同值对其进行编程。我们只是倒退到将要生成响应的那一点之前，然后让它生成一个随机值（这将与第一次执行中的绝大多数不同）。这为原始海报的第三个问题提供了一些启示。
用菲亚特·沙米尔（Fiat-Shamir）进行模拟
与提取类似，使用随机预言机使模拟变得轻而易举。假设您已经读了那么远，您可能会发现我将如何用一句话说出来：为$ c $设置一个随机值，首先选择$ d $来计算$ \ langle b，c，d \ rangle $ ，当验证程序与oracle检查$ c = \ mathcal {H}（b）$时，将$ c $编程为响应。

#2 楼

随机预言是理想的对象。有关更多详细信息，请参见前面的问题。使随机预言方便进行证明的原因是，如果不尝试，则对于给定输入的输出一无所知。例如，考虑以下加密方案：


$ H $是一个随机的oracle，它输出$ n $位值。
密钥是$ K $，a $ k $位的字符串。
通过计算$ c = m \ oplus H（K || 1）||对单个消息$ m $进行加密。 H（K || 2）|| ... $（您通过随机oracle反复“散列”通过将$ K $与一个计数器连接而获得的连续字符串，然后将oracle输出连接到一个大流中，并与要加密的消息进行XOR）。 >
如果$ H $是随机的oracle，则可以很容易地证明加密是安全的，直到$ 2 $的$ 2 ^ {k-1} $调用的工作因子：对于任何索引$ i $，除非您确实在产生它的确切输入上调用了$ H $，否则您将无法在生成的流的$ i $上学到任何东西（“什么也没有，甚至没有丝毫的统计偏差”）。因为$ K $有$ 2 ^ k $个可能的值，所以最好的攻击方法是尝试（按任何顺序），平均来说，在$ 2 ^ {k-1} $个猜测之后，它将平均击中正确的键。每个猜测都涉及调用$ H $。

现在，有了加密哈希函数，事情就不那么容易了。密码散列函数定义为可抵抗原像，第二原像和碰撞。这些是较弱的性质。函数可能是一个很好的哈希函数，但仍然不能成为随机预言。对于常用的Merkle-Damgård功能（例如SHA-256和SHA-512）尤其如此：这些功能遭受所谓的“长度扩展攻击”。给定$ H（x）$，可以在某些条件下但不知道$ x $的情况下，为$ x'$的某些值计算$ H（x || x'）$。随机预言不允许。并且，该特定属性完全破坏了我们证明上述加密方案的安全性的尝试。但是，当您尝试计算原像或碰撞时，“长度扩展”似乎没有任何帮助。的确，在SHA-256或SHA-512上，目前还没有有效的原像或碰撞攻击。

总而言之，随机预言片是理想的对象，可以轻松证明它们的构造。使用证明依赖于实际哈希函数不一定要表现出来的属性的证明（即使它们是“安全”哈希函数）。


当我们“实现”随机预言机时，我们使用散列函数和其他基元，其方式类似于随机Oracle的理想属性。如上所述，现有的散列函数本身还不够好。常见的工具是HMAC，它使用密钥并建立在现有哈希函数的基础上，但是以特定方式调用它两次，从而避免了诸如SHA-256之类的具体函数的已知缺点。例如，这就是为什么在构建如NIST所述的加密安全的伪随机数生成器时，您可能更喜欢“ HMAC_DRBG”构造，而不是更快但“未经证实”的Hash_DRBG。

在协议中使用带有散列函数的给定结构时，仍应具有一定的技术性，直觉性和坚定的信念，在该协议中应使用随机预言。但是我们没有什么更好的：我们不知道随机预言是否真的存在（或者什至是安全的哈希函数）。


给定的实现是否使用表来存储预先计算的结果对理论安全性没有任何影响：随机预言机模型中的证明依赖于预言机必须被调用的次数（针对不同的输入），而不取决于调用的发生时间。您可以根据需要使用内部表。

函数的诞生日期有一个细微之处：如果oracle是带有密钥的HMAC，则由于生成了密钥，oracle“存在”了，并且所有的oracle调用都必须使用该密钥；另一方面，可以将诸如SHA-256之类的无密钥哈希函数视为一种自10年前定义SHA-256以来就存在的随机预言。在过去十年中一直忙于调用它。因此，使用原始SHA-256作为随机预言机（如果我们忽略有关长度扩展的问题）等效于考虑到攻击者可能具有十年的计算能力，与整个世界一样强大。为避免这种情况，定义使用键控函数作为随机预言机的协议是很平常的事情。

#3 楼

https://link.springer.com/chapter/10.1007/3中详细考虑了ROM的可编程性问题，以及为什么在应用经过ROM验证的具有真实哈希功能的结构时，它会导致“错误”的问题。 -540-45708-9_8

回答您的问题：


是的，通常不可能基于哈希函数的属性来找到证明，例如防碰撞原像抵抗。示例是
Schnorr签名的证明。
随机oracle的可编程性通常是构造证明的必要属性。这意味着，oracle的响应不是预先固定的（因为对于真正的散列函数，所有散列值都是固定的），
，但是我们可以在证明中考虑的实验中自适应地选择它们。
例如，对Schnorr签名的证明表明，如果存在针对Schnorr签名的攻击者A，那么我们可以创建攻击者B，它将A用作黑盒子例程，并且能够打破离散对数问题。
要运行A，B应该模拟其环境：响应随机oracle查询，响应签名oracle查询。但是B不知道秘密密钥（这是一个离散日志，而B实际上想找到它！），那么它如何在签署oracle请求时响应A？这是随机oracle可编程性出现的地方。 B将为特定于
特定请求的随机oracle响应分配一个特定值，以便B能够创建签名（从某些角度来看，通过操纵随机oracle响应来“伪造”签名）。但是以某种方式无法识别A的这种骇客行为（无法将该值与随机值区分开）。
实际上，哈希函数值是事先已知的（一旦声明/选择了哈希函数）。允许即时选择随机的oracle值，
这实质上有助于构建证明。