Cohomology pairings on singular quotients in geometric invariant theory

In this paper we shall give formulas for the pairings of intersection cohomology classes of complementary dimensions in the intersection cohomology of geometric invariant-theoretic quotients for which semistability is not necessarily the same as stability (although we make some weaker assumptions on the action). We also give formulas for intersection pairings on resolutions of singularities (or more precisely partial resolutions, since orbifold singularities are allowed) of the quotients.     

Pairings for cryptographers

Many research papers in pairing-based cryptography treat pairings as a “black box”. These papers build cryptographic schemes making use of various properties of pairings. If this approach is taken, then it is easy for authors to make invalid assumptions concerning the properties of pairings. The cryptographic schemes developed may not be realizable in practice, or may not be as efficient as the authors assume.The aim of this paper is to outline, in as simple a fashion as possible, the basic choices that are available when using pairings in cryptography. For each choice, the main properties and efficiency issues are summarized. The paper is intended to be of use to non-specialists who are interested in using pairings to design cryptographic schemes.     

Crew pairing at Air France

In the airline industry, crew schedules consist of a number of pairings. These are round trips originating and terminating at the same crew home base composed of legal work days, called duties, separated by rest periods. The purpose of the airline crew pairing problem is to generate a set of minimal cost crew pairings covering all flight legs. The set of pairings must satisfy all the rules in the work convention and all the appropriate air traffic regulations. The resulting constraints can affect duty construction, may restrict each pairing, or be imposed on the overall crew schedule.The pairing problem is formulated as an integer, nonlinear multi-commodity network flow problem with additional resource variables. Nonlinearities occur in the objective function as well as in a large subset of constraints. A branch-and-bound algorithm based on an extension of the Dantzig-Wolfe decomposition principle is used to solve this model. The master problem becomes a Set Partitioning type model, as in the classical formulation, while pairings are generated using resource constrained shortest path subproblems. This primal approach implicitly considers all feasible pairings and also provides the optimality gap value on a feasible solution. A nice feature of this decomposition process is that it isolates all nonlinear aspects of the proposed multi-commodity model in the subproblems which are solved by means of a specialized dynamic programming algorithm.We present the application and implementation of this approach at Air France. It is one of the first implementations of an optimal approach for a large airline carrier. We have chosen a subproblem network representation where the duties rather than the legs are on the arcs. This ensures feasibility relative to duty restrictions by definition. As opposed to Lavoie, Minoux and Odier (1988), the nonlinear cost function is modeled without approximations. The computational experiments were conducted using actual Air France medium haul data. Even if the branch-and-bound trees were not fully explored in all cases, the gaps certify that the computed solutions are within a fraction of one percentage point of the optimality. Our results illustrate that our approach produced substantial improvements over solutions derived by the expert system in use at Air France. Their magnitude led to the eventual implementation of the approach.     

On the Enumeration of Non-Crossing Pairings of Well-Balanced Binary Strings

A non-crossing pairing on a binary string pairs ones and zeroes such that the arcs representing the pairings are non-crossing. A binary string is well-balanced if it is of the form ${1^{a_1} 0^{a_1}1^{a_2} 0^{a_2} . . .1^{a_r} 0^{a_r}}$ . In this paper we establish connections between non-crossing pairings of well-balanced binary strings and various lattice paths in plane. We show that for well-balanced binary strings with a ₁ ≤ a ₂ ≤  . . . ≤  a _r , the number of non-crossing pairings is equal to the number of lattice paths on the plane with certain right boundary, and hence can be enumerated by differential Goncarov polynomials. For the regular binary strings S =  (1 ^k 0 ^k ) ⁿ , the number of non-crossing pairings is given by the (k + 1)-Catalan numbers. We present a simple bijective proof for this case.     

Pairings of function spaces

Pairings and copairings of topological spaces induce pairings of function spaces. These induced pairings of function spaces are studied. For this purpose, the C-open topology of function spaces is studied for subcategories C of Top. It is shown that the C-open topology enjoys good properties for homotopy theory. Making use of the C-open topology, theory of induced pairings is established and fundamental results on pairings which deduce various commutativity properties of elements in homotopy set are extended to function spaces.     

Universal Norms on Abelian Varieties over Global Function Fields

We examine the Mazur-Tate canonical height pairing defined between an abelian variety over a global field and its dual. We show in the case of global function fields that certain of these pairings are annihilated by universal norms coming from Carlitz cyclotomic extensions. Furthermore, for elliptic curves we find conditions for the triviality of these universal norms.     

Pairing-Based Cryptography on Elliptic Curves

We give a brief overview of a recent branch of Public Key Cryptography, the so called Pairing-based Cryptography or Identity-based Cryptography. We describe the Weil pairing and its applications to cryptosystems and cryptographic protocols based on pairings as well as the elliptic curves suitable for the implementation of this kind of cryptography, the so called pairing-friendly curves. Some recent results of the authors are included.     

On computable isomorphisms in efficient asymmetric pairing-based systems

In this paper, we examine the hard problems underlying asymmetric pairings, their precise relationships and how they affect a number of existing protocols. Furthermore, we present a new model for the elliptic curve groups used in asymmetric pairings, which allows both an efficient pairing and an efficiently computable isomorphism.     

Provably secure non-interactive key distribution based on pairings

We define a security notion for non-interactive key distribution protocols. We identify an apparently hard computational problem related to pairings, the Bilinear Diffie-Hellman problem (BDH). After extending Sakai, Ohgishi, and Kasahara's pairing based protocol to a slightly more general setting, we show that breaking the system is polynomially equivalent to solving BDH in the random oracle model and thus establish a security proof.     

Intersection homology with general perversities

