Source author record

Dongdai Lin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT Cryptography and Security math.CO math.NT Symbolic Computation Discrete Mathematics

Catalog footprint

Research overview

13works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

A class of three-weight and five-weight linear codes

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 three-weight and five-weight 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.

preprint2014arXiv

A Monomial-Oriented GVW for Computing Gröbner Bases

The GVW algorithm, presented by Gao et al., is a signature-based algorithm for computing Gröbner bases. In this paper, a variant of GVW is presented. This new algorithm is called a monomial-oriented GVW algorithm or mo-GVW algorithm for short. The mo-GVW 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 mo-GVW makes efforts to find the smallest signature that can generate this monomial. The mo-GVW algorithm also avoids generating J-pairs, and uses efficient methods of searching reducers and checking criteria. Thus, the mo-GVW algorithm has a better performance during practical implementations.

preprint2014arXiv

An Improvement over the GVW Algorithm for Inhomogeneous Polynomial Systems

The GVW algorithm is a signature-based algorithm for computing Gröbner bases. If the input system is not homogeneous, some J-pairs with higher signatures but lower degrees are rejected by GVW's Syzygy Criterion, instead, GVW have to compute some J-pairs 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 M-GVW, 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 M-GVW have been implemented in C++ and tested by many examples from boolean polynomial rings. The timings show M-GVW usually performs much better than the original GVW algorithm when mutant pairs are found. Besides, M-GVW is also compared with intrinsic Gröbner bases functions on Maple, Singular and Magma. Due to the efficient routines from the M4RI library, the experimental results show that M-GVW is very efficient.

preprint2014arXiv

Constructing Boolean Functions With Potential Optimal Algebraic Immunity Based on Additive Decompositions of Finite Fields

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 Tu-Deng 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 Tu-Deng 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.

preprint2014arXiv

Distribution properties of compressing sequences derived from primitive sequences modulo odd prime powers

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 $α(t)=k$ , where $\underlineα$ 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$ .

preprint2014arXiv

Generalized Hamming Weights of Irreducible Cyclic Codes

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.

preprint2014arXiv

On constructing complete permutation polynomials over finite fields of even characteristic

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.

preprint2014arXiv

On the distinctness of binary sequences derived from $2$ -adic expansion of m-sequences over finite prime fields

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, p-1\}$ 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 m-sequences 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}$ .

preprint2013arXiv

Complete permutation polynomials induced from complete permutations of subfields

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.

preprint2013arXiv

New constructions of quaternary bent functions

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 semi-bent functions in polynomial forms are derived. This work generalizes the recent work of N. Li, X. Tang and T. Helleseth.

preprint2011arXiv

Ergodic Theory Over ${\F}_2[[T]]$

In cryptography and coding theory, it is important to study the pseudo-random sequences and the ergodic transformations. We already have the 1-Lipshitz 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.

preprint2011arXiv

Linear Relation on General Ergodic T-Function

We find linear (as well as quadratic) relations in a very large class of T-functions. The relations may be used in analysis of T-function-based stream ciphers.

preprint2009arXiv

Fast Algebraic Attacks and Decomposition of Symmetric Boolean Functions

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Dongdai Lin

Research overview

Is this your work?

13 publications

A class of three-weight and five-weight linear codes

A Monomial-Oriented GVW for Computing Gröbner Bases

An Improvement over the GVW Algorithm for Inhomogeneous Polynomial Systems

Constructing Boolean Functions With Potential Optimal Algebraic Immunity Based on Additive Decompositions of Finite Fields

Distribution properties of compressing sequences derived from primitive sequences modulo odd prime powers

Generalized Hamming Weights of Irreducible Cyclic Codes

On constructing complete permutation polynomials over finite fields of even characteristic

On the distinctness of binary sequences derived from $2$ -adic expansion of m-sequences over finite prime fields

Complete permutation polynomials induced from complete permutations of subfields

New constructions of quaternary bent functions

Ergodic Theory Over ${\F}_2[[T]]$

Linear Relation on General Ergodic T-Function

Fast Algebraic Attacks and Decomposition of Symmetric Boolean Functions

See the researcher in context

Building this map preview

Dongdai Lin

Research overview

Is this your work?

13 publications

A class of three-weight and five-weight linear codes

A Monomial-Oriented GVW for Computing Gröbner Bases

An Improvement over the GVW Algorithm for Inhomogeneous Polynomial Systems

Constructing Boolean Functions With Potential Optimal Algebraic Immunity Based on Additive Decompositions of Finite Fields

Distribution properties of compressing sequences derived from primitive sequences modulo odd prime powers

Generalized Hamming Weights of Irreducible Cyclic Codes

On constructing complete permutation polynomials over finite fields of even characteristic

On the distinctness of binary sequences derived from 222-adic expansion of m-sequences over finite prime fields

Complete permutation polynomials induced from complete permutations of subfields

New constructions of quaternary bent functions

Ergodic Theory Over ${\F}_2[[T]]$

Linear Relation on General Ergodic T-Function

Fast Algebraic Attacks and Decomposition of Symmetric Boolean Functions

See the researcher in context

Building this map preview

On the distinctness of binary sequences derived from $2$ -adic expansion of m-sequences over finite prime fields