In this article, we study the geometry of units and ideals of cyclotomic rings and derive an algorithm to find a mildly short vector in any given cyclotomic ideal lattice in quantum polynomial time, under some plausible number-theoretic assumptions. More precisely, given an ideal lattice of the cyclotomic ring of conductor m , the algorithm finds an approximation of the shortest vector by a factor exp (Õ(√ m )). This result exposes an unexpected hardness gap between these structured lattices and general lattices: The best known polynomial time generic lattice algorithms can only reach an approximation factor exp (Õ(m)). Following a recent series of attacks, these results call into question the hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE, upon which relies the security of a number of cryptographic schemes. N OTE . This article is an extended version of a conference paper [11]. The results are generalized to arbitrary cyclotomic fields. In particular, we also extend some results of Reference [10] to arbitrary cyclotomic fields. In addition, we prove the numerical stability of the method of Reference [10]. These extended results appeared in the Ph.D. dissertation of the third author [46].

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity. In this paper, we focus on Reed-Muller codes with usual parameter regime, namely, the total degree of evaluation polynomials is d = Θ(q), where q is the code alphabet size (in fact, d can be as big as q/4 in our setting). By introducing a novel variation of codex, i.e., interleaved codex (the concept of codex has been used for arithmetic secret sharing), we are able to locally recover arbitrarily large number k of coordinates of a Reed-Muller code simultaneously with error probability exp(-Ω(k)) at the cost of querying merely O(q2k) coordinates. It turns out that our local decoding of Reed-Muller codes shows (perhaps surprisingly) that accessing k locations is in fact cheaper than repeating the procedure for accessing a single location for k times. Precisely speaking, to get the same success probability by repeating the local decoding algorithm of a single coordinate, one has to query Ω(qk2) coordinates. Thus, the query complexity of our local decoding is smaller for k = Ω(q). If we impose the same query complexity constraint on both algorithm, our local decoding algorithm yields smaller error probability when k = Ω(qq). In addition, our local decoding is efficient, i.e., the decoding complexity is Poly(k, q). Construction of an interleaved codex is based on concatenation of a codex with a multiplication friendly pair, while the main tool to realize codex is based on algebraic function fields (or more precisely, algebraic geometry codes).

At CRYPTO 2018, Cramer et al. introduced a secret-sharing based protocol called SPD \(\mathbb {Z}_{2^k}\) that allows for secure multiparty computation (MPC) in the dishonest majority setting over the ring of integers modulo \(2^k\) , thus solving a long-standing open question in MPC about secure computation over rings in this setting. In this paper we study this problem in the information-theoretic scenario. More specifically, we ask the following question: Can we obtain information-theoretic MPC protocols that work over rings with comparable efficiency to corresponding protocols over fields? We answer this question in the affirmative by presenting an efficient protocol for robust Secure Multiparty Computation over \(\mathbb {Z}/p^{k}\mathbb {Z}\) (for any prime p and positive integer k ) that is perfectly secure against active adversaries corrupting a fraction of at most 1/3 players, and a robust protocol that is statistically secure against an active adversary corrupting a fraction of at most 1/2 players.

Multiplicative linear secret sharing is a fundamental notion in the area of secure multiparty computation and, since recently, in the area of two-party cryptography as well. In a nutshell, this notion guarantees that the product of two secrets is obtained as a linear function of the vector consisting of the coordinatewise product of two respective share-vectors. This paper focuses on the following foundational question, which is novel to the best of our knowledge. Suppose we abandon the latter linearity condition and instead require that this product is obtained by some, not-necessarily-linear “product reconstruction function.” Is the resulting notion equivalent to multiplicative linear secret sharing? We show the (perhaps somewhat counterintuitive) result that this relaxed notion is strictly more general. Concretely, fix a finite field ${\mathbb F}_q$ as the base field over which linear secret sharing is considered. Then we show there exists an (exotic) linear secret sharing scheme with an unbounded number of players $n$ such that it has $t$-privacy with $t = \Omega(n)$ and such that it does admit a product reconstruction function, yet this function is necessarily nonlinear. In addition, we determine the minimum number of players for which those exotic schemes exist. Our proof is based on combinatorial arguments involving quadratic forms. It extends to similar separation results for important variations, such as strongly multiplicative secret sharing.

