Abstract:
In 2024, at the NSUCRYPTO Olympiad the problem of representing any post-quantum signature algorithm using a “succinct” Mealy finite-state machine was proposed. Most post-quantum signature schemes hash a message before signing it (the “Hash-and-Sign” paradigm). We show that any hash function satisfying reasonable requirements for its security cannot be represented by a Mealy finite-state machine, if we require some natural succintness of representation property. We call a family of Mealy automata/DFA $\{A_n \}$ compact if the number of states in $A_n$ grows polynomially in $n$. We show that for any function $\mathsf{H}_n$ it is easy to find a collision in each of the following cases: (1) if the family of languages $L_n = \{ (\omega \,\|\, \mathsf{H}_n(\omega)) : \omega \in \{0,1\}^{*} \}$ can be recognized by a compact DFA family; (2) if $\mathsf{H}_n(\omega)$ can be computed via compact Mealy Machine; (3) if the compression function $g_n$ used in Merkle — Damgard construction can be computed via compact Mealy Machine. Thus, Hash-and-Sign schemes most likely cannot be implemented using relatively simple and succinct computational models.
Fulltext:
PDF file (524 kB)