
At EUROCRYPT 2011, Gentry and Halevi implemented a variant of Gentry's fully
homomorphic encryption scheme. The core part in their key generation is to
generate an odddeterminant ideal lattice having a particular type of Hermite
Normal Form. However, they did not give a rigorous proof for the correctness.
We present a better key generation algorithm, improving their algorithm from
two aspects.
We show how to deterministically generate ideal lattices with odd
determinant, thus increasing the success probability close to 1.
We give a rigorous proof for the correctness. To be more specific, we
present a simpler condition for checking whether the ideal lattice has the
desired Hermite Normal Form. Furthermore, our condition can be checked more
efficiently.
As a result, our key generation is about 1.5 times faster. We also give
experimental results supporting our claims. Our optimizations are based on the
properties of ideal lattices, which might be of independent interests.

In this paper, we construct some new classes of complete permutation
monomials with exponent $d=\frac{q^n1}{q1}$ using AGW criterion (a special
case). This proves two recent conjectures in [Wuetal2] and extends some of
these recent results to more general $n$'s.

For binary $[n,k,d]$ linear locally repairable codes (LRCs), two new upper
bounds on $k$ are derived. The first one applies to LRCs with disjoint local
repair groups, for general values of $n,d$ and locality $r$, containing some
previously known bounds as special cases. The second one is based on solving an
optimization problem and applies to LRCs with arbitrary structure of local
repair groups. Particularly, an explicit bound is derived from the second bound
when $d\geq 5$. A specific comparison shows this explicit bound outperforms the
CadambeMazumdar bound for $5\leq d\leq 8$ and large values of $n$. Moreover, a
construction of binary linear LRCs with $d\geq6$ attaining our second bound is
provided.

An improved characteristic set algorithm for solving Boolean polynomial
systems is proposed. This algorithm is based on the idea of converting all the
polynomials into monic ones by zero decomposition, and using additions to
obtain pseudoremainders. Three important techniques are applied in the
algorithm. The first one is eliminating variables by new generated linear
polynomials. The second one is optimizing the strategy of choosing polynomial
for zero decomposition. The third one is to compute addremainders to eliminate
the leading variable of new generated monic polynomials. By analyzing the depth
of the zero decomposition tree, we present some complexity bounds of this
algorithm, which are lower than the complexity bounds of previous
characteristic set algorithms. Extensive experimental results show that this
new algorithm is more efficient than previous characteristic set algorithms for
solving Boolean polynomial systems.

Recently, linear codes with few weights have been constructed and extensively
studied. In this paper, for an odd prime p, we determined the complete weight
enumerator of two classes of pary linear codes constructed from defining set.
Results show that the codes are at almost sevenweight linear codes and they
may have applications in secret sharing schemes.

Linear codes have been an interesting subject of study for many years.
Recently, linear codes with few weights have been constructed and extensively
studied. In this paper, for an odd prime p, a class of threeweight linear
codes over Fp are constructed. The weight distributions of the linear codes are
settled. These codes have applications in authentication codes, association
schemes and data storage systems.

Recently, linear codes with few weights have been widely studied, since they
have applications in data storage systems, communication systems and consumer
electronics. In this paper, we present a class of threeweight and fiveweight
linear codes over Fp, where p is an odd prime and Fp denotes a finite field
with p elements. The weight distributions of the linear codes constructed in
this paper are also settled. Moreover, the linear codes illustrated in the
paper may have applications in secret sharing schemes.

The generalized Hamming weight (GHW) $d_r(C)$ of linear codes $C$ is a
natural generalization of the minimum Hamming distance $d(C)(=d_1(C))$ and has
become one of important research objects in coding theory since Wei's originary
work [23] in 1991. In this paper two general formulas on $d_r(C)$ for
irreducible cyclic codes are presented by using Gauss sums and the weight
hierarchy $\{d_1(C), d_2(C), \ldots, d_k(C)\}$ $(k=\dim C)$ are completely
determined for several cases.

In this paper, a construction of complete permutation polynomials over finite
fields of even characteristic proposed by Tu et al. recently is generalized in
a recursive manner. Besides, several classes of complete permutation
polynomials are derived by computing compositional inverses of known ones.

