Reference:

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.

Abstract:

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:

@inproceedings{BESS08,
    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}
}