Search

Since the seminal work of Garg eti¾?al. FOCS'13 in which they proposed the first candidate construction for indistinguishability obfuscation iO for short, iO has become a central cryptographic primitive with numerous applications. The security of the proposed construction of Garg eti¾?al. and its variants are proved based on multi-linear maps Garg eti¾?al. Eurocrypt'13 and their idealized model called the graded encoding model Brakerski and Rothblum TCC'14 and Barak eti¾?al. Eurocrypt'14. Whether or not iO could be based on standard and well-studied hardness assumptions has remain an elusive open question. In this work we prove lower bounds on the assumptions that imply iO in a black-box way, based on computational assumptions. Note that any lower bound for iO needs to somehow rely on computational assumptions, because if $$\mathbf {P}= \mathbf {NP}$$ then statistically secure iO does exist. Our results are twofold: 1.There is no fully black-box construction of iO from exponentially secure collision-resistant hash functions unless the polynomial hierarchy collapses. Our lower bound extends to separate iO from any primitive implied by a random oracle in a black-box way.2.Let $${\mathcal P}$$ be any primitive that exists relative to random trapdoor permutations, the generic group model for any finite abelian group, or degree-O1 graded encoding model for any finite ring. We show that achieving a black-box construction of iO from $${\mathcal P}$$ is as hard as basing public-key cryptography on one-way functions. In particular, for any such primitive $${\mathcal P}$$ we present a constructive procedure that takes any black-box construction of iO from $${\mathcal P}$$ and turns it into a construction of semantically secure public-key encryption form any one-way functions. Our separations hold even if the construction of iO from $${\mathcal P}$$ is semi-black-box Reingold, Trevisan, and Vadhan, TCC'04 and the security reduction could access the adversary in a non-black-box way.

Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class ACC0. They are also precisely the functions computable efficiently by programs over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.

Various information-theoretically secure Multi-Party Computation (MPC) schemes have been proposed over some finite field F or some finite ring R. A function f that can be evaluated on MPC is usually represented by boolean or arithmetic circuits. In general, the function class that have constant-depth arithmetic circuit is studied. Additionally, some literatures show that one can represent any formulas and branching program by low-degree randomizing polynomials, which can be evaluated in constant rounds. However, these approaches have their limitations, and it is not easy to construct the optimal branching program for a complex function. Therefore, it is not obvious how to efficiently perform oblivious sort in constant rounds, but oblivious sort is one of the most important primitive protocols for MPC in practice. In this paper, we are going to show several constant-round 0-error oblivious sorting algorithms, together with some useful applications.

This paper considers the problem of efficiently transmitting quantum states through a network. It has been known for some time that without additional assumptions it is impossible to achieve this task perfectly in general -- indeed, it is impossible even for the simple butterfly network. As additional resource we allow free classical communication between any pair of network nodes. It is shown that perfect quantum network coding is achievable in this model whenever classical network coding is possible over the same network when replacing all quantum capacities by classical capacities. More precisely, it is proved that perfect quantum network coding using free classical communication is possible over a network with k source-target pairs if there exists a classical linear (or even vector-linear) coding scheme over a finite ring. Our proof is constructive in that we give explicit quantum coding operations for each network node. This paper also gives an upper bound on the number of classical communication required in terms of k , the maximal fan-in of any network node, and the size of the network.

We address the concept of "minimal polynomial encoder" for finite support linear convolutional codes over ${\mathbb Z}_{p^r}$. These codes can be interpreted as polynomial modules which enables us to apply results from the 2007-paper [8] to introduce the notions of "p-encoder" and "minimal p-encoder". Here the latter notion is the ring analogon of a row reduced polynomial encoder from the field case. We show how to construct a minimal trellis representation of a delay-free finite support convolutional code from a minimal p-encoder. We express its number of trellis states in terms of a degree invariant of the code. The latter expression generalizes the wellknown expression in terms of the degree of a delay-free finite support convolutional code over a field to the ring case. The results are also applicable to block trellis realization of polynomial block codes over ${\mathbb Z}_{p^r}$, such as CRC codes over ${\mathbb Z}_{p^r}$.

