Cryptography with constant computational overhead
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.