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
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 format(s): (-- withdrawn --)
Version: 20040416:063538 (All versions of this report)
Short URL: ia.cr/2004/042
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]