Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing.
Zvika BrakerskiVadim LyubashevskyVinod VaikuntanathanDaniel WichsPublished in: EUROCRYPT (3) (2019)
Keyphrases
- worst case
- hash functions
- binary codes
- upper bound
- average case
- np hard
- greedy algorithm
- approximation algorithms
- lower bound
- order preserving
- error bounds
- smart card
- hashing algorithm
- source code
- computational complexity
- file organization
- random projections
- smoothing algorithm
- np complete
- running times
- nearest neighbor search
- error correcting
- gray code
- space complexity
- denoising
- encryption scheme
- special case
- hash table
- information theoretic