Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR05-078 | 25th May 2005
Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz

A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme

Revisions: 1

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 >>>


TR05-077 | 15th July 2005
Zenon Sadowski

On a D-N-optimal acceptor for TAUT

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 >>>


TR05-076 | 2nd July 2005
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

Time hierarchies for cryptographic function inversion with advice

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 >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint