Paillier 複雜殘差問題？

Paillier Cryptosystem 取決於分解 $ n = p.q $ 以及在原始論文中定義的複雜剩餘問題：

決定第n個殘基的問題，即區分第n個殘基和非第n個殘基的問題將用CR表示

$$ n $$. 觀察像決定二次或更高階殘差的問題，CR$$ n $$是一個隨機自約問題，即它的所有實例都是多項式等價的。因此，每種情況都是平均情況，問題要麼是一致難以處理的，要麼是一致多項式的。至於素殘差，確定第 n 個殘差被認為在計算上是困難的。因此，我們將假設： **猜想2.**不存在第n個餘數模n2的多項式時間區分器，即CR

$$ n $$是棘手的。 因此，根據本說明中給出的數字 $ \mathbb{Z}_{n^2}^* $ 我無法確定這個數字是否在殘基集上。

我的問題是：

1. 如果這有什麼難的 $ z=y^n\ mod\ n^2 $
2. 更重要的是知道殘基中的一個數字是多麼危險。它如何幫助我破解加密？

1. 如果這有什麼難的 $ z=y^n\ mod\ n^2 $

我們不知道解決它的有效方法。這基本上就是我們可以說的密碼學中的任何難題。

我們也不知道如何簡化為更好研究的問題（例如，分解問題）；因此它被稱為一個單獨的難題。

2. 更重要的是知道殘基中的一個數字是多麼危險。它如何幫助我破解加密？

這很容易; 一個可以解決第 n 個殘留問題（不知道分解）的 Oracle 允許我們確定 Pallier 加密消息是否是 0 的編碼（因為密文是 0 的編碼當且僅當它是第 n殘留物）。

這不僅本身會被視為安全漏洞，我們還可以（例如）測試加密消息與任何其他值的相等性（通過加密該值，從加密值的密文中同態地減去測試密文，並檢查這是否是 0 的編碼）。

引用自：https://crypto.stackexchange.com/questions/74831