The Continued Fraction Algorithm and Regulator for Quadratic Function Fields of Characteristic 2

The continued fraction expansion and infrastructure for quadratic congruence function fields of odd characteristic have been well studied. Recently, these ideas have even been used to produce cryptosystems. Much less is known concerning the continued fraction expansion and infrastructure for quadratic function fields of even characteristic. We will explore these ideas, and show that the situation is very similar to the odd characteristic case. This exploration will result in a method for computing the regulator for quadratic function fields of characteristic 2.     

Les formes bilin��aires et quadratiques bonnes de hauteur 2 en caract��ristique 2

Our aim is to give a complete classification of bilinear and quadratic forms which are good of height 2 over a field of characteristic 2, i.e., those whose anisotropic parts over their function fields are similar to bilinear Pfister forms which are definable over the ground field. We include other related results.     

Average values of L-functions in characteristic two

Gauss made two conjectures about average values of class numbers of orders in quadratic number fields, later on proven by Lipschitz and Siegel. A version for function fields of odd characteristic was established by Hoffstein and Rosen. In this paper, we extend their results to the case of even characteristic. More precisely, we obtain formulas of average values of L-functions associated to orders in quadratic function fields over a constant field of characteristic two, and then derive formulas of average class numbers of these orders.     

Factorization of involutions in characteristic two orthogonal groups: An application of the Jordan form to group theory

This paper uses the theory of the Jordan canonical form for a matrix and the theory of orthogonal sums of isometries in metric vector spaces (quadratic spaces) in order to prove a theorem on the factorization of involutions in the orthogonal groups of metric vector spaces over fields of characteristic two. Using this theorem, a classification scheme for such involutions is devised. This scheme is similar to the scheme for involutions when the field is of characteristic not equal of two.     

On class number relations in characteristic two

A theorem of F. Hirzebruch relates continued fractions to class numbers of quadratic number fields. A version for function fields of odd characteristic was established by D. R. Hayes and C. D. González. We present here a complete treatment of the even characteristic theory, in particular, two class number relations involving continued fractions are derived, one of which is an analogue of the Hirzebruch relation in characteristic 2. Research partially supported by National Science Council, Republic of China.     

Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic

We investigate in this paper the security of HFE and Multi-HFE schemes as well as their minus and embedding variants. Multi-HFE is a generalization of the well-known HFE schemes. The idea is to use a multivariate quadratic system—instead of a univariate polynomial in HFE—over an extension field as a private key. According to the authors, this should make the classical direct algebraic (message-recovery) attack proposed by Faugère and Joux on HFE no longer efficient against Multi-HFE. We consider here the hardness of the key-recovery in Multi-HFE and its variants, but also in HFE (both for odd and even characteristic). We first improve and generalize the basic key recovery proposed by Kipnis and Shamir on HFE. To do so, we express this attack as matrix/vector operations. In one hand, this permits to improve the basic Kipnis-Shamir (KS) attack on HFE. On the other hand, this allows to generalize the attack on Multi-HFE. Due to its structure, we prove that a Multi-HFE scheme has much more equivalent keys than a basic HFE. This induces a structural weakness which can be exploited to adapt the KS attack against classical modifiers of multivariate schemes such as minus and embedding. Along the way, we discovered that the KS attack as initially described cannot be applied against HFE in characteristic 2. We have then strongly revised KS in characteristic 2 to make it work. In all cases, the cost of our attacks is related to the complexity of solving MinRank. Thanks to recent complexity results on this problem, we prove that our attack is polynomial in the degree of the extension field for all possible practical settings used in HFE and Multi-HFE. This makes then Multi-HFE less secure than basic HFE for equally-sized keys. As a proof of concept, we have been able to practically break the most conservative proposed parameters of multi-HFE in few days (256 bits security broken in 9 days).     

A Signature Scheme Based on the Intractability of Computing Roots

We present RDSA, a variant of the DSA signature scheme, whose security is based on the intractability of extracting roots in a finite abelian group. We prove that RDSA is secure against an adaptively chosen message attack in the random oracle model if and only if computing roots in the underlying group is intractable. We report on a very efficient implementation of RDSA in the class group of imaginary quadratic orders. We also show how to construct class groups of algebraic number fields of degree < 2 in which RDSA can be implemented.     

The genus fields of Kummer function fields

In this paper, we give a definition of genus field of function field with one variable over finite fields. And we explicitly describe the genus fields of Kummer function fields. For quadratic function fields case, our results are analogous to the genus fields of quadratic number fields.     

Ramification of Valuations and Local Rings in Positive Characteristic

In characteristic zero, local monomialization is true along any valuation. However, we have recently shown that local monomialization is not always true in positive characteristic, even in two dimensional algebraic function fields. In this paper we show that local monomialization is true for defectless extensions of two dimensional excellent local rings, extending an earlier result of Piltant and the author for two dimensional algebraic function fields over an algebraically closed field. We also give theorems showing that in many cases there are good stable forms of the extension of associated graded rings in a finite separable field extension.     

Multiround Unconditionally Secure Authentication

