Answering queries without revealing secrets

Abstract

Question-answering systems must often keep certain information secret. This can be accomplished, for example, by sometimes refusing to answer a query. Here the danger of revealing a secret by refusing to answer a query is investigated. First several criteria that can be used to decide whether or not to answer a query are developed. Then it is shown which of these criteria are safe if the questioner knows nothing at all about what is kept secret. Furthermore, it is proved that one of these criteria is safe even if the user of the system knows which information is to be kept secret.