13^th Estonian Winter School in Computer Science (EWSCS)
XIII Eesti Arvutiteaduse Talvekool

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⁰. 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⁰. 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/