Efficient secure password protocols are constructed that remain secure against offline dictionary attacks even when a large, but bounded, part of the storage of a server responsible for password verification is retrieved by an adversary through a remote or local connection. A registration algorithm and a verification algorithm accomplish the goal of defeating a dictionary attack. A password protocol where a server, on input of a login and a password, carefully selects several locations from the password files, properly combines their content according to some special function, and stores the result of this function as a tag that can be associated with this password and used in a verification phase to verify access by users. Two main instantiations of our method are given; in one, a combination of mathematical tools, called dispersers and pairwise-independent hash functions is used to achieve security against adaptive intrusions (dispersers make sure that the password of each user depends on randomly chosen locations in a large password file, and pairwise-independent hash functions help in making this dependency sufficiently random); in a second one, a combination of mathematical tools, called k-wise independent hash functions and locally-computable and strong extractors (k-wise independent hash functions make sure that the locations chosen in the large password file from each password are sufficiently random, and locally-computable and strong extractors are used to combine the contents of these locations to generate a single long random value, which makes verification harder for the adversary to foil).