Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing.
Zvika BrakerskiVadim LyubashevskyVinod VaikuntanathanDaniel WichsPublished in: IACR Cryptol. ePrint Arch. (2018)
Keyphrases
- worst case
- hash functions
- binary codes
- np hard
- average case
- upper bound
- greedy algorithm
- lower bound
- error bounds
- smart card
- source code
- running times
- worst case analysis
- hashing algorithm
- error correcting
- approximation algorithms
- nearest neighbor search
- smoothing methods
- video copy detection
- worst case scenario
- random projections
- learning theory
- similarity search
- np complete
- security protocols
- hash table
- order preserving
- space complexity
- phase transition