Paper 2016/1035

Improved Estimation of Collision Entropy in High and Low-Entropy Regimes and Applications to Anomaly Detection

Maciej Skorski

Abstract

We revisit the problem of estimating Renyi Entropy from samples, focusing on the important case of collision entropy. With $n$ samples we approximate the collision entropy of $X$ within an additive factor of $O\left( 2^{2\Delta}\log^{\frac{1}{2}}(1/\epsilon) \right)$ with probability $1-\epsilon$, where $\Delta$ is a known (a priori) upper bound on the difference between Renyi entropies of $X$ of order 2 and 3 respectively. In particular, we simplify and improve the previous result on estimating collision entropy due to Acharya et al. (SODA'15) up to a factor exponential in the entropy gap. We also discuss applications of our bound in anomaly analysis, namely (a) detection of attacks against stateless sources in TRNGs, and (b) detection of DDoS attacks at network firewalls.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Entropy EstimatorsCollision EntropyAnomaly Detection
Contact author(s)
mskorski @ ist ac at
History
2016-11-02: received
Short URL
https://ia.cr/2016/1035
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1035,
      author = {Maciej Skorski},
      title = {Improved Estimation of Collision Entropy in High and Low-Entropy Regimes and Applications to Anomaly Detection},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1035},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1035}},
      url = {https://eprint.iacr.org/2016/1035}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.