Evaluating the expectation of a quantum circuit is a classically difficult problem known as the quantum mean value problem (QMV). It is used to optimize the quantum approximate optimization algorithm and other variational quantum eigensolvers. We sho
w that such an optimization can be improved substantially by using an approximation rather than the exact expectation. Together with efficient classical sampling algorithms, a quantum algorithm with minimal gate count can thus improve the efficiency of general integer-value problems, such as the shortest vector problem (SVP) investigated in this work.
Whilst lattice-based cryptosystems are believed to be resistant to quantum attack, they are often forced to pay for that security with inefficiencies in implementation. This problem is overcome by ring- and module-based schemes such as Ring-LWE or Mo
dule-LWE, whose keysize can be reduced by exploiting its algebraic structure, allowing for neater and faster computations. Many rings may be chosen to define such cryptoschemes, but cyclotomic rings, due to their cyclic nature allowing for easy multiplication, are the community standard. However, there is still much uncertainty as to whether this structure may be exploited to an adversarys benefit. In this paper, we show that the decomposition group of a cyclotomic ring of arbitrary conductor may be utilised in order to significantly decrease the dimension of the ideal (or module) lattice required to solve a given instance of SVP. Moreover, we show that there exist a large number of rational primes for which, if the prime ideal factors of an ideal lie over primes of this form, give rise to an easy instance of SVP. However, it is important to note that this work does not break Ring-LWE or Module-LWE, since the security reduction is from worst case ideal or module SVP to average case Ring-LWE or Module-LWE respectively, and is one way.
In this paper, we propose a polar coding based scheme for set reconciliation between two network nodes. The system is modeled as a well-known Slepian-Wolf setting induced by a fixed number of deletions. The set reconciliation process is divided into
two phases: 1) a deletion polar code is employed to help one node to identify the possible deletion indices, which may be larger than the number of genuine deletions; 2) a lossless compression polar code is then designed to feedback those indices with minimum overhead. Our scheme can be viewed as a generalization of polar codes to some emerging network-based applications such as the package synchronization in blockchains. Some connections with the existing schemes based on the invertible Bloom lookup tables (IBLTs) and network coding are also observed and briefly discussed.
The Learning with Errors (LWE) problem is the fundamental backbone of modern lattice based cryptography, allowing one to establish cryptography on the hardness of well-studied computational problems. However, schemes based on LWE are often impractica
l, so Ring LWE was introduced as a form of `structured LWE, trading off a hard to quantify loss of security for an increase in efficiency by working over a well chosen ring. Another popular variant, Module LWE, generalizes this exchange by implementing a module structure over a ring. In this work, we introduce a novel variant of LWE over cyclic algebras (CLWE) to replicate the addition of the ring structure taking LWE to Ring LWE by adding cyclic structure to Module LWE. The proposed construction is both more efficient than Module LWE and conjecturally more secure than Ring LWE, the best of both worlds. We show that the security reductions expected for an LWE problem hold, namely a reduction from certain structured lattice problems to the hardness of the decision variant of the CLWE problem. As a contribution of theoretic interest, we view CLWE as the first variant of Ring LWE which supports non-commutative multiplication operations. This ring structure compares favorably with Module LWE, and naturally allows a larger message space for error correction coding.
We consider the problem of secure distributed matrix computation (SDMC), where a textit{user} can query a function of data matrices generated at distributed textit{source} nodes. We assume the availability of $N$ honest but curious computation server
s, which are connected to the sources, the user, and each other through orthogonal and reliable communication links. Our goal is to minimize the amount of data that must be transmitted from the sources to the servers, called the textit{upload cost}, while guaranteeing that no $T$ colluding servers can learn any information about the source matrices, and the user cannot learn any information beyond the computation result. We first focus on secure distributed matrix multiplication (SDMM), considering two matrices, and propose a novel polynomial coding scheme using the properties of finite field discrete Fourier transform, which achieves an upload cost significantly lower than the existing results in the literature. We then generalize the proposed scheme to include straggler mitigation, as well as to the multiplication of multiple matrices while keeping the input matrices, the intermediate computation results, as well as the final result secure against any $T$ colluding servers. We also consider a special case, called computation with own data, where the data matrices used for computation belong to the user. In this case, we drop the security requirement against the user, and show that the proposed scheme achieves the minimal upload cost. We then propose methods for performing other common matrix computations securely on distributed servers, including changing the parameters of secret sharing, matrix transpose, matrix exponentiation, solving a linear system, and matrix inversion, which are then used to show how arbitrary matrix polynomials can be computed securely on distributed servers using the proposed procedure.
Cache-aided content delivery is studied in a multi-server system with $P$ servers and $K$ users, each equipped with a local cache memory. In the delivery phase, each user connects randomly to any $rho$ out of $P$ servers. Thanks to the availability o
f multiple servers, which model small-cell base stations (SBSs), demands can be satisfied with reduced storage capacity at each server and reduced delivery rate per server; however, this also leads to reduced multicasting opportunities compared to the single-server scenario. A joint storage and proactive caching scheme is proposed, which exploits coded storage across the servers, uncoded cache placement at the users, and coded delivery. The delivery textit{latency} is studied for both textit{successive} and textit{parallel} transmissions from the servers. It is shown that, with successive transmissions the achievable average delivery latency is comparable to the one achieved in the single-server scenario, while the gap between the two depends on $rho$, the available redundancy across the servers, and can be reduced by increasing the storage capacity at the SBSs. The optimality of the proposed scheme with uncoded cache placement and MDS-coded server storage is also proved for successive transmissions.
We consider a key encapsulation mechanism (KEM) based on Module-LWE where reconciliation is performed on the 8-dimensional lattice $E_8$, which admits a fast CVP algorithm. Our scheme generates 256 bits of key and requires 3 or 4 bits of reconciliati
on per dimension. We show that it can outperform Kyber in terms of the modulus q with comparable error probability. We prove that our protocol is IND-CPA secure and improves the security level of Kyber by 7.3%.
Since quantum computers are known to break the vast majority of currently-used cryptographic protocols, a variety of new protocols are being developed that are conjectured, but not proven to be safe against quantum attacks. Among the most promising i
s lattice-based cryptography, where security relies upon problems like the shortest vector problem. We analyse the potential of adiabatic quantum computation for attacks on lattice-based cryptography, and give numerical evidence that even outside the adiabatic regime such methods can facilitate the solution of the shortest vector and similar problems.
A code construction and repair scheme for optimal functional regeneration of multiple node failures is presented, which is based on stitching together short MDS codes on carefully chosen sets of points lying on a linearized polynomial. The nodes are
connected wirelessly, hence all transmissions by helper nodes during a repair round are available to all the nodes being repaired. The scheme is simple and practical because of low subpacketization, low I/O cost and low computational cost. Achievability of the minimum-bandwidth regenerating (MBR) point, as well as an interior point, on the optimal storage-repair bandwidth tradeoff curve is shown. The subspace properties derived in the paper provide insight into the general properties of functional regenerating codes.
Cache-aided content delivery is studied in a multi-server system with $P$ servers and $K$ users, each equipped with a local cache memory. In the delivery phase, each user connects randomly to any $rho$ out of $P$ servers. Thanks to the availability o
f multiple servers, which model small base stations with limited storage capacity, user demands can be satisfied with reduced storage capacity at each server and reduced delivery rate per server; however, this also leads to reduced multicasting opportunities compared to a single server serving all the users simultaneously. A joint storage and proactive caching scheme is proposed, which exploits coded storage across the servers, uncoded cache placement at the users, and coded delivery. The delivery textit{latency} is studied for both textit{successive} and textit{simultaneous} transmission from the servers. It is shown that, with successive transmission the achievable average delivery latency is comparable to that achieved by a single server, while the gap between the two depends on $rho$, the available redundancy across servers, and can be reduced by increasing the storage capacity at the SBSs.
