Cryptology ePrint Archive: Report 2004/042

Cryptanalyzing Bresson, et al.'s Spontaneous Anonymous Threshold Signature for Ad Hoc Groups and Patching via Updating Cramer, et al.'s Threshold Proof-of-Knowledge

Joseph K. Liu and Victor K. Wei and Duncan S. Wong

Abstract: We present an algebraic cryptanalysis of Bresson, et al.'s spontaneous anonymous threshold signature for ad hoc groups. The technique is to reduce a degenerate condition in Lagrange interpolation to an algebraically solvable high-density knapsack problem over $GF(2^\ell)$. We repair their protocol by revisiting and updating Cramer, et al.'s result on spontaneous anonymous threshold proof-of-knowledge (partial proof-of-knowledge). We generalize their proof by removing two assumptions, and reduce its security to a new candidate hard problem, PoK-Collision, in the random oracle model. To add to the urgency of our update, we present major versions of major PoK schemes that do not satisfy their special soundness assumption.

Category / Keywords: cryptographic protocols / Cryptanalysis

Date: received 15 Feb 2004, withdrawn 15 Apr 2004

Contact author: ksliu9 at ie cuhk edu hk

Available formats: (-- withdrawn --)

Version: 20040416:063538 (All versions of this report)

Discussion forum: Show discussion | Start new discussion