Asymptotic local revers of some random finite-state machine with a growing number of internal states

V. I. Vinokurov

Academy of Cryptography of Russian Federation

Abstract: We consider the sequence of random finite-state machine $\aleph_n(X,Q_n,Y,F_n,\Phi_n)$ with finite input $X$ and output $Y$ alphabets, a growing number $|Q_n|=n$ of internal states and functions of the output and state transition $f_{n,t}$, $\varphi_{n,t}$ in each clock cycle $t$ of the automaton selected randomly from the sets of functions $F_n$ and $\Phi_n$. The possibility of asymptotic local inversion of the automaton $\aleph_n$ is proved. Namely, the value $x_{n,t}$ of the input sequence $\{x_{n,t}\}_{t=1}^T$ of the automaton at the moment $t$ at $T,t,n\rightarrow\infty$ so that $\sqrt{n}=o(\min(t,T-t))$ with a probability of at least $1/3$ can be reconstructed from the known output sequence $\{y_{n,t}\}_{t=1}^T$ and the known sequences of functions $\{\varphi_{n,t}\}_{t=1}^T$ and $\{f_{n,t}\}_{t=1}^T$.

Keywords: finite state machine, Markov chain, stationary distribution, limit theorem, Rayleigh distribution, Poisson distribution, method of moments.

UDC: 519.713.6+519.217.2

Received: 13.02.2024

DOI: 10.4213/dm1901