Search

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.

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.

Mean Centering (MC) is an important data preprocessing technique, which has a wide range of applications in data mining, machine learning, and multivariate statistical analysis. When the data set is large, this process will be time-consuming. In this paper, we propose an efficient quantum MC algorithm based on the block-encoding technique, which enables the existing quantum algorithms can get rid of the assumption that the original data set has been classically mean-centered. Specifically, we first adopt the strategy that MC can be achieved by multiplying by the centering matrix $C$, i.e., removing the row means, column means and row-column means of the original data matrix $X$ can be expressed as $XC$, $CX$ and $CXC$, respectively. This allows many classical problems involving MC, such as Principal Component Analysis (PCA), to directly solve the matrix algebra problems related to $XC$, $CX$ or $CXC$. Next, we can employ the block-encoding technique to realize MC. To achieve it, we first show how to construct the block-encoding of the centering matrix $C$, and then further obtain the block-encodings of $XC$, $CX$ and $CXC$. Finally, we describe one by one how to apply our MC algorithm to PCA and other algorithms.

International audience; The Poisson equation has wide applications in many areas of science and engineering. Although there are some quantum algorithms that can efficiently solve the Poisson equation, they generally require a fault-tolerant quantum computer, which is beyond the current technology. We propose a variational quantum algorithm (VQA) to solve the Poisson equation, which can be executed on noisy intermediate-scale quantum devices. In detail, we first adopt the finite-difference method to transform the Poisson equation into a linear system. Then, according to the special structure of the linear system, we find an explicit tensor product decomposition, with only (2log2n+1) items, of its coefficient matrix under a specific set of simple operators, where n is the dimension of the coefficient matrix. This implies that the proposed VQA needs fewer quantum measurements, which dramatically reduces the required quantum resources. Additionally, we design observables to efficiently evaluate the expectation values of the simple operators on a quantum computer. Numerical experiments demonstrate that our algorithm can solve the Poisson equation.

With the advent of data outsourcing, how to efficiently verify the integrity of data stored at an untrusted cloud service provider (CSP) has become a significant problem in cloud storage. Provable data possession (PDP) is a model that allows clients or a trusted auditor to verify whether CSP possesses the outsourced data without downloading it. However, this model requires clients to tolerate non-negligible computation burden incurred by frequent verifications in private schemes, and does not provide any security assurances when client or/and auditor are dishonest. Therefore, it cannot be directly transformed into a secure outsourced auditing scheme, where any one of three participants (i.e., CSP, client and auditor) may be dishonest and any two participants may be colluded with each other. In this paper, we propose an outsourced dynamic provable data possession (ODPDP) scheme, which migrates frequent auditing task to an external auditor to reduce clients’ verification overhead, and simultaneously provides log audit mechanism with lower computation burden for clients to prevent from dishonest auditor. In addition, we propose a batch update algorithm that can perform and verify multiple update operations at once, avoiding repetitive calculations and transmissions. Security analysis proves that our scheme is secure in the enhanced threat model, and experimental results show that our scheme achieves high efficiency in terms of computation time and communication cost compared with existing outsourced auditing schemes.

Dimensionality reduction (DR) algorithms, which reduce the dimensionality of a given data set while preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan \emph{et al}. proposed a quantum version of the A-optimal projection algorithm (AOP) for dimensionality reduction [Phys. Rev. A 99, 032311 (2019)] and claimed that the algorithm has exponential speedups on the dimensionality of the original feature space $n$ and the dimensionality of the reduced feature space $k$ over the classical algorithm. In this paper, we correct the time complexity of Duan \emph{et al}.'s algorithm to $O(\frac{\kappa^{4s}\sqrt{k^s}} {\epsilon^{s}}\mathrm{polylog}^s (\frac{mn}{\epsilon}))$, where $\kappa$ is the condition number of a matrix that related to the original data set, $s$ is the number of iterations, $m$ is the number of data points and $\epsilon$ is the desired precision of the output state. Since the time complexity has an exponential dependence on $s$, the quantum algorithm can only be beneficial for high dimensional problems with a small number of iterations $s$. To get a further speedup, we propose an improved quantum AOP algorithm with time complexity $O(\frac{s \kappa^6 \sqrt{k}}{\epsilon}\mathrm{polylog}(\frac{nm}{\epsilon}) + \frac{s^2 \kappa^4}{\epsilon}\mathrm{polylog}(\frac{\kappa k}{\epsilon}))$ and space complexity $O(\log_2(nk/\epsilon)+s)$. With space complexity slightly worse, our algorithm achieves at least a polynomial speedup compared to Duan \emph{et al}.'s algorithm. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when both $\kappa$, $k$ and $1/\epsilon$ are $O(\mathrm{polylog}(nm))$., Comment: 11 pages, 2 figures

