Mathematical Methods of Cryptography

WOTS-BC — Winternitz signature scheme based on lightweight block ciphers

V. A. Kiryukhin, A. A. Shcherbachenko


Abstract: We propose a variant of the Winternitz one-time signature scheme named $\mathsf{WOTS\text{-}BC}$. This scheme is based on the $\mathsf{XORP}$ construction with a lightweight block cipher, which is used as a compression transformation. We prove that the proposed construction is resistant to preimage attacks under standard assumptions about the cipher's properties, and demonstrate its insecurity against second preimage attacks (in the general case). We formulate and discuss the hypothesis that the hardness of the problem of searching/distinguishing the second preimage is not the necessary condition for the security of the Winternitz scheme. Finally, we evaluate the (non-)applicability of concrete attacks on the proposed transformation when using the Russian GOST 34.12-2018 “Magma” block cipher.

Keywords: WOTS, block cipher, Magma.

UDC: 519.7

DOI: 10.17223/2226308X/18/29