Description
Le problème NP-complet classique de la satisfiabilité d'une formule Booléenne mise sous forme normale conjonctive a connu un intérêt croissant non seulement dans la communauté d'informatique théorique, mais aussi dans des domaines d'applications divers ou une solution pratique à ce problème permet des avancées significatives. Depuis les premiers développements de la procédure de base proposée par Davis, Putnam, Logemann et Loveland (DPLL), il y a plus d'une quarantaine d'années, ce domaine a connu un effort de recherche croissant ayant abouti aux solveurs SAT modernes d'aujourd'hui, capable de résoudre des instances de plusieurs centaines de milliers et même de millions de variables. Dans cet exposé, nous examinerons les idées principales ayant permis ce passage à l'échelle et nous évoquerons quelques directions possibles pour des recherches futures.
Next sessions
-
Oblivious Transfer from Zero-Knowledge Proofs (or how to achieve round-optimal quantum Oblivious Transfer without structure)
Speaker : Léo Colisson - Université Grenoble Alpes
We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable oblivious transfer (OT) protocol (the protocol itself involving quantum interactions), mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions…) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely[…]-
Cryptography
-