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

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

• ASIACRYPT 2005 proceedings version: PDF.
• Slides for Aleksandr Yampolskiy's ASIACRYPT talk PowerPoint.
• IACR ePrint archive version at IACR Cryptology ePrint archive.
• Technical report: PDF.
• Full version: PDF.

BibTeX

@inproceedings(AspnesDGPY2005,
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",
booktitle="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.",
publisher="Springer-Verlag",
series="Lecture Notes in Computer Science",
volume="3788",
month=dec,
year=2005,
pages={253--272}
)