关于晶体中定理2的问题--Kyber纸

Question

我有一些关于凯伯论文的问题，特别是关于第6页的定理2，我想在这里问。首先，我引用论文中的下列定理，然后提出我的问题。

Theorem 2。对于任何一个对手A，都有一个像Adv_{Kyber.CPA'}^{cpa}(A) \leq 2 \cdot Adv_{k+1,k,\eta}^{mlwe}(B)这样的对手B。

1. 我的第一个问题是关于Adv_{Kyber.CPA'}^{cpa}(A)的定义，这里是如何定义的？如果我正确理解CPA，游戏G_0的思想是:对手选择两条明文消息，将它们发送给挑战者，挑战者随机加密一条消息。然后，对手必须猜出挑战者所选择的信息(位)。在这个设置中，算法1-3中定义的所有变量(在本文中)都是相同的吗？但是Adv_{Kyber.CPA'}^{cpa}(A)究竟是如何定义的，参数是什么呢？
2. 在从游戏0到游戏1的变化中，以前不均匀分布的\mathbf{t}在游戏1中被\mathbf{t}' = \mathbf{As} + \mathbf{e}代替，而D12现在是均匀随机分布的。现在，有人声称有一个对手B持有：|Pr(b=b' \text{ in game } G_0) - Pr(b=b' \text{ in game } G_1)| \leq Adv_{k,k,\eta}^{mlwe}(B) \leq Adv_{k+1,k,\eta}^{mlwe}(B)。我有一些关于这个和方程式的问题。

• 首先，这样一个对手B会是什么样子？如果我的理解正确，它将不得不尝试区分0和1？游戏中的不同之处只存在于\mathbf{t}？这只是一个想法，我们是否可以定义对手B作为输入\mathbf{t}，然后在加密中继续进行，这样，如果我们在游戏0 (\mathbf{t} = \mathbf{t})中，值\mathbf{u}和v就遵循\beta的分布，如果我们在游戏1 (\mathbf{t} = \mathbf{t}')中，则遵循一致随机分布吗？现在，如果B能够区分游戏0和1，那么它也可以区分游戏样本，那么MLWE就不会比区分游戏更困难了？这会是一种方法吗？不幸的是，从论文中还不清楚对手B是如何被明确定义的。
• 这里如何解释不等式|Pr(b=b' \text{ in game } G_0) - Pr(b=b' \text{ in game } G_1)| \leq Adv_{k,k,\eta}^{mlwe}(B)？这是否意味着区分0和1的游戏比普通MLWE中对手的优势更难？为什么会是这样呢？或者更确切地说，游戏的区别并不比对手在MLWE中的优势更难？
• 最后，我感兴趣的是如何说Adv_{k,k,\eta}^{mlwe}(B) \leq Adv_{k+1,k,\eta}^{mlwe}(B)持有？这意味着对手在设置(k,k,\eta)时的优势要小于(k+1,k,\eta)设置中的优势，这怎么可能呢？我认为随着k的增加，MLWE的复杂性增加了，安全性也随之增加，攻击者应该会发现更难提取优势吗？这个问题可以追溯到上一段关于解释不平等的权利。

我希望这些问题虽然是技术性的，但到目前为止，是可以理解的。我将非常高兴收到有帮助的意见和答复！

Answer 1

1. 你的理解是正确的。如果你指的是“参数是什么”的问题“什么是kyber的参数”，那么它(大部分)并不重要。你有一些隐式参数的密码系统Kyber.CPA′。你用这些参数。唯一重要的部分是kyber的参数与MLWE实例匹配，用于绑定kyber的优势。特别是，我假设Kyber是相对于常量k, \eta定义的。由于这些是在MLWE实例中使用的，所以它们也应该在kyber中使用。
2. 你看错了。游戏G_0有\mathbf{t}的结构。对策G_1的\mathbf{t}是一致随机的。区分G_0和G_1将(最终)简化为区分(A, As + e)和(A, u)，即LWE类型的假设(在这种情况下是LWE)。
3. MLWE对手如下。它得到(A, b)，其中b要么是u，要么是As + e。然后，它使用这种方法，就像在Kyber中使用MLWE样本来构造PKE方案一样。这个PKE方案要么是游戏G_0中的Kyber，要么是游戏G_1中的Kyber。这就是说，B模拟的是游戏G_0或G_1，然后使用Kyber对手来区分这两个游戏，从而区分MLWE对手的样本来自哪一个MLWE分布。请注意，这里有一些技术上的细微差别--其中一个必须使用两个混合动力车来验证Kyber的安全性。首先，从公钥切换为MLWE样本到一致随机切换。然后对加密本身进行类似的切换。这就是优势表达式中因子2的来源。
4. 粗略地说，任何能够区分游戏G_0和G_1的对手，都会在MLWE游戏中导致这个优势(或更好)的对手。
5. 这完全取决于优势表达式的含义。MLWE有两个自然参数--一个维/秩类型参数，一个样本#得到参数。增加维度/等级会使问题变得更难(就像你说的那样)，所以不清楚不平等是否应该存在。增加样本的数量会使问题变得更容易(人们总是可以忽略一些样本)。因此，如果这个参数对应于维/秩，我同意这看起来很奇怪。如果它与#样本相对应，这是有意义的--让对手忽略它的最后一个样本，或者其他什么。