The GVW algorithm, presented by Gao et al., is a signaturebased algorithm
for computing Gr\"obner bases. In this paper, a variant of GVW is presented.
This new algorithm is called a monomialoriented GVW algorithm or moGVW
algorithm for short. The moGVW algorithm presents a new frame of GVW and
regards {\em labeled monomials} instead of {\em labeled polynomials} as basic
elements of the algorithm. Being different from the original GVW algorithm, for
each labeled monomial, the moGVW makes efforts to find the smallest signature
that can generate this monomial. The moGVW algorithm also avoids generating
Jpairs, and uses efficient methods of searching reducers and checking
criteria. Thus, the moGVW algorithm has a better performance during practical
implementations.

The GVW algorithm is a signaturebased algorithm for computing Gr\"obner
bases. If the input system is not homogeneous, some Jpairs with higher
signatures but lower degrees are rejected by GVW's Syzygy Criterion, instead,
GVW have to compute some Jpairs with lower signatures but higher degrees.
Consequently, degrees of polynomials appearing during the computations may
unnecessarily grow up higher and the computation become more expensive. In this
paper, a variant of the GVW algorithm, called MGVW, is proposed and mutant
pairs are introduced to overcome inconveniences brought by inhomogeneous input
polynomials. Some techniques from linear algebra are used to improve the
efficiency. Both GVW and MGVW have been implemented in C++ and tested by many
examples from boolean polynomial rings. The timings show MGVW usually performs
much better than the original GVW algorithm when mutant pairs are found.
Besides, MGVW is also compared with intrinsic Gr\"obner bases functions on
Maple, Singular and Magma. Due to the efficient routines from the M4RI library,
the experimental results show that MGVW is very efficient.

Let $p$ be an odd prime with $2$adic expansion $\sum_{i=0}^kp_i\cdot2^i$.
For a sequence $\underline{a}=(a(t))_{t\ge 0}$ over $\mathbb{F}_{p}$, each
$a(t)$ belongs to $\{0,1,\ldots, p1\}$ and has a unique $2$adic expansion
$$a(t)=a_0(t)+a_1(t)\cdot 2+\cdots+a_{k}(t)\cdot2^k,$$ with $a_i(t)\in\{0,
1\}$. Let $\underline{a_i}$ denote the binary sequence $(a_i(t))_{t\ge 0}$ for
$0\le i\le k$. Assume $i_0$ is the smallest index $i$ such that $p_{i}=0$ and
$\underline{a}$ and $\underline{b}$ are two different msequences generated by
a same primitive characteristic polynomial over $\mathbb{F}_p$. We prove that
for $i\neq i_0$ and $0\le i\le k$, $\underline{a_i}=\underline{b_i}$ if and
only if $\underline{a}=\underline{b}$, and for $i=i_0$,
$\underline{a_{i_0}}=\underline{b_{i_0}}$ if and only if
$\underline{a}=\underline{b}$ or $\underline{a}=\underline{b}$. Then the
period of $\underline{a_i}$ is equal to the period of $\underline{a}$ if $i\ne
i_0$ and half of the period of $\underline{a}$ if $i=i_0$. We also discuss a
possible application of the binary sequences $\underline{a_i}$.

We propose a general approach to construct cryptographic significant Boolean
functions of $(r+1)m$ variables based on the additive decomposition
$\mathbb{F}_{2^{rm}}\times\mathbb{F}_{2^m}$ of the finite field
$\mathbb{F}_{2^{(r+1)m}}$, where $r$ is odd and $m\geq3$. A class of unbalanced
functions are constructed first via this approach, which coincides with a
variant of the unbalanced class of generalized TuDeng functions in the case
$r=1$. This class of functions have high algebraic degree, but their algebraic
immunity does not exceeds $m$, which is impossible to be optimal when $r>1$. By
modifying these unbalanced functions, we obtain a class of balanced functions
which have optimal algebraic degree and high nonlinearity (shown by a lower
bound we prove). These functions have optimal algebraic immunity provided a
combinatorial conjecture on binary strings which generalizes the TuDeng
conjecture is true. Computer investigations show that, at least for small
values of number of variables, functions from this class also behave well
against fast algebraic attacks.

