Proving Security of Duplex Construction. ∈ Our proof uses many ideas from the solid black-box research already performed on keyed sponges and duplexes [1, 8, 10, 12, 15, 21, 26, 30, 31]. However, not all tech- niques from this line of research are suited in the leakage resilience setting. Most importantly, a notable technique [1, 12, 15, 30] is to view the keyed sponge/duplex as a mode based on an Even-Xxxxxxx construction on top of the permutation p perm(b). The trick is to XOR two copies of a dummy key with the inner part in-between every two evaluations of the permutation p. The change is purely syn- tactical, and a distinguisher cannot note the difference. However, in the leakage resilience setting, the distinguisher may have chosen the leakage function L so as to leak part of the state that is keyed, and XORing dummy keys turns out to become tricky. In particular, adoption of the approach to the leakage resilience setting would require us to be able to “split” leakages into input leakages and output leakages, but this is not always possible, depending on the leakage func- tion L. Instead, the proof resembles much of the approach of Xxxxxxxxx et al. [26], who performed a direct security proof of the NORX nonce-based authenticated encryption scheme that also applied to other CAESAR candidates. At a high level, the proof of Xxxxxxxxx et al. consists of observing that the output states are always uniformly random (bar repetition, as a permutation is evaluated), as long as no bad event occurs. A bad event, in turn, occurs if there are two construction queries with colliding states or if there is a construction query and a primitive query with colliding states. The absence of collisions is dealt with in the first phase by replacing the random permutation by a function that samples values from random at the cost of an RP-to-RF switch. In our leakage resilience proofs, we follow the same approach. We also start by replacing the random permutation by a function f, that samples values from random and provides two-sided oracle access. Then, as long as the state of the keyed duplex has enough entropy, the result after applying f is random and also has enough entropy. Clearly, the entropy of the state reduces with the amount of leakage that occurs on the state, and consequently, bad events happen with a slightly larger probability as before. This also shows that estimating (formally, lower bounding) the amount of min-entropy of the states in the keyed duplex construction is important for deriving a tight...
