Collaborative Research: SaTC: CORE: Medium: Making Crypto Too BIG To Break

This project aims to build new cryptosystems with strong security guarantees, by making the secret keys and/or communication large. The unifying technique is to overwhelm the adversary with information to ensure that it cannot store enough of it to break the scheme, even given significantly more resources than the honest users. The project's novelties are new cryptosystems where: (1) security holds even if an adversary compromises the machine storing the secret key and exfiltrates large amounts of data, (2) security does not rely on any unproven mathematical assumptions, but instead just requires either a large key, or large amounts of communication between the honest participants.

The project's impacts are: (a) the design of more secure systems in the real world, (b) synergizing, unifying and abstracting techniques from many diverse areas of computer science, and (c) mentoring undergraduates, graduate students and postdocs with an emphasis on fostering diversity.

The design of cryptographic schemes and protocols traditionally strives to make secret keys and communication as small as possible. In this project, the investigators argue that there are several important settings where it is possible to dramatically improve security by making secret keys and/or communication large, while still allowing the resulting scheme to be quite practical.

The project focuses on three such settings. The first setting considers an adversary who breaks a cryptographic scheme by outright stealing the corresponding secret key. A promising approach to mitigate against such attacks is to make cryptographic keys intentionally huge, to prevent an adversary from exfiltrating them in their entirety.

This project suggests novel research directions towards bringing such schemes closer to reality. The second setting studies cryptosystems with Information-theoretic (IT) security, that are provably secure even against attackers with unlimited computational power. While such cryptosystems are known to require a large key, the project studies how to make them practical by ensuring that they are stateless and read only small portions of their large keys at every use.

The third setting studies IT-secure protocols, where the protocol communication is made intentionally large, so that it becomes infeasible for the attacker to store it all. The honest participants process the communication in a streaming manner using much less storage than the adversary.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.