Cryptology ePrint Archive: Report 2005/282
Spreading Alerts Quietly and the Subgroup Escape Problem
James Aspnes and Zoë Diamadi and Kristian Gjøsteen and René Peralta and Aleksandr Yampolskiy
Abstract: We introduce a new cryptographic primitive called the blind coupon mechanism (BCM). In effect, the BCM is an authenticated bit-commitment, which is AND-homomorphic. It has not been known how to construct such commitments before. We show that the BCM has natural and important applications. In particular, we use it to construct a mechanism for transmitting alerts undetectably in a message-passing system of n nodes. Our algorithms allow an alert to quickly propagate to all nodes without its source or existence being detected by an adversary, who controls all message traffic. Our proofs of security are based on a new subgroup escape problem, which seems hard on certain groups with bilinear pairings and on elliptic curves over the ring Zn.
Category / Keywords: AND-homomorphic bit commitment, Blind coupon mechanism, Elliptic curves over composite moduli, Subgroup escape problem, Anonymous communication.
Publication Info: Extended abstract is to appear in ASIACRYPT 2005
Date: received 22 Aug 2005
Contact author: aleksandr yampolskiy at yale edu
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20050825:074136 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]