RSA 累加器中的包含和排除證明
我正在從該影片和其他幾個來源中閱讀有關RSA 累加器的資訊。我很困惑是否需要完整的集合來建構 RSA 累加器中的包含/排除證明，或者是否可以僅通過知道累加器根和成員資格/非成員資格的值來創建包含/排除證明必須提供證明。有人可以澄清一下嗎？
不，是的！對於包含證明，您需要陷門或累積集。然而，可以在不知道陷門的情況下生成排除證明，即模的分解， $ N=p\cdot q $ ，或組的大小，即 $ \phi(N) $ .
讓 $ A $ 表示累加器的目前值， $ x $ 一個物品， $ g $ , 群的生成器和 $ \pi $ 包含/排除證明。所有算術都已完成 $ \mod N $ . 另請注意，所有項目（累加元素）都是素數。
$ inclusionProof(A,x): \pi =A^{\frac{1}{x}} $ . 請注意，只有當您知道組的順序或累積集作為計算時，這才是可計算的 $ x $ 根 $ \mod N $ 在不知道因式分解的情況下假設是困難的 $ N $ .
驗證包含證明很容易，只需要檢查是否 $ \pi^x=A $ . 一旦物品被積累，人們就可以輕鬆地更新她的包含見證人。
讓 $ A=g^u $ 那麼，
$ exclusionProof(A,x): $ 自從 $ x $ 不是累積的，這意味著 $ gcd(u,x)=1, $ 因此可以計算 $ a,b $ ，所謂的 Bezout 係數，這樣 $ ax+bu=gcd(x,u)=1 $ . 因此 $ \pi=(g^a,b). $ 通過檢查來驗證證明 $ (g^a)^x\cdot A^b=g^{ax+ub}=g $ .
批量包含/排除證明也是可以實現的。看到這個最近的結果。
假設你不知道累加器的活板門。
答案取決於，如果值已經存在於累加器中，那麼您需要所有元素來生成見證。如果要添加，則見證是添加新值之前的累加器值。
例如。如果你有元素 $ S_1 = {x_1, x_2, … x_k} $ , 累加器是 $ A_{S_1} = g^{\prod_{i=0}^k x_i} $ . 現在如果 $ y_1 $ 要添加，集合將變為 $ S_2 = {x_1, x_2, … x_k, y_1} $ 累加器將變為 $ A_{S_2} = g^{{\prod_{i=0}^k x_i} . y_1} $ . 為證人 $ y_1 $ 是 $ A_{S_1} $ .
但是一旦你有一個元素的見證，隨著累加器的變化更新見證應該花費與累加器變化成正比的時間。