Determining the Core Primitive for Optimally Secure Ratcheting

Fatih Balli; Paul Rösler; Serge Vaudenay

Paper 2020/148

Determining the Core Primitive for Optimally Secure Ratcheting

Fatih Balli, Paul Rösler, and Serge Vaudenay

Abstract

After ratcheting attracted attention mostly due to practical real-world protocols, recently a line of work studied ratcheting as a primitive from a theoretic point of view. Literature in this line, pursuing the strongest security of ratcheting one can hope for, utilized for constructions strong, yet inefficient key-updatable primitives – based on hierarchical identity based encryption (HIBE). As none of these works formally justified utilizing these building blocks, we answer the yet open question under which conditions their use is actually necessary. We revisit these strong notions of ratcheted key exchange (RKE), and propose a more realistic (and slightly stronger) security definition. In this security definition, both the exposure of the communicating parties' local states and the adversary's ability to attack the executions' randomness are considered. While these two attacks were partially considered in previous work, we are the first to unify them cleanly in a natural game based notion. Our definitions are based on the systematic RKE notion by Poettering and Rösler (CRYPTO 2018). Due to slight (but meaningful) changes to regard attacks against randomness, we are ultimately able to show that, in order to fulfill strong security for RKE, public key cryptography with (independently) updatable key pairs is a necessary building block. Surprisingly, this implication already holds for the simplest RKE variant (which was previously instantiated with only standard public key cryptography). Hence, (1) we model optimally secure RKE under randomness manipulation to cover realistic attacks, (2) we (provably) extract the core primitive that is necessary to realize strongly secure RKE, and (3) our results indicate under which conditions this primitive is necessary for strongly secure ratcheting and which relaxations in security allow for constructions that only rely on standard public key cryptography.

Note: This is a minor revision and full version of the article presented at Asiacrypt 2020.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in ASIACRYPT 2020
Keywords: Ratcheting Ratcheted Key Exchange Key-Updatable Public Key Cryptography Relations Hardness
Contact author(s): paul roesler @ rub de
History: 2020-08-24: last of 2 revisions; 2020-02-10: received; See all versions
Short URL: https://ia.cr/2020/148
License: CC BY

BibTeX

@misc{cryptoeprint:2020/148,
      author = {Fatih Balli and Paul Rösler and Serge Vaudenay},
      title = {Determining the Core Primitive for Optimally Secure Ratcheting},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/148},
      year = {2020},
      url = {https://eprint.iacr.org/2020/148}
}