Efficient parallelizable hashing using small non-compressing primitives

A well-established method of constructing hash functions is to base them on non-compressing primitives, such as one-way functions or permutations. In this work, we present \(S^r\), an \(rn\)-to-\(n\)-bit compression function (for \(r\ge 1\)) making \(2r-1\) calls to \(n\)-to-\(n\)-bit primitives (random functions or permutations). \(S^r\) compresses its inputs at a rate (the amount of message blocks per primitive call) up to almost 1/2, and it outperforms all existing schemes with respect to rate and/or the size of underlying primitives. For instance, instantiated with the \(1600\)-bit permutation of NIST’s SHA-3 hash function standard, it offers about \(800\)-bit security at a rate of almost 1/2, while SHA-3-512 itself achieves only \(512\)-bit security at a rate of about \(1/3\). We prove that \(S^r\) achieves asymptotically optimal collision security against semi-adaptive adversaries up to almost \(2^{n/2}\) queries and that it can be made preimage secure up to \(2^n\) queries using a simple tweak.     

Two Mixed Finite Element Methods for Time-Fractional Diffusion Equations

Based on spatial conforming and nonconforming mixed finite element methods combined with classical L1 time stepping method, two fully-discrete approximate schemes with unconditional stability are first established for the time-fractional diffusion equation with Caputo derivative of order \(0<\alpha <1\). As to the conforming scheme, the spatial global superconvergence and temporal convergence order of \(O(h^2+\tau ^{2-\alpha })\) for both the original variable u in \(H^1\)-norm and the flux \(\vec {p}=\nabla u\) in \(L^2\)-norm are derived by virtue of properties of bilinear element and interpolation postprocessing operator, where h and \(\tau \) are the step sizes in space and time, respectively. At the same time, the optimal convergence rates in time and space for the nonconforming scheme are also investigated by some special characters of \(\textit{EQ}_1^{\textit{rot}}\) nonconforming element, which manifests that convergence orders of \(O(h+\tau ^{2-\alpha })\) and \(O(h^2+\tau ^{2-\alpha })\) for the original variable u in broken \(H^1\)-norm and \(L^2\)-norm, respectively, and approximation for the flux \(\vec {p}\) converging with order \(O(h+\tau ^{2-\alpha })\) in \(L^2\)-norm. Numerical examples are provided to demonstrate the theoretical analysis.     

A highly efficient scheme for joint remote preparation of multi-qubit W state with minimum quantum resource

We present a highly efficient scheme for perfect joint remote preparation of an arbitrary \( 2^{n} \)-qubit W state with minimum quantum resource. Both the senders Alice and Bob intend to jointly prepare one \( 2^{n} \)-qubit W state for the remote receiver Charlie. In the beginning, they help the remote receiver Charlie to construct one n-qubit intermediate state which is closely related to the target \( 2^{n} \)-qubit W state. Afterward, Charlie introduces auxiliary qubits and applies appropriate operations to obtain the target \( 2^{n} \)-qubit W state. Compared with previous schemes, our scheme requires minimum quantum resource and least amount of classical communication. Moreover, our scheme has a significant potential for being adapted to remote state preparation of other special states.     

Numerical Algorithm With High Spatial Accuracy for the Fractional Diffusion-Wave Equation With Neumann Boundary Conditions

A fourth-order compact algorithm is discussed for solving the time fractional diffusion-wave equation with Neumann boundary conditions. The \(L1\) discretization is applied for the time-fractional derivative and the compact difference approach for the spatial discretization. The unconditional stability and the global convergence of the compact difference scheme are proved rigorously, where a new inner product is introduced for the theoretical analysis. The convergence order is \(\mathcal{O }(\tau ^{3-\alpha }+h^4)\) in the maximum norm, where \(\tau \) is the temporal grid size and \(h\) is the spatial grid size, respectively. In addition, a Crank–Nicolson scheme is presented and the corresponding error estimates are also established. Meanwhile, a compact ADI difference scheme for solving two-dimensional case is derived and the global convergence order of \(\mathcal{O }(\tau ^{3-\alpha }+h_1^4+h_2^4)\) is given. Then extension to the case with Robin boundary conditions is also discussed. Finally, several numerical experiments are included to support the theoretical results, and some comparisons with the Crank–Nicolson scheme are presented to show the effectiveness of the compact scheme.     