We provide a generic framework that, with the help of a preprocessing phase that is independent of the inputs of the users, allows an arbitrary number of users to securely outsource a computation to two non-colluding external servers. Our approach is shown to be provably secure in an adversarial model where one of the servers may arbitrarily deviate from the protocol specification, as well as employ an arbitrary number of dummy users. We use these techniques to implement a secure recommender system based on collaborative filtering that becomes more secure, and significantly more efficient than previously known implementations of such systems, when the preprocessing efforts are excluded. We suggest different alternatives for preprocessing, and discuss their merits and demerits.

Given a linear code C, one can define the dth power of C as the span of all componentwise products of d elements of C. A power of C may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code typically fill the whole space? We give a positive answer, for codes of dimension k and length roughly (1/2)k2or smaller. Moreover, the convergence speed is exponential if the difference k(k+1)/2-n is at least linear in k. The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros.

The Ihara limit (or constant) A(q) has been a central problem of study in the asymptotic theory of global function fields (or equivalently, algebraic curves over finite fields). It addresses global function fields with many rational points and, so far, most applications of this theory do not require additional properties. Motivated by recent applications, we require global function fields with the additional property that their zero class divisor groups contain at most a small number of d -torsion points. We capture this with the notion of torsion limit, a new asymptotic quantity for global function fields. It seems that it is even harder to determine values of this new quantity than the Ihara constant. Nevertheless, some nontrivial upper bounds are derived. Apart from this new asymptotic quantity and bounds on it, we also introduce Riemann-Roch systems of equations. It turns out that this type of equation system plays an important role in the study of several other problems in each of these areas: arithmetic secret sharing, symmetric bilinear complexity of multiplication in finite fields, frameproof codes, and the theory of error correcting codes. Finally, we show how our new asymptotic quantity, our bounds on it and Riemann-Roch systems can be used to improve results in these areas.

We consider the class of secret sharing schemes where there is no a priori bound on the number of players n but where each of the n share-spaces has fixed cardinality q. We show two fundamental lower bounds on the threshold gap of such schemes. The threshold gap g is defined as r-t, where r is minimal and t is maximal such that the following holds: for a secret with arbitrary a priori distribution, each r-subset of players can reconstruct this secret from their joint shares without error ( r-reconstruction) and the information gain about the secret is nil for each t-subset of players jointly ( t-privacy). Our first bound, which is completely general, implies that if , then g ≥ [( n-t+1)/q] independently of the cardinality of the secret-space. Our second bound pertains to \BBF q-linear schemes with secret-space \BBF qk( k ≥ 2). It improves the first bound when k is large enough. Concretely, it implies that g ≥ [( n-t+1)/ q]+f(q,k,t,n), for some function f that is strictly positive when k is large enough. Moreover, also in the \BBF q-linear case, bounds on the threshold gap independent of t or r are obtained by additionally employing a dualization argument. As an application of our results, we answer an open question about the asymptotics of arithmetic secret sharing schemes and prove that the asymptotic optimal corruption tolerance rate is strictly smaller than 1.

In this invited talk,1we introduce the notion of arithmetic codex, or codex for short. It encompasses several well-established notions from cryptography (arithmetic secret sharing schemes, which enjoy additive as well as multiplicative properties) and algebraic complexity theory (bilinear complexity of multiplication) in a natural mathematical framework. Arithmetic secret sharing schemes have important applications to secure multi-party computation and even to two-party cryptography. Interestingly, several recent applications to two-party cryptography rely crucially on the existing results on “asymptotically good families” of suitable such schemes. Moreover, the construction of these schemes requires asymptotically good towers of function fields over finite fields: no elementary (probabilistic) constructions are known in these cases. Besides introducing the notion, we discuss some of the constructions, as well as some limitations.

