分叉引理Forking lemma

https://blog.csdn.net/qq_44775134/article/details/107833717

这节课感觉意义不大，FS转换很简单，默认使用就行。这里给出了在RO中的FS的安全性证明。

一、The Fiat-Shamir Transform

二、FS in the ROM

三、Instantiating Fiat Shamir with Explicit Hash functions

一、The Fiat-Shamir Transform

简而言之：用于最小化公共硬币交互协议中的交互。在理论和实践上都令人着迷。最初的目标是将身份识别ID方案转换为签名方案。

完备性：P说服V x in L。

计算可靠性,无限算力的作弊证明者可以说服V接受x not in L。除非概率可忽略。

Public coin， 验证者抛硬币，概率是均匀随机的。

核心技巧就是V发送的随机值，换成了P自己算个哈希。交互式协议变成非交互的。

这种转换很实用。哈希效率也不错，是通用方法。

二、FS in the ROM

FS安全性 基于安全性假设ideal hash function。

Random Oracles

Random oracles(2)

这是个民间流传出来的定理。

紧归约。

在RO中，作弊的P选择对自己有利的β1。在常数轮交互中是安全的。

以三轮交互为例，证明FS在RO中是安全的。

证明数字签名方案安全性的一个重要技术就是随机预言机重放技术，也就是通过重放hash值来破解一个困难问题。该技术的理论依据就是著名的分叉引理(Forking Lemma)。

尚未在ROM中定义ZK，并且存在多个定义（和问题）。

直观上，除了看到?，?，?（可以由HV-ZK从x生成）之外，验证者还获得了对随机函数?的预言机访问，使得?(x,?)= ?。

它本身能否获得这种功能？

短答案：有点...

长答案：取决于定义。

结论：FS在ROM中有可靠性（对于某些合适的定义还有ZK）。

但是我们不能使用需要2^? 比特来描述的哈希函数！

那么，Fiat-Shamir转换是否安全？

坏消息[CHG98]：存在协议在ROM中是安全的，但使用任何实例化都将完全破坏安全性。

Fiat Shamir安全吗？给定负面的结果，如何解释ROM的安全性证明？

乐观的观点：

•设计了反例。

•ROM分析⇒强烈指示FS在现实生活中是安全的。

•ROM分析⇒启发式。在可行性和效率上都可以提供帮助。

悲观的观点：

•基于安全的假设是我们不理解，并且带有负面的暗示，如果不是完全危险的话，则是不可取的。

三、Instantiating Fiat Shamir with Explicit Hash functions

使用显式Hash函数实例化Fiat Shamir。

定义：如果可以随机采样h∈H（满足条件h(?,?)=?）则H是可编程的。