there are no good constant-time data structures -- wingolog

Added on 2023-08-13
Page: https://wingolog.org/archives/2014/12/02/there-are-no-good-constant-time-data-structures
See on Internet Archive
#security #time-attack #structure

Imagine you have a web site that people can access via a password. No user name, just a password. There are a number of valid passwords for your service. Determining whether a password is in that set is security-sensitive: if a user has a valid password then they get access to some secret information; otherwise the site emits a 404. How do you determine whether a password is valid?