The framework of algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized knowledge algorithms. We then characterize the information provided by a randomized knowledge algorithm when its answers have some probability of being incorrect. We formalize this information in terms of evidence; a randomized knowledge algorithm returning "Yes" to a query about a fact ~o provides evidence for qo being true. Finally, we discuss the extent to which this evidence can be used as a basis for decisions. Algorithmic knowledge is a very general approach. For example, Berman, Garay, and Perry [1989] implicitly use a particular form of algorithmic knowledge in their analysis of Byzantine agreement. Roughly speaking they allow agents to perform limited tests based on the information they have; agents know only what follows from these limited tests. Ramanujam [1999] investigates *a particular form of algorithmic knowledge, where the knowledge algorithm is essentially a modelchecking procedure for a standard logic of knowledge. More specifically, Ramanujam considers, at every state, the plm of the model that a particular agent sees (for instance, an agent in a distributed system may be aware only of its immediate neighbors, the ones with whom he can communicate) and takes as knowledge algorithm the model-checking procedure for epistemic logic, applied to the submodel generated by the visible states. Halpern and Pucella [2002] have applied algorithmic knowledge to security to capture intruders who are resource bounded (and thus, for example, cannot factor the products of large primes that arise in the RSA cryptosystem [Rivest, Shamir, and Adelman 1978] ). All these examples use sound knowledge algorithms: although the algorithm may not give an answer under all circumstances, when it says "Yes" on input qo, the agent really does know 79 in the standard possible-worlds sense. Although soundness is not required in the basic definition, it does seem to be useful in many applications. Our interest in this paper is knowledge algorithms that may use some randomization. As we shall see, there are numerous examples of natural randomized knowledge algorithms. With randomization, whether or not the knowledge algorithm says "Yes" may depend on the outcome of coin tosses. This poses a slight difficulty in even giving semantics to algorithmic knowledge, since the standard semantics makes sense only for deterministic algorithms. To deal with this problem, we make the algorithms deterministic by supplying them an extra argument (intuitively, the outcome of a sequence of coin tosses) to "derandomize" them. We show that this approach provides a natural extension of the deterministic case. To motivate t~he use of randomized knowledge algorithms, we consider a security example from Halpern and Pucclla [2002]. The framework in that paper lets us reason about principals communicating in the presence of adversaries, using cryptographic protocols. The typical assumption made when analyzing security protocols is that adversaries can intercept all the messages exchanged by the principals, but cannot necessarily decrypt encrypted messages unless they have the appropriate decryption key. To capture precisely the capabilities of adversaries, we use knowledge algorithms. Roughly speaking, a knowledge algorithm for an adversary will specify what information the adversary can extract from intercepted messages. In this paper, we consider an adversary that further attempts to guess the cryptographic keys used by the principals in the protocol. We show how to capture the knowledge of such an adversary using a randomized knowledge algorithm. Having defined the framework, we try to characterize the information obtained by getting a "Yes" answer to a query for ~o. If the knowledge algorithm is sound, then a "Yes" answer guarantees that 79 is true. However, the randomized algorithms of most interest to us give wrong answers with positive probability, so are not sound. Nevertheless, it certainly seems that if the probability that the algorithm gives the wrong answer is low, it provides very useful information when it says "Yes" to a query ~. This intuition appears in the randomized algorithms literature, where a "Yes" answer from a highly reliable randomized algorithm that is, one with a low probability of being wrong, is deemed "good enough". In what sense is this true? One contribution of our work is to provide a formal answer to that question. It may seem that a "Yes" answer to a query 79 from a highly reliable randomized knowledge algorithm should make the probability that 79 is true be high but, as we show, this is not necessarily true. Rather, the information should be viewed as evidence that 79 is true; the probability that 79 is true also depends in part on the prior probability of 79. Evidence has been widely studied in the literature on inductive logic [Kyburg 1 983]. Evidence for a particular hypothesis can be accumulated from different sources, and it is possible to combine
The goal of the authors of REF ) is "to understand what the evidence provided by a knowledge algorithm tells us.", which is quite a different than ours.
Probabilistic algorithmic knowledge
TARK '03
Computer Science