Rsa
排除證明費用
我想了解通用累加器的非會員驗證成本是多少？
更具體地說，我該如何計算它？
使用累加器是否比 Merkle 雜湊樹更有效？
答案取決於您正在考慮的通用累加器方案：
- 排序 的 Merkle 樹 如果 Merkle 樹是排序的，那麼可以只發送兩個相鄰的 Merkle 路徑，顯示不包含元素。這給出了對數的非成員證明以及對數的驗證成本。
- Merkle Tree 按照 Micali、Rabin 和 Kilian 的想法，您可以創建兩棵樹。一個用於集合中的元素，另一個樹用於所謂的邊界集。Frontier是所有不在樹中的值的祖先集合（請注意，這與集合本身的大小大致相同）。然後，為了證明一個值包含在集合中，您使用第一棵樹，並證明它不是您使用第二棵樹。請參閱Yehuda Lindell的相關答案和此處的論文。
- RSA 累加器 Let $ A $ 表示累加器的目前值和 $ g $ RSA 組中的生成器。讓 $ A=g^u $ 那麼，（快速提醒，在 RSA 累加器中，您可以“僅”累加素數！） $ exclusionProof(A,x): $ 自從 $ x $ 不是累積的，這意味著 $ gcd(u,x)=1, $ 因此可以計算 $ a,b $ ，所謂的 Bezout 係數，這樣 $ ax+bu=gcd(x,u)=1 $ . 因此 $ \pi=(g^a,b). $ 通過檢查來驗證證明 $ \pi^x\cdot A^b=g $ . 因此，證明大小和驗證成本都是恆定的。但是，您需要一個可信的 RSA 累加器設置。批量排除證明也是可能的。看到這個最近的結果。
- 基於配對的累加器 Damgard 等人。為基於配對的累加器創建非成員證明。非成員證明的驗證成本是單個配對檢查，但是計算這樣的證明是累積集合大小的多項式。