只有非會員見證的動態累加器
目標：建構一個可以添加元素並提供非成員見證的動態累加器。我想知道我的結構是否正確。
考慮一組 $ Z_p $ 在哪裡 $ p $ 是質數。考慮集合 $ S={c_1, c_2,\cdots, c_m} $ 在哪裡 $ c_i\in Primes(Z_p) $ . 考慮以下累加器： $$ A = \left(\prod_{c_i \in S} c_i\right) \text{mod } p. $$
添加：添加新元素 $ c \in Primes(Z_p) $ , $$ A \longleftarrow \left(A\times c\right) \text{mod } p. $$
非會員證人 $ (x,y) $ ： 以顯示 $ c \not\in S $ ，我們使用的事實是 $ c $ 與中的所有元素互質 $ S $ . 我們使用 Bezout 係數 $ (x,y) $ 表明 $$ cx+Ay=1 \text{ mod } p. $$
安全： $ \forall c\in S $ , 不存在算法 $ \mathcal{A} $ 這樣
$$ (x,y) \leftarrow \mathcal{A}(c,S),; cx+Ay=1 \text{ mod } p. $$
這不是一個正確的動態累加器方案。
您的方案假設以下成立：如果 $ a,b $ 是質數和 $ 0< a,b < p $ ， 然後$$ (a,b)=1 \implies (ab\mod p,a)\neq1. $$如果這是真的，那麼你的方案是正確的，但事實並非如此。
玩具範例： $ p=11,a=5,b=7 $ . 自從 $ ab \mod 11=35 \mod 11=2, $ 所以 $ A=2 $ . 現在，很明顯安全性不成立，因為可以證明虛假的非會員聲明。原因是： $ (a,A)=1=(b,A) $ . 意思是可以證明 $ a $ 和 $ b $ 不會累加，但它們確實已添加到累加器中。例如 $ (2,1) $ 是非會員證人 $ 5 $ ， 什麼時候 $ A=2 $ ， 自從 $ 52+21 \mod 11 = 1 $ .