加密方案nnnpk 任何 sk 的 pk 都可以解密？
假設有 $ n $ 每個使用者都有公鑰/私鑰對 $ (pk_i,sk_i) $ $ i=1,\cdots,n $ . 有沒有我可以加密的方案 $ m $ 使用一組公鑰 $ (pk_1,\cdots,pk_n) $ ，並且可以使用任何 $ sk_i $ ? 那是 $ C=Enc_{(pk_1,\cdots,pk_n)}(m) $ 和 $ m=Dec_{any\ sk_i}(C) $ .
當這些 $ n $ 使用者只是一組中的一小部分 $ N $ 使用者。有點像“環加密”（與環簽名相反）。謝謝！
這絕不是實際的，但描述一個方案相對容易。
如果公鑰包含（或允許輕鬆推導）唯一質數（只需在收件人中唯一 - 如果每個收件人都知道任何其他收件人的公鑰，並且可以訂購公鑰，我們可以使用第一個 $ n $ 素數。），說 $ r_i $ ， 您可以使用：
$$ C=\prod_{i=1}^n r_i^{\operatorname{enc}_{pk_i}(m)} $$ （在哪裡 $ \operatorname{enc} $ 是加密給一個收件人的功能）。 然後為了解密你“只是”需要確定因素 $ C $ 並確定最高功率 $ r_i $ 將其除以指數，並將指數放入函式中以解密給一個接收者。
我沒有試圖證明打破這個比打破它所基於的方案更容易。我不明白為什麼會這樣，而且考慮到這是多麼不切實際，我認為這並不重要。
這在 RSA 下是可行的。
為清楚起見，我將把使用者數重命名為 $ u $ 和使用者總數 $ U $ , 因為 mod $ n $ 在 RSA 中很重要。
我將為 RSA 使用以下符號：
消息 M 通過填充轉換為整數 $ m $ .
在標準 RSA 下，消息將被加密為 $ m^e $ 反對 $ n $ . 然後接收者將通過執行解密 $ (m^e)^d $ 反對 $ n $ . $ e $ 和 $ n $ 組成公鑰。 $ d $ 是私鑰。
我們要建立一些最小值， $ n_{\min} $ （足夠大）。所有使用者將具有完全相同的值 $ e $ . 然後每個人都會生成自己的 $ n_i \geq n_{\min} $ 以便 $ e $ 對它來說是“合法的”（即，如果 $ n_i=p_iq_i $ ， 然後 $ e < \lambda(n_i)=lcm(p_i-1,q_i-1) $ 和 $ e $ 是互質的 $ \lambda(n_i) $ ）。每個人都有自己的私鑰 $ d_i $ .
為了發送消息 $ M $ 它被填充到一個整數 $ 0 \leq m < n_{\min} $ . 讓 $ N = \prod n_i $ （其實就夠了 $ N $ 作為所有的lcm $ n_i $ 對於接收消息的使用者，但發送者當然不知道 $ n_i $ ）。那麼加密的消息是 $ m^e $ 反對 $ N $ .
讓加密的消息成為 $ x $ . 那麼，存在一些 $ c $ 這樣 $ m^e = cN + x $ . 所以 $ m^e $ 反對 $ n_i $ 是 $ x $ 對所有人 $ i $ . 因此， $ (m^e)^{d_i} $ 反對 $ n_i $ 是 $ m $ 對所有人 $ i $ .
有效性威脅：如果 $ N $ 大到 whp $ m^e < N $ ，那麼任何其他使用者都可以解密該消息，因為 $ m^e $ 將是明文。為避免這種情況，填充方案應確保 $ m $ 足夠大。同樣我們可能需要 $ e $ 足夠大以支持多達 $ R $ 使用者。為簡單起見，如果我們假設 $ n $ 有長度 $ b $ -bits，那麼我們需要那個 $ e\log m >> Rb $ . 雖然Håstad 的廣播攻擊不應該是相關的，但可以採取 $ e > R $ 無論如何，為了安全起見。
雖然某些消息可能被加密為較短的長度，但輸出可能與 $ \log N $ 這將是 $ ub $ - 在哪裡 $ b $ 是位大小的 $ n $ 的（例如讓 $ n_\min=2^b $ 並讓所有 $ n_i $ 是 $ b $ 位長）。如果我們能以某種方式將輸出轉換為大約為 $ b $ 位（畢竟，我們擁有的消息數量是 $ n_\min $ ）。例如，如果我們可以緊湊地編碼一個額外的乘法器 $ c $ 這樣 $ cm^e $ 很小，我們可以很容易地分開 $ c $ .