Abstract

Type-two constructions abound in cryptography: adversaries for encryption and authentication schemes, if active, are modeled as algorithms having access to oracles, i.e. as second-order algorithms. But how about making cryptographic schemes higher-order themselves? Moreover, how about seeing cryptographic reductions as higher-order functions? We give an answer to this question, by first describing why higher-order cryptography is interesting as an object of study, and then showing how the concept of probabilistic polynomial time algorithm can be generalised so as to encompass algorithms of order strictly higher than two. We then prove some positive and negative results about the existence of higher-order cryptographic primitives, namely authentication schemes and pseudorandom functions. The talk is based on some joint work with Boaz Barak and Raphaëlle Crubillé.


Last modified: Mon Oct 4 18:13:41 CEST 2021