TCS+ Online Seminar

Cryptographic Graded-Encoding Schemes: Recent Developments

Graded-encoding schemes are an extremely powerful tool in our crypto toolbox. Introduced two years ago by Garg, Gentry, and Halevi (as an approximation of multilinear maps), they ere used to realize such "impossible goals" as general-purpose obfuscation, functional encryption, witness encryption, and more. However so far we have very few candidate constructions of graded encoding schemes, all based on similar principles, and the security of these candidates is poorly understood.Recently, Cheon, Han, Lee, Ryu, and Stehle developed a powerful line of attacks on the existing candidate constructions (extending early attacks of Garg, Gentry, and Halevi), and showed how to break many of the hardness assumptions that were made about these schemes. These attacks were further developed by Gentry et al. and Coron et al., extending them to even wider settings and adapting them to defeat some attempted counter-measures.In this talk I will survey the existing constructions and attacks, and try to describe our current view of the security landscape for these constructions.