With the growth of model sizes and the scale of their deployment, their sheer size burdens the infrastructure requiring more network and more storage to accommodate these. While there is a vast model compression literature deleting parts of the model weights for faster inference, we investigate a more traditional type of compression - one that represents the model in a compact form and is coupled with a decompression algorithm that returns it to its original form and size - namely lossless compression. We present ZipNN, a lossless compression tailored to neural networks. Somewhat surprisingly, we show that specific lossless compression can gain significant network and storage reduction on popular models, often saving 33% and at times reducing over 50% of the model size. We investigate the source of model compressibility and introduce specialized compression variants tailored for models that further increase the effectiveness of compression. On popular models (e.g. Llama 3) ZipNN shows space savings that are over 17% better than vanilla compression while also improving compression and decompression speeds by 62%. Using multiple workers and threads, ZipNN can achieve decompression speeds of up to 80GB/s and compression speed of up to 13GB/s. We estimate that these methods could save over an ExaByte per year of network traffic downloaded from a large model hub like Hugging Face.

Hybrid cloud applications elastically burst to public clouds from an on-premise private cloud. In this setup only the public cloud directly charges applications for storing and processing data while the on-premise storage and network are already paid for and hence are considered free of charge. Consequently, application designers are naturally inclined to store and serve data remotely, while only paying for compute in the public cloud.

Modern applications span multiple clouds to reduce costs, avoid vendor lock-in, and leverage low-availability resources in another cloud. However, standard object stores operate within a single cloud, forcing users to manually manage data placement across clouds, i.e., navigate their diverse APIs and handle heterogeneous costs for network and storage. This is often a complex choice: users must either pay to store objects in a remote cloud, or pay to transfer them over the network based on application access patterns and cloud provider cost offerings. To address this, we present SkyStore, a unified object store that addresses cost-optimal data management across regions and clouds. SkyStore introduces a virtual object and bucket API to hide the complexity of interacting with multiple clouds. At its core, SkyStore has a novel TTL-based data placement policy that dynamically replicates and evicts objects according to application access patterns while optimizing for lower cost. Our evaluation shows that across various workloads, SkyStore reduces the overall cost by up to 6X over academic baselines and commercial alternatives like AWS multi-region buckets. SkyStore also has comparable latency, and its availability and fault tolerance are on par with standard cloud offerings.

Client side encryption is a setting in which storage I/O is encrypted at the client machine before being sent out to a storage system. This is typically done by adding an encryption layer before the storage client or driver. We identify that in cases where some of the storage functions are performed at the client, it is beneficial to also integrate the encryption into the storage client. We implemented such an encryption layer into Ceph RBD - a popular open source distributed storage system. We explain some the main benefits of this approach: The ability to do layered encryption with different encryption keys per layer, the ability to support more complex storage encryption, and finally we observe that by integrating the encryption with the storage client we managed to achieve a nice performance boost.

Disk encryption today uses standard encryption methods that are length preserving and do not require storing any additional information with an encrypted disk sector. This significantly simplifies disk encryption management as the disk mapping does not change with encryption. On the other hand, it forces the encryption to be deterministic when data is being overwritten and it disallows integrity mechanisms, thus lowering security guarantees. Moreover, because the most widely used standard encryption methods (like AES-XTS) work at small sub-blocks of no more than 32 bytes, deterministic overwrites form an even greater security risk. Overall, today's standard practice forfeits some security for ease of management and performance considerations. This shortcoming is further amplified in a virtual disk setting that supports versioning and snapshots so that overwritten data remains accessible.

This work tackles an inherent conflict between two important trends. The first is the integration of data compression capabilities into many storage systems supporting random I/O on the compressed data. The second is encrypting data at the host, before data is written to the storage, in order to address regulatory and enterprise requirements. This provides end-to-end protection for the data, but since the data arrives encrypted, it prevents the storage from compressing the data. Can compression savings be achieved together with host side encryption without changing the storage protocols or storage backend? In this paper we show that they can.

The adoption of deduplication in storage systems has introduced significant new challenges for storage management. Specifically, the physical capacities associated with volumes are no longer readily available. In this work, we introduce a new approach to analyzing capacities in deduplicated storage environments. We provide sketch-based estimations of fundamental capacity measures required for managing a storage system: How much physical space would be reclaimed if a volume or group of volumes were to be removed from a system (the reclaimable capacity) and how much of the physical space should be attributed to each of the volumes in the system (the attributed capacity). Our methods also support capacity queries for volume groups across multiple storage systems, e.g., how much capacity would a volume group consume after being migrated to another storage system? We provide analytical accuracy guarantees for our estimations as well as empirical evaluations. Our technology is integrated into a prominent all-flash storage array and exhibits high performance even for very large systems. We also demonstrate how this method opens the door for performing placement decisions at the data-center level and obtaining insights on deduplication in the field.

