Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-092 | 4th November 2010 23:21

A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security

RSS-Feed




Revision #1
Authors: Charanjit Jutla, Arnab Roy
Accepted on: 4th November 2010 23:21
Downloads: 1794
Keywords: 


Abstract:

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



Changes to previous version:

The paper now handles randomized functionalities, as well as randomized simulators.


Paper:

TR10-092 | 22nd May 2010 21:34

A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security





TR10-092
Authors: Charanjit Jutla, Arnab Roy
Publication: 2nd June 2010 18:31
Downloads: 1710
Keywords: 


Abstract:

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


Comment(s):

Comment #1 to TR10-092 | 11th July 2012 11:30

Cross Reference

Authors: Charanjit Jutla
Accepted on: 11th July 2012 11:30
Keywords: 


Comment:

This paper now appears in the Proceedings of ESORICS 2012 under the title "Decision Procedures for Simulatability".




ISSN 1433-8092 | Imprint