International Association for Cryptologic Research

International Association
for Cryptologic Research

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
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
}