Spreading alerts quietly and the subgroup escape problem

James Aspnes, Zoë Diamadi, Kristian Gjøsteen, René Peralta, and Aleksandr Yampolskiy. Spreading alerts quietly and the subgroup escape problem. Journal of Cryptology 28(4):796–819, October 2015. An earlier version appeared in Advances in Cryptology — ASIACRYPT 2005: 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4–8, 2005. Proceedings. Lecture Notes in Computer Science 3788, Springer-Verlag, December 2005, pp. 253–272. Available as YALEU/DCS/TR-1326, December 2005.


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. 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 ℤn.


title="Spreading alerts quietly and the subgroup escape problem",
author="James Aspnes and Zo{\"e} Diamadi and Kristian Gj\o{}steen and Ren\'e Peralta and Aleksandr Yampolskiy",
journal="Journal of Cryptology",

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page