笔记分享|浙大暑期密码学课程：Idealized Model ll
上篇笔记是针对张聪老师在浙江大学的暑期Crypto School的《Idealized Model l》，详情请见笔记分享|浙大暑期密码学课程：Idealized Model l。
本篇笔记对张聪老师在浙江大学的暑期Crypto School的《Idealized Model lI》课程进行了整理，可前往以下b站链接或点击下列视频观看完整课程。
浙大暑期Crypto课程- ldealized Models ll（上)-Cong Zhang
https://www.bilibili.com/video/BV18V4y187Ak/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
浙大暑期Crypto课程- ldealized Models ll（下)-Cong Zhang
https://www.bilibili.com/video/BV12z4y1E76P/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
签名
我们将基于以下signature构造介绍如何用RO做证明，体会RO的优劣之处。
,
①randomly samples , compute
②compute
③compute
Output
①compute
②test
可以看到，
下面将展示，若H为RO，如何将这个signature reduce到Dlog上去 Theorem.
Scheme is UF-CMA secure under the assumption DLOG in ROM.
Reduction:R需要在不知道x，也就是sk，的情况下完成signature，并提取出x
由于A具有问询，问询两项能力，因此R需要控制这两个部分。
控制
R（对A来说的Challenger）：收到（目的是输出x）
A（在R内部）：问询，问询收到，即pk 输出信息m
R向A输入随机选择的
A计算，并向R模拟的H query
R返回e
以上reduction保证了e的分布与真实情况一致，并且验证成立。
控制,如Idealized Model Ⅰ中所介绍，R需要存两个表：T1（random table），T2（R回应的）
A每次query，R查T1中是否存有该值，若有则回答对应值，若无则查T2是否存有该值，若有则回答对应值。
A最后输出,若A的输出通过了验证，则其对应的大
概率出现在T1中。若不出现在T1中，则猜中的概率可忽略。
假设query出现在T1中的第100个，即，我们将替换成，我们期望第二次rewind时，仍出现在第100的位置上。
定义，则第一轮出现概率为，第二轮出现的概率也是。
则碰撞的概率为
此时，可以通过解方程组,得到sk
2Generic Group Model
许多算法都是基于assumption，如果能够确认它在Stand Model下确实是困难的，那么就能得到无条件的安全。然而这会得出one-way function的存在，也就是P≠NP，而这时暂时无法解决的。因此我们需要进行弱化限制。这就是需要Generic Group Model（GGM）的原因。下面给出GGM的定义。Shoup’s GGM:
定义一个随机映射，为所有满足映射的函数，从中随机. 选一个f来进行映射，用表示这个随机映射。GGM需要提供两个接口: Labeling和Addition。
If Then return
Else
在这个模型中，攻击者可以看到，能力较强，下面给出一种攻击者较弱的模型。
3Maurer's GGM
初始化一张空表，仅有序号。
A调用，就将x放入表中。A调用，就将y+z存入表中。这两个query都没有回复。
GGM还有一种调用称为Equaling Test，query两个序号，若内容相同，则回答1，不同则回答0.
然而对于前两种调用没有回应，作为一个程序来说总是有点怪怪的。因此对他们做一些调整，回应放入的表中position序号。
(PS：笔记里是作者自己整理，可能会有一些不太准确的表达，也会有一些不当的理解，欢迎大家在留言区指出，一起学习交流)
往期推荐
1. 笔记分享|浙大暑期密码学课程：Idealized Model l
2.学习同态加密：第二代全同态加密经典论文合集学习同态加密：第一代全同态加密经典论文合集4.文章速览 | 联邦学习 x AAAI'2023 （下）