Source author record

Sze Ling Yeo

Sze Ling Yeo appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Discrete Mathematics Information Theory math.AC math.AG math.IT math.NT Symbolic Computation

Catalog footprint

What is connected

3works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2015arXiv

Notes on summation polynomials

In these short notes, we will show the following. Let F_q be a finite field and let E/\F_q be an elliptic curve. Let S_r be the rth summation/Semaev polynomial for E. Under an assumption, we show that it is NP-complete to check if S_r evaluates to zero on some input. Unconditionally, we prove a similar result for summation polynomials over singular curves. This suggests limitations in the usage of summation polynomials in for example algorithms to solve the elliptic curve discrete logarithm problem. Assume that q is a power of 2. We show that the Weil descent to F_2 of S_3 for ordinary curves in general has first fall degree 2, which is much lower than expected. The reason is the existence of a group morphism to F_2 which gives a linear polynomial after Weil descent. We want to raise awareness of its existence and raise doubt on certain Groebner basis heuristics which claim that the first fall degree is close to the degree of regularity. Furthermore, this morphism can be used to speed up the relation generation to solve the elliptic curve discrete logarithm problem.

preprint2015arXiv

On the last fall degree of zero-dimensional Weil descent systems

In this article we will discuss a new, mostly theoretical, method for solving (zero-dimensional) polynomial systems, which lies in between Gröbner basis computations and the heuristic first fall degree assumption and is not based on any heuristic. This method relies on the new concept of last fall degree. Let $k$ be a finite field of cardinality $q^n$ and let $k'$ be its subfield of cardinality $q$. Let $\mathcal{F} \subset k[X_0,\ldots,X_{m-1}]$ be a finite subset generating a zero-dimensional ideal. We give an upper bound of the last fall degree of the Weil descent system of $\mathcal{F}$, which depends on $q$, $m$, the last fall degree of $\mathcal{F}$, the degree of $\mathcal{F}$ and the number of solutions of $\mathcal{F}$, but not on $n$. This shows that such Weil descent systems can be solved efficiently if $n$ grows. In particular, we apply these results for multi-HFE and essentially show that multi-HFE is insecure. Finally, we discuss that the degree of regularity (or last fall degree) of Weil descent systems coming from summation polynomials to solve the elliptic curve discrete logarithm problem might depend on $n$, since such systems without field equations are not zero-dimensional.

preprint2010arXiv

New Constant-Weight Codes from Propagation Rules

This paper proposes some simple propagation rules which give rise to new binary constant-weight codes.