Let $\underline{a}$ and $\underline{b}$ be primitive sequences over
$\mathbb{Z}/(p^e)$ with odd prime $p$ and $e\ge 2$. For certain compressing
maps, we consider the distribution properties of compressing sequences of
$\underline{a}$ and $\underline{b}$, and prove that
$\underline{a}=\underline{b}$ if the compressing sequences are equal at the
times $t$ such that $\alpha(t)=k$, where $\underline{\alpha}$ is a sequence
related to $\underline{a}$. We also discuss the $s$uniform distribution
property of compressing sequences. For some compressing maps, we have that
there exist different primitive sequences such that the compressing sequences
are $s$uniform. We also discuss that compressing sequences can be $s$uniform
for how many elements $s$.

We propose several techniques to construct complete permutation polynomials
of finite fields by virtue of complete permutations of subfields. In some
special cases, any complete permutation polynomials over a finite field can be
used to construct complete permutations of certain extension fields with these
techniques. The results generalize some recent work of several authors.

In this paper, a new construction of quaternary bent functions from
quaternary quadratic forms over Galois rings of characteristic 4 is proposed.
Based on this construction, several new classes of quaternary bent functions
are obtained, and as a consequence, several new classes of quadratic binary
bent and semibent functions in polynomial forms are derived. This work
generalizes the recent work of N. Li, X. Tang and T. Helleseth.

We find linear (as well as quadratic) relations in a very large class of
Tfunctions. The relations may be used in analysis of Tfunctionbased stream
ciphers.

In cryptography and coding theory, it is important to study the pseudorandom
sequences and the ergodic transformations. We already have the 1Lipshitz
ergodic theory over ${\Z}_2$ established by V. Anashin and others. In this
paper we present an ergodic theory over ${\F}_2[[T]]$ and some ideas which
might be very useful in applications.

Algebraic and fast algebraic attacks are power tools to analyze stream
ciphers. A class of symmetric Boolean functions with maximum algebraic immunity
were found vulnerable to fast algebraic attacks at EUROCRYPT'06. Recently, the
notion of AAR (algebraic attack resistant) functions was introduced as a
unified measure of protection against both classical algebraic and fast
algebraic attacks. In this correspondence, we first give a decomposition of
symmetric Boolean functions, then we show that almost all symmetric Boolean
functions, including these functions with good algebraic immunity, behave badly
against fast algebraic attacks, and we also prove that no symmetric Boolean
functions are AAR functions. Besides, we improve the relations between
algebraic degree and algebraic immunity of symmetric Boolean functions.

We consider a type of zeroknowledge protocols that are of interest for their
practical applications within networks like the Internet: efficient
zeroknowledge arguments of knowledge that remain secure against concurrent
maninthemiddle attacks. In an effort to reduce the setup assumptions
required for efficient zeroknowledge arguments of knowledge that remain secure
against concurrent maninthemiddle attacks, we consider a model, which we
call the Authenticated PublicKey (APK) model. The APK model seems to
significantly reduce the setup assumptions made by the CRS model (as no trusted
party or honest execution of a centralized algorithm are required), and can be
seen as a slightly stronger variation of the Bare PublicKey (BPK) model from
\cite{CGGM,MR}, and a weaker variation of the registered publickey model used
in \cite{BCNP}. We then define and study maninthemiddle attacks in the APK
model. Our main result is a constantround concurrent nonmalleable
zeroknowledge argument of knowledge for any polynomialtime relation
(associated to a language in $\mathcal{NP}$), under the (minimal) assumption of
the existence of a oneway function family. Furthermore,We show timeefficient
instantiations of our protocol based on known numbertheoretic assumptions. We
also note a negative result with respect to further reducing the setup
assumptions of our protocol to those in the (unauthenticated) BPK model, by
showing that concurrently nonmalleable zeroknowledge arguments of knowledge
in the BPK model are only possible for trivial languages.

In this paper we resolve an open problem regarding resettable zero knowledge
in the bare publickey (BPK for short) model: Does there exist constant round
resettable zero knowledge argument with concurrent soundness for $\mathcal{NP}$
in BPK model without assuming \emph{subexponential hardness}? We give a
positive answer to this question by presenting such a protocol for any language
in $\mathcal{NP}$ in the bare publickey model assuming only
collisionresistant hash functions against \emph{polynomialtime} adversaries.