notesum.ai

Published at December 6

Quantum Security Analysis of the Key-Alternating Ciphers

quant-ph

cs.CR

Released Date: December 6, 2024

Authors: Chen Bai¹, Mehdi Esmaili¹, Atul Mantri¹

Aff.: ¹Virginia Tech

Arxiv: http://arxiv.org/pdf/2412.05026v1

Refer to caption

Target	Setting	Upper Bound	Lower Bound
KAC	Classical	$O(2^{n/2})$ [Dae93]	$\Omega(2^{n/2})$ [EM97]
	$Q1$	$\tilde{O}(2^{n/3})$ [KM12, BHNP⁺19a]	$\Omega(2^{n/3})$ [ABKM22]
	$Q2$	$O(n)$ [KM12]	-
2-KAC	$Q2$	$O(n2^{n/2})$ [CGL22]	-
4-KAC	$Q2$ (two alternated keys)	$O(n2^{n/2})$ [AGIS24]	-
$t$ -KAC	Classical	$O(2^{{\frac{tn}{t+1}}})$ [BKL⁺12]	$\Omega(2^{{\frac{tn}{t+1}}})$ [CS14]
$t$ -KAC	Classical (same key/permutation)	$O(2^{n/2})$ [CLL⁺18]	-
$t$ -KAC	$Q2$ (same key/permutation)	$O(n)$ [KLLNP16]	-
$t$ -KAC	$Q1$ ( $t$ equal keys)	$O(2^{n})$ Subsection 3.3	-
$t$ -KAC	$Q1^{*}$	$O(2^{\frac{t(t+1)n}{(t+1)^{2}+1}})$	$\Omega(2^{\frac{(t-1)n}{t}})$ (for $t\geq 2$ )
		(Theorem 3.4)	(Theorem 4.5)
$t$ -KAC	$Q1$	$O(2^{\frac{t(t+1)n}{(t+1)^{2}+1}})$ (Theorem 3.4)	-