Authentication codes are used to protect communication against a malicious adversary. In this paper we investigate unconditionally secure multiround authentication schemes. In a multiround scheme a message is authenticated by passing back and forth several codewords between the sender and receiver. We define a multiround authentication model and show how to calculate the probability of a successful attack for this model. We prove the security for a 3-round scheme and give a construction for the 3-round scheme based on Reed-Solomom codes. This construction has a very small key size for even extremely large messages. Furthermore, a secure scheme for an arbitrary number of rounds is given. We give a new upper bound for the keys size of an n-round scheme.     

Cryptography in Quadratic Function Fields

We describe severalcryptographic schemes in quadratic function fields of odd characteristic.In both the real and the imaginary representation of such a field,we present a Diffie-Hellman-like key exchange protocol as wellas a public-key cryptosystem and a signature scheme of ElGamaltype. Several of these schemes are improvements of systems previouslyfound in the literature, while others are new. All systems arebased on an appropriate discrete logarithm problem. In the imaginarysetting, this is the discrete logarithm problem in the idealclass group of the field, or equivalently, in the Jacobian ofthe curve defining the function field. In the real case, theproblem in question is the task of computing distances in theset of reduced principal ideals, which is a monoid under a suitableoperation. Currently, the best general algorithms for solvingboth discrete logarithm problems are exponential (subexponentialonly in fields of high genus), resulting in a possibly higherlevel of security than that of conventional discrete logarithmbased schemes.     

Strongly Real Special 2-Groups

Strongly real groups and totally orthogonal groups form two important subclasses of real groups. In this article we give a characterization of strongly real special 2-groups. This characterization is in terms of quadratic maps over fields of characteristic 2. We then provide examples of groups which are in one subclass and not the other. It is a conjecture of Tiep that such examples are not possible for finite simple groups.     

On a class of fields admitting only cyclic extensions of prime power degree

We will give three characterizations of such fields and an application to quadratic forms in characteristic 2. This work has been supported by D.I.U.C. (Dirección de Investigaciones de la Pontificia Universidad Católica de Chile).     

Computing discrete logarithms in real quadratic congruence function fields of large genus

The discrete logarithm problem in various finite abelian groups is the basis for some well known public key cryptosystems. Recently, real quadratic congruence function fields were used to construct a public key distribution system. The security of this public key system is based on the difficulty of a discrete logarithm problem in these fields. In this paper, we present a probabilistic algorithm with subexponential running time that computes such discrete logarithms in real quadratic congruence function fields of sufficiently large genus. This algorithm is a generalization of similar algorithms for real quadratic number fields.

     

New Imperfect Conjugate Gradient Algorithm

We present a method which generates conjugate search directions and maintains the quadratic convergence property, when applied to a quadratic function, even when the line searches are not exact. The method is similar to that given by Dixon, but needs one less vector store. When the method is applied to a number of general functions of different dimensionality, results show the efficiency of the method.     

Amorphic association schemes with negative Latin square-type graphs

Applying results from partial difference sets, quadratic forms, and recent results of Brouwer and Van Dam, we construct the first known amorphic association scheme with negative Latin square-type graphs and whose underlying set is a nonelementary abelian 2-group. We give a simple proof of a result of Hamilton that generalizes Brouwer's result. We use multiple distinct quadratic forms to construct amorphic association schemes with a large number of classes.     

On zeros of characteristic p zeta function

The location and multiplicity of the zeros of zeta functions encode interesting arithmetic information. We study the characteristic p zeta function of Goss. We focus on “trivial” zeros and prove a theorem on zeros at negative integers, showing more vanishing than that suggested by naive analogies. We also compute some concrete examples providing the extra vanishing, when the class number is more than one.Finally, we give an application of these results to the non-vanishing of certain class group components for cyclotomic function fields. In particular, we give examples of function fields, where all the primes of degree more than two are “irregular”, in the sense of the Drinfeld-Hayes cyclotomic theory.     

实二次域的一个同余式

本文证明了关于实二次域的类数和某类特征和的同余式,同时给出某类实二次域的类数可除性的一个判别法则．     

Chorded complexes and a necessary condition for a monomial ideal to have a linear resolution

In this paper we extend one direction of Fröberg?s theorem on a combinatorial classification of quadratic monomial ideals with linear resolutions. We do this by generalizing the notion of a chordal graph to higher dimensions with the introduction of d-chorded and orientably-d-cycle-complete simplicial complexes. We show that a certain class of simplicial complexes, the d-dimensional trees, correspond to ideals having linear resolutions over fields of characteristic 2 and we also give a necessary combinatorial condition for a monomial ideal to be componentwise linear over all fields.     

Horn函数可满足性的复杂性(英文)

本文证明了 Ｈｏｒｎ函数的极大可满足性即使是限制在如下两种情况中的任何一种也是 ＭＡＸ ＳＮＰ困难的,第一种情况是每个公式都是二次的,第二种是公式中每一个非单位子句有且只有一个补元,这意味着在这档两种情况下没有多项式的近似算法,除非Ｐ＝ＮＰ．