README.md

Random systems

This library holds the concrete objects and their laws: deterministic systems, automata and environments (System), distributions over deterministic systems (PDS), random systems given by their cumulative probabilities, with their presentations (Cumulative), deterministic converters and their compositions (DDC), probabilistic converters, programs, attachment and parallel composition (Converter), the transcript distance and distinguishers (Distance), games (Game), and typed systems on interfaces (Typed). It knows nothing of the classes of ConstructiveCryptography, whose instances on interfaces take their fields from here. Citations refer to the numbered references of THEORY.md.

Systems over finite alphabets, answering exactly on a bounded domain [1], [2, Chapter 2], [3, Chapter 3]. Laws are finitely supported distributions and $\delta$ is the statistical distance (Probability).

Deterministic systems

A deterministic system (DDS) is a partial function from input histories to the next output, $s : \mathcal X^{*} \rightharpoonup \mathcal Y$, silent at the empty history, whose domain is closed under nonempty prefixes. Systems are wired together, each output leaving the wiring or returning as an input. A system replies $y_1 \dots y_n$ to $x_1 \dots x_n$ when it answers each prefix with the next output, and a DDS is determined by its completed replies. An automaton is a transition function started in a state, and bisimilar automata have the same system. An environment (DDE) chooses the next query from the replies so far.

Probabilistic systems

A domain $\mathcal D$ admits next queries after each transcript, with a bound on the length. A PDS is a finite distribution over DDSs with domain $\mathcal D$ [1, Definition 8]. A random system is given by its cumulative probabilities $p$ on transcripts [1, after Lemma 5], normalized on the domain:

$$p(\varepsilon) = 1, \qquad p \ge 0, \qquad \sum_{y} p\big(h \cdot (x, y)\big) = \begin{cases} p(h) & \text{if } x \text{ is admitted after } h, \\ 0 & \text{otherwise.} \end{cases}$$

A PDS has a random system, and equivalent PDSs have the same one. Every random system has a finite presentation, so random systems are exactly the classes of equivalent PDSs. Two random systems are equal exactly when their transcript laws agree in every compatible environment, and on a domain of input histories fixed query sequences suffice [1, Lemma 5]. Random systems on one domain form mixtures, and two random systems run independently in parallel form one on the combined alphabets.

A probabilistic automaton answers a query from its state with a law on the next state and the reply, a probabilistic step; its random system follows the sub-law of the states reached with the replies of a transcript, whose weight is the probability of the transcript. On an input domain, two probabilistic automata have the same random system along a simulation, a kernel between their states through which their steps commute. A deterministic automaton with a random initial state is the probabilistic automaton of its point steps, and a probabilistic automaton is a deterministic automaton reading pre-sampled draws, sampled once with the initial state: a random automaton [4, Definition 2].

A random system is memoryless when the law of its reply depends only on the current query, never on the history: a source "can be memoryless or have memory" [3, Definition 3.1], and a single-input system given by a conditional distribution is a "discrete memoryless channel" [3, §3.6.1]. With the reply law $\nu$, its probabilities obey the chain rule

$$p\big(h \cdot (x, y)\big) = p(h)\, \nu_x(y) \qquad \text{for every query } x \text{ admitted after } h,$$

and a random system obeying it is the memoryless system. A probabilistic automaton whose step replies from every state with the same law $\nu$ is the memoryless system of this law. Two memoryless systems side by side are memoryless: a query to either system is answered with the reply law of that system.

Converters

A DDC is a system on the converter alphabets (outside queries and inside replies in; inside queries and outside replies out) with at most $b$ consecutive inside queries [3, Definition 3.8]. A DDC from $E$ to $F$ (IsDDCFrom) answers exactly the converter domain and queries only in $E$; attached to a system with domain $E$ it gives one with domain $F$. A PDC is a distribution over DDCs, and its behavior is a random system over the converter domain [3, Definitions 3.17–3.18].

Serial composition $\beta \odot \alpha$ connects the inside of $\beta$ to the outside of $\alpha$, and DDCs compose with the product of their bounds. PDC behaviors have a composition and an identity, with associativity and the left and right identity laws. Attachment samples the PDC, then attaches the sample deterministically: presentations attach to presentations, the identity leaves a system unchanged, and a composition attaches its inner converter first. Parallel composition samples two PDCs independently and runs them side by side, with interchange against serial composition.

A program is a deterministic oracle body: from its state, the outside query and the inside exchanges of the current invocation, it computes the reply or the next inside query. A program can be bounded (at most $b$ inside queries per invocation), have exact costs, or preserve a partial port map $\iota : O \to \mathrm{Option}\ J$: an invocation at $o$ queries the labels in the image of $\iota$ only at $\iota(o)$, at most once, and none of them when $\iota(o)$ is none, so it queries $\iota(o)$ at most as often as it is queried at $o$. On an outside domain, a bounded program is a DDC from every inside domain containing its inside queries. Attached to an automaton, a program is inlined [4, §3.3]: the result is the combined automaton on pairs of states, also on domains.

Run against a probabilistic automaton, a program is the probabilistic automaton on pairs of states whose step runs one invocation, the automaton answering the inside queries with fresh steps; it respects simulations. Attaching the program's converter to a probabilistic automaton is the program run against it, the combined system $C(F)$ of a system $C(\cdot)$ invoking $F$ [4, §3.3]; for point steps it is the combined automaton. Against memoryless replies of the laws $\nu$, a program replies memorylessly when its reply law $\kappa$, the law of one invocation whose inside queries are answered by fresh samples of $\nu$, is the same from every program state. So the composition law holds, whatever the number of the program's inside queries:

$$\alpha_P\, \mathrm{mem}(\nu) = \mathrm{mem}(\kappa).$$