Cryptology ePrint Archive: Report 2018/126

Onion-AE: Foundations of Nested Encryption

Phillip Rogaway and Yusi Zhang

Abstract: Nested symmetric encryption is a well-known technique for low-latency communication privacy. But just what problem does this technique aim to solve? In answer, we provide a provable-security treatment for onion authenticated-encryption (onion-AE). Extending the conventional notion for authenticated-encryption, we demand indistinguishability from random bits and time-of-exit authenticity verification. We show that the encryption technique presently used in Tor does not satisfy our definition of onion-AE security, but that a construction by Mathewson (2012), based on a strong, tweakable, wideblock PRP, does do the job. We go on to discuss three extensions of onion-AE, giving defini- tions to handle inbound flows, immediate detection of authenticity errors, and corrupt ORs.

Category / Keywords: foundations / Anonymity, authenticated encryption, onion routing, privacy, oracle silencing, provable security, Tor

Original Publication (in the same form): PETS 2018, Issue 2

Date: received 2 Feb 2018

Contact author: ysizhang at ucdavis edu

Available format(s): PDF | BibTeX Citation

Version: 20180205:191724 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]