### Eyal Kushilevitz

Department of Computer Science

Technion

Haifa, Israel

## Randomization Techniques for Secure Computation and Parallel Cryptography

#### Abstract

To what extent can we simplify computations if we settle for producing a randomized encoding of their output?

I will survey algebraic techniques for tackling this problem and discuss their applications to secure computation and to parallel cryptography. For example, I will show that under standard assumptions it is possible to carry out useful cryptographic operations (such as encryption) by functions in which every bit of the output depends on at most four bits of the input.

This mini-course is based on a sequence of joint works with Benny Applebaum and Yuval Ishai.

#### Course materials

- E. Kushilevitz. Randomization techniques for secure computation and parallel cryptography. Lecture slides [part1.pdf, part2.pdf, part3.pdf, part4.pdf, part5.pdf, part6.pdf].
- Y. Ishai, E. Kushilevitz. Randomizing polynomials: a new
representation with applications to round-efficient secure
computation. In
*Proc. of 41st IEEE Symp. on Foundations of Comput. Sci., FOCS 2000*, pp. 294-304. IEEE CS Press, 2000. - Y. Ishai, E. Kushilevitz. Perfect constant-round secure
computation via perfect randomizing polynomials. In P. Widmayer et
al., eds.,
*Proc. of 29 Int. Coll. on Automata, Languages and Programming, ICALP 2002*, v. 2380 of*Lect. Notes in Comput. Sci.*, pp. 244-256. Springer, 2002. - B. Applebaum, Y. Ishai, E. Kushilevitz. Computationally private
randomizing polynomials and their
applications.
*Comput. Complex.*, v. 15, n. 2, pp. 115-162, 2006. - B. Applebaum, Y. Ishai, E. Kushilevitz. Cryptography in
NC
^{0}.*SIAM J. of Comput.*, v. 36, n. 4, pp. 845-888, 2006. - B. Applebaum, Y. Ishai, E. Kushilevitz. On pseudorandom generators
with linear stretch in NC
^{0}. In J. Diaz et al., eds.,*Proc. of 9th Int. Wksh. on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006, and 10th Int. Wksh. on Randomization and Computation, RANDOM 2006*, v. 4110 of*Lect. Notes in Comput. Sci.*, pp. 260-271. Springer, 2006. - B. Applebaum, Y. Ishai, E. Kushilevitz. Cryptography with constant
input locality. In A. Menezes, ed.,
*Advances in Cryptology, CRYPTO 2007*, v. 4622 of*Lect. Notes in Comput. Sci.*, pp. 92-110. Springer, 2007.

Last changed **
March 12, 2008 23:55 EET**
by
local organizers, ewscs08(at)cs.ioc.ee

EWSCS'08 page:
//cs.ioc.ee/ewscs/2008/