Cache replacement policies comprise one of the oldest and most researched topic in computer science. But recent advances in the fields of artificial intelligence and machine learning introduce novel insight and new opportunities which can benefit prefetching and cache replacement policies.

Summary form only given. In this work we identify a surprising effect by which searching for less repetitions in fast compressors can occasionally gain more compression (may reach up to a 30% improvement). Moreover, when executed on the correct data, restricting the repetition search manages to simultaneously improve both compression ratio and compression and decompression speeds. The rationale behind this phenomena is that for many highly compressible files, resources are "wasted" towards finding the short repetitions and this obscuresfinding longer repetitions. This can be remedied by restricting the attention solely to longer repetitions. Moreover, restricting attention to long repetitions has less interference with benefits of Huffman encoding, interfering only when long and beneficial repetitions are found. Following this observation we face the challenge of identifying the aforementioned data in order to deploy the restricted repetition search on it and doing so in an online manner. The problem is that while some data types can benefit greatly from the restricted search, others data types can suffer compression degradation from it. So being able to identify the data correctly is paramount to achieving an overall improvement. Moreover, since we are targeting high speed compressors, we are restricted to using only methods that are extremely fast and will not degrade the compression speeds for data that is unaffected by this method. Our solution is an adaptive algorithm that tunes the compression to the data at hand in order to reap the benefits on data types where restricted repetition exhibits gains. On other data types the compressor performs on par with the original fast compressor. We implemented our approach on two compressors: The worst is LZ4 [1] where nice improvements could be seen on a few selectfiles (some files showed a 20% improvement on compression ratio), but for the most part gains were limited to 5-7%. The second implementation was for RapidZlib [3] which is Deflate [2] compatible and also combines Huffman encoding on top of the repetition elimination process. The results here were by far better, exhibiting improvements upward of 20% on manyfiles and at times over 30%. We evaluated our adaptive RapidZlib solution on a large collection of data from various types and verified that it improves significantly on the potential files and does not add overheads or degrade on others.

We present a fast implementation of the Deflate protocol that is substantially faster than the fastest version of the Zlib software package, yet maintains full compatibility to the Deflate standard. Our solution outperforms the fastest Zlib version by a factor of 2.6 and higher (in compression time) yet demonstrates only a negligible drop-off in terms of compression ratio. The basic building blocks for our solution are a fast LZ77 compressor (the LZ4 package) and a standard Huffman encoding package (Zlib). In the paper we describe how a non-trivial combination constructed around these building blocks achieves the aforementioned performance and compatibility.

Sampling has long been a prominent tool in statistics and analytics, first and foremost when very large amounts of data are involved. In the realm of very large file systems (and hierarchical data stores in general), however, sampling has mostly been ignored and for several good reasons. Mainly, running sampling in such an environment introduces technical challenges that make the entire sampling process non-beneficial. In this work we demonstrate that there are cases for which sampling is very worthwhile in very large file systems. We address this topic in two aspect: (a) the technical side where we design and implement solutions to efficient weighted sampling that is also distributed, one-pass and addresses multiple efficiency aspects; and (b) the usability aspect in which we demonstrate several use-cases in which weighted sampling over large file systems is extremely beneficial. In particular, we show use-cases regarding estimation of compression ratios, testing and auditing and offline collection of statistics on very large data stores.

