程老师，您理解是对的，定理1由于使用了Forking Lemma，与d相关的部分可以消掉，从而和目标向量的范数无关，进一步从安全证明中和困难假设“lost”掉了。而QROM由于不能使用Forking lemma，d的影响就会直接体现在安全证明和困难假设。另外，如果您和我们第一封邮件所述，取更大的d会影响敌手的时间和成功概率，但通常的安全规约损失都不考虑敌手的运行时间和成功概率（而把他们当成既定的值），所以ROM下安全证明体现不出d的影响。祝好Aigis-sig团队
michael <chengzh@myibc.net> 于2019年12月11日周三 下午1:37写道：

张老师， 我想这个问题的一个原因应该是"lost in forking lemma"。您们在引理6的证明使用了forking lemma，证明没有给出规约关于时间/优势的比例关系的扩展倍数。实际上，如果d很大，攻击者A输出伪造签名的时间就会显著加大（第33补失败的概率显著变大），规约求解AMSIS-R的时间就会显著变大，规约的时间/优势的比例关系会变大，规约就更加松散了。我没有试验过如果d变大，生成有效签名的概率会是什么样的情况变化。如果要是的规约有意义（当然forking lemma规约已经很松散了），我想d是需要确定值区间的。  michael，chengzh@myibc.net2019-12-11

----- Original Message -----From: Jiang ZhangTo: chengzhSent: 2019-12-11, 13:17:04Subject: Re: Re: Fw: Aigis-sig　 程老师，上一封邮件在您的要求下，我的回复仅仅限于定理1 ROM下的证明。而您引用的Dilithium的第二轮文档，以及Fiat-shamir那篇论文都是在考虑QROM下的证明，您可以进一步从他们的文档中得以确认（即敌手是Quantum的且以Quantum的方式询问RO，见Dilithium文档第5.2.1节第一句话）。而对于Aigis-sig的QROM的证明，即定理2，我们也是有相同的限制的（见我们文档34页最下面的一个公式），这个之前也和您确认过，所以这并不冲突。　至于您指出的公式（6）和公式（8）的问题，这似乎假设和中间过程描述不同而已，其结果都是一样的，具体您可以看到Dilithium第二轮文档的公式（12）（以及脚注7）和我们的公式（8）是一样的。祝好，Aigis-sig团队
michael <chengzh@myibc.net> 于2019年12月11日周三 下午12:44写道：

Jiang Zhang，　关于第1个问题，从Dilithium的第二轮报告中22页公式（10）后对u'的范数分析看，如果2^{d-1}*60 > 2r_2, u'无穷范数的上界会超过4r2，其对应问题转为找z, c, u'，其中u'的范数上界为60*2^{d-1}+2r_2+1。等式（11）中的问题会随着d变大，难度有所降低。我理解如果将这个问题在ROM模型下通过ForkingLamma转为为对应的AMSIS，对应向量的范数上界也是保持这样对应情况。Dilithium的这个证明过程和埃奎斯证明的方法上是否有重要区别，导致你们的证明可以忽略d的影响，而Dilithium则不可以？或者算法的正确性要求ct_0的范数 < r2（其对d有约束）是否隐式要求了引理6中对应r_2的取值。　关于第2个问题，看到您假设了2*2^d < r2，所以解能够进行转换。　关于Dilithium的分析，我觉得重要的差别在于其NIST文档的分析过程一直假设了60*2^{d-1}<2r_2（包括ROM)。这是对d明确的取值约束，d不是完全自由的。另外在A concrete treatment of fiat-shamir signatures in the quantum random-oracle model中Lemma 4.6也假设了2^d < 2\alph_1，进行后续的分析。但是如您所说，您们的结果显示在ROM下，从安全性角度d是自由的（除了2^d< q)。　PS1. 因为现有艾奎斯的参数选择遵循了60*2^{d-1}<2r_2的约束，所以这些讨论可能只在理论上有意义。　PS2. 我理解Dilithium第一轮文档公式（9）和（11）有误，第二轮文档进行了修订。您们对应文档中第34页等式（6）和第35页等式（8）也有这样的问题。　michael，chengzh@myibc.net2019-12-11

