泄密信息？

Question

设a，b，c，d随机从$\mathbb Z^*_q$中选择。我们选择值$r_1、r_2、r_3、z_1、z_2、z_3 \get \mathbb Z^*_q$。计算如下的$u_1、u_2$是否泄漏了关于值$a、b、c、d$的信息？( p.p.t周年可以以不可忽略的概率؟获得关于a、b、c、d或这些关系的信息)。

$$u_1=(r_1\cdot a，r_2\cdot b，r_3\cdot c，(r1+r2-r3)\cdot d)$$

$$u_2=(z_1\cdot a，z_2\cdot b，z_3\cdot c，(z_1+z_2-z_3)\cdot d)$$

Answer 1

任何信息，甚至是特殊情况下的信息？好的。只是一个简单的例子：

由于我们知道$(r_1 \cdot a)$ amd $(z_1 \cdot a)$，所以对于$f_2$和$f_3$，可以很容易地计算出$f_1 = (r_1 \cdot a) \cdot (z_1 \cdot a)^{-1} = z_1 \cdot r_1^{-1}$。

在这个简单的例子中，让我们假设$f_2 = f_3$。

我们还知道$(r_1 + r_2 - r_3) \cdot d$和$(z_1 + z_2 - z_3) \cdot d$，这是$(r_1 \cdot f_1 + r_2 \cdot f_2 - r_3 \cdot f_3) \cdot d$，我们假设$(r_1 \cdot f_1 + r_2 \cdot f_2 - r_3 \cdot f_2) \cdot d$

从最后一行减去$(r_1 + r_2 - r_3) \cdot d \cdot f_2$后，$r_1 \cdot (f_1 - f_2) \cdot d$

将易于计算的$(f_1 - f_2)^{-1}$和已知的$(a \cdot r_1)^ {-1}相乘得到“商”$d ^ {-1}$

根据给定的值是什么以及为什么/如何选择它们，$f_2 = f_3$可能非常不可能(或不可能)。不过，在这种情况下，所描述的方式提供了一些信息(这对安全性ofc不利)。

除了$d \cdot a^{-1}$，$d \cdot b^{-1}$和$d \cdot c^{-1}$可以以类似的方式计算，如果$f_1 = f_3$和/或$f_1 = f_2$。

Answer 2

答案是正确的。为此目的，您可以考虑以下后果：

$$f_1=r_1^{-1}\cdot z_1，~f_2=r_2^{-1}\cdot z_2，~f_3=r_3^{-1}\cdot z_3$$

然后，我们从第三个组件$u_1$和$u_2$获得：

$$(r1+r2-r3)\cdot d=\alpha$$

$$(z_1+z_2-z_3)\cdot d= (r_1 \cdot f_1+r_2 \cdot f_2-r_3 \cdot f_3)\cdot d=\beta$$

利用上述公式中的乘法$f_1$、$f_2$和$f_3$，并从第二个公式中减去，我们得到了以下三个方程：

$$ r_2 \cdot d \cdot (f_1-f_2) - r_3 \cdot d \cdot (f_1 - f_3)= \alpha \cdot f_1 -\β$

$$ r_1 \cdot d \cdot (f_2-f_1) - r_3 \cdot d \cdot ( f_2 - f_3)= \alpha \cdot f_2-\β$$

$$ r_1 \cdot d \cdot (f_3-f_1) - r_2 \cdot d \cdot (f_3 - f_2)= \alpha \cdot f_3 -\β$

在接下来的步骤中，让$x_1=r_1 \cdot d、x_2=r_2.d、x_3=r_3 \cdot d$，因此我们有：

$$ x_2 \cdot (f_1-f_2) - x_3 \cdot (f_1 - f_3)= \alpha \cdot f_1 -\β$

$$ x_1 \cdot (f_2-f_1) - x_3 \cdot (f_2 - f_3)= \alpha \cdot f_2 -\β$

$$ x_1 \cdot (f_3-f_1) - x_2 \cdot (f_3 - f_2)= \alpha \cdot f_3 -\β$

最后，对线性方程组进行了求解。因此，我们得到了$x_1$、$x_2$和$x_3$的值。