Timed protocols insecurity problem is NP-complete.
Massimo BenerecettiNicola CuomoAdriano PeronPublished in: HPCS (2010)
Keyphrases
- np complete
- np hard
- randomly generated
- petri net
- satisfiability problem
- pspace complete
- data complexity
- constraint satisfaction problems
- computational complexity
- cryptographic protocols
- communication protocols
- timed automata
- phase transition
- finite state machines
- conp complete
- polynomial time complexity
- lower bound
- communication protocol
- authentication protocol
- security protocols
- discrete event
- dynamic systems
- branch and bound algorithm
- np complete problems
- conjunctive queries
- smart card
- optimal policy
- voting protocols