Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNon-Commutative Ring Learning With Errors From Cyclic Algebras
58
0
0.0
(
0
)
Added by
Cong Ling
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 impractical, 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.
rate research
Read More
A long standing problem in the area of error correcting codes asks whether there exist good cyclic codes. Most of the known results point in the direction of a negative answer. The uncertainty principle is a classical result of harmonic analysis asserting that given a non-zero function $f$ on some abelian group, either $f$ or its Fourier transform $hat{f}$ has large support. In this note, we observe a connection between these two subjects. We point out that even a weak version of the uncertainty principle for fields of positive characteristic would imply that good cyclic codes do exist. We also provide some heuristic arguments supporting that this is indeed the case.
Let $mathbb{F}_q$ be a finite field of order $q$, a prime power integer such that $q=et+1$ where $tgeq 1,egeq 2$ are integers. In this paper, we study cyclic codes of length $n$ over a non-chain ring $R_{e,q}=mathbb{F}_q[u]/langle u^e-1rangle$. We define a Gray map $varphi$ and obtain many { maximum-distance-separable} (MDS) and optimal $mathbb{F}_q$-linear codes from the Gray images of cyclic codes. Under certain conditions we determine { linear complementary dual} (LCD) codes of length $n$ when $gcd(n,q) eq 1$ and $gcd(n,q)= 1$, respectively. It is proved that { a} cyclic code $mathcal{C}$ of length $n$ is an LCD code if and only if its Gray image $varphi(mathcal{C})$ is an LCD code of length $4n$ over $mathbb{F}_q$. Among others, we present the conditions for existence of free and non-free LCD codes. Moreover, we obtain many optimal LCD codes as the Gray images of non-free LCD codes over $R_{e,q}$.
As the size of data storing arrays of disks grows, it becomes vital to protect data against double disk failures. A popular method of protection is via the Reed-Solomon (RS) code with two parity words. In the present paper we construct alternative examples of linear block codes protecting against two erasures. Our construction is based on an abstract notion of cone. Concrete cones are constructed via matrix representations of cyclic groups of prime order. In particular, this construction produces EVENODD code. Interesting conditions on the prime number arise in our analysis of these codes. At the end, we analyse an assembly implementation of the corresponding system on a general purpose processor and compare its write and recovery speed with the standard DP-RAID system.
In this paper, we clarify some aspects on LCD codes in the literature. We first prove that a non-free LCD code does not exist over finite commutative Frobenius local rings. We then obtain a necessary and sufficient condition for the existence of LCD code over finite commutative Frobenius rings. We later show that a free constacyclic code over finite chain ring is LCD if and only if it is reversible, and also provide a necessary and sufficient condition for a constacyclic code to be reversible over finite chain rings. We illustrate the minimum Lee-distance of LCD codes over some finite commutative chain rings and demonstrate the results with examples. We also got some new optimal $mathbb{Z}_4$ codes of different lengths {which are} cyclic LCD codes over $mathbb{Z}_4$.
Cyclic codes, as linear block error-correcting codes in coding theory, play a vital role and have wide applications. Ding in cite{D} constructed a number of classes of cyclic codes from almost perfect nonlinear (APN) functions and planar functions over finite fields and presented ten open problems on cyclic codes from highly nonlinear functions. In this paper, we consider two open problems involving the inverse APN functions $f(x)=x^{q^m-2}$ and the Dobbertin APN function $f(x)=x^{2^{4i}+2^{3i}+2^{2i}+2^{i}-1}$. From the calculation of linear spans and the minimal polynomials of two sequences generated by these two classes of APN functions, the dimensions of the corresponding cyclic codes are determined and lower bounds on the minimum weight of these cyclic codes are presented. Actually, we present a framework for the minimal polynomial and linear span of the sequence $s^{infty}$ defined by $s_t=Tr((1+alpha^t)^e)$, where $alpha$ is a primitive element in $GF(q)$. These techniques can also be applied into other open problems in cite{D}.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
