Paper 2018/994

People Who Live in Glass Houses Should not Throw Stones: Targeted Opening Message Franking Schemes

Long Chen and Qiang Tang

Abstract

Message franking enables a receiver to report a potential abuse in a secure messaging system which employs an end to end encryption. Such mechanism is crucial for accountability and is already widely adopted in real world products such as the Facebook messenger. Grubs et al initiated a systematic study of such a new primitive, and Dodis et al gave a more efficient construction. We observe that in all existing message franking schemes, the receiver has to reveal the whole communication for a session in order to report one abuse. This is highly undesirable in many settings where revealing other non-abusive part of the communication leaks too much information; what is worse, a foxy adversary may intentionally mixing private information of the receiver with the abusive message so that the receiver will be reluctant to report. This essentially renders the abuse reporting mechanism ineffective. To tackle this problem, we propose a new primitive called targeted opening compactly committing AEAD (TOCE for short). In a TOCE, the receiver can select arbitrary subset of bits from the plaintext to reveal during opening, while keep all the rest still secure as in an authenticated encryption. We gave a careful formulation, together with a generic construction which allowing a bit level targeted opening. While the generic construction may require a substantial number of passes of symmetric key ciphers when encrypting a large message such as a picture, we thus further set forth and give a more efficient non-black-box construction allowing a block-level (e.g., 256 bit) opening. We also propose a privacy-efficiency trade off if we can relax the security of non-opened messages to be one way secure after the abusive reporting (they are still semantically secure if no opening).

Note: Revise some typos