Tweakable ForkCipher from Ideal Block Cipher

In ASIACRYPT 2019, Andreeva et al. introduced a new symmetric key primitive called the forkcipher, designed for lightweight applications handling short messages. A forkcipher is a keyed function with a public tweak, featuring fixed-length input and fixed-length (expanding) output. They also proposed a specific forkcipher, ForkSkinny, based on the tweakable block cipher SKINNY, and its security was evaluated through cryptanalysis. Since then, several efficient AEAD and MAC schemes based on forkciphers have been proposed, catering not only to short messages but also to various purposes such as leakage resilience and cloud security. While forkciphers have proven to be efficient solutions for designing AEAD schemes, the area of forkcipher design remains unexplored, particularly the lack of provably secure forkcipher constructions. In this work, we propose forkcipher design for various tweak lengths, based on a block cipher as the underlying primitive. We provide proofs of security for these constructions, assuming the underlying block cipher behaves as an ideal block cipher. First, we present a forkcipher, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mtext mathvariant="sans-serif">F</mml:mtext> </mml:mrow> <mml:mo>~</mml:mo> </mml:mover> <mml:mn>1</mml:mn> </mml:mrow> </mml:math>, for an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-bit tweak and prove its optimal (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-bit) security. Next, we propose another construction, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mtext mathvariant="sans-serif">F</mml:mtext> </mml:mrow> <mml:mo>~</mml:mo> </mml:mover> <mml:mn>2</mml:mn> </mml:mrow> </mml:math>, for a <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-bit tweak, also proving its optimal (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-bit) security. Finally, we introduce a construction, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mtext mathvariant="sans-serif">F</mml:mtext> </mml:mrow> <mml:mo>~</mml:mo> </mml:mover> <mml:mi>r</mml:mi> </mml:mrow> </mml:math>, for a general <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-bit tweak, achieving <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-bit security.