In this paper we first examine the computational complexity of the problem LCON defined as follows: given a matrix A and a column vector b over ℤ, determine if Ax=b is a feasible system of linear equations over ℤq. Here q is also given as part of the input by its prime factorization $q = p^{e_1}_{1}p^{e_2}_{2}p^{e_k}_{k}$, such that each $p^{e_i}_{i}$ is tiny (i.e. given in unary). In [MC87] an NC3 algorithm is given for this problem. We show that in fact the problem can be solved in randomized NC2. More precisely, we show that LCON is in the nonuniform class LGapL/poly. Combined with the hardness of LCON for LGapL, we have a fairly tight characterization of the complexity of LCON in terms of logspace counting classes. We prove the same upper bound results for the problem of testing feasibility of Ax=b over finite rings R with unity, where R is given as part of the input as a table.

The doctrine in cryptology is that the algorithm of encryption is known to the adversary (Eve) and that the only thing that is kept secret is the key, which normally is a bitsequence or a sequence of natural numbers or elements of a finite ring (e.g. a residue ring or a finite field). Mostly, such key sequences are produced by an algorithmic generator (i.e., they are socalled pseudo-random numbers), since these offer the following benefits: the sequence of numbers can be reproduced for debugging and testing; no special hardware is necessary; a large quantity of random numbers can be produced in a short time.

Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite fields. We are motivated by two limitations of these techniques: - GENERALITY. Existing protocols do not apply to computation over more general algebraic structures (except via a brute-force simulation of computation in these structures). - EFFICIENCY. The best known constant-round protocols do not efficiently scale even to the case of large finite fields. Our contribution goes in these two directions. First, we propose a basis for unconditionally secure MPC over an arbitrary finite ring, an algebraic object with a much less nice structure than a field, and obtain efficient MPC protocols requiring only a black-box access to the ring operations and to random ring elements. Second, we extend these results to the constant-round setting, and suggest efficiency improvements that are relevant also for the important special case of fields. We demonstrate the usefulness of the above results by presenting a novel application of MPC over (non-field) rings to the round-efficient secure computation of the maximum function.

This paper gives new examples that exploit the idea of using sparse polynomials with restricted coefficients over a finite ring for designing fast, reliable cryptosystems and identification schemes.

Let M be a finite left module over a finite ring R with identity, u be a linear recurring sequence over M. In the previous paper of the author [1] an algorithm was stated which finds a minimal polynomial μ(x) ∈ R[x] of a finite sequence u(\(u(\overline {0,l - 1} )\)). In this paper we show that for sufficiently large l the polynomials developed in this algorithm form a generating system for the annihilator An(u) ⊑ R[x] of the sequence u. This result can also be applied to a sequence over a right module, over a bimodule, and over a ring R.

With a view toward applications to number theory, coding theory, and combinatorics, we consider in this article Gauss sums defined over finite rings, especialy those arising from p-adic fields. The principal theme is the application of the classical method of stationary phase in a number theoretic context. After surveying the well known results of Kummer, Lamprecht, and Dwork, we indicate some generalizations which include and extend certain results of Hua in the one variable case, and Igusa in the case of several variables. In general, Gauss sums over finite rings possess asymptotic expansions whose leading term can be expressed in terms of quadratic Gauss sums. The principal tool turns out to be an arithmetic analogue of Morse’s Lemma.

A module M R is semisimple in case M is a direct sum Ц i ∈ I M i of a family of simple submodules {M i | i ∈ I}. A ring R is semisimple in case R R is. We have seen that any simple Artinian ring is semisimple. Finite ring products of simple Artinian rings are also semisimple. The Wedderburn-Artin theorem implies the converse: Every semisimple ring is isomorphic to a finite product of full matrix rings of various degrees over various fields. These rings are also characterized by the Wedderburn-Artin theorem (8.8) as right Artinian rings with no nilpotent ideals. (The condition is right-left symmetric.)