Search

In this paper we present new constructions of multi-party homomorphic secret sharing (HSS) based on a new primitive that we call homomorphic encryption with decryption to shares (HEDS). Our first scheme, which we call Scooby , is based on many popular fully homomorphic encryption (FHE) schemes with a linear decryption property. Scooby achieves an n -party HSS for general circuits with complexity O (| F | + log ⁡ n) , as opposed to O (n 2 ⋅ | F |) for the prior best construction based on multi-key FHE. Scooby relies on a trusted setup procedure, and can be based on (ring)-LWE with a super-polynomial modulus-to-noise ratio. In our second construction, Scrappy , assuming any generic FHE plus HSS for NC1-circuits, we obtain a HEDS scheme which does not require a super-polynomial modulus. While these schemes all require FHE, in another instantiation, Shaggy , we show how it is also possible to obtain multi-party HSS without FHE, instead relying on the DCR assumption to obtain 4-party HSS for constant-degree polynomials. [ABSTRACT FROM AUTHOR]

General error locator polynomials were introduced in 2005 as an alternative decoding for cyclic codes. We now present a conjecture on their sparsity, which would imply polynomial-time decoding for all cyclic codes. A general result on the explicit form of the general error locator polynomial for all cyclic codes is given, along with several results for specific code families, providing evidence to our conjecture. From these, a theoretical justification of the sparsity of general error locator polynomials is obtained for all binary cyclic codes with $t\leq 2$ and $n<105$ , as well as for $t=3$ and $n<63$ , except for some cases where the conjectured sparsity is proved by a computer check. Moreover, we summarize all related results, previously published, and we show how they provide further evidence to our conjecture. Finally, we discuss the link between our conjecture and the complexity of bounded-distance decoding of the cyclic codes. [ABSTRACT FROM AUTHOR]

Abstract: General error locator polynomials are polynomials able to decode any correctable syndrome for a given linear code. Such polynomials are known to exist for all cyclic codes and for a large class of linear codes. We provide some decoding techniques for affine-variety codes using some multidimensional extensions of general error locator polynomials. We prove the existence of such polynomials for any correctable affine-variety code and hence for any linear code. We propose two main different approaches, that depend on the underlying geometry. We compute some interesting cases, including Hermitian codes. To prove our coding theory results, we develop a theory for special classes of zero-dimensional ideals, that can be considered generalizations of stratified ideals. Our improvement with respect to stratified ideals is twofold: we generalize from one variable to many variables and we introduce points with multiplicities. [Copyright &y& Elsevier]

The most important families of nonlinear codes are systematic. A brute-force check is the only known method to compute their weight distribution and distance distribution. On the other hand, it outputs also all closest word pairs in the code. In the black-box complexity model, the check is optimal among closest-pair algorithms. In this paper, we provide a Gröbner basis technique to compute the weight/distance distribution of any systematic nonlinear code. Also our technique outputs all closest pairs. Unlike the check, our method can be extended to work on code families. [ABSTRACT FROM AUTHOR]

In this paper, we show that a recently proposed algorithm for decoding cyclic codes may be applied efficiently to all binary cyclic codes with t ⩽ 2 and n < 63. This is accomplished by providing structure theorems for the codes in this range and classifying the relevant cases. [ABSTRACT FROM AUTHOR]

Abstract: We propose a new syndrome variety, which can be used to decode cyclic codes. We present also a generalization to erasure and error decoding. We can exhibit a polynomial whose roots give the error locations, once it has been specialized to a given syndrome. This polynomial has degree in the variable corresponding to the error locations and its coefficients are polynomials in the syndromes. [Copyright &y& Elsevier]