Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - SDSIrep: A Reputation System based on SDSI


Ahmed Bouajjani, Javier Esparza, Stefan Schwoon, and Dejvuth Suwimonteerabuth. SDSIrep: A reputation system based on SDSI. In C.R. Ramakrishnan and Jakob Rehof, editors, Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), volume 4963 of Lecture Notes in Computer Science, pages 501–516, Budapest, Hungary, April 2008. Springer.


We introduce SDSIrep, a reputation system based on the SPKI/SDSI authorization system. It is well-known that a system of SPKI/SDSI certificates corresponds to the formal model of a pushdown system (PDS). Our system, SDSIrep, allows principals to express trust and recommendations in the form of so-called certificates with weights. By interpreting weights as probabilities, we obtain a random-walk model of the reputation of a principal. Thus, SDSIrep represents an application of the theory of probabilistic PDSs to the field of computer security. We present an algorithm to compute the reputation of each principal. An extension of SDSIrep also provides for so-called intersection certificates, by which, loosely speaking, a principal gains reputation if recommended by all members of a given group of principals. On a formal-methods level, this extension makes SDSIrep correspond to probabilistic alternating PDSs, and we extend the underlying theory of PDSs to handle this case. As an example we sketch a small academic reputation system that combines information from different reputation sources, like conferences, coauthors, and rankings.

Suggested BibTeX entry:

    address = {Budapest, Hungary},
    author = {Ahmed Bouajjani and Javier Esparza and Stefan Schwoon and Dejvuth Suwimonteerabuth},
    booktitle = {Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS)},
    editor = {C.R. Ramakrishnan and Jakob Rehof},
    month = {April},
    pages = {501--516},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{SDSIrep}: A Reputation System based on {SDSI}},
    volume = {4963},
    year = {2008}

GZipped PostScript (76 kB)