Connecting unextendible maximally entangled base with partial Hadamard matrices

We study the unextendible maximally entangled bases (UMEB) in \(\mathbb {C}^{d}\bigotimes \mathbb {C}^{d}\) and connect the problem to the partial Hadamard matrices. We show that for a given special UMEB in \(\mathbb {C}^{d}\bigotimes \mathbb {C}^{d}\), there is a partial Hadamard matrix which cannot be extended to a Hadamard matrix in \(\mathbb {C}^{d}\). As a corollary, any \((d-1)\times d\) partial Hadamard matrix can be extended to a Hadamard matrix, which answers a conjecture about \(d=5\). We obtain that for any d there is a UMEB except for \(d=p\ \text {or}\ 2p\), where \(p\equiv 3\mod 4\) and p is a prime. The existence of different kinds of constructions of UMEBs in \(\mathbb {C}^{nd}\bigotimes \mathbb {C}^{nd}\) for any \(n\in \mathbb {N}\) and \(d=3\times 5 \times 7\) is also discussed.     

Bidirectional controlled teleportation by using nine-qubit entangled state in noisy environments

A theoretical scheme is proposed to implement bidirectional quantum controlled teleportation (BQCT) by using a nine-qubit entangled state as a quantum channel, where Alice may transmit an arbitrary two-qubit state called qubits \(A_1\) and \(A_2\) to Bob; and at the same time, Bob may also transmit an arbitrary two-qubit state called qubits \(B_1\) and \(B_2\) to Alice via the control of the supervisor Charlie. Based on our channel, we explicitly show how the bidirectional quantum controlled teleportation protocol works. And we show this bidirectional quantum controlled teleportation scheme may be determinate and secure. Taking the amplitude-damping noise and the phase-damping noise as typical noisy channels, we analytically derive the fidelities of the BQCT process and show that the fidelities in these two cases only depend on the amplitude parameter of the initial state and the decoherence noisy rate.     

车载自组网中可撤销的聚合签名认证方案

为解决车载自组网(VANET)面临的通信安全和隐私保护方面的问题,提出了一种车载自组网中可撤销的聚合签名认证方案.该方案通过匿名认证保障用户隐私,通过使用防篡改设备和聚合签名技术提高认证效率.为实现车辆撤销,要求车辆使用路边单元发放的成员密钥生成签名,当车辆进入路边单元的通信范围时,路边单元实时审查车辆身份,拒绝为撤销...     

Quantum image rotation by an arbitrary angle

In this paper, a novel method of quantum image rotation (QIR) based on shear transformations on NEQR quantum images is proposed. To compute the horizontal and vertical shear mappings required for rotation, we have designed quantum self-adder, quantum control multiplier, and quantum interpolation circuits as the basic computing units in the QIR implementation. Furthermore, we provide several examples of our results by presenting computer simulation experiments of QIR under \(30^\circ \), \(45^\circ \), and \(60^\circ \) rotation scenarios and have a discussion onto the anti-aliasing and computational complexity of the proposed QIR method.     

Master Lovas–Andai and equivalent formulas verifying the $$\frac{8}{33}$$ two-qubit Hilbert–Schmidt separability probability and companion rational-valued conjectures

