부산대학교 도서관

Summary: ``Password-based authentication is a central tool for end-usersecurity. As part of this, password hashing is used to ensure thesecurity of passwords at rest. If quantum computers become available atsufficient size, they are able to significantly speed up thecomputation of preimages of hash functions. Using Grover's algorithm,at most, a square-root speedup can be achieved, and thus it is expectedthat quantum password guessing also admits a square-root speedup.However, password inputs are not uniformly distributed but highlybiased. Moreover, typical password attacks do not only compromise arandom user's password but address a large fraction of all users'passwords within a database of millions of users.\par ``In this work, we study those quantum large-scale password guessingattacks for the first time. In comparison to classical attacks, westill gain a square-root speedup in the quantum setting when attackinga constant fraction of all passwords, even considering strongly biasedpassword distributions as they appear in real-world password breaches.We verify the accuracy of our theoretical predictions using theLinkedIn leak and derive specific recommendations for password hashingand password security for a quantum computer era.''