International Association
for Cryptologic Research

With the development of quantum attacks, many classical-secure structures are not secure in quantum. How to evaluate the quantum security of structure and give a tight security bound becomes a challenging research topic. As a tweakable block cipher structure based on block ciphers, $\mathsf{TNT}$ was proven to be of classical beyond-birthday-bound $O(2^{3n/4})$ security. We prove that $\mathsf{TNT}$ is a quantum-secure tweakable block cipher with a bound of $O(2^{n/6})$. In addition, we show the tight quantum PRF security bound of $O(2^{n/3})$ when $\mathsf{TNT}$ is based on random functions, which is better than $O(2^{n/4})$ given by Bhaumik et al. and solves their open problem. Our proof uses the recording standard oracle with errors technique of Hosoyamada and Iwata based on Zhandry’s compressed oracle technique.