Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Charanjit Jutla:

TR18-149 | 25th August 2018
Craig Gentry, Charanjit Jutla

Obfuscation using Tensor Products

We describe obfuscation schemes for matrix-product branching programs that are purely algebraic and employ matrix algebra and tensor algebra over a finite field. In contrast to the obfuscation schemes of Garg et al (SICOM 2016) which were based on multilinear maps, these schemes do not use noisy encodings. We prove ... more >>>

TR12-093 | 1st July 2012
Charanjit Jutla, Vijay Kumar, Atri Rudra

On the Circuit Complexity of Composite Galois Field Transformations

We study the circuit complexity of linear transformations between Galois fields GF(2^{mn}) and their isomorphic composite fields GF((2^{m})^n). For such a transformation, we show a lower bound of \Omega(mn) on the number of gates required in any circuit consisting of constant-fan-in XOR gates, except for a class of transformations between ... more >>>

TR10-092 | 22nd May 2010
Charanjit Jutla, Arnab Roy

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

Revisions: 1 , Comments: 1

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

TR09-120 | 18th November 2009
Charanjit Jutla

Almost Optimal Bounds for Direct Product Threshold Theorem

Revisions: 2

We consider weakly-verifiable puzzles which are challenge-response puzzles such that the responder may not
be able to verify for itself whether it answered the challenge correctly. We consider $k$-wise direct product of
such puzzles, where now the responder has to solve $k$ puzzles chosen independently in parallel.
Canetti et ... more >>>

TR06-121 | 14th September 2006
Charanjit Jutla

A Simple Biased Distribution for Dinur's Construction

ISSN 1433-8092 | Imprint