We begin by investigating relationships between two forms of Hilbert–Schmidt two-rebit and two-qubit “separability functions”—those recently advanced by Lovas and Andai (J Phys A Math Theor 50(29):295303, 2017), and those earlier presented by Slater (J Phys A 40(47):14279, 2007). In the Lovas–Andai framework, the independent variable \(\varepsilon \in [0,1]\) is the ratio \(\sigma (V)\) of the singular values of the \(2 \times 2\) matrix \(V=D_2^{1/2} D_1^{-1/2}\) formed from the two \(2 \times 2\) diagonal blocks (\(D_1, D_2\)) of a \(4 \times 4\) density matrix \(D= \left||\rho _{ij}\right||\). In the Slater setting, the independent variable \(\mu \) is the diagonal-entry ratio \(\sqrt{\frac{\rho _{11} \rho _ {44}}{\rho _ {22} \rho _ {33}}}\)—with, of central importance, \(\mu =\varepsilon \) or \(\mu =\frac{1}{\varepsilon }\) when both \(D_1\) and \(D_2\) are themselves diagonal. Lovas and Andai established that their two-rebit “separability function” \(\tilde{\chi }_1 (\varepsilon )\) (\(\approx \varepsilon \)) yields the previously conjectured Hilbert–Schmidt separability probability of \(\frac{29}{64}\). We are able, in the Slater framework (using cylindrical algebraic decompositions [CAD] to enforce positivity constraints), to reproduce this result. Further, we newly find its two-qubit, two-quater[nionic]-bit and “two-octo[nionic]-bit” counterparts, \(\tilde{\chi _2}(\varepsilon ) =\frac{1}{3} \varepsilon ^2 \left( 4-\varepsilon ^2\right) \), \(\tilde{\chi _4}(\varepsilon ) =\frac{1}{35} \varepsilon ^4 \left( 15 \varepsilon ^4-64 \varepsilon ^2+84\right) \) and \(\tilde{\chi _8} (\varepsilon )= \frac{1}{1287}\varepsilon ^8 \left( 1155 \varepsilon ^8-7680 \varepsilon ^6+20160 \varepsilon ^4-25088 \varepsilon ^2+12740\right) \). These immediately lead to predictions of Hilbert–Schmidt separability/PPT-probabilities of \(\frac{8}{33}\), \(\frac{26}{323}\) and \(\frac{44482}{4091349}\), in full agreement with those of the “concise formula” (Slater in J Phys A 46:445302, 2013), and, additionally, of a “specialized induced measure” formula. Then, we find a Lovas–Andai “master formula,” \(\tilde{\chi _d}(\varepsilon )= \frac{\varepsilon ^d \Gamma (d+1)^3 \, _3\tilde{F}_2\left( -\frac{d}{2},\frac{d}{2},d;\frac{d}{2}+1,\frac{3 d}{2}+1;\varepsilon ^2\right) }{\Gamma \left( \frac{d}{2}+1\right) ^2}\), encompassing both even and odd values of d. Remarkably, we are able to obtain the \(\tilde{\chi _d}(\varepsilon )\) formulas, \(d=1,2,4\), applicable to full (9-, 15-, 27-) dimensional sets of density matrices, by analyzing (6-, 9, 15-) dimensional sets, with not only diagonal \(D_1\) and \(D_2\), but also an additional pair of nullified entries. Nullification of a further pair still leads to X-matrices, for which a distinctly different, simple Dyson-index phenomenon is noted. C. Koutschan, then, using his HolonomicFunctions program, develops an order-4 recurrence satisfied by the predictions of the several formulas, establishing their equivalence. A two-qubit separability probability of \(1-\frac{256}{27 \pi ^2}\) is obtained based on the operator monotone function \(\sqrt{x}\), with the use of \(\tilde{\chi _2}(\varepsilon )\).     

New asymmetric quantum codes over $$F_{q}$$

Two families of new asymmetric quantum codes are constructed in this paper. The first family is the asymmetric quantum codes with length \(n=q^{m}-1\) over \(F_{q}\), where \(q\ge 5\) is a prime power. The second one is the asymmetric quantum codes with length \(n=3^{m}-1\). These asymmetric quantum codes are derived from the CSS construction and pairs of nested BCH codes. Moreover, let the defining set \(T_{1}=T_{2}^{-q}\), then the real Z-distance of our asymmetric quantum codes are much larger than \(\delta _\mathrm{max}+1\), where \(\delta _\mathrm{max}\) is the maximal designed distance of dual-containing narrow-sense BCH code, and the parameters presented here have better than the ones available in the literature.     

Indistinguishability of pure orthogonal product states by LOCC

We construct two sets of incomplete and extendible quantum pure orthogonal product states (POPS) in general bipartite high-dimensional quantum systems, which are all indistinguishable by local operations and classical communication. The first set of POPS is composed of two parts which are \(\mathcal {C}^m\otimes \mathcal {C}^{n_1}\) with \(5\le m\le n_1\) and \(\mathcal {C}^m\otimes \mathcal {C}^{n_2}\) with \(5\le m \le n_2\), where \(n_1\) is odd and \(n_2\) is even. The second one is in \(\mathcal {C}^m\otimes \mathcal {C}^n\) \((m, n\ge 4)\). Some subsets of these two sets can be extended into complete sets that local indistinguishability can be decided by noncommutativity which quantifies the quantumness of a quantum ensemble. Our study shows quantum nonlocality without entanglement.     

