Modern cryptography offers an impressive virtual buffet to a consumer who is wealthy in resources, with powerful tools like fully homomorphic encryption (which allows a provider to compute with encrypted values while keeping the client's data safe) and general purpose obfuscation (which allows one to hide the purpose of a given computation). But for more modestly minded users, who seek to perform less lofty tasks using more affordable computing resources or under more time-tested assumptions, the offerings are comparatively paltry. Many fundamental and practically motivated questions remain unanswered, such as what are the lowest complexity classes (essentially, the weakest, and thus cheapest, computing models) containing basic cryptographic primitives? How much protection against adversarial intrusions can information-theoretic techniques provide for interactive protocols? Or, what levels of provable security are achievable within fixed efficiency constraints? This project will advance a theory of cryptography for the minimalist: a cryptography that is nimble enough to offer attractive value propositions to conservative consumers. The PIs will focus investigation on three main themes. First, the PIs will study complexity (e.g., several notions of circuit complexity) of pseudrandom primitives such as pseudorandom generators, pseudorandom functions, and weak pseudorandom functions. Secondly, the PIs will develop Information-theoretic techniques for robustness in adversarial environments, deepening connections between error-resilient communication and computation. Finally, the PIs will improve tradeoffs between security and efficiency in settings where overly stringent security requirements obstruct practicality, by studying incrementally relaxed notions of security and the gains in efficiency that they afford. The proposed research activity is tightly weaved with an educational and outreach plan for K-12, undergraduate, and graduate students, with an emphasis on encouraging participation of under-represented minorities. The PIs are involved in computer science programs for elementary school children and for high school girls, both being taught by undergraduate women in the department of Computer Science, who will be mentored by the PIs. The educational plan additionally includes integration with the undergraduate and graduate curriculum, through incorporation of the research into the introductory and advanced cryptography classes taught by the PIs, and through individual research projects and mentoring.
AF: Small: Minimalist cryptography