Cryptographic Compression

Joshua Cooper and Grant Fickes Atombeam Technologies · 2025

Read Cryptographic Compression by Joshua Cooper and Grant Fickes Atombeam Technologies (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16184.txt.

Introduction

Joshua Cooper and Grant Fickes present in 2025 a method called ENCORE that squeezes and locks data in one pass. Both tasks reshape data so the output looks close to random bits. The authors argue the two tasks can share one process for data that follows a stable pattern.

The method first reshapes data toward a form whose code is near random. The changes made are then stored in a second stream woven into the first with a user key. Tests show a form of next-bit safety while using far less random input than standard locks. The paper ends with open questions and room to make the claims stronger.

Catalog record

CREATORJoshua Cooper and Grant Fickes Atombeam Technologies
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16184

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cryptographic Compression Joshua Cooper and Grant Fickes Atombeam Technologies Abstract We introduce a protocol called ENCORE which simultaneously compresses and encrypts data in a one-pass process that can be implemented efficiently and possesses a number of desirable features as a streaming encoder/decoder. Motivated by the observation that both lossless compression and encryption consist of performing an invertible transformation whose output is close to a uniform distribution over bit streams, we show that these can be done simultaneously, at least for “typical” data with a stable distribution, i.e., approximated reasonably well by the output of a Markov model. The strategy is to transform the data into a dyadic distribution whose Huffman encoding is close to uniform, and then store the transformations made to said data in a compressed secondary stream interwoven into the first with a user-defined encryption protocol. The result is an encoding which we show exhibits a modified version of Yao’s “next-bit test” while requiring many fewer bits of entropy than standard encryption. Numerous open questions remain, particularly regarding results that we suspect can be strengthened considerably. 1 Introduction Lossless compression and encryption share a goal: transforming strings reversibly and efficiently into an approximately uniformly random string. Encryption seeks this end because there is no information that can be extracted from a uniform sequence, so the user’s plaintext remains private; compression seeks this end because only sequences whose distribution is uniform cannot be further compressed, so the user’s data is maximally shortened. Naturally, the measures of success are different between these two perspectives. Nonetheless, here we show that, at least for typical-looking streaming data – that sampled from a Markov chain – it is possible to achieve both types of benefit simultaneously, with a protocol we term ENCORE: ENcryption and COmpression REconciled. The use of Markov models as a proxy for “typicality” is a standard going back at least to Shannon’s foundational 1948 paper [ 4 ] . We describe the ENCORE protocol in the next section. Broadly, the strategy is comprised of two components. First, the underlying distribution of data is transformed into a distribution that is dyadic , i.e., wherein each probability is a negative power of 2 . As we show below in Section 3 , data which is sampled iid from a dyadic distribution gives rise to a Huffman encoding which is a pure uniform bit stream, i.e., it is indistinguishable from a sequence of iid fair coin tosses. (It has been previously observed that Huffman coding provides a semblance of encryption; see, for example, [ 2 ] .) We then show that data generated by a Markov model and then transformed in a particular manner has this property asymptotically, i.e., following a burn-in period whose length is governed by the mixing time of the model, bits of the Huffman encoded data are exponentially close to a fair coin toss – even when conditioned on the entire past of the stream. The second component of the protocol provides the “reconstruction” information to invert the transformations in order to recover the original data. We want to ensure that few bits are used to perform the transformations – as true random samples are notoriously costly. We also aim to minimize the damage done by additional reconstruction data to the abridgement provided by Huffman coding. Therefore, transformations are chosen to occur infrequently – in practice, a greedy approach works well – and the resulting sequence of modifications is compressed in a manner designed to take advantage of this sparseness. This compressed transformation data can then be encrypted with any cryptographic scheme. One might use two channels, if available, to send the encoded-transformed stream and the transformation-reconstruction stream. However, for the purpose of self-containment of the protocol, we introduce in Section 4 a way to interleave the two streams into one which we prove avoids exposing information about the original data. Finally, in Section 5 , we present a number of open questions about the protocol – in particular, we conjecture that a number of the properties we prove it exhibits can be strengthened. 2 The ENCORE Algorithm Here we present the ENCORE (ENcrpytion and COmpression REconciled) algorithm whose cryptographic properties are formally considered in the sequel. We denote by \Omega the set of states (typically, words of a fixed length over a finite alphabet generated by an ergodic Markov model) and write \sigma for the stationary distribution of these states. The distribution \sigma is used to generate a Huffman encoding, C , of \Omega . The encoding given by C defines another “implied” distribution on \Omega , called \pi , where for each \omega\in\Omega , \pi(\omega):=2^{-|C(\omega)|} , where C(\omega) denotes the codeword assigned to \omega by C and |\omega^{\prime}| is the length of the word \omega^{\prime} in bits. States of \Omega can be partitioned by the relation between \sigma(\omega) and \pi(\omega) as follows. Let \mathcal{O}:=\{\omega\in\Omega:\sigma(\omega)\geq\pi(\omega)\} be the collection of overrepresented (including perfectly represented) states, and let \mathcal{U}:=\{\omega\in\Omega:\sigma(\omega)<\pi(\omega)\} be the underrepresented states. From here, we define a nonnegative matrix B=\{b_{\omega\omega^{\prime}}\}_{\omega,\omega^{\prime}\in\Omega} of \Omega\mapsto\Omega “transformation probabilities” with the properties that: 1. B is row-stochastic: For all \omega\in\Omega , \sum_{\omega^{\prime}\in\Omega}b_{\omega\omega^{\prime}}=1 . 2. If \Omega is sampled according to \sigma and then the elements are mapped to \Omega according to the transformation probabilities B , the result is \pi : For all \omega\in\Omega , \sum_{\omega^{\prime}\in\Omega}\sigma(\omega^{\prime})b_{\omega\omega^{\prime}}=\pi(\omega) . 3. Underrepresented states only transform to themselves: for \omega\in\mathcal{U} , b_{\omega\omega}=1 . 4. Overrepresented states only transform to (themselves and) underrepresented states: for \omega\in\mathcal{O} , b_{\omega\omega^{\prime}}>0 implies \omega^{\prime}\in\mathcal{U}\cup\{\omega\} . To see that it is always possible to define such a B , note that the following satisfies the above properties (where the third case can be ignored if \mathcal{U}=\emptyset , i.e., \sigma is already dyadic and \pi\equiv\sigma ): b_{\omega\omega^{\prime}}=\begin{cases}1&\text{if $\omega=\omega^{\prime}\in\mathcal{U}$}\\ \pi(\omega)/\sigma(\omega)&\text{if $\omega=\omega^{\prime}\in\mathcal{O}$}\\ \displaystyle\left(1-\frac{\pi(\omega)}{\sigma(\omega)}\right)\frac{\pi(\omega^{\prime})-\sigma(\omega^{\prime})}{\sum_{\alpha\in U}\pi(\alpha)-\sigma(\alpha)}&\text{if $\omega\in\mathcal{O}$ and $\omega^{\prime}\in\mathcal{U}$}\\ 0&\text{otherwise.}\end{cases} In practice, it is preferable for row \omega of B to represent a probability distribution with small support whenever possible, so often we allocate the probabilities \pi(\omega^{\prime})-\sigma(\omega^{\prime}) , \omega^{\prime}\in\mathcal{U} , greedily to states \omega\in\mathcal{O} to saturate the probabilities 1-\pi(\omega)/\sigma(\omega) of nontrivial transformation instead of proportionally across all elements of \mathcal{U} . This choice does not impact the analysis below, but may offer some advantages in computational efficiency and minimal use of additional entropy. (See Section 5 for more explanation.) As we show below (see Proposition 3.7 ), Huffman encoding of \pi – which we refer to as the “encoded-transformed data” stream – approaches a uniform distribution over bit streams exponentially quickly, and (see Section 4 ) the data required to reconstruct \omega from \omega^{\prime} is very limited. This data can therefore be compressed effectively (in a manner that exploits its sparsity) and then encrypted by any mechanism. The result of said compression and encryption we will refer to as the “transformation-reconstruction data” stream. Thus, by carefully interleaving the two resulting types of information, we can attain one stream which is simultaneously shorter on average than the original source stream sampled from \sigma and passes a modified next-bit test (q.v. [ 5 ] ) that says nearby bits cannot be predicted with substantial accuracy, even given all previous data. Overall, the process described herein uses significantly less computational power and bits of entropy (to feed the encryption of transformation data)

Read the complete text