概念

KEA 是一种用于构造零知识证明(Zero-Knowledge Proof)的密码学假设 1

此假设大致如下:

  • 是一个素数,使得 也是素数(即 Sophie Germain 素数);
  • 的阶为 的子群的生成元(generator)。

表示模 的剩余类 乘法群,也称为模 的单位元素群(unit group modulo )。在这个群中,元素是与 互素的 剩余类,并且群操作是取模 的乘法运算。

这意味着 是一个满足以下条件的元素:

  • 属于 ,也就是模 的互质同余类的集合,其中 是一个正整数。
  • 的阶(order)是 ,也就是说,,且对于任何小于 的正整数 ,都有
  • 的乘方可以生成 的一个子群,也就是说,存在一个 的子集 ,使得

换句话说, 的一个循环子群的生成元,这个子群的阶是

  • 假设我们的输入是 ,其中:
    • 是一个未知的指数
    • 目标是输出一对 ,使得 成立。
  • 一种简单的方法是,随机选择一个 ,令 ,并令 。这样,我们就可以保证 ,因为
  • KEA1 假设的直观含义是,这是生成这样一对 的唯一方法。换句话说,任何能够输出这样一对 的敌手,必须“知道”一个指数 ,使得 成立。
  • KEA1 假设的形式化表述是,对于任何能够输出这样一对 的敌手 ,存在一个“提取器” ,它可以在给定相同的输入 的情况下,返回一个指数 ,使得 成立。

最后这句话可能不太好理解。

这句话的意思是,如果有一个敌手 ,它可以根据 这三个参数,生成一对满足 的值 ,那么一定有一个方法,可以从 的输出中“提取”出一个指数 ,使得 等于 次方。也就是说, 不能随意生成 ,而必须遵循一定的规则,否则就会被“提取器” 揭穿。

甚至可以断言,生成的 ,

我们可以用一个类比来理解这个假设。

假设有一个魔术师 ,他可以根据一个数字 ,一个颜色 ,和一个形状 ,变出一对物品 ,其中 的形状和 的形状相同,但是颜色不同。

例如,如果 是红色, 是圆形,那么 可能会变出一个红色的圆形 ,和一个蓝色的圆形 。这个魔术看起来很神奇,但是其实有一个秘密。 必须根据 的颜色,选择一个数字 ,然后用 来决定 的颜色。

现在,假设有一个揭秘者 ,他可以根据 这三个参数,以及 变出的 ,猜出 选择的数字 。例如,如果 看到 是绿色, 是黄色,他就知道 。这样, 就可以“提取”出 ,并且揭穿 的魔术。这个揭秘者就相当于 KEA1 假设中的“提取器”。

KEA1 假设的含义是,对于任何一个魔术师 ,都存在一个揭秘者 ,可以根据 的魔术,猜出 的秘密。也就是说, 的魔术并不是真正的魔术,而是有一定的规律可循的。

这个假设在密码学中是很有用的,因为它可以用来构造一种特殊的证明,叫做零知识证明。零知识证明是一种让证明者向验证者证明某个陈述是真的,而不泄露任何其他信息的方法。例如,证明者可以用 KEA1 假设来证明他知道 的指数 ,而不需要告诉验证者 的具体值。这样,证明者就可以保护自己的隐私,而验证者就可以信任证明者的证明。

后文的内容,也就是关于 KEA2 和 KEA3 假设的部分。这些假设是在 KEA1 假设的基础上,增加了一些复杂性和泛化性。

KEA2 假设的大致意思是:

  • 给定一个素数 ,使得 也是素数,以及一个生成 中阶为 的子群的元素 是模 的互质同余类的集合。

  • 假设我们的输入是 ,其中 是两个未知的指数,我们的目标是输出一对 ,使得 成立。

  • 一种简单的方法是,随机选择一个 ,令 ,并令 。这样,我们就可以保证 ,因为

  • 另一种简单的方法是,随机选择一个 ,令 ,并令 。这样,我们也可以保证 ,因为

  • KEA2 假设的直观含义是,这是生成这样一对 的唯一方法。换句话说,任何能够输出这样一对 的敌手,必须“知道”一个指数 ,使得 或者 成立。

  • KEA2 假设的形式化表述是,对于任何能够输出这样一对 的敌手 ,存在一个“提取器” ,它可以在给定相同的输入 的情况下,返回一个指数 ,使得 或者 成立。

  • [!] 大佬说 KEA1 假设是不可证伪的。2

例子

Alice 想让 Bob 帮忙完成一个基于 的计算, 是一个 生成元。并且还要 Bob 证明运算结果的确基于 ,怎么做?

  • Alice 和 Bob 先协商一个
  • Alice 有一个值 ,有一个随机数 ,衍生值
    • 比如说,,那么
    • 是 Alice 的证明
  • Alice 将 发送给 Bob,并希望得到
    • 那 Bob 能不能直接回 给 Alice 呢?不能,规则要求必须是
    • 所以 Bob 必须要计算出一个 ,使得 ,同时又不知道
    • 于是 Bob 想到一个办法,先计算一个 ,比如 3
      • 然后计算
      • 然后计算
    • 这样
  • Alice 核验发现,确实 ,所以 是正确的。
    • 这样 Alice 确信,Bob 在元组的两个值的计算上都用了同一个指数(即
    • 而且,都是基于 完成的运算。

Footnotes

  1. The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols https://eprint.iacr.org/2004/008.pdf

  2. discrete logarithm - How much do we trust KEA1 Assumption? - Cryptography Stack Exchange https://crypto.stackexchange.com/questions/6117/how-much-do-we-trust-kea1-assumption