CryptoDB
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
Authors: | |
---|---|
Download: | |
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. |
BibTeX
@misc{eprint-2004-12018, title={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}, booktitle={IACR Eprint archive}, keywords={cryptographic protocols / Cryptanalysis}, url={http://eprint.iacr.org/2004/042}, note={ ksliu9@ie.cuhk.edu.hk 12524 received 15 Feb 2004, withdrawn 15 Apr 2004}, author={Joseph K. Liu and Victor K. Wei and Duncan S. Wong}, year=2004 }