We study intersection homology with general perversities that assign integers to stratum components with none of the classical constraints of Goresky and MacPherson. We extend Goresky and MacPherson’s axiomatic treatment of Deligne sheaves, and use these to obtain Poincaré and Lefschetz duality results for these general perversities. We also produce versions of both the sheaf-theoretic and the piecewise linear chain-theoretic intersection pairings that carry no restrictions on the input perversities.     

On p-quaternionic pairings of non-elementary type

We show that a p-analogue to the elementary type conjecture is not true. In fact, p-quaternionic pairings of non-elementary type are constructed for every prime p≥ 3. Received: 17 March 1999 / Revised version: 19 August 1999     

Certificateless signature and proxy signature schemes from bilinear pairings

Due to avoiding the inherent escrow of identity-based cryptography and yet not requiring certificates to guarantee the authenticity of public keys, certificateless public key cryptography has received a significant attention. Due to various applications of bilinear pairings in cryptography, numerous pairing-based encryption schemes, signature schemes, and other cryptographic primitives have been proposed. In this paper, a new certificateless signature scheme based on bilinear pairings is presented. The signing algorithm of the proposed scheme is very simple and does not require any pairing computation. Combining our signature scheme with certificateless public key cryptography yields a complete solution of certificateless public key system. As an application of the proposed signature scheme, a certificateless proxy signature scheme is also presented. We analyze both schemes from security point of view.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 1, pp. 95–103, January–March, 2005.     

The linking pairings of orientable Seifert manifolds

We compute the p-primary components of the linking pairings of orientable 3-manifolds admitting a fixed-point free S¹-action. Any linking pairing on a finite abelian group of odd order is realized by such a manifold. We find necessary and sufficient conditions for a pairing on an abelian 2-group to be the 2-primary component of such a linking pairing, and give simple examples which are not realizable by any Seifert fibred 3-manifold.     

Solving large scale crew scheduling problems

The crew pairing problem is posed as a set partitioning zero-one integer program. Variables are generated as legal pairings meeting all work rules. Dual values obtained from solving successive large linear program relaxations are used to prune the search tree. In this paper we present a graph based branching heuristic applied to a restricted set partitioning problem representing a collection of ‘best’ pairings. The algorithm exploits the natural integer properties of the crew pairing problem. Computational results are presented to show realized crew cost savings.     

一种无证书的环签名方案和一个基于身份的多重签名方案

在这篇文章里,我们用双线性对构造了一种无证书的环签名方案,并证明它是无条件匿名的,且在随机预言模型中,计算性Diffie-Hellman问题是难解的,我们方案在适应性选择消息攻击下是存在性不可伪造的,它的安全性比在基于身份的公钥密码体制下高.本文首次用多线性形式构造了一个基于身份的广播多重签名方案,它的安全性是基于计算性Diffie-Hellman困难问题.     

Function Spaces and Continuous Algebraic Pairings for Varieties

Given a quasi-projective complex variety X and a projective variety Y, one may endow the set of morphisms, Mor(X, Y), from X to Y with the natural structure of a topological space. We introduce a convenient technique (namely, the notion of a functor on the category of 'smooth curves') for studying these function complexes and for forming continuous pairings of such. Building on this technique, we establish several results, including (1) the existence of cap and join product pairings in topological cycle theory; (2) the agreement of cup product and intersection product for topological cycle theory; (3) the agreement of the motivic cohomology cup product with morphic cohomology cup product; and (4) the Whitney sum formula for the Chern classes in morphic cohomology of vector bundles.     

Group-valued equivariant localization

We prove a localization formula for group-valued equivariant de Rham cohomology of a compact G-manifold. This formula is a non-trivial generalization of the localization formula of Berline-Vergne and Atiyah-Bott for the usual equivariant de Rham cohomology. We derive from this result a Duistermaat-Heckman formula for group valued moment maps. As an application, we prove part of Witten’s conjectures about intersection pairings on moduli spaces of flat connections on 2-manifolds. Oblatum 24-VI-1999 & 29-X-1999?Published online: 21 February 2000     

Efficient pairing computation on supersingular Abelian varieties

We present a general technique for the efficient computation of pairings on Jacobians of supersingular curves. This formulation, which we call the eta pairing, generalizes results of Duursma and Lee for computing the Tate pairing on supersingular elliptic curves in characteristic 3. We then show how our general technique leads to a new algorithm which is about twice as fast as the Duursma–Lee method. These ideas are applied to elliptic and hyperelliptic curves in characteristic 2 with very efficient results. In particular, the hyperelliptic case is faster than all previously known pairing algorithms.      

Operator-Valued Herglotz Kernels and Functions of Positive Real Part on the Ball

We describe several classes of holomorphic functions of positive real part on the unit ball; each is characterized by an operator-valued Herglotz formula. Motivated by results of J. E. McCarthy and M. Putinar, we define a family of weighted Cauchy–Fantappiè pairings on the ball and establish duality relations between certain pairs of classes, and in particular we identify the dual of the positive Schur class. We also establish the existence of self-dual classes with respect to this pairing, and identify some extreme points of the positive Schur class.     

Computing pairings using <Emphasis Type="Italic">x</Emphasis>-coordinates only

To reduce bandwidth in elliptic curve cryptography one can transmit only x-coordinates of points (or x-coordinates together with an extra bit). This is called point compression. For further computation using the points one can either recover the y-coordinates by taking square roots or one can use point multiplication formulae which use x-coordinates only. We consider how to efficiently use point compression in pairing-based cryptography when the embedding degree is even. We give a method to compute compressed pairings using x-coordinates only. We also show how to compute the compressed pairings using two x-coordinates and one y-coordinate. Our methods are more efficient than taking square roots when the embedding degree is small. We implemented the algorithms in the case of embedding degree 2 curves over where (mod 4) and found that our methods can be 10–15% faster than the analogous methods using square roots.