International Association for Cryptologic Research

International Association
for Cryptologic Research


ByeongHak Lee


Tight Security Bounds for Double-block Hash-then-Sum MACs 📺
In this work, we study the security of deterministic MAC constructions with a double-block internal state, captured by the double-block hash-then-sum (DBH) paradigm. Most DBH constructions, including PolyMAC, SUM-ECBC, PMAC-Plus, 3kf9 and LightMAC-Plus, have been proved to be pseudorandom up to 2^{2n/3} queries when they are instantiated with an n-bit block cipher, while the best known generic attacks require 2^{3n/4} queries. We close this gap by proving the PRF-security of DBH constructions up to 2^{3n/4} queries (ignoring the maximum message length). The core of the security proof is to refine Mirror theory that systematically estimates the number of solutions to a system of equations and non-equations, and apply it to prove the security of the finalization function. Then we identify security requirements of the internal hash functions to ensure 3n/4-bit security of the resulting constructions when combined with the finalization function. Within this framework, we prove the security of DBH whose internal hash function is given as the concatenation of a universal hash function using two independent keys. This class of constructions include PolyMAC and SUM-ECBC. Moreover, we prove the security of PMAC-Plus, 3kf9 and LightMAC-Plus up to 2^{3n/4} queries.
Indifferentiability of Truncated Random Permutations
Wonseok Choi Byeonghak Lee Jooyoung Lee
One of natural ways of constructing a pseudorandom function from a pseudorandom permutation is to simply truncate the output of the permutation. When n is the permutation size and m is the number of truncated bits, the resulting construction is known to be indistinguishable from a random function up to $$2^{{n+m}\over 2}$$ queries, which is tight.In this paper, we study the indifferentiability of a truncated random permutation where a fixed prefix is prepended to the inputs. We prove that this construction is (regularly) indifferentiable from a public random function up to $$\min \{2^{{n+m}\over 3}, 2^{m}, 2^\ell \}$$ queries, while it is publicly indifferentiable up to $$\min \{ \max \{2^{{n+m}\over 3}, 2^{n \over 2}\}, 2^\ell \}$$ queries, where $$\ell $$ is the size of the fixed prefix. Furthermore, the regular indifferentiability bound is proved to be tight when $$m+\ell \ll n$$.Our results significantly improve upon the previous bound of $$\min \{ 2^{m \over 2}, 2^\ell \}$$ given by Dodis et al. (FSE 2009), allowing us to construct, for instance, an $$\frac{n}{2}$$-to-$$\frac{n}{2}$$ bit random function that makes a single call to an n-bit permutation, achieving $$\frac{n}{2}$$-bit security.
Tweakable Block Ciphers Secure Beyond the Birthday Bound in the Ideal Cipher Model
ByeongHak Lee Jooyoung Lee
We propose a new construction of tweakable block ciphers from standard block ciphers. Our construction, dubbed $$\mathsf {XHX2}$$, is the cascade of two independent $$\mathsf {XHX}$$ block ciphers, so it makes two calls to the underlying block cipher using tweak-dependent keys. We prove the security of $$\mathsf {XHX2}$$ up to $$\min \{2^{2(n+m)/3},2^{n+m/2}\}$$ queries (ignoring logarithmic factors) in the ideal cipher model, when the block cipher operates on n-bit blocks using m-bit keys. The $$\mathsf {XHX2}$$ tweakable block cipher is the first construction that achieves beyond-birthday-bound security with respect to the input size of the underlying block cipher in the ideal cipher model.


Wonseok Choi (1)
Seongkwang Kim (1)
Jooyoung Lee (3)