Information Security Seminar 

13/07/2012, 15:00 — 16:00 — Room P4.35, Mathematics Building
André Souto, SQIG-IT

Individual Witness Hiding

In an interactive proof systems, there is a prover and a verifier and the goal of the prover is to convince the verifier of the validity of "$x\in L$'', for some language $L$. A natural question arises: "What knowledge does the verifier gain during the interaction?'' The definitions of zero knowledge and witness hiding are based on the existence of simulators or witness extractors. One might raise some questions about such "operational'' definitions. For instance, can there be protocols which actually leak no information to the verifier, but which are so obfuscating that there does not exist a simulator? Also, the existence of a simulator might be too weak to guarantee that no information is leaked to the verifier in any instances of the protocol. We propose a new approach based on Kolmogorov complexity, a rigorous measure of the amount of information contained in an object, usually a string. It is the difference between the Kolmogorov complexity of the witness when one does not see the conversation and one sees it. We explore some of its properties, design an IWHP for all languages in $fewp$. This is a joint work with Luís Antunes, Sophie Laplante, Paulo Mateus and Andreia Teixeira