We consider multivariate pseudo-linear functions over finite fields of characteristic two. A pseudo-linear polynomial is a sum of guarded linear-terms, where a guarded linear-term is a product of one or more linear-guards
and a single linear term, and each linear-guard is again a linear term but raised to the power $q$-1, where $q$ is the field size. Pseudo-linear
functions over GF($2^m$) are given by pseudo-linear polynomials defined over GF(2).
Let $f_1, f_2,...,f_k$ be $k$ pseudo-linear functions in $n$ variables, and let
$f$ be another pseudo-linear function in the $n$ variables. We show that if $f$ is a function of the given $k$ functions, then it must be a pseudo-linear function of the given $k$ functions. This generalizes the straightforward claim for just linear functions. We also prove a more general
theorem where the $k$ functions can in addition take further arguments, and prove that if $f$ can be represented as an iterated composition of these $k$ functions, then it can be represented as a probabilistic pseudo-linear iterated composition of these functions. Proceeding further, we generalize the theorem to randomized pseudo-linear functions. Additionally, we allow $f$ itself to be a randomized function,
i.e. we give a procedure for deciding if $f$ is a probabilistic sub-exponential
in $m$ time iterated function of the given $k$ randomized functions, and the decision procedure runs in computational time independent of $m$.
These theorems have implications for automatic proving of universally-composable security
theorems for ideal and real functionalities composed of if-then-else programs with
(uniform) random number generation and data objects
from additive group of GF($2^m$).
The theorems imply that, within this language framework, there is a decision procedure to find out if a real functionality realizes an ideal functionality, and this procedure is in computational time independent of $m$ (which is essentially the security parameter).
The paper now handles randomized functionalities, as well as randomized simulators.
We consider multivariate pseudo-linear functions
over finite fields of characteristic two. A pseudo-linear polynomial
is a sum of guarded linear-terms, where a guarded linear-term is a product of one or more linear-guards
and a single linear term, and each linear-guard is
again a linear term but raised to the power $2^m$-1, where $2^m$ is the field size. Pseudo-linear
functions over GF($2^m$) are given by pseudo-linear polynomials defined over GF2.
Let $f_1, f_2,...,f_k$ be $k$ pseudo-linear functions in $n$ variables, and let
$f$ be another pseudo-linear function in the $n$ variables. We show that if $f$ is a function of the
given $k$ functions, then it must be a pseudo-linear function of the given $k$ functions. This
generalizes the straightforward claim for just linear functions. We also prove a more general
theorem where the $k$ functions can in addition take further arguments, and prove that if
$f$ can be represented as an iterated composition of these $k$ functions, then it can be
represented as a probabilistic pseudo-linear iterated composition of these functions.
These theorems have implications for automatic proving of universally-composable security
theorems for ideal and real functionalities composed of if-then-else programs and data objects
from additive group of GF($2^m$). It follows that deciding if a simulator exists for such restricted
languages is in computational time independent of $m$.
This paper now appears in the Proceedings of ESORICS 2012 under the title "Decision Procedures for Simulatability".
