Security claims

Our formal security claims are given below in four different settings: with and without leakage, and in the single-user and multi-user settings. Their complete analysis can be found in:

Single-user security claims with leakage

We focus on integrity and confidentiality in two different leakage models:

  1. Integrity: We show Ciphertext Integrity with nonce Misuse-resistance and Leakages during both encryption and decryption (CIML2), assuming that the two TBCs do not leak (LF-TBC – for Leak-Free Tweakable Block Cipher), and that the permutations leak their state in full (ULM – for Unbounded Leakage Model). In the CIML2 game, the adversary must produce a fresh valid ciphertext while being able to obtain the encryption (resp.) decryption of chosen messages (resp. ciphertexts), together with the corresponding leakages. In doing so, the adversary is authorized to select and also repeat nonces.
  2. Confidentiality: We show confidentiality under Chosen-Ciphertext Attacks with nonce misuse resilence and Leakage in encryption (CCAmL1), assuming that the two TBCs do not leak, that the leakage function of the permutation does not contain any permutation oracle query (OFL – for Oracle-Free Leakage function) and is hard to invert (HIL – for hard to invert leakage function). In the CCAmL1 game, the adversary must provide a fresh nonce and decide which one, among 2 messages, is encrypted with that nonce based on the corresponding ciphertext and encryption leakage. The adversary is also allowed to query a leaking encryption oracle and a (non-leaking) decryption oracle under the usual CCA conditions.

Our security claims in these settings for an n bits secret key are as follows:

security property security (bits) leakage model
CIML2 n - log(n) LF-TBC and ULM
CCAmL1 n/2 LF-TBC and OFL+HIL

The leakage model proposed for CCAmL1 obviously needs to be more restrictive than the one used for CIML2: in the ULM, the leakage function would provide the full internal state of the permuation, which would trivially remove any form of plaintext confidentiality. The misuse-resilience requirement (rather than misuse-resistance) is needed to keep a meaningful notion of leakage resistance, and the non-leaking decryption oracle (rather than a leaking one) is there to keep the requirements compatible with a mode that proceeds in one pass both in encryption and decryption.

Multi-user security claims with leakage (same leakage models)

Here, we consider the natural extensions of CIML2 and CCAmL1 security to the multi-user setting, in which the adversary can interact with multiple users holding different keys. We refer to these notions as muCIML2 and muCCAmL1 respectively.

security property security (bits) # of users
muCIML2 n - 2 log(n) 2n-2
muCCAmL1 n/2 2n-2

Single-user security claims without leakage

In the absence of leakage, we focus on:

  1. Ciphertext integrity with nonce-misuse resistance (CIM), and
  2. CCA real-or-random confidentiality with nonce-misuse resilience (CCAm$)

As usual, the TBC and permutation are treated as ideal objects.

security property security (bits)
CIM n - log(n)
CCAm$ n - log(n)

Multi-user security claims without leakage

security property security (bits) # of users
muCIM n - 2 log(n) 2n-2
muCCAm$ n - 2 log(n) 2n-2