Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 107

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 117
CiE 2008 - Regular Talk: - Succinct NP Proofs from an Extractability Assumption
Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Succinct NP Proofs from an Extractability Assumption

Edit abstract data

THIS TALK HAS BEEN CANCELLED!!!
Speaker: Helger Lipmaa
Author(s): Giovanni Di Crescenzo and Helger Lipmaa

Abstract

We prove, \emph{using a non-standard complexity assumption}, that any language
in $\NP$ has a \emph{1-round} (that is, the verifier sends a message to the
prover, and the prover sends a message to the verifier) argument system (that
is, a proof system where soundness holds against polynomial-time provers) with
communication complexity \emph{only polylogarithmic in the size of the $\NP$
instance}. We also show formal evidence that the nature of the non-standard
complexity assumption we use is 
analogous to previous assumptions proposed in the cryptographic literature. The
question of whether complexity assumptions of this nature can be considered
acceptable or not remains of independent interest in complexity-theoretic
cryptography as well as complexity theory.



websites: Arnold Beckmann
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie08/conf-code.php on line 136
2008-06-16 Valid HTML 4.01! Valid CSS!