We study the problem of supporting queries in overlay networks on a dynamic collection of networked hosts in which some fraction of the hosts may be malicious. We present novel hashing schemes that can be employed to limit the ability of adversarial nodes to carry out attacks. When used in conjunction with previous work, our scheme yields a distributed hash table that behaves near-optimally in the absence of malicious nodes and efficiently in the presence of malicious nodes. This talk is based on the joint work of Michael T. Goodrich, Michael J. Nelson, Jonathan Z. Sun, Roberto Tamassia, and Nikos Triandopoulos.