在不洩露資訊的情況下有效地展示/證明第三方秘密的知識
假設愛麗絲發布（即宇宙中的所有各方）密鑰或證書 $ x $ 並發送一個秘密 $ s $ 給鮑勃。然後 Bob 發布了一些數據 $ d $ （他的身份或消息或 smt。）以及使用秘密對數據的身份驗證， $ auth = mac(d,s) $ . 戴夫現在可以驗證 $ d $ , $ verify(auth,x) $ ，並且不能提取關於 $ s $ , 即使 Bob 重用 $ s $ 對於不同的消息。此外，愛麗絲可能會產生許多 $ (x_i,s_i) $ 對和各方的計算資源有限。最後，各方的身份都是已知的，並且私有側通道是可能的（所以 $ s $ 可以安全地傳輸給 Bob）。
這可以使用公鑰加密來實現 $ x $ 作為公鑰和 $ s $ 私鑰。然而，我所知道的（公鑰）算法依賴於大量的素數生成（或其他昂貴的操作），我認為在實踐中 Alice 產生大量未使用的密鑰對時成本太高。
是否有針對上述情況的廉價解決方案？
（標題可能有點不對勁——要是我知道我在找什麼就好了）
對於必須使用其他方法進行身份驗證協議的地方，公鑰密碼術的計算負擔不夠。請注意，您所描述的實際上並不是基於公鑰的。MAC 的驗證要求 Dave 和 Bob 都擁有一個共享密鑰。另外，請注意，必須以某種方式在所有身份驗證協議中包含隨機組件，否則攻擊者將能夠發起中間人攻擊和/或將來重用身份驗證字元串。然而，純粹基於公鑰算法的類似方案確實存在，並且更常用。無論哪種方式，愛麗絲都扮演著 $ TA $ ，通過一些輔助通道驗證 Bob 的身份，並發布一種機制，Dave 可以通過該機制確認 Bob 的私有簽名算法的所有者（可能是 Bob）實際上是 Bob。
在這種情況下，生成公鑰-私鑰對的計算繁重的過程並非每次進行身份驗證時都會發生，而只會在 Bob 向 Alice 要求證書時發生。另請注意，生成公鑰-私鑰對並不是特別昂貴，前提是可以訪問高效的密碼安全隨機數生成器或大型熵池，這兩者都相對容易獲得。
除此之外，還設計了公鑰算法，以便可以有效地計算加密和解密過程。例如，RSA 和其他基於離散對數的問題具有平方乘法或某些變體。因此，Bob 和 Dave 的實際簽名和驗證步驟非常簡單和高效，並且有許多方案只需要有限的計算能力，比如智能卡。