The challenge posed by the many-body problem in quantum physics originates from the difficulty of describing the nontrivial correlations encoded in the many-body wave functions with high complexity. Quantum neural network provides a powerful tool to represent the large-scale wave function, which has aroused widespread concerns in the quantum superiority era. A significant open problem is what exactly the representational power boundary of the single-layer quantum neural network is. In this paper, we design a 2-local Hamiltonian and then give a kind of Quantum Restricted Boltzmann Machine (QRBM, i.e. single-layer quantum neural network) based on it. The proposed QRBM has the following two salient features. (1) It is proved universal for implementing quantum computation tasks. (2) It can be efficiently implemented on the Noisy Intermediate-Scale Quantum (NISQ) devices. We successfully utilize the proposed QRBM to compute the wave functions for the notable cases of physical interest including the ground state as well as the Gibbs state (thermal state) of molecules on the superconducting quantum chip. The experimental results illustrate the proposed QRBM can compute the above wave functions with an acceptable error.

For a high level of data availability and reliability, a common strategy for cloud service providers is to rely on replication, i.e. storing several replicas onto different servers. To provide cloud users with a strong guarantee that all replicas required by them are actually stored, many multi-replica integrity auditing schemes were proposed. However, most existing solutions are not resource economical since users need to create and upload replicas of their files by themselves. A multi-replica solution called Mirror is presented to overcome the problems, but we find that it is vulnerable to storage saving attack, by which a dishonest provider can considerably save storage costs compared to the costs of storing all the replicas honestly—while still can pass any challenge successfully. In addition, we also find that Mirror is easily subject to substitution attack and forgery attack, which pose new security risks for cloud users. To address the problems, we propose some simple yet effective countermeasures and an improved proofs of retrievability and replication scheme, which can resist the aforesaid attacks and maintain the advantages of Mirror, such as economical bandwidth and efficient verification. Experimental results show that our scheme exhibits comparable performance with Mirror while achieving high security.

Recently, a new type of protocol named Round-robin differential-phase-shift quantum key distribution (RRDPS QKD) was proposed, where the security can be guaranteed without monitoring conventional signal disturbances. The active decoy state method can be used in this protocol to overcome the imperfections of the source. But, it may lead to side channel attacks and break the security of QKD systems. In this paper, we apply the passive decoy state method to the RRDPS QKD protocol. Not only can the more environment disturbance be tolerated, but in addition it can overcome side channel attacks on the sources. Importantly, we derive a new key generation rate formula for our RRDPS protocol using passive decoy states and enhance the key generation rate. We also compare the performance of our RRDPS QKD to that using the active decoy state method and the original RRDPS QKD without any decoy states. From numerical simulations, the performance improvement of the RRDPS QKD by our new method can be seen.

As we know, unextendible product basis (UPB) is an incomplete basis whose members cannot be perfectly distinguished by local operations and classical communication. However, very little is known about those incomplete and locally indistinguishable product bases that are not UPBs. In this paper, we first construct a series of orthogonal product bases that are completable but not locally distinguishable in a general m ⊗ n (m ≥ 3 and n ≥ 3) quantum system. In particular, we give so far the smallest number of locally indistinguishable states of a completable orthogonal product basis in arbitrary quantum systems. Furthermore, we construct a series of small and locally indistinguishable orthogonal product bases in m ⊗ n (m ≥ 3 and n ≥ 3). All the results lead to a better understanding of the structures of locally indistinguishable product bases in arbitrary bipartite quantum system.

It is known that there are many sets of orthogonal product states which cannot be distinguished perfectly by local operations and classical communication (LOCC). However, these discussions have left the following open question: What entanglement resources are necessary and/or sufficient for this task to be possible with LOCC? In m ⊗ n, certain classes of unextendible product bases (UPB) which can be distinguished perfectly using entanglement as a resource, had been presented in 2008. In this paper, we present protocols which use entanglement more efficiently than teleportation to distinguish some classes of orthogonal product states in m ⊗ n, which are not UPB. For the open question, our results offer rather general insight into why entanglement is useful for such tasks and present a better understanding of the relationship between entanglement and nonlocality.

Constructed from Bai-Xu-Wang-class monogamy relations, multipartite entanglement indicators can detect the entanglement not stored in pairs of the focus particle and the other subset of particles. We investigate the k-partite entanglement indicators related to the αth power of entanglement of formation (αEoF) for k ≤ n, αϵ"Equation missing" and n-qubit symmetric states. We then show that (1) The indicator based on αEoF is a monotonically increasing function of k. (2) When n is large enough, the indicator based on αEoF is a monotonically decreasing function of α and then the n-partite indicator based on "Equation missing" works best. However, the indicator based on 2 EoF works better when n is small enough.

