This paper points out the privacy issue in the OCSP (Online Certificate Status Protocol), namely, the OCSP responder learns confidential information - who sends a message to whom. To preserve the privacy of the OCSP requester, this paper presents a cryptographic protocol for the authenticated dictionary, namely, an untrusted directory provides a verifiable answer to a membership query for a given element. In the protocol, a user is able to retrieve whether or not a target element belongs to a database that the directory has without revealing which element he/she wishes to know against the untrusted directory. The protocol requires linear exponentiations to the number of elements in the database, but achieves a constant size communication complexity between a user and a directory. The privacy of query is assured under the ?-hiding assumption introduced by Cachin.