International Association for Cryptologic Research

International Association
for Cryptologic Research

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