A new distribution-sensitive secure sketch and popularity-proportional hashing

Joanne Woodage, Rahul Chatterjee, Yevgeniy Dodis, Ari Juels, Thomas Ristenpart

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Motivated by typo correction in password authentication, we investigate cryptographic error-correction of secrets in settings where the distribution of secrets is a priori (approximately) known. We refer to this as the distribution-sensitive setting. We design a new secure sketch called the layer-hiding hash (LHH) that offers the best security to date. Roughly speaking, we show that LHH saves an additional log H0(W) bits of entropy compared to the recent layered sketch construction due to Fuller, Reyzin, and Smith (FRS). Here H0(W) is the size of the support of the distribution W. When supports are large, as with passwords, our new construction offers a substantial security improvement. We provide two new constructions of typo-tolerant password-based authentication schemes. The first combines a LHH or FRS sketch with a standard slow-to-compute hash function, and the second avoids secure sketches entirely, correcting typos instead by checking all nearby passwords. Unlike the previous such brute-force-checking construction, due to Chatterjee et al., our new construction uses a hash function whose run-time is proportional to the popularity of the password (forcing a longer hashing time on more popular, lower entropy passwords). We refer to this as popularity-proportional hashing (PPH). We then introduce a framework for comparing different typo-tolerant authentication approaches. We show that PPH always offers a better time/security trade-off than the LHH and FRS constructions, and for certain distributions outperforms the Chatterjee et al. construction. Elsewhere, this latter construction offers the best trade-off. In aggregate our results suggest that the best known secure sketches are still inferior to simpler brute-force based approaches.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings
EditorsJonathan Katz, Hovav Shacham
PublisherSpringer Verlag
Pages682-710
Number of pages29
ISBN (Print)9783319636962
DOIs
StatePublished - 2017
Event37th Annual International Cryptology Conference, CRYPTO 2017 - Santa Barbara, United States
Duration: Aug 20 2017Aug 24 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10403 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other37th Annual International Cryptology Conference, CRYPTO 2017
CountryUnited States
CitySanta Barbara
Period8/20/178/24/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A new distribution-sensitive secure sketch and popularity-proportional hashing'. Together they form a unique fingerprint.

  • Cite this

    Woodage, J., Chatterjee, R., Dodis, Y., Juels, A., & Ristenpart, T. (2017). A new distribution-sensitive secure sketch and popularity-proportional hashing. In J. Katz, & H. Shacham (Eds.), Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings (pp. 682-710). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10403 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-63697-9_23