Elligator

Introduction

Wustrow, Wolchok, Goldberg, and Halderman (USENIX Security Symposium 2011) introduce "Telex, a new approach to resisting state-level Internet censorship". They say that for efficiency and security "we must use elliptic curve groups" but that it is "quite tricky" to "transmit group elements" in a way that is "indistinguishable from uniformly random strings of the same size". To achieve indistinguishability, Telex is forced to work simultaneously with "two elliptic curves" (a curve and its "twist") using "two generators" and two "public keys".

Similar comments apply to "Stegotorus" from Weinberg, Wang, Yegneswaran, Briesemeister, Cheung, Wang, and Boneh (ACM CCS 2012). One should expect the same problem in every new anti-censorship protocol: when there are constraints on computation and bandwidth (especially when a protocol is being hidden in the nooks and crannies of a cover protocol), the only high-security option is ECC, but elliptic-curve points are easily distinguished from uniform random strings.

Elligator has exactly the same motivation but introduces a new solution: an encoding for points on a single curve as strings indistinguishable from uniform random strings. This eliminates the problem at its source once and for all, rather than forcing every protocol designer to somehow deal with the same problem at a higher level. The advantages of Elligator are particularly clear for Stegotorus, which uses a separate Möller layer for no reason other than to achieve indistinguishability; Elligator eliminates this protocol layer, simplifying and accelerating the client and server and saving half of the space for the initial Stegotorus communication.

Poster

Elligator contributors (alphabetical order)

Daniel J. Bernstein, University of Illinois at Chicago and Technische Universiteit Eindhoven

Mike Hamburg, Cryptography Research, a division of Rambus

Anna Krasnova, Radboud Universiteit Nijmegen

Tanja Lange, Technische Universiteit Eindhoven

Acknowledgments

This work was supported by the U.S. National Science Foundation under grant 1018836. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation."

This work was supported by the Netherlands Organisation for Scientific Research (NWO) under grants 639.073.005 and 040.09.003.

This work was supported by the National Science Council of Taiwan under NSC 101-2915-I-001-019. Part of this work was done while Bernstein, Krasnova, and Lange visited Academia Sinica; they wish to thank Bo-Yin Yang for his hospitality.

This work was supported by the European Commission under Contract ICT-2007-216676 ECRYPT II.

This work was supported by SIDN.nl.

Thanks to Steven Galbraith for pointing out the role of indistinguishability in password-authenticated key exchange. Thanks to Moti Yung for pointing out the role of indistinguishability in kleptography.

Version: This is version 2017.01.22 of the index.html web page.