Password file disclosures are a frequent problem for many companies, which makes their users the target of identify theft and similar attacks. This work provides a new general cryptographic technique to prevent an attacker from efficiently cracking individual passwords from a stolen password database. PolyPassHash employs a threshold cryptosystem to protect password hashes so that they cannot be verified unless a threshold of them are known. (This is conceptually similar to encrypting the passwords with a key that is only recoverable when a threshold of passwords are known.) Even if the password file and all other data on disk is obtained by a malicious party, the attacker cannot crack any individual password without simultaneously guessing a large number of them correctly. PolyPassHash is the first single server, software-only technique that increases the attacker's search space exponentially. The result is that even cracking small numbers of weak passwords is infeasible for an attacker. PolyPassHash achieves these properties with similar efficiency, storage, and memory requirements to existing salted hash schemes, performing tens of thousands of account authentications per second. When using the current best practice (of salting and hashing), cracking three passwords that are comprised of 6 random characters on a modern laptop would take under a hour. However, when protected with PolyPassHash, cracking these passwords when using every computer in existence would take longer than the estimated age of the universe.