engleski

Computational complexity of collaborative systems with nonce creation

In this thesis we consider existing models for collaborative systems with confidentiality policies. We extend these systems with nonce creation. We also consider a restriction that each instance of an action is used at most once in a process. Administrative processes usually involve such progressing behavior, that is, whenever a transaction is performed, it does not need to be repeated. We investigate the complexity of the decision problem whether there exists a sequence of transitions from an initial state to a final state that avoids any critical states, e.g., states which conflict with the given confidentiality policies. Collaborative systems allow modeling of the protocols and the relevant security problems. We model systems with limited resources to allow a new view on the standard Dolev-Yao intruder, namely, an intruder with bounded memory. The power of such an intruder is analyzed.

multiset rewriting ; collaborative systems ; confidentiality ; nonce ; complexity ; linear logic ; protocol security ; Dolev-Yao intruder

naslov na hrvatskom jeziku: Složenost u sustavima suradnje koji mogu generirati nove vrijednosti