## CryptoDB

### Paper: 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: Joseph K. Liu Victor K. Wei Duncan S. Wong URL: http://eprint.iacr.org/2004/042 Search ePrint Search Google 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
}