Source author record

Vladimir Anashin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Cryptography and Security math.DS Formal Languages and Automata Theory Information Theory Logic in Computer Science math-ph math.IT math.MP math.NT

Catalog footprint

Research overview

10works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Quantization causes waves:Smooth finitely computable functions are affine

Given an automaton (a letter-to-letter transducer, a dynamical 1-Lipschitz system on the space $\mathbb Z_p$ of $p$ -adic integers) $\mathfrak A$ whose input and output alphabets are $\mathbb F_p=\{0,1,\ldots,p-1\}$ , one visualizes word transformations performed by $\mathfrak A$ by a point set $\mathbf P(\mathfrak A)$ in real plane $\mathbb R^2$ . For a finite-state automaton $\mathfrak A$ , it is shown that once some points of $\mathbf P(\mathfrak A)$ constitute a smooth (of a class $C^2$ ) curve in $\mathbb R^2$ , the curve is a segment of a straight line with a rational slope; and there are only finitely many straight lines whose segments are in $\mathbf{P}(\mathfrak A)$ . Moreover, when identifying $\mathbf P(\mathfrak A)$ with a subset of a 2-dimensional torus $\mathbb T^2\subset\mathbb R^3$ (under a natural mapping of the real unit square $[0,1]^2$ onto $\mathbb T^2$ ) the smooth curves from $\mathbf P(\mathfrak A)$ constitute a collection of torus windings. In cylindrical coordinates either of the windings can be ascribed to a complex-valued function $ψ(x)=e^{i(Ax-2πB(t))}$ $(x\in\mathbb R)$ for suitable rational $A,B(t)$ . Since $ψ(x)$ is a standard expression for a matter wave in quantum theory (where $B(t)=tB(t_0)$ ), and since transducers can be regarded as a mathematical formalization for causal discrete systems, the paper might serve as a mathematical reasoning why wave phenomena are inherent in quantum systems: This is because of causality principle and the discreteness of matter.

preprint2012arXiv

Ergodicity criteria for non-expanding transformations of 2-adic spheres

In the paper, we obtain necessary and sufficient conditions for ergodicity (with respect to the normalized Haar measure) of discrete dynamical systems $<f;\mathbf S_{2^{-r}}(a)>$ on 2-adic spheres $\mathbf S_{2^{-r}}(a)$ of radius $2^{-r}$ , $r\ge 1$ , centered at some point $a$ from the ultrametric space of 2-adic integers $\mathbb Z_2$ . The map $f\colon\mathbb Z_2\to\mathbb Z_2$ is assumed to be non-expanding and measure-preserving; that is, $f$ satisfies a Lipschitz condition with a constant 1 with respect to the 2-adic metric, and $f$ preserves a natural probability measure on $\mathbb Z_2$ , the Haar measure $μ_2$ on $\mathbb Z_2$ which is normalized so that $μ_2(\mathbb Z_2)=1$ .

preprint2012arXiv

T-functions revisited: New criteria for bijectivity/transitivity

The paper presents new criteria for bijectivity/transitivity of T-functions and fast knapsack-like algorithm of evaluation of a T-function. Our approach is based on non-Archimedean ergodic theory: Both the criteria and algorithm use van der Put series to represent 1-Lipschitz $p$ -adic functions and to study measure-preservation/ergodicity of these.

preprint2012arXiv

The Non-Archimedean Theory of Discrete Systems

In the paper, we study behavior of discrete dynamical systems (automata) w.r.t. transitivity; that is, speaking loosely, we consider how diverse may be behavior of the system w.r.t. variety of word transformations performed by the system: We call a system completely transitive if, given arbitrary pair $a,b$ of finite words that have equal lengths, the system $\mathfrak A$ , while evolution during (discrete) time, at a certain moment transforms $a$ into $b$ . To every system $\mathfrak A$ , we put into a correspondence a family $\mathcal F_{\mathfrak A}$ of continuous maps of a suitable non-Archimedean metric space and show that the system is completely transitive if and only if the family $\mathcal F_{\mathfrak A}$ is ergodic w.r.t. the Haar measure; then we find easy-to-verify conditions the system must satisfy to be completely transitive. The theory can be applied to analyze behavior of straight-line computer programs (in particular, pseudo-random number generators that are used in cryptography and simulations) since basic CPU instructions (both numerical and logical) can be considered as continuous maps of a (non-Archimedean) metric space $\mathbb Z_2$ of 2-adic integers.

preprint2011arXiv

Automata finiteness criterion in terms of van der Put series of automata functions

In the paper we develop the $p$ -adic theory of discrete automata. Every automaton $\mathfrak A$ (transducer) whose input/output alphabets consist of $p$ symbols can be associated to a continuous (in fact, 1-Lipschitz) map from $p$ -adic integers to $p$ integers, the automaton function $f_\mathfrak A$ . The $p$ -adic theory (in particular, the $p$ -adic ergodic theory) turned out to be very efficient in a study of properties of automata expressed via properties of automata functions. In the paper we prove a criterion for finiteness of the number of states of automaton in terms of van der Put series of the automaton function. The criterion displays connections between $p$ -adic analysis and the theory of automata sequences.

