关于OU实现

[ssdyue]

请问，在ou实现过程中，计算 gp=g^(p-1) mod p^2 后，为什么还要计算gp^p mod p^2呢，如下：

MPInt::PowMod(g % sk->p2_, sk->p_ - MPInt::_1_, sk->p2_, &gp); MPInt::PowMod(gp, sk->p_, sk->p2_, &check);

[usafchn]

hello，您好~

我们的 OU 是按照这篇 paper 实现的，推荐看一下原文。

计算 gp^p mod p^2 是为了确保 gp 在 Z/p^2*Z 群中的阶是p，paper 中也有提到。

[ssdyue]

@usafchn 感谢！

[ssdyue]

@usafchn

您好，请问这篇paper的Key Setup：

choose g‘ < n at random

是否需要g'和p互素呢？

因为根据欧拉定理，解密过程的g'^{nr(p−1)} =1 mod p^2应该是要求g'与p^2互质吧

[usafchn]

@ssdyue 抱歉前几天没有看到问题，好问题啊， 首先强调一下 p 本来就是一个素数，原文说的是 "p − 1 has a large (160-bit) prime factor t"，而不是说 p 有 large factor t 。

所以 g' 随机采样一个数，g' 只有正好等于 p 的倍数时与p^2不互质，不互质的概率就非常小了，小到可以忽略不计，一般小于 2^-128 的概率就可以忽略不计了，何况 p 是一个600多 bits 的大整数。anyway，给g' 加个校验是更好的方式，我后面加一下