Threshold Anonymous Group Identification and Zero-Knowledge Proof

摘要

We show that the communication efficient t-out-of-m scheme proposed by De Santis, Di Crescenzo, and Persiano [Communication-efficient anonymous group identification, ACM Conference on Computer and Communications Security, (1998) 73–82] is incorrect; an authorized group may fail to prove the identity even though the verifier is honest. We rigorously discuss the condition where the scheme works correctly. In addition, we propose a new scheme attaining Θ(mn) communication complexity, where n is the security parameter. It improves the current best communication complexity Θ(mn logm) of the t-out-of-m scheme, and it can be also considered as a zero-knowledge proof for t out of m secrets.