Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Spreading alerts quietly and the subgroup escape problem



J. Aspnes, Z. Diamadi, A. Yampolskiy, K. Gjosteen, Rene Peralta


We introduce a new cryptographic primitive called a blind coupon mechanism (BCM). In effect, a BCM is an authenticated bit commitment scheme, which is AND-homomorphic. We show that a 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.
Journal of Cryptology


Blind Coupon Mechanism, AND-Homomorphic Bit Commitment, Subgroup Escape Problem, Elliptic Curves Over Composite Moduli, Anonymous Communication, Intrusion Detection


Aspnes, J. , Diamadi, Z. , Yampolskiy, A. , Gjosteen, K. and Peralta, R. (2015), Spreading alerts quietly and the subgroup escape problem, Journal of Cryptology, [online],, (Accessed April 20, 2024)
Created September 30, 2015, Updated October 12, 2021