Probabilistic function

A probabilistic function/from a set X to a set 7 is a function from X to the set of probability spaces on Y. The reason is that the relation of a probabilistic function to a probabilistic algorithm should be the same as that of a usual function to a deterministic algorithm. Hence for every input i, the term/(i) denotes a probability space on Y. 

Alternatively, one can represent a probabilistic function as a deterministic function with an additional random input. Then one writes /(/, r), where r is chosen from a given probability space, and (i) is a random variable on the original space. Usually, r is uniformly distributed on a given set, such as the bit strings of a certain length, because it represents results of unbiased coin flips. ... 

The notation for probability spaces defined by successive assignments is particularly useful if the individual SjS are defined by probabilistic functions or algorithms One can write probabihties as... 

In cryptology, probabilistic algorithms are usually represented as deterministic Turing machines with an additional input tape, the so-called random tape. The random tape contains a (potentially infinite) sequence of random bits. Each bit on this tape is read exactly once. The content (or each finite subsequence) is supposed to be uniformly distributed. If A is a probabilistic algorithm, A(i) denotes the probability space on the outputs if A is run on input i (i.e., with i on the input tape — i does not include the content of the random tape). To cover non-terminating computations, the output space is augmented by an element t. The probabilistic function computed by A is not distinguished from A in the notation. 

A probabilistic interactive function is a probabilistic state-transition function, usually on a countable domain. Hence it is characterized by three sets /, O, and 5, the sets of possible inputs, outputs, and states, respectively, and a probabilistic function (see above) / 7 x 5 — O x 5. (In contrast to the field of non-cryptologic protocol specification, the functions themselves, and not finite descriptions of them, are used here. Anyway, they are mainly used to model the unknown behaviour of computationally unrestricted attackers.)... 

Definition 7.3 (Functional notation). The names of the algorithms in Definitions 7.1 and 7.2 can also be used for the (probabilistic or deterministic) functions realized by these algorithms. However, this notation is only used with test and verify. For the three other components, the following probabilistic functions are defined ... 

The resulting protocol and the probabilistic function it defines are called Gen. Thus Gen defines probabilistic assignments of the form acc, idsjfj h g f, pk, sk) <— Gen ipar). 

As mentioned in Section 4.4.1, Related Work in Cryptology , multi-party protocols have almost exclusively been considered for the evaluation of (probabilistic) functions. The informal definition of a multi-party protocol that securely evaluates a function/on n inputs, jcj,. .., x , which are assumed to be contributed by n different users, is that the protocol has exactly the same effect for all users, honest and dishonest, as an evaluation by a trasted host would have. Such a trusted host would receive each input x,- secretly from the i-th user, apply/, and output y. =f(x, . .., x ) to everybody (or, if/is probabilistic, a value y distributed... 

Variants exist where each user obtains a different output y,- secretly from the trusted host. If probabilistic functions are considered, the results may be correlated, i.e., there is a global probabilistic function F that maps n-tuples (xj,. .., x ) to w-tuples (yj,..., y , and the i-th user obtains y,- as a result. 

To apply a multi-party function evaluation protocol to key generation, which is an interactive protocol, it is usefiil to regard Gen as one probabilistic function. This has implicitly been done all the time Gen maps values par to tuples acc, idspi h- f, pk, sk temp). Hence a trusted host performing the entire key generation, i.e.. A, B, and res, will be simulated. The correctness of initialization implies that acc and idsout always TRUE and 1), respectively, in this case. Hence one can omit them. The trusted host would tell the signer s entity both sk and pk, and the other entities obtain pk only. 

The main restriction, in conventional terms, is that a probabilistic function sign and a deterministic non-interactive function test exist, where each signature is supposed to pass the test of several other participants, called testers. In the classification of Chapter 5, this can be justified for several classes of schemes, e.g. ... 

LE Baum. An inequality and associated maximization technique in statistical estimation for probabilistic functions of a Markov process. Inequalities 3 1-8, 1972. 

To derive this submatrix, vhich collects structural and electronic features responsible for activity, the flexibility of molecules is taken into account by choosing some tolerance limits for variation of diagonal (Ai) and off-diagonal (A2 for bonded atoms and A3 for nonbonded atoms) elements. Then, to decide vhich features are responsible for activity, two probabilistic functions are used ... 

Baum, L. E., Pertie, T., Soules, G. Weiss, N. (1970). A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. Ann Math Stat 41(1), 164—171. 

In fact the threshold of corrosion should be considered to be a probabilistic function rather than a fixed number. Figure 3.5(a) shows the cumulative probability of corrosion vs. the chloride concentration on a UK bridge (Vassie, 1987). However, when differentiated (3.5b), it can be seen that there are thresholds at 3%, 6% and 1.2% chloride by mass of cement. One possible reason is discussed in the next section. 

Baum LE, Petrie T (1966) Statistical inference for probabilistic functions of finite state Markov chains... 

Artificial realization of the system behavior (35). This method is commonly applied to complex particulate processes, which are described in some detail here. In the artificial realization, the direct evaluation of integral and differential functions is replaced by the simulation of the stochastic behavior modeled by using a randomness generator to vary the behavior of the system (20). The important probabilistic functions in the original model equations, such as coalescence kernels for granulation processes, are still essential in Monte Carlo simulations and are shown later. 

---