Group homomorphism | EPFL Graph Search

In mathematics, given two groups, (G, ∗) and (H, ·), a group homomorphism from (G, ∗) to (H, ·) is a function h : G → H such that for all u and v in G it holds that : h(u*v) = h(u) \cdot h(v) where the group operation on the left side of the equation is that of G and on the right side that of H. From this property, one can deduce that h maps the identity element eG of G to the identity element eH of H, : h(e_G) = e_H and it also maps inverses to inverses in the sense that : h\left(u^{-1}\right) = h(u)^{-1}. , Hence one can say that h "is compatible with the group structure". Older notations for the homomorphism h(x) may be xh or xh, though this may be confused as an index or a general subscript. In automata theory, sometimes homomorphisms are written to the right of their arguments without parentheses, so that h(x) becomes simply xh. In areas of mathematics where one considers groups endowed with additional structure, a h

Annihilating Polynomials for Quadratic Forms

Klaas-Tido Rühl

Let K be a field with char(K) ≠ 2. The Witt-Grothendieck ring (K) and the Witt ring W (K) of K are both quotients of the group ring ℤ[𝓖(K)], where 𝓖(K) := K*/(K*)2 is the square class group of K. Since ℤ[𝓖(K)] is integral, the same holds for (K) and W(K). The subject of this thesis is the study of annihilating polynomials for quadratic forms. More specifically, for a given quadratic form φ over K, we study polynomials P ∈ ℤ[X] such that P([φ]) = 0 or P({φ}) = 0. Here [φ] ∈ (K) denotes the isometry class and {φ} ∈ W(K) denotes the equivalence class of φ. The subset of ℤ[X] consisting of all annihilating polynomials for [φ], respectively {φ}, is an ideal, which we call the annihilating ideal of [φ], respectively {φ}. Chapter 1 is dedicated to the algebraic foundations for the study of annihilating polynomials for quadratic forms. First we study the general structure of ideals in ℤ[X], which later on allows us to efficiently determine complete sets of generators for annihilating ideals. Then we introduce a more natural setting for the study of annihilating polynomials for quadratic forms, i.e. we define Witt rings for groups of exponent 2. Both (K) and W(K) are Witt rings for the square class group 𝓖(K). Studying annihilating polynomials in this more general setting relieves us to a certain extent from having to distinguish between isometry and equivalence classes of quadratic forms. In Section 1.1 we study the structure of ideals in R[X], where R is a principal ideal domain. For an ideal I ⊂ R[X] there exist sets of generators, which can be obtained in a natural way by considering the leading coefficients of elements in I. These sets of generators are called convenient. By discarding super uous elements we obtain modest sets of generators, which under certain assumptions are minimal sets of generators for I. Let G be a group of exponent 2. In Section 1.2 we study annihilating polynomials for elements of ℤ[G]. With the help of the ring homomorphisms Hom(ℤ[G],ℤ) it is possible to completely classify annihilating polynomials for elements of ℤ[G]. Note that an annihilating polynomial for an element f ∈ ℤ[G] also annihilates the image of f in any quotient of ℤ[G]. In particular, Witt rings for G are quotients of ℤ[G]. In Section 1.3 we use the ring homomorphisms Hom(ℤ[G],ℤ) to describe the prime spectrum of ℤ[G]. The obtained results can then be employed for the characterisation of the prime spectrum of a Witt ring R for G. Section 1.4 is dedicated to proving the structure theorems for Witt rings. More precisely, we generalise the structure theorems for Witt rings of fields to the general setting of Witt rings for groups of exponent 2. Section 1.5 serves to summarise Chapter 1. If R is a Witt ring for G, then we use the structure theorems to determine, for an element x ∈ R, the specific shape of convenient and modest sets of generators for the annihilating ideal of x. In Chapter 2 we study annihilating polynomials for quadratic forms over fields. More specifically, we first consider fields K, over which quadratic forms can be classified with the help of the classical invariants. Calculations involving these invariants allow us to classify annihilating ideals for isometry and equivalence classes of quadratic forms over K. Then we apply methods from the theory of generic splitting to study annihilating polynomials for excellent quadratic forms. Throughout Chapter 2 we make heavy usage of the results obtained in Chapter 1. Let K be a field with char(K) ≠ 2. Section 2.1 constitutes an introduction to the algebraic theory of quadratic forms over fields. We introduce the Witt-Grothendieck ring (K) and the Witt ring W(K), and we show that these are indeed Witt rings for 𝓖(K). In addition we adapt the structure theorems to the specific setting of quadratic forms. In Section 2.2 we introduce Brauer groups and quaternion algebras, and in Section 2.3 we define the first three cohomological invariants of quadratic forms. In particular we use quaternion algebras to define the Clifford invariant. In Section 2.4 we begin our actual study of annihilating polynomials for quadratic forms. Henceforth it becomes necessary to distinguish between isometry and equivalence classes of quadratic forms. We start by classifying annihilating ideals for quadratic forms over fields K, for which (K) and W(K) have a particularly simple structure. Subsequently we use calculations involving the first three cohomological invariants to determine annihilating ideals for quadratic forms over a field K such that I3(K) = {0}, where I(K) ⊂ W(K) is the fundamental ideal. Local fields, which are a special class of such fields, are studied in Section 2.5. By applying the Hasse-Minkowski Theorem we can then determine annihilating ideals of quadratic forms over global fields. Section 2.6 serves as an introduction to the elementary theory of generic splitting. In particular we introduce Pfister neighbours and excellent quadratic forms, which are the subjects of study in Section 2.7. We use methods from generic splitting to study annihilating polynomials for Pfister neighbours. The obtained result can be applied inductively to obtain annihilating polynomials for excellent quadratic forms. We conclude the section by giving an alternative, elementary approach to the study of annihilating polynomials for excellent forms, which makes use of the fact that (K) and W(K) are quotients of ℤ[𝓖(K)].

