Over the years DNS has proved to be an integral part of the internet infracstructure. For our purposes, DNS is simply a large scale distributed database that maps human-readable domain names to network recognizable IP addresses. Unfortunately, authenticity of responses was not integral to the initial DNS design. This lead to the possibility of a very practical forgery of responses as displayed by Kaminsky's cache poisoning attacks. DNSSEC is primarily designed as a security extension of DNS, that guarantees authenticity of DNS responses. To answer invalid queries in an authenticated manner, DNSSEC initially employed the NSEC records. To its credit, NSEC allowed nameservers to precompute signatures for such negative responses offline. As a result, NSEC is highly scalable while preserving the authenticity/correctness of responses. But, while doing so, NSEC leaks domains from nameserver's zone. This is called zone enumeration. To counter zone enumeration, NSEC3 was deployed. It is a hashed authenticated denial of existence of mechanism,i.e., it reveals the hashes of the zones in a domain. NSEC3 yet allows offline signatures, and is scalable like NSEC. Unfortunately, hashes are vulnerable to dictionary attacks a property exploited by conventional NSEC3 zone enumeration tool, e.g., nsec3walkertool. This leads us to investigate the possibility of constructing an authenticated denial of existence of mechanism which yet allows offline cryptography. To do so, we first define the security goals of a "secure" DNSSEC mechanism in terms of an Authenticated Database System (ADS) with additional goals of privacy, that we define. Any protocol that achieves these goals, maintains the integrity of DNSSEC responses and prevents zone enumeration. We then show that any protocol that achieves such security goals, can be used to construct weak signatures that prevent selective forgeries. This construction, though a strong indication, doesn't confirm the impossibility of generating proofs offline. To confirm that such proofs aren't possible offline, we show attacks of zone enumeration on two large classes of proofs. The provers/responders in this case either repeat proofs non-negligibly often or select proofs as subsets from a pre-computed set of proof elements. The attackers we present use a dictionary of all elements that are likely to occur in the database/zone. The attackers prune the said dictionary to obtain the set of all elements in the database (along with a few additional elements that are erroneously classified to be in the database). These attackers minimize the number of queries made to such responders and are loosely based on the paradigm of Probably Approximately Correct learning as introduced by Valiant.