GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks
Abstract
Guillou–Quisquater（GQ）與 Schnorr identification schemes，是最有效率且最知名的 Fiat–Shamir follow-ons 之一；然而，關於它們是否能在 impersonation under active attack 下被證明安全，這個問題一直懸而未決。
-
本文針對 GQ，基於 RSA 在 one-more inversion 假設下的安全性，給出了這樣的安全證明；這個假設是對一般 one-wayness assumption 的延伸，最早由文獻 BNPS01 提出。
-
本文也針對 Schnorr scheme，基於一個對應的、與 discrete logarithm 相關的假設，給出了同樣的安全證明。
這些結果是首次在與底層 one-way functions 相關的假設下，為這些 schemes 建立安全證明。此外，兩項結果也都可以進一步延伸，用來證明它們在 concurrent attack 下仍然安全。
在 identification schemes 中，常見的攻擊模型包括 passive, active and concurrent attack。
Passive attack.
在 passive attack 下，攻擊者只能被動觀察 honest Prover 與 honest Verifier 之間的合法互動，也就是只能取得 transcripts，而不能自行參與協議。若攻擊者在觀察之後仍無法成功冒充 Prover，則稱該 scheme 對 impersonation under passive attack 安全。
Active attack.
在 active attack 下，攻擊者可以主動與 honest Prover 互動，扮演 verifier 並自選 challenge、蒐集多次執行的資訊；之後再嘗試向 honest Verifier 冒充為合法 Prover。若在此模型下仍無法成功冒充，則稱該 scheme 對 impersonation under active attack 安全。
Concurrent attack.
在 concurrent attack 下，攻擊者除了可以主動互動之外，還可以同時發起並操控多個 protocol sessions，並將不同 sessions 的訊息交錯、延遲或轉送，以進行更強的攻擊。若 scheme 在這種並行互動環境下仍能防止冒充，則稱其對 impersonation under concurrent attack 安全。
強弱關係：concurrent attack > active attack > passive attack
References
- BNPS01 Mihir Bellare, Chanathip Namprempre, David Pointcheval, and Michael Semanko. The one-more-RSA inversion problems and the security of Chaum’s blind signature scheme. Available as IACR ePrint Archive Report 2001/002, 2001.