How to Prove that Minicrypt=Cryptomania (in the future)
or
Secret Sharing for Access Structures beyond P


These are the slides of a talk I gave at the Weizmann Institute in 2006 describing two approaches for showing that "minicrypt = cryptomania". The first is based on Rudich's approach via secret sharing for access structures in NP (e.g. Hamiltonicity: participants correspond to edges of the complete graph and a subset of the participants should be able to recover the secret if they contain a Hamiltonian cycle). The second is based on the work with Danny Harnik on compressibility. Major hurdles regarding the feasibility of the latter approach where shown since then; see Section and the papers by Fortnow and Santhanam and Dell and van Melkebeek.

Slides of the talk.

 

Related On-Line Papers: