Home > Academic Announcements > (Jan. 11) Zero-Knowledge Proof for Simultaneous Discrete Logarithms and its Applications

(Jan. 11) Zero-Knowledge Proof for Simultaneous Discrete Logarithms and its Applications

Last updated :2019-01-07

Topic: Zero-Knowledge Proof for Simultaneous Discrete Logarithms and its Applications
Speaker: Prof. WENG Jian
(Jinan University)
Time: 16:00-17:00, Friday, January 11, 2019
Venue: Room 415, New Mathematics Building, Guangzhou South Campus, SYSU

Abstract:
The protocol for proving the equality of two discrete logarithms (EQDL) is a fundamental primitive in cryptography. The best existing EQDL protocol was introduced by Chaum and Pedersen in Crypto 1992, and it can be naturally extended for simultaneously proving the equality of n discrete logarithms. However, the Chaum–Pedersen protocol requires O(n) computational complexity and O(n) communication overhead. Somewhat surprisingly, Chaum–Pedersen protocol has never been improved in the past nearly twenty years. In this paper, we introduced a new technique named inhomogeneous commitment aggregation, and proposed a new EQDL protocol, which requires only O(/logn) computational complexity and O(1) communication overhead. Our protocol can benefit a variety of interesting cryptosystems, ranging from signatures and anonymous credential systems, to verifiable secret sharing and threshold cryptosystems. Based on our new protocol, we proposed two tightly secure signature schemes under the well-studied DDH problem and CDH problem respectively. We further proposed a rather efficient multi-signature scheme which can be used in block chain-based systems. Our proposed schemes gain an advantage over the state-of-the-art schemes in terms of both computational cost and communication overhead.