Rafail Ostrovsky - Publications

Cryptography with constant computational overhead.

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai


Current constructions of cryptographic primitives typically involve a large multiplicative computational overhead that grows with the desired level of security. We explore the possibility of implementing basic cryptographic primitives, such as encryption, authentication, signatures, and secure two-party computation, while incurring only a constant computational overhead compared to insecure implementations of the same tasks. Here we make the usual security requirement that the advantage of any polynomial-time attacker must be negligible in the input length. We obtain affirmative answers to this question for most central cryptographic primitives under plausible, albeit sometimes nonstandard, intractability assumptions.

comment: Preliminary version in STOC 2008: 433-442

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List