We study the problem of accurately estimating the data reduction ratio achieved by deduplication and compression on a specific data set. This turns out to be a challenging task - It has been shown both empirically and analytically that essentially all of the data at hand needs to be inspected in order to come up with a accurate estimation when deduplication is involved. Moreover, even when permitted to inspect all the data, there are challenges in devising an efficient, yet accurate, method. Efficiency in this case refers to the demanding CPU, memory and disk usage associated with deduplication and compression. Our study focuses on what can be done when scanning the entire data set. We present a novel two-phased framework for such estimations. Our techniques are provably accurate, yet run with very low memory requirements and avoid overheads associated with maintaining large deduplication tables. We give formal proofs of the correctness of our algorithm, compare it to existing techniques from the database and streaming literature and evaluate our technique on a number of real world workloads. For example, we estimate the data reduction ratio of a 7 TB data set with accuracy guarantees of at most a 1% relative error while using as little as 1 MB of RAM (and no additional disk access). In the interesting case of full-file deduplication, our framework readily accepts optimizations that allow estimation on a large data set without reading most of the actual data. For one of the workloads we used in this work we achieved accuracy guarantee of 2% relative error while reading only 27% of the data from disk. Our technique is practical, simple to implement, and useful for multiple scenarios, including estimating the number of disks to buy, choosing a deduplication technique, deciding whether to dedupe or not dedupe and conducting large-scale academic studies related to deduplication ratios.

Cloud storage systems are becoming increasingly popular. A promising technology that keeps their cost down is deduplication, which stores only a single copy of repeating data. Client-side deduplication attempts to identify deduplication opportunities already at the client and save the bandwidth of uploading copies of existing files to the server. In this work we identify attacks that exploit client-side deduplication, allowing an attacker to gain access to arbitrary-size files of other users based on a very small hash signatures of these files. More specifically, an attacker who knows the hash signature of a file can convince the storage service that it owns that file, hence the server lets the attacker download the entire file. (In parallel to our work, a subset of these attacks were recently introduced in the wild with respect to the Dropbox file synchronization service.) To overcome such attacks, we introduce the notion of proofs-of-ownership (PoWs), which lets a client efficiently prove to a server that that the client holds a file, rather than just some short information about it. We formalize the concept of proof-of-ownership, under rigorous security definitions, and rigorous efficiency requirements of Petabyte scale storage systems. We then present solutions based on Merkle trees and specific encodings, and analyze their security. We implemented one variant of the scheme. Our performance measurements indicate that the scheme incurs only a small overhead compared to naive client-side deduplication.

The emergence of cloud environments has made feasible the delivery of Internet-scale services by addressing a number of challenges such as live migration, fault tolerance and quality of service. However, current approaches do not tackle key issues related to cloud storage, which are of increasing importance given the enormous amount of data being produced in today's rich digital environment (e.g. by smart phones, social networks, sensors, user generated content). In this paper we present the architecture of a scalable and flexible cloud environment addressing the challenge of providing data-intensive storage cloud services through raising the abstraction level of storage, enabling data mobility across providers, allowing computational and content-centric access to storage and deploying new data-oriented mechanisms for QoS and security guarantees. We also demonstrate the added value and effectiveness of the proposed architecture through two real-life application scenarios from the healthcare and media domains.

We consider two of the most fundamental theorems in cryptography. The first, due to Håstad et al. [SIAM J. Comput., 28 (1999), pp. 1364–1396] is that pseudorandom generators can be constructed from any one-way function. The second, due to Yao [Proceedings of the $23$rd Annual Symposium on Foundations of Computer Science (FOCS), 1982, pp. 80–91], states that the existence of weak one-way functions implies the existence of full-fledged one-way functions. These powerful plausibility results shape our understanding of hardness and randomness in cryptography, but unfortunately their proofs are not as tight (i.e., security preserving) as one may desire. This work revisits a technique that we call the randomized iterate, introduced by Goldreich, Krawczyk, and Luby [SIAM J. Comput., 22 (1993), pp. 1163–1175]. This technique was used by Goldreich, Krawczyk, and Luby [SIAM J. Comput., 22 (1993), pp. 1163–1175] to give a construction of pseudorandom generators from regular one-way functions. We simplify and strengthen this technique in order to obtain a similar construction, where the seed length of the resulting generators is as short as $\Theta(n \log n)$ (rather than $\Theta(n^3)$ achieved by Goldreich, Krawczyk, and Luby [SIAM J. Comput., 22 (1993), pp. 1163–1175]). Our technique has the potential of implying seed length $\Theta(n)$, and the only bottleneck for such a result are the parameters of current generators against bounded-space computations. We give a construction with similar parameters for security amplification of regular one-way functions. This improves upon the construction of Goldreich et al. [Proceedings of the $31$st Annual Symposium on Foundations of Computer Science, (FOCS), 1990, pp. 318–326] in that the construction does not need to “know" the regularity parameter of the functions (in terms of security, the two reductions are incomparable). In addition, we use the randomized iterate to show a construction of a pseudorandom generator based on an exponentially hard one-way function that has a seed length of only $\Theta(n^2)$. This improves a recent result of Holenstein [Proceedings of the Theory of Cryptography, Third Theory of Cryptography Conference (TCC), 2006] that shows a construction with seed length $\Theta(n^5)$ based on such one-way functions. Finally, we show that the randomized iterate may even be useful in the general context of Håstad et al. [SIAM J. Comput., 28 (1999), pp. 1364–1396]. In particular, we use the randomized iterate to replace the basic building block of the Håstad et al. [SIAM J. Comput., 28 (1999), pp. 1364–1396] construction. Interestingly, this modification improves efficiency by an $\Theta(n^2)$ factor and reduces the seed length to $\Theta(n^7)$ (which also implies improvement in the security of the construction).