In the general bipartite quantum system $m\ensuremath{\bigotimes}n\phantom{\rule{0.16em}{0ex}}(m,n\ensuremath{\ge}3)$, Y.-L. Wang et al. [Phys. Rev. A 92, 032313 (2015)] presented $3(m+n)\ensuremath{-}9$ orthogonal product states which cannot be distinguished by local operations and classical communication (LOCC). In this paper, we aim to construct less locally indistinguishable orthogonal product states in $m\ensuremath{\bigotimes}n$. First, in the $3\ensuremath{\bigotimes}n\phantom{\rule{0.28em}{0ex}}(3ln)$ quantum system, we construct $3n\ensuremath{-}2$ locally indistinguishable orthogonal product states which are not unextendible product bases. Then, for $m\ensuremath{\bigotimes}n\phantom{\rule{0.28em}{0ex}}(4\ensuremath{\le}m\ensuremath{\le}n)$, we present $3n+m\ensuremath{-}4$ orthogonal product states which cannot be perfectly distinguished by LOCC. Finally, in the general bipartite quantum system $m\ensuremath{\bigotimes}n\phantom{\rule{0.28em}{0ex}}(3\ensuremath{\le}m\ensuremath{\le}n)$, we show a smaller set with $2n\ensuremath{-}1$ orthogonal product states and prove that these states are LOCC indistinguishable using a very simple but quite effective method. All of the above results demonstrate the phenomenon of nonlocality without entanglement.

Cryptanalysis is an important branch in the study of cryptography, including both the classical cryptography and the quantum one. In this paper we analyze the security of two three-party quantum key distribution protocols (QKDPs) proposed recently, and point out that they are susceptible to a simple and effective attack, i.e. the dense-coding attack. It is shown that the eavesdropper Eve can totally obtain the session key by sending entangled qubits as the fake signal to Alice and performing collective measurements after Alice's encoding. The attack process is just like a dense-coding communication between Eve and Alice, where a special measurement basis is employed. Furthermore, this attack does not introduce any errors to the transmitted information and consequently will not be discovered by Alice and Bob. The attack strategy is described in detail and a proof for its correctness is given. At last, the root of this insecurity and a possible way to improve these protocols are discussed., 6 pages, 3 figures

Interaction of the Flos Lonicerae Japonicae (FLJ) with protein was studied by microdialysis coupled with HPLC-DAD-MS. Eight compounds were identified by comparing their t(R), UV data and MS data with reference compounds. Microdialysis recoveries and binding degrees of compounds in FLJ with bovine serum albumin (BSA) were determined. Recoveries of microdialysis sampling ranged from 51.3 to 73.2% with relative standard deviation (RSD) below 3.1%, and the binding degrees of those compounds to BSA ranged from 4.8 to 61.2 (0.3 mM BSA) and from 11.1 to 76.2% (0.6 mM BSA), respectively. The results showed that the binding properties of compounds in FLJ were influenced by pH. Furthermore, the binding degrees of five reference compounds were determined separately under the same conditions, the binding degrees of chlorogenic acid, luteolin-3-O-glucoside and 4,5-di-O-caffeoyl quinic acid was lower in FLJ than in single compound solution, on the contrary the binding degree of caffeic acid and rutin was higher in FLJ, which indicated that a significant effects of the interaction of compounds with each other on their binding degrees to BSA. The results showed that there were ten compounds had interaction with BSA, eight of them were the proven active compounds, and the other two compounds had similar binding degree with the proven active compounds, so the ten compounds might possess potential activities.

In quantum communication, passive decoy-state QKD protocols can eliminate many side channels, but the protocols without any finite-key analyses are not suitable for in practice. The finite-key securities of passive decoy-state (PDS) QKD protocols with two different unstable sources, type-II parametric down-convention (PDC) and phase randomized weak coherent pulses (WCPs), are analyzed in our paper. According to the PDS QKD protocols, we establish an optimizing programming respectively and obtain the lower bounds of finite-key rates. Under some reasonable values of quantum setup parameters, the lower bounds of finite-key rates are simulated. The simulation results show that at different transmission distances, the affections of different fluctuations on key rates are different. Moreover, the PDS QKD protocol with an unstable PDC source can resist more intensity fluctuations and more statistical fluctuation.

