是否有任何輸出的偽隨機函式nnn環的素數從ñ從ñZ_{N}在哪裡ññN是 Paillier 公鑰
讓我們假設 $ N $ 是 Paillier 加密公鑰，其中 $ N=pq $ 和 $ p,q $ 是強素數。
我有一組明文 $ p_i $ 誰的域是 $ N $ . 我想確定性地生成一系列偽隨機值 $ r_i $ 有乘法逆元。所以 $ r_i $ 應該均勻隨機分佈在 $ N $ 或其子欄位。
我想將每個明文視而不見 $ b_i=p_i\cdot r_i \bmod N $ . 所以給定 $ b_i $ 半誠實的對手無法學到任何東西 $ p_i $ .
問題：有沒有辦法構造一個偽隨機函式，輸出均勻隨機值 $ N $ （或其子域）並且具有高機率的乘法逆？
TL；DR：所需範圍內的任何（偽）隨機值都有很高的可逆機會。
要理解這一點，首先要記住一個值的標準 $ x $ 乘法可逆 $ \mathbb Z_n $ :
$$ \gcd(n,x)=1 $$ 現在記住存在多少這樣的值，確切地說：
$$ \varphi(n)=(p-1)(q-1)=pq-p-q+1 $$ 現在假設這些不可逆值稍微均勻地分佈在所有小於的整數集合上 $ n $ . 那麼一個值可逆的機會就是
$$ \Pr[x\in \mathbb Z_n:\exists x^{-1}]=\frac{\varphi(n)}{n}=\frac{pq-p-q+1}{pq}=1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq} $$ 現在記住了 $ p,q $ 很大（否則加密可能會被破壞），然後 $ 1/p,1/q $ 和 $ 1/(pq) $ 可以忽略不計，因此整數可逆的機率接近 1。
至於構造這樣的值：只需生成適當大小的位串並丟棄它們，直到它們符合您的限制（例如 $ \leq n $ )，通常您將不得不以這種方式丟棄一個整數或一個整數。