Paper 2026/2776
One-Way Functions and Local Descriptions of Random Data
Abstract
Sample compression describes a labeled sample by retained examples and extra information from which a decoder recovers the labels. We show that estimating the length of the shortest such description of random data is hard on average if and only if one-way functions exist. As in Hirahara and Nanashima's (FOCS 2023) consistent pointwise programs, the decoder labels each sample point separately, as a hypothesis does, but in our main result the labels are random rather than given by a concept. To label a point, it sees only that point, the retained examples with one extra bit each, a program, and a public random string revealed before the description is chosen. The length counts the choice of retained examples, their extra bits and the program, not the examples themselves. The task is to output a number between the $1/2$ and $3/4$ quantiles of the shortest length over the public string, up to an additive $a\lceil\log_2m\rceil$ for $m$ points and a fixed integer $a\ge0$. The main result takes polynomially many, at least $8n$, uniform $n$-bit points with independent uniform labels and any large enough polynomial time bound per query. If one-way functions exist, every efficient randomized algorithm fails to output such a number for all large $n$ with probability above an inverse polynomial that is the same for all algorithms and time bounds. Otherwise, for every inverse polynomial, some such algorithm fails with at most that probability for infinitely many $n$. For hardness, labels derived from one-way functions look random yet have short local descriptions, which random labels rarely have. The converse inverts a function that generates descriptions. One-way functions also exist if and only if estimating between the quantiles is hard, at some suitable time bound, for some PAC-style samplable data of the same sizes, labeled by a concept independent of the points.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- one-way functionsmeta-complexitysample compressionKolmogorov complexityaverage-case complexityPAC learning
- Contact author(s)
- dimyrisiotis @ gmail com
- History
- 2026-11-08: approved
- 2026-11-05: received
- See all versions
- Short URL
- https://ia.cr/2026/2776
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2776,
author = {Dimitrios Myrisiotis},
title = {One-Way Functions and Local Descriptions of Random Data},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2776},
year = {2026},
url = {https://eprint.iacr.org/2026/2776}
}