Search

Cloud storage attracts a lot of clients to join the paradise. For a high data availability, some clients require their files to be replicated and stored on multiple servers. Because clients are generally charged based on the redundancy level required by them, it is critical for clients to obtain convincing evidence that all replicas are stored correctly and are updated to the up-to-date version. In this paper, we propose a dynamic proof of data possession and replication (DPDPR) scheme, which is proved to be secure in the defined security model. Our scheme shares a single authenticated tree across multiple replicas, which reduces the tree's storage cost significantly. Our scheme allows for batch verification for multiple challenged leaves and can verify multiple replicas in a single batch way, which considerably save bandwidth and computation resources during audit process. We also evaluate the DPDPR's performance and compare it with the most related scheme. The evaluation results show that our scheme saves almost 66% tree's storage cost for three replicas, and obtains almost 60% and 80% efficiency improvements in terms of the overall bandwidth and computation costs, respectively, when three replicas are checked and each challenged with 460 blocks.

By introducing the BHT algorithm into the slide attack on 1K-AES and the related-key attack on PRINCE, we present the corresponding quantum attacks in this paper. In the proposed quantum attacks, we generalize the BHT algorithm to the situation where the number of marked items is unknown ahead of time. Moreover, we give an implementation scheme of classifier oracle based on Quantum Phase Estimation algorithm in presented quantum attacks. The complexity analysis shows that the query complexity, time complexity and memory complexity of the presented quantum attacks are all $\mathcal{O}(2^{n/3})$ when the success probability is about $63\%$, where $n$ is the block size. Compared with the corresponding classical attacks, the proposed quantum attacks can achieve subquadratic speed-up under the same success probability no matter on query complexity, time complexity or memory complexity. Furthermore, the query complexity of the proposed quantum slide attack on 1K-AES is less than Grover search on 1K-AES by a factor of $2^{n/6}.$ When compared with the Grover search on PRINCE, the query complexity of the presented quantum attack on PRINCE is reduced from $\mathcal{O}(2^{n})$ to $\mathcal{O}(2^{n/2}).$ When compared with the combination of Grover and Simon’s algorithms on PRINCE, the query complexity of our quantum attack on PRINCE is reduced from $\mathcal{O}(n\cdot 2^{n/2})$ to $\mathcal{O}(2^{n/2}).$ Besides, the proposed quantum slide attack on 1K-AES indicates that the quantum slide attack could also be applied on Substitution-Permutation Network construction, apart from the iterated Even-Mansour cipher and Feistel constructions.

Discriminative Canonical Correlation Analysis (DCCA) is a powerful supervised feature extraction technique for two sets of multivariate data, which has wide applications in pattern recognition. DCCA consists of two parts: (i) mean-centering that subtracts the sample mean from the sample; (ii) solving the generalized eigenvalue problem. The cost of DCCA is expensive when dealing with a large number of high-dimensional samples. To solve this problem, here we propose a quantum DCCA algorithm. Specifically, we devise an efficient method to compute the mean of all samples, then use block-Hamiltonian simulation and quantum phase estimation to solve the generalized eigenvalue problem. Our algorithm achieves a polynomial speedup in the dimension of samples under certain conditions over its classical counterpart.

Self-testing refers to a device-independent way to uniquely identify an unknown quantum device based only on the observed statistics. Earlier results on self-testing of multipartite state were restricted either to Dicke states or Graph states. In this paper, we propose self-testing schemes for a large family of symmetric three-qubit states, namely the superposition of $W$ state and $GHZ$ state. We first propose and analytically prove a self-testing criterion for the special symmetric state with equal coefficients of the canonical bases, by designing subsystem self-testing of partially and maximally entangled state simultaneously. Then we demonstrate for the general case, the states can be self-tested numerically by the swap method combining semidefinite programming (SDP) in high precision.

Most existing quantum private query (QPQ) protocols can hardly work in the presence of noise. The user Alice may obtain a false database item in noisy environments and both participants may cheat under the disguise of noise, so dealing with the noise needs an overall consideration of error correction, user privacy and database security. However, the only two existing protocols aiming to correct errors in QPQ lack such an overall consideration (at least one party’s privacy can be revealed), and they did not estimate what extent of errors can be tolerated (actually, noise is seldom discussed in quantum two-party secure computations, and to the best of our knowledge, relevant bounds on tolerable errors remain unattainable so far). To solve this problem, we first exemplify how one participant reveals the other party’s privacy in the existing QPQ protocols aiming to correct errors. Then we propose a practical protocol which can really work via noisy channel, that is, the error rate of the retrieved database item is reduced significantly and both parties’ privacy are well protected. Besides, we deduce that the final error rate, user privacy and database security are pairwise in a “trade-off” relationship. By balancing them according to the required level of security and reliability, we obtain an upper bound on tolerable errors.

The Android packing techniques were originally used to pack and conceal important information of the apps to prevent malicious developers from deconstructing the software logic. However, due to the lack of supervision, packing techniques have become the common methods for Android malwares to harden apps and circumvent virus detection engines in recent years. With obfuscation and encryption techniques, packing engines can alter the code structure of malwares and hide the malicious code to deceive and bypass the detection mechanisms, such as signature matching. For packing techniques, the packers are the agents created by packing engines and used to protect the softwares. Hence the packers pose a major challenge to the automated malware detection when researchers analyze a large collection of Android apps statically. It is necessary to identify packed samples in advance so that researchers can adopt different process procedures. To address this problem, we propose an intelligent AnDroid Packer Detection Framework called DroidPDF. It adopts a concise feature set that is resilient to obfuscation techniques. It also introduces weighted entropy to improve the detection effectiveness and achieves an average F1 Score of 0.9870.

International audience; Matrices with the displacement structures of circulant, Toeplitz, and Hankel types as well as matrices with structures generalizing these types are omnipresent in computations of sciences and engineering. In this paper we present efficient and memory-reduced quantum algorithms for solving linear systems with such structures by devising an approach to implement the block-encodings of these structured matrices. More specifically, by decomposing n×n dense matrices into linear combinations of displacement matrices, we first deduce the parametrized representations of the matrices with displacement structures so that they can be treated similarly. With such representations, we then construct ε-approximate block-encodings of these structured matrices in two different data access models, i.e., the black-box model and the quantum random access memory (QRAM) data structure model. It is shown the quantum linear system solvers based on the proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms in the black-box model and an exponential speedup in the QRAM data structure model. In particular, these linear system solvers subsume known results with significant improvements and also can motivate new instances where there was no specialized quantum algorithm before. As an application, one of the quantum linear system solvers is applied to the linear prediction of time series, which justifies the claimed quantum speedup is achievable for problems of practical interest.