Recently, Oblivious Storage has been proposed to prevent privacy leakage from user access patterns, which obfuscates and makes it computationally indistinguishable from the random sequences by fake accesses and probabilistic encryption. The same data exhibits distinct ciphertexts. Thus, it seriously impedes cloud providers’ efforts to improve storage utilization to remove user redundancy, which has been widely used in the existing cloud storage scenario. Inspired by the successful adoption of removing duplicate data in cloud storage, we attempt to integrate obliviousness, remove redundancy, and propose a practical oblivious storage, PEO-Store. Instead of fake accesses, introducing delegates breaks the mapping link between a valid access pattern and a specific client. The cloud interacts only with randomly authorized delegates. This design leverages non-interactive zero-knowledge-based redundancy detection, discrete logarithm problem-based key sharing, and secure time-based delivery proof. These components collectively protect access pattern privacy, accurately eliminate redundancy, and prove the data delivery among delegates and the cloud. Theoretical proof demonstrates that, in our design, the probability of identifying the valid access pattern with a specific client is negligible. Experimental results show that PEO-Store outperforms state-of-the-art methods, achieving an average throughput of up to 3 times faster and saving 74% of storage space.

In this paper, we aim to construct a class of complete permutations$\mathcal F$over$\mathbb F_{q}^{n}$from some polynomials$f_{1},f_{2},\ldots,f_{n}$over$\mathbb F_{q}$. First of all, we determine a necessary and sufficient condition such that$\mathcal F$is complete. Briefly, we transform the completeness of$\mathcal F$into showing the permutation properties of two polynomials over$\mathbb F_{q}$obtained from these$f_{i}$’s. Then, following the wide applications, we investigate the constructions of linear complete permutations over$\mathbb F_{2}^{n}$based on the rotations andXORs. The following two cases are considered: the first one is to use some different circularly left shift transforms$f_{i}$’s and the second one is to assume$f_{i}$’s are of the form$b_{i}f$with a fixed$f$and different$b_{i}$’s in$\mathbb F_{q}$. In both cases, we show that the completeness of the permutation is closely related to the ranks of some matrices with particular forms, which can be determined by the cycle decomposition of the permutation over the$n$branches. Besides, we present several explicit linear complete permutations which might be used in the design as well as the provable security of cryptographic schemes.

Hash combiners are a practical way to make cryptographic hash functions more tolerant to future attacks and compatible with existing infrastructure. A combiner combines two or more hash functions in a way that is hopefully more secure than each of the underlying hash functions, or at least remains secure as long as one of them is secure. Two classical hash combiners are the exclusive-or (XOR) combiner \( \mathcal {H}_1(M) \oplus \mathcal {H}_2(M) \) and the concatenation combiner \( \mathcal {H}_1(M) \Vert \mathcal {H}_2(M) \) . Both of them process the same message using the two underlying hash functions in parallel. Apart from parallel combiners, there are also cascade constructions sequentially calling the underlying hash functions to process the message repeatedly, such as Hash-Twice \(\mathcal {H}_2(\mathcal {H}_1(IV, M), M)\) and the Zipper hash \(\mathcal {H}_2(\mathcal {H}_1(IV, M), \overleftarrow{M})\) , where \(\overleftarrow{M}\) is the reverse of the message M . In this work, we study the security of these hash combiners by devising the best-known generic attacks. The results show that the security of most of the combiners is not as high as commonly believed. We summarize our attacks and their computational complexities (ignoring the polynomial factors) as follows: Several generic preimage attacks on the XOR combiner: A first attack with a best-case complexity of \( 2^{5n/6} \) obtained for messages of length \( 2^{n/3} \) . It relies on a novel technical tool named interchange structure. It is applicable for combiners whose underlying hash functions follow the Merkle–Damgård construction or the HAIFA framework. A second attack with a best-case complexity of \( 2^{2n/3} \) obtained for messages of length \( 2^{n/2} \) . It exploits properties of functional graphs of random mappings. It achieves a significant improvement over the first attack but is only applicable when the underlying hash functions use the Merkle–Damgård construction. An improvement upon the second attack with a best-case complexity of \( 2^{5n/8} \) obtained for messages of length \( 2^{5n/8} \) . It further exploits properties of functional graphs of random mappings and uses longer messages. These attacks show a rather surprising result: regarding preimage resistance, the sum of two n -bit narrow-pipe hash functions following the considered constructions can never provide n -bit security. A generic second-preimage attack on the concatenation combiner of two Merkle–Damgård hash functions. This attack finds second preimages faster than \( 2^n \) for challenges longer than \( 2^{2n/7} \) and has a best-case complexity of \( 2^{3n/4} \) obtained for challenges of length \( 2^{3n/4} \) . It also exploits properties of functional graphs of random mappings. The first generic second-preimage attack on the Zipper hash with underlying hash functions following the Merkle–Damgård construction. The best-case complexity is \( 2^{3n/5} \) , obtained for challenge messages of length \( 2^{2n/5} \) . An improved generic second-preimage attack on Hash-Twice with underlying hash functions following the Merkle–Damgård construction. The best-case complexity is \( 2^{13n/22} \) , obtained for challenge messages of length \( 2^{13n/22} \) . The last three attacks show that regarding second-preimage resistance, the concatenation and cascade of two n -bit narrow-pipe Merkle–Damgård hash functions do not provide much more security than that can be provided by a single n -bit hash function. Our main technical contributions include the following: The interchange structure, which enables simultaneously controlling the behaviours of two hash computations sharing the same input. The simultaneous expandable message, which is a set of messages of length covering a whole appropriate range and being multi-collision for both of the underlying hash functions. New ways to exploit the properties of functional graphs of random mappings generated by fixing the message block input to the underlying compression functions.