Perfect ZK Argument of Knowledge of Discrete Logarithm in A Cyclic Group with Unknown Order

Abstract

ZK (zero knowledge) proof of knowledge of discrete logarithm (and sometimes extended to ZK proof of equality of discrete logarithms) in cyclic groups with unknown orders are widely employed in various cryptographic applications. To the best of our knowledge the present implementations of these two proofs have some drawbacks. Firstly, they can only achieve statistical ZK, which is not only weaker in theory than perfect ZK but also difficult to formally prove in practice. Moreover, the drawback is not limited to theoretic problems like provability but sometimes deteriorate efficiency of ZK proof to an intolerable level as we will show in a case study. The first perfect ZK argument of the proof is proposed in this paper, which is formally provable and can always guarantee acceptable efficiency. It is especially suitable for applications with high requirement on privacy and complex secure protocols requiring concise and formal proof of ZK privacy.