We study compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of $\mathcal{NP}$ decision problems. We consider $\mathcal{NP}$ problems that have long instances but relatively short witnesses. The question is whether one can efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness and polylog in the length of original input. Such compression enables succinctly storing instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. In this paper, we first develop the basic complexity theory of compression, including reducibility, completeness, and a stratification of $\mathcal{NP}$ with respect to compression. We then show that compressibility (say, of SAT) would have vast implications for cryptography, including constructions of one-way functions and collision resistant hash functions from any hard-on-average problem in $\mathcal{NP}$ and cryptanalysis of key agreement protocols in the “bounded storage model” when mixed with (time) complexity-based cryptography.

We consider large scale, distributed storage systems with a redundancy mechanism; cloud storage being a prime example. We investigate how such systems can reduce their power consumption during low-utilization time intervals by operating in a low-power mode. In a low power mode, a subset of the disks or nodes are powered down, yet we ask that each data item remains accessible in the system; this is called full coverage. The objective is to incorporate this option into an existing system rather than redesign the system. When doing so, it is crucial that the low power option should not affect the performance or other important characteristics of the system during full-power (normal) operation. This work is a comprehensive study of what can or cannot be achieved with respect to full coverage low power modes. The paper addresses this question for generic distributed storage systems (where the key component under investigation is the placement function of the system) as well as for specific popular system designs in the realm of storing data in the cloud. Our observations and techniques are instrumental for a wide spectrum of systems, ranging from distributed storage systems for the enterprise to cloud data services. In the cloud environment where low cost is imperative, the effects of such savings are magnified by the large scale.

We initiate the study of compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of NP decision problems. We consider NP problems that have long instances but relatively short witnesses. The question is, can one efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness rather than the length of original input. Such compression enables to succinctly store instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. We give a new classification of NP with respect to compression. This classification forms a stratification of NP that we call the VC hierarchy. The hierarchy is based on a new type of reduction called W-reduction and there are compression-complete problems for each class. Our motivation for studying this issue stems from the vast cryptographic implications compressibility has. For example, we say that SAT is compressible if there exists a polynomial p(middot, middot) so that given a formula consisting of m clauses over n variables it is possible to come up with an equivalent (w.r.t satisfiability) formula of size at most p(n, log m). Then given a compression algorithm for SAT we provide a construction of collision resistant hash functions from any one-way function. This task was shown to be impossible via black-box reductions (D. Simon, 1998), and indeed the construction presented is inherently non-black-box. Another application of SAT compressibility is a cryptanalytic result concerning the limitation of everlasting security in the bounded storage model when mixed with (time) complexity based cryptography. In addition, we study an approach to constructing an oblivious transfer protocol from any one-way function. This approach is based on compression for SAT that also has a property that we call witness retrievability. However, we mange to prove severe limitations on the ability to achieve witness retrievable compression of SAT

A Secure Function Evaluation (SFE) of a two-variable function f(·,·) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns "more than is necessary". A rich body of work deals with the study of completeness for secure two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols.The previous study of these questions was mainly conducted from an Information Theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computational row non-transitivity) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having SFE unconditionally.

We prove a lower bound of 2fl((~)~) onthemonotone size of an explicit function in monotone-Af:P (where n is the number of input variables).This is higher than any previous lower bound on the monotone size of a function.The previous best being a lower bound of about 2 ~('~¼) for Andreev's function, proved in [A1Bo87].Our lower bound is proved by the symmetric version of Razborov's method of approximations.However, we present this method in a new and simpler way: Rather than building approximator functions for all the gates in a circuit, we use a gate elimination argument that is based on a Monotone Switching Lemma.The bound applies for a family of functions, each defined by a construction of a small probability space of c-wise independent random variables.