离散对数Fiat-Shamir参数选择

Question

根据菲亚特-沙米尔启发式，该算法有两个参数:大素数p和原根g。因此，出现了若干问题：

1. 质数p应该有多大？如何选择p使之，例如Pohlig算法或其他已知的算法不能破坏它？
2. 如何选择原根g？据我所知，这是一个NP问题。
3. 在一些挑战中使用p和g的相同值安全吗？

Answer 1

这里似乎有些混乱。正如fgrieu正确指出的，菲亚特-沙米尔是一种使公共硬币(诚实验证者)零知识证明非互动性的方法.除了哈希函数之外，您不需要为Fiat选择任何参数:所有其他参数都是您正在进行非交互式的交互协议的参数，或者是您试图证明的语句的参数。通常，对于离散对数知识的证明，组、生成器g和模p是语句描述的一部分。Schnorr证明是处理此类语句的交互式证明，而Fiat-Shamir可以用来使其成为非交互式的。

语句的参数通常将由您打算为语句使用零知识证明的上下文来确定。通常，您会希望在计算离散对数被认为难以解决的组上使用离散对数知识的零知识证明(否则，证明离散对数的知识实际上没有任何意义)。这类组有大量的标准选项(例如，使用ed25519和任何生成器，可以使用你的另一个问题的例子)。