A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines,small looseness,and small slack

We study the problem of non-preemptively scheduling n jobs, each job j with a release time \(t_j\), a deadline \(d_j\), and a processing time \(p_j\), on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints \(|d_j-t_j|\le \lambda {}p_j\) and \(|d_j-t_j|\le p_j +\sigma \) and showed the problem to be NP-hard for any \(\lambda >1\) and for any \(\sigma \ge 2\). We complement their results by parameterized complexity studies: we show that, for any \(\lambda >1\), the problem remains weakly NP-hard even for \(m=2\) and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and \(\lambda \) and a fixed-parameter tractability result for the parameter m combined with \(\sigma \).     

Mutually unbiased maximally entangled bases in $$\mathbb {C}^d\otimes \mathbb {C}^d$$

We study mutually unbiased maximally entangled bases (MUMEB’s) in bipartite system \(\mathbb {C}^d\otimes \mathbb {C}^d (d \ge 3)\). We generalize the method to construct MUMEB’s given in Tao et al. (Quantum Inf Process 14:2291–2300, 2015), by using any commutative ring R with d elements and generic character of \((R,+)\) instead of \(\mathbb {Z}_d=\mathbb {Z}/d\mathbb {Z}\). Particularly, if \(d=p_1^{a_1}p_2^{a_2}\ldots p_s^{a_s}\) where \(p_1, \ldots , p_s\) are distinct primes and \(3\le p_1^{a_1}\le \cdots \le p_s^{a_s}\), we present \(p_1^{a_1}-1\) MUMEB’s in \(\mathbb {C}^d\otimes \mathbb {C}^d\) by taking \(R=\mathbb {F}_{p_1^{a_1}}\oplus \cdots \oplus \mathbb {F}_{p_s^{a_s}}\), direct sum of finite fields (Theorem 3.3).     

An improved low-cost yoking proof protocol based on Kazahaya’s flaws

Peris-Lopez et al. (J Netw Comput Appl 34:833–845, 2011) recently provided some guidelines that should be followed to design a secure yoking proof protocol. In addition, conforming to those guidelines and EPC C1-G2, they presented a yoking proof for medical systems based on low-cost RFID tags, named Kazahaya. In this paper, we compromise its security and show how a passive adversary can retrieve secret parameters of a patient’s tag in cost of \(O(2^{16})\) off-line PRNG evaluations. Nevertheless, to show other weaknesses of the protocol and rule out any possible improvement by increasing the length of the used PRNG, we present a forgery attack that proves that a generated proof at time \(t_n\) can be used to forge a valid proof for any desired time \(t_j\). The success probability of this attack is ‘1’ and the complexity is negligible. In addition, we present a new lightweight protocol based on 128-bit PRNG function to solve the problems of Kazahaya protocol. In terms of security, we evaluate the new protocol based on formal and informal methods and prove that the improved protocol is not vulnerable to RFID attacks.     

Numerical Methods and Comparison for the Dirac Equation in the Nonrelativistic Limit Regime

We analyze rigorously error estimates and compare numerically spatial/temporal resolution of various numerical methods for the discretization of the Dirac equation in the nonrelativistic limit regime, involving a small dimensionless parameter \(0<\varepsilon \ll 1\) which is inversely proportional to the speed of light. In this limit regime, the solution is highly oscillatory in time, i.e. there are propagating waves with wavelength \(O(\varepsilon ^2)\) and O(1) in time and space, respectively. We begin with several frequently used finite difference time domain (FDTD) methods and obtain rigorously their error estimates in the nonrelativistic limit regime by paying particular attention to how error bounds depend explicitly on mesh size h and time step \(\tau \) as well as the small parameter \(\varepsilon \). Based on the error bounds, in order to obtain ‘correct’ numerical solutions in the nonrelativistic limit regime, i.e. \(0<\varepsilon \ll 1\), the FDTD methods share the same \(\varepsilon \)-scalability on time step and mesh size as: \(\tau =O(\varepsilon ^3)\) and \(h=O(\sqrt{\varepsilon })\). Then we propose and analyze two numerical methods for the discretization of the Dirac equation by using the Fourier spectral discretization for spatial derivatives combined with the symmetric exponential wave integrator and time-splitting technique for temporal derivatives, respectively. Rigorous error bounds for the two numerical methods show that their \(\varepsilon \)-scalability is improved to \(\tau =O(\varepsilon ^2)\) and \(h=O(1)\) when \(0<\varepsilon \ll 1\). Extensive numerical results are reported to support our error estimates.     