EPFL2010

Convolution Operators And Homomorphisms Of Locally Compact Groups

Let 1 < p < infinity, let G and H be locally compact groups and let c) be a continuous homomorphism of G into H. We prove, if G is amenable, the existence of a linear contraction of the Banach algebra CVp (G) of the p-convolution operators on G into CVp (H) which extends the usual definition of the image of a bounded measure by omega. We also discuss the uniqueness of this linear contraction onto important subalgebras of CVp(G). Even if G and H are abelian, we obtain new results. Let G(d) denote the group G provided with a discrete topology. As a corollary, we obtain, for every discrete measure, vertical bar parallel to mu vertical bar parallel to CVp(G)

Cambridge University Press2008

Short undeniable signatures

Jean Monnerat

Digital signatures are one of the main achievements of public-key cryptography and constitute a fundamental tool to ensure data authentication. Although their universal verifiability has the advantage to facilitate their verification by the recipient, this property may have undesirable consequences when dealing with sensitive and private information. Motivated by such considerations, undeniable signatures, whose verification requires the cooperation of the signer in an interactive way, were invented. This thesis is mainly devoted to the design and analysis of short undeniable signatures. Exploiting their online property, we can achieve signatures with a fully scalable size depending on the security requirements. To this end, we develop a general framework based on the interpolation of group elements by a group homomorphism, leading to the design of a generic undeniable signature scheme. On the one hand, this paradigm allows to consider some previous undeniable signature schemes in a unified setting. On the other hand, by selecting group homomorphisms with a small group range, we obtain very short signatures. After providing theoretical results related to the interpolation of group homomorphisms, we develop some interactive proofs in which the prover convinces a verifier of the interpolation (resp. non-interpolation) of some given points by a group homomorphism which he keeps secret. Based on these protocols, we devise our new undeniable signature scheme and prove its security in a formal way. We theoretically analyze the special class of group characters on Z*n. After studying algorithmic aspects of the homomorphism evaluation, we compare the efficiency of different homomorphisms and show that the Legendre symbol leads to the fastest signature generation. We investigate potential applications based on the specific properties of our signature scheme. Finally, in a topic closely related to undeniable signatures, we revisit the designated confirmer signature of Chaum and formally prove the security of a generalized version.

EPFL2006