Can I read Flat and one-variable clauses: Complexity of verifying cryptographic protocols with single blind copying on EtoBox?
Flat and one-variable clauses: Complexity of verifying cryptographic protocols with single blind copying by Helmut Seidl; Kumar Neeraj Verma is a Computer Science article available to read on EtoBox.
What is Flat and one-variable clauses: Complexity of verifying cryptographic protocols with single blind copying about?
Cryptographic protocols with single blind copying were defined and modeled by Comon and Cortier using the new class C of first-order clauses. They showed its satisfiability problem to be in 3-DEXPTIME. We improve this result by showing that satisfiability for this class is NEXPTIME-complete, using new resolution techniques. We show satisfiability to be DEXPTIME-complete if clauses are Horn, which is what is required for modeling cryptographic protocols. While translation to Horn clauses only gives a DEXPTIME upper bound for the secrecy problem for these protocols, we further show that this secrecy problem is actually DEXPTIME-complete.
Who reads Flat and one-variable clauses: Complexity of verifying cryptographic protocols with single blind copying?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Helmut Seidl; Kumar Neeraj Verma
- Publisher
- ACM
- Published
- 2008
- Language
- EN
- Field
- Computer Science (Physical Sciences)