×

Count-min sketches for estimating password frequency within Hamming distance two. (English) Zbl 1379.68109

Boyd, Colin (ed.) et al., Information security and privacy. 18th Australasian conference, ACISP 2013, Brisbane, Australia, July 1–3, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-39058-6/pbk). Lecture Notes in Computer Science 7959, 388-402 (2013).
Summary: The count-min sketch is a useful data structure for recording and estimating the frequency of string occurrences, such as passwords, in sub-linear space with high accuracy. However, it cannot be used to draw conclusions on groups of strings that are similar, for example close in Hamming distance. This paper introduces a variant of the count-min sketch which allows for estimating counts within a specified Hamming distance of the queried string. This variant can be used to prevent users from choosing popular passwords, like the original sketch, but it also allows for a more efficient method of analysing password statistics.
For the entire collection see [Zbl 1264.94003].

MSC:

68P05 Data structures
94A62 Authentication, digital signatures and secret sharing
PDFBibTeX XMLCite
Full Text: DOI Link