Revision #1 Authors: Charanjit Jutla, Arnab Roy

Accepted on: 4th November 2010 23:21

Downloads: 3518

Keywords:

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.

TR10-092 Authors: Charanjit Jutla, Arnab Roy

Publication: 2nd June 2010 18:31

Downloads: 3642

Keywords:

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".