preprint2011arXiv

Linear Relation on General Ergodic T-Function

We find linear (as well as quadratic) relations in a very large class of T-functions. The relations may be used in analysis of T-function-based stream ciphers.

preprint2007arXiv

Non-Archimedean Ergodic Theory and Pseudorandom Generators

The paper develops techniques in order to construct computer programs, pseudorandom number generators (PRNG), that produce uniformly distributed sequences. The paper exploits an approach that treats standard processor instructions (arithmetic and bitwise logical ones) as continuous functions on the space of 2-adic integers. Within this approach, a PRNG is considered as a dynamical system and is studied by means of the non-Archimedean ergodic theory.

preprint2006arXiv

Wreath Products in Stream Cipher Design

The paper develops a novel approach to stream cipher design: Both the state update function and the output function of the corresponding pseudorandom generators are compositions of arithmetic and bitwise logical operations, which are standard instructions of modern microprocessors. Moreover, both the state update function and the output function are being modified dynamically during the encryption. Also, these compositions could be keyed, so the only information available to an attacker is that these functions belong to some exponentially large class. The paper shows that under rather loose conditions the output sequence is uniformly distributed, achieves maximum period length and has high linear complexity and high $\ell$ -error linear complexity. Ciphers of this kind are flexible: One could choose a suitable combination of instructions to obtain due performance without affecting the quality of the output sequence. Finally, some evidence is given that a key recovery problem for (reasonably designed) stream ciphers of this kind is intractable up to plausible conjectures.

preprint2004arXiv

Pseudorandom number generation by $p$ -adic ergodic transformations

The paper study counter-dependent pseudorandom generators; the latter are generators such that their state transition function (and output function) is being modified dynamically while working: For such a generator the recurrence sequence of states satisfies a congruence $x_{i+1}\equiv f_i(x_i)\pmod{2^n}$ , while its output sequence is of the form $z_{i}=F_i(u_i)$ . The paper introduces techniques and constructions that enable one to compose generators that output uniformly distributed sequences of a maximum period length and with high linear and 2-adic spans. The corresponding stream chipher is provably strong against a known plaintext attack (up to a plausible conjecture). Both state transition function and output function could be key-dependent, so the only information available to a cryptanalyst is that these functions belong to some (exponentially large) class. These functions are compositions of standard machine instructions (such as addition, multiplication, bitwise logical operations, etc.) The compositions should satisfy rather loose conditions; so the corresponding generators are flexible enough and could be easily implemented as computer programs.

preprint2004arXiv

Pseudorandom number generation by p-adic ergodic transformations: an addendum

The paper study counter-dependent pseudorandom number generators based on $m$ -variate ( $m>1$ ) ergodic mappings of the space of 2-adic integers $\Z_2$ . The sequence of internal states of these generators is defined by the recurrence law $\mathbf x_{i+1}= H^B_i(\mathbf x_i)\bmod{2^n}$ , whereas their output sequence is %while its output sequence is of the $\mathbf z_{i}=F^B_i(\mathbf x_i)\mod 2^n$ ; here $\mathbf x_j, \mathbf z_j$ are $m$ -dimensional vectors over $\Z_2$ . It is shown how the results obtained for a univariate case could be extended to a multivariate case.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Vladimir Anashin

Research overview

Is this your work?

10 publications

Quantization causes waves:Smooth finitely computable functions are affine

Ergodicity criteria for non-expanding transformations of 2-adic spheres

T-functions revisited: New criteria for bijectivity/transitivity

The Non-Archimedean Theory of Discrete Systems

Automata finiteness criterion in terms of van der Put series of automata functions

Linear Relation on General Ergodic T-Function

Non-Archimedean Ergodic Theory and Pseudorandom Generators

Wreath Products in Stream Cipher Design

Pseudorandom number generation by $p$ -adic ergodic transformations

Pseudorandom number generation by p-adic ergodic transformations: an addendum

See the researcher in context

Building this map preview

Vladimir Anashin

Research overview

Is this your work?

10 publications

Quantization causes waves:Smooth finitely computable functions are affine

Ergodicity criteria for non-expanding transformations of 2-adic spheres

T-functions revisited: New criteria for bijectivity/transitivity

The Non-Archimedean Theory of Discrete Systems

Automata finiteness criterion in terms of van der Put series of automata functions

Linear Relation on General Ergodic T-Function

Non-Archimedean Ergodic Theory and Pseudorandom Generators

Wreath Products in Stream Cipher Design

Pseudorandom number generation by ppp-adic ergodic transformations

Pseudorandom number generation by p-adic ergodic transformations: an addendum

See the researcher in context

Building this map preview

Pseudorandom number generation by $p$ -adic ergodic transformations