Close to linear space routing schemes

Let \(G=(V,E)\) be an unweighted undirected graph with n vertices and m edges, and let \(k>2\) be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source s and a destination t at distance \(\varDelta \) from s, routes a message from s to t on a path whose length is \(O(k\varDelta +m^{1/k})\). The total space used by our routing scheme is \(mn^{O(1/\sqrt{\log n})}\), which is almost linear in the number of edges of the graph. We present also a routing scheme with \(n^{O(1/\sqrt{\log n})}\) header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of every \(v\in V\) is at most \(kn^{O(1/\sqrt{\log n})}deg(v)\), where deg(v) is the degree of v in G. Our results are obtained by combining a general technique of Bernstein (2009), that was presented in the context of dynamic graph algorithms, with several new ideas and observations.     

USSOR methods for solving the rank deficient linear least squares problem

In order to find the least squares solution of minimal norm to linear system \(Ax=b\) with \(A \in \mathcal{C}^{m \times n}\) being a matrix of rank \(r< n \le m\), \(b \in \mathcal{C}^{m}\), Zheng and Wang (Appl Math Comput 169:1305–1323, 2005) proposed a class of symmetric successive overrelaxation (SSOR) methods, which is based on augmenting system to a block \(4 \times 4\) consistent system. In this paper, we construct the unsymmetric successive overrelaxation (USSOR) method. The semiconvergence of the USSOR method is discussed. Numerical experiments illustrate that the number of iterations and CPU time for the USSOR method with the appropriate parameters is respectively less and faster than the SSOR method with optimal parameters.     

Novel classical post-processing for quantum key distribution-based quantum private query

Existing classical post-processing (CPP) schemes for quantum key distribution (QKD)-based quantum private queries (QPQs) including the \(kN\rightarrow N\), \(N\rightarrow N\), and \(rM\rightarrow N\) ones have been found imperfect in terms of communication efficiency and security. In this paper, we propose a novel CPP scheme for QKD-based QPQs. The proposed CPP scheme reduces the communication complexity and improves the security of QKD-based QPQ protocols largely. Furthermore, the proposed CPP scheme can provide a multi-bit query efficiently.     

Optimizing the Matrix Multiplication Using Strassen and Winograd Algorithms with Limited Recursions on Many-Core

Many-core systems are basically designed for applications having large data parallelism. We propose an efficient hybrid matrix multiplication implementation based on Strassen and Winograd algorithms (S-MM and W-MM) on many-core. A depth first (DFS) traversal of a recursion tree is used where all cores work in parallel on computing each of the \(N \times N\) sub-matrices, which are computed in sequence. DFS reduces the storage to the detriment of large data motion to gather and aggregate the results. The proposed approach uses three optimizations: (1) a small set of basic algebra functions to reduce overhead, (2) invoking efficient library (CUBLAS 5.5) for basic functions, and (3) using parameter-tuning of parametric kernel to improve resource occupancy. Evaluation of S-MM and W-MM is carried out on GPU and MIC (Xeon Phi). For GPU, W-MM and S-MM with one recursion level outperform CUBLAS 5.5 Library with up to twice as fast for arrays satisfying \(N \ge 2048\) and \(N \ge 3072\), respectively. Similar trends are observed for S-MM with reordering (R-S-MM), which is used to save storage. Compared to NVIDIA SDK library, S-MM and W-MM achieved a speedup between 20\(\times \) and 80\(\times \) for the above arrays. For MIC, two-recursion S-MM with reordering is faster than MKL library by 14–26 % for \(N \ge 1024\). Proposed implementations achieve 2.35 TFLOPS (67 % of peak) on GPU and 0.5 TFLOPS (21 % of peak) on MIC. Similar encouraging results are obtained for a 16-core Xeon-E5 server. We conclude that S-MM and W-MM implementations with a few recursion levels can be used to further optimize the performance of basic algebra libraries.