----- Original Message -----From: Jiang ZhangTo: chengzhSent: 2019-12-11, 11:30:13Subject: Re: Fw: Aigis-sig程老师，

感谢您的问题，也感谢您的提醒，我们后续也会关注学会网站的内容，并在学会网上给与正式回复。接下来，我们就以上两个问题做简短的回答。

对于第一个问题：签名的安全性通常需要考虑私钥恢复攻击的安全性和抗伪造攻击的安全性。定理1给出了签名抵抗伪造攻击的安全证明，如果单单从这个角度来讲，定理1与d的取值无关。但需要注意的是，通常情况下签名的抗伪造攻击的安全性也蕴含着私钥恢复攻击的安全性，前提是给定私钥我们能够高效的计算出合法（能通过签名算法验证）的签名，或者签名算法本身是高效的。由于d的取值实际上会影响这个前提（见签名算法第33步的判断|v|>= r2，左边v与d相关，右边与r2相关），d选择过大可能造成即使拿到“私钥”也不能产生合法的签名，这时候定理1就仅仅只说明了签名方案能够抵抗签名伪造攻击，而不能蕴含密钥恢复攻击的安全性，所以从这种极端情况下来看d也与安全性有关（但这种安全性并没有被定理1刻画） ，而且对于一个有意义的签名方案，其签名算法需要是高效（即能在多项式时间内完成）的，所以这种极端情况在现实中并不会出现。

对于第二个问题：首先，按照AMSIS和AMSIS-R实例（即问题的输入）的定义是完全一致的（我们可以简单将AMSIS问题矩阵A最后一个向量为AMSIS-R的t向量），唯一的差异只是对解的要求不一样，因此稍微调整下参数，我们可以将AMSIS实例转换成AMSIS-R实例，进而调用AMSIS-R问题求解算法。进一步，如果2*2^d < r2成立的话，我们可以很容易将AMSIS-R问题的解转换成相应AMSIS问题的解（因为t = t1 *2^d + t0，我们可以将t0那部分加到AMSIS-R的解中，其中|t0|<2^d），显然该规约是多项式时间的。需要强调的是这里对于d的限制并不是来自于定理1，因为定理1中我们直接假设了AMSIS-R是困难的。此外，值得注意的是目前针对(A)MSIS的攻击算法并没有区分(A)MSIS-R问题和(A)MSIS问题最后一个向量的不同形式，例如Dilithium就没有考虑MSIS和MSIS-R他们之间的差异（事实上他们甚至都没有正式的提MSIS-R问题，但他们的确需要一个MSIS-R问题）而是直接通过分析MSIS问题的攻击算法来评估具体安全性。
祝好，Aigis-sig团队
michael <chengzh@myibc.net> 于2019年12月11日周三 上午8:27写道：

张老师，　应要求，我把评估过程中的一些问题昨天发到了学会网站上，但是流程比较慢，还没贴出来。我这里转发给您，以便于大家快速交流。这些问题我们周一在电话中有讨论过，我想您们也有相关的工作。如果您们有响应，我想后续交流可以抄送给sfyjhz@cacrnet.org.cn。这样既有速度，又符合规则要求。　程朝辉　　----- Original Message -----From: michaelTo: sfyjhzSent: 2019-12-10, 11:29:55Subject: Aigis-sigsfyjhz，　　

1. 定理1中特别是引理6中没有明确给出d的取值约束，请算法设计者从安全性角度明确d的取值是否与其他参数相关。如果有相关性，请给出具体的相关性。（请仅针对ROM下的定理1的要求）

2. 定理1中SUF-CMA基于AMLWE和AMSIS-R复杂性假设进行分析，但是具体参数分析时采用了AMLWE和AMSIS进行评估。请问如何利用AMSIS-R的算法求解AMSIS，规约是否有损失？特别是AMSIS-R中的d值是否影响规约的效率，如果有，如何影响规约效率？

　　michael，chengzh@myibc.net2019-12-10

-- 

Jiang Zhang, PhDAssociate Researcher,State Key Laboratory of Cryptology, Beijing, China

-- 

Jiang Zhang, PhDAssociate Researcher,State Key Laboratory of Cryptology, Beijing, China