In 1986, D. V. Chudnovsky and G. V. Chudnovsky first employed algebraic curves over finite fields to construct bilinear multiplication algorithms implicitly through supercodes introduced by Shparlinski-Tsfasman-Vladuţ, or equivalently, multiplication-friendly codes that we will introduce in this paper. This idea was further developed by Shparlinski-Tsfasman-Vladuţ in order to study the asymptotic behavior of multiplication complexity in extension fields. Later on, Ballet et al. further investigated the method and obtained some improvements. Recently, Ballet and Pieltant made use of curves over an extension field of to obtain an improvement on the complexity of multiplications in extensions of the binary field. In this paper, we develop the multiplication-friendly splitting technique and then apply this technique to study asymptotic behavior of multiplications in extension fields. By combining this with the idea of using algebraic function fields, we are able to improve further the asymptotic results of multiplication complexity. In particular, the improvement for small fields such as the binary and ternary fields is substantial.

Error-correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, the connections between codes, matroids, and a special class of secret sharing schemes, namely, multiplicative linear secret sharing schemes (LSSSs), are studied. Such schemes are known to enable multiparty computation protocols secure against general (nonthreshold) adversaries. Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. A property of strongly multiplicative LSSSs that could be useful in solving this problem is proved. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, it is shown that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, the considered open problem is to determine whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be restated in terms of representability of identically self-dual matroids by self-dual codes. A new concept is introduced, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. It is proved that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.

A new public-key encryption scheme, along with several variants, is proposed and analyzed. The scheme and its variants are quite practical and are proved secure against adaptive chosen ciphertext attack under standard intractability assumptions. These appear to be the first public-key encryption schemes in the literature that are simultaneously practical and provably secure.

We first study the problem of doing Verifiable Secret Sharing (VSS) information theoretically secure for a general access structure.We do it in the model where private channels between players and a broadcast channel is given, and where an active, adaptive adversary can corrupt any set of players not in the access structure.In particular, we consider the complexity of protocols for this problem, as a function of the access structure and the number of players.For all access structures where VSS is possible at all, we show that, up to a polynomial time black-box reduction, the complexity of adaptively secure VSS is the same as that of ordinary secret sharing (SS), where security is only required against a passive, static adversary.Previously, such a connection was only known for linear secret sharing and VSS schemes.We then show an impossibility result indicating that a similar equivalence does hot hold for Multiparty Computation (MPC): we show that even if protocols are given black-box access for free to an idealized secret sharing scheme secure for the access structure in question, it is not possible to handle all relevant access structures efficiently, not even if the adversary is passive and static.In other words, general MPC can only be black-box reduced efficiently to secret sharing if extra properties of the secret sharing scheme used (such as linearity) are assumed.

We describe and analyze a new digital signature scheme. The new scheme is quite efficient, does not require the signer to maintain any state, and can be proven secure against adaptive chosen message attack under a reasonable intractability assumption, the so-called strong RSA assumption. Moreover, a hash function can be incorporated into the scheme in such a way that it is also secure in the random oracle model under the standard RSA assumption.

We describe and analyze a new digital signature scheme. The new scheme is quite efficient, does not require the the signer to maintain any state, and can be proven secure against adaptive chosen message attack under a reasonable intractability assumption, the so-called strong RSA assumption. Moreover, a hash function can be incorporated into the scheme in such a way that it is also secure in the random oracle model under the standard RSA assumption.

We present a 4-move zero-knowledge proof system [21] for any NP language L, which allows showing that z E L with error probability y less than 2-k using com-Email: ivan~dainri.aau.dk ~BMic ReSear& in Computer Science, Center of the Danish National Research Foundation 1The meaning of 1 is that if the prover is unable tO SO1vean instance of a hard problem of size 1 before the protocol is finished, he can cheat with probability at most Z-k able.Thus, if we use k = n, the number of commitments required for the proof is linear in n.Finally, we present an application of our results that results in a protocol for oblivious transfer requiring O(1) commitments of size O(k) bits for a maximal cheating probability y of 2-k.Corresponding results for multipart y computations follow from this.'Here c1 is any positive constant and cz = 0(1/cl).