We investigate the distinguishability of orthogonal multipartite entangled states in d-qudit system by restricted local operations and classical communication. According to these properties, we propose a standard (2, n)-threshold quantum secret sharing scheme (called LOCC-QSS scheme), which solves the open question in [Rahaman et al., Phys. Rev. A, 91, 022330 (2015)]. On the other hand, we find that all the existing (k, n)-threshold LOCC-QSS schemes are imperfect (or “ramp”), i.e., unauthorized groups can obtain some information about the shared secret. Furthermore, we present a (3, 4)-threshold LOCC-QSS scheme which is close to perfect.

Keyword: Genetic algorithm, Resource scheduling, Mult-fitness, Resources perception Abstract: Current real-time task scheduling algorithm only focus on the user tasks' real-time demand, and these algorithms are not flexible enough to adapt for real-time change in heterogeneous systems. In this paper, by means of the characteristics of global optimization searching of genetic algorithm, from the point of user's real-time demand and the overall throughput of system, we design the fitness function based on real-time and overall throughput. Aimed at solving the existing problems of slow convergence speed of genetic algorithm, based on the strategy of resources perception, according to the size of the workload, the virtual machine parameters and load conditions (I/O intensive or CPU intensive), we guide the process of convergence of genetic algorithm, to make it to the larger probability of the corresponding type task variation or evolve to the adapted virtual machine, therefore we can accelerate the convergence process.

The determination of many special types of quantum states has been studied thoroughly, such as the generalized |GHZ> states, |W> states equivalent under stochastic local operations and classical communication and Dicke states. In this paper, we are going to study another special entanglement states which is stabilizer states. The stabilizer states and their subset graph states play an important role in quantum error correcting codes, multipartite purification and so on. We show that all n- qubit stabilizer states are uniquely determined (among arbitrary states, pure or mixed) by their reduced density matrices for systems which are the supports of n independent generators of the corresponding stabilizer formalisms.

As a new model for signing quantum message, arbitrated quantum signature (AQS) has recently received a lot of attention. In this paper we study the cryptanalysis of previous AQS protocols from the aspects of forgery and disavowal. We show that in these protocols the receiver Bob can realize existential forgery of the sender's signature under known message attack. Bob can even achieve universal forgery when the protocols are used to sign a classical message. Furthermore, the sender Alice can successfully disavow any of her signatures by simple attack. The attack strategies are described in detail and some discussions about the potential improvements of the protocols are given. Finally we also present several interesting topics in future study on AQS protocols., Comment: 7 pages, no figures

The participant attack is the most serious threat for quantum secret-sharing protocols. We present a method to analyze the security of quantum secret-sharing protocols against this kind of attack taking the scheme of Hillery, Buzek, and Berthiaume (HBB) [Phys. Rev. A 59 1829 (1999)] as an example. By distinguishing between two mixed states, we derive the necessary and sufficient conditions under which a dishonest participant can attain all the information without introducing any error, which shows that the HBB protocol is insecure against dishonest participants. It is easy to verify that the attack scheme of Karlsson, Koashi, and Imoto [Phys. Rev. A 59, 162 (1999)] is a special example of our results. To demonstrate our results further, we construct an explicit attack scheme according to the necessary and sufficient conditions. Our work completes the security analysis of the HBB protocol, and the method presented may be useful for the analysis of other similar protocols., Revtex, 7 pages, 3 figures; Introduction modified

Based on quantum encryption, we present a new idea for quantum public-key cryptography (QPKC) and construct a whole theoretical framework of a QPKC system. We show that the quantum-mechanical nature renders it feasible and reasonable to use symmetric keys in such a scheme, which is quite different from that in conventional public-key cryptography. The security of our scheme is analyzed and some features are discussed. Furthermore, the state-estimation attack to a prior QPKC scheme is demonstrated., Comment: 8 pages, 1 figure, Revtex4

In a recent paper [S. Bagherinezhad and V. Karimipour, Phys. Rev. A 67, 044302 (2003)], a quantum secret sharing protocol based on reusable GHZ states was proposed. However, in this comment, it is shown that this protocol is insecure because a cheater can gain all the secret bits before sharing, while introducing one data bit error at most in the whole communication, which makes the cheater avoid the detection by the communication parities.

Grover's operator in the two-qubit case can transform a basis into its conjugated basis. A permutation operator can transform a state in the two conjugated bases into its orthogonal state. These properties are included in a threshold quantum protocol. The proposed threshold quantum protocol is secure based the proof that the legitimate participators can only eavesdrop 2 bits of 3 bits operation information on one two-qubit with error probability 3/8. We propose a scheme to detect the Trojan horse attack without destroying the legal qubit., Comment: 7 pages, 1 figures