In this paper, firstly we propose two new concepts concerning the notion of key escrow encryption schemes: provable partiality and independency. Roughly speaking we say that a scheme has provable partiality if existing polynomial time algorithm for recovering the secret knowing escrowed information implies a polynomial time algorithm that can ... more >>>
The notion of an optimal acceptor for TAUT (the optimality
property is stated only for input strings from TAUT) comes from the line
of research aimed at resolving the question of whether optimal
propositional proof systems exist. In this paper we introduce two new
types of optimal acceptors, a D-N-optimal ...
more >>>
We prove a time hierarchy theorem for inverting functions
computable in polynomial time with one bit of advice.
In particular, we prove that if there is a strongly
one-way function, then for any k and for any polynomial p,
there is a function f computable in linear time
with one ...
more >>>