Search

In this work we focus on tailoring and optimizing the computational Private Information Retrieval (cPIR) scheme proposed in WAHC 2014 for efficient execution on graphics processing units (GPUs). Exploiting the mass parallelism in GPUs is a commonly used approach in speeding up cPIRs. Our goal is to eliminate the efficiency bottleneck of the Doroz et al. construction which would allow us to take advantage of its excellent bandwidth performance. To this end, we develop custom code to support polynomial ring operations and extend them to realize the evaluation functions in an optimized manner on high end GPUs. Specifically, we develop optimized CUDA code to support large degree/large coefficient polynomial arithmetic operations such as modular multiplication/reduction, and modulus switching. Moreover, we choose same prime numbers for both the CRT domain representation of the polynomials and for the modulus switching implementation of the somewhat homomorphic encryption scheme. This allows us to combine two arithmetic domains, which reduces the number of domain conversions and permits us to perform faster arithmetic. Our implementation achieves 14–34 times speedup for index comparison and 4–18 times speedup for data aggregation compared to a pure CPU software implementation.

We present a high-performance C++ library for high but fixed precision (128 to 512 bit) integer arithmetic and symbolic polynomial computations. While the large integer and polynomial computation parts of the library can be used independently optimized kernels for symbolic polynomials with large integer coefficients are provided. The kernels were manually optimized in assembly language for the x86-64 and power64 architectures. Our main target application is high-temperature series expansions which requires inner products of large vectors of polynomials with large integer coefficients. For this purpose we implemented a tunable hybrid CPU/GPU inner product function using OpenMP and NVIDIA CUDA with inline PTX assembly. This way we make optimal use of today’s and upcoming hybrid supercomputers and attain 49% of the peak performance of the current NVIDIA Kepler GPU. Compared to a pure CPU solution using the GNU Multiple Precision Arithmetic Library (GMP) we gain a speedup of 13x for a pure CPU inner product and 38x using a GPU accelerator.

We discuss FLINT (Fast Library for Number Theory), a library to support computations in number theory, including highly optimised routines for polynomial arithmetic and linear algebra in exact rings.

Puzzles and games have been used for centuries to nurture problem-solving skills. Although often presented as isolated brain-teasers, the desire to know how to win makes games ideal examples for teaching algorithmic problem solving. With this in mind, this paper explores one-person solitaire-like game. The key to understanding solutions to solitaire-like games is the identification of invariant properties of polynomial arithmetic. We demonstrate this via three case studies: solitaire itself, tiling problems and a collection of novel one-person games. The known classification of states of the game of (peg) solitaire into 16 equivalence classes is used to introduce the relevance of polynomial arithmetic. Then we give a novel algebraic formulation of the solution to a class of tiling problems. Finally, we introduce an infinite class of challenging one-person games inspired by earlier work by Chen and Backhouse on the relation between cyclotomic polynomials and generalisations of the seven-trees-in-one type isomorphism. We show how to derive algorithms to solve these games.

We report efficient implementation techniques for FFT-based dense multivariate polynomial arithmetic over finite fields, targeting multi-cores. We have extended a preliminary study dedicated to polynomial multiplication and obtained a complete set of efficient parallel routines in Cilk++ for polynomial arithmetic such as normal form computation. Since bivariate multiplication applied to balanced data is a good kernel for these routines, we provide an in-depth study on the performance and the cut-off criteria of our different implementations for this operation. We also show that, not only optimized parallel multiplication can improve the performance of higher-level algorithms such as normal form computation but also this composition is necessary for parallel normal form computation to reach peak performance on a variety of problems that we have tested.

Polynomial constraint-solving plays a prominent role in several areas of engineering and software verification. In particular, polynomial constraint solving has a long and successful history in the development of tools for proving termination of programs. Well-known and very efficient techniques, like SAT algorithms and tools, have been recently proposed and used for implementing polynomial constraint solving algorithms through appropriate encodings. However, powerful techniques like the ones provided by the SMT (SAT modulo theories) approach for linear arithmetic constraints (over the rationals) are underexplored to date. In this paper we show that the use of these techniques for developing polynomial constraint solvers outperforms the best existing solvers and provides a new and powerful approach for implementing better and more general solvers for termination provers.

We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials, and show that under some plausible assumptions, high-degree polynomials as compression functions has good properties. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials generated by a small number of random parameters, where the security of the system would then relies on stronger assumptions, and we give empirical evidence for the validity of using such polynomials.

Embedded systems require efficient yet flexible implementations of cryptographic primitives with a minimal impact on the overall cost of a device. In this paper we present the design of a functional unit (FU) for accelerating the execution of cryptographic software on 32-bit processors. The FU is basically a multiply-accumulate (MAC) unit able to perform multiplications and MAC operations on integers and binary polynomials. Polynomial arithmetic is a performance-critical building block of numerous cryptosystems using binary extension fields, including public-key primitives based on elliptic curves (e.g. ECDSA), symmetric ciphers (e.g. AES or Twofish), and hash functions (e.g. Whirlpool). We integrated the FU into the Leon2 SPARC V8 core and prototyped the extended processor in an FPGA. All operations provided by the FU are accessible to the programmer through custom instructions. Our results show that the FU allows to accelerate the execution of 128-bit AES by up to 78% compared to a conventional software implementation using only native SPARC V8 instructions. Moreover, the custom instructions reduce the code size by up to 87.4%. The FU increases the silicon area of the Leon2 core by just 8,352 gates and has almost no impact on its cycle time.

Toom-Cook strategy is a well-known method for building algorithms to efficiently multiply dense univariate polynomials. Efficiency of the algorithm depends on the choice of interpolation points and on the exact sequence of operations for evaluation and interpolation. If carefully tuned, it gives the fastest algorithm for a wide range of inputs. This work smoothly extends the Toom strategy to polynomial rings, with a focus on . Moreover a method is proposed to find the faster Toom multiplication algorithm for any given splitting order. New results found with it, for polynomials in characteristic 2, are presented. A new extension for multivariate polynomials is also introduced; through a new definition of density leading Toom strategy to be efficient.

In this note a primality test for polynomials over a finite field is analyzed. It is particularly well suited to achieve fast computations in the binary case. Lots of prime polynomials which do not have to possess the maximum length property can be easily accessed by means of the best. Examples of binary polynomials generated through the use of the test are given for degrees from 35 up to 55. The computational requirements are compared with a related test for maximum length and also with some common factorization procedures. As main application the use of prime polynomials in certain crypto geenrators is considered.

The purpose of this study is to measure the impact of C level code polynomial arithmetic on the performances of AXIOM high-level algorithms, such as polynomial factorization. More precisely, given a high-level AXIOM package P parametrized by a univariate polynomial domain U , we have compared the performances of P when applied to different U 's, including an AXIOM wrapper for our C level code. Our experiments show that when P relies on U for its univariate polynomial computations, our specialized C level code can provide a significant speed-up. For instance, the improved implementation of square-free factorization in AXIOM is 7 times faster than the one in Maple and very close to the one in MAGMA . On the contrary, when P does not rely much on the operations of U and implements its private univariate polynomial operation, then P cannot benefit from our highly optimized C level code. Consequently, code which is poorly generic reduces the speed-up opportunities when applied to highly efficient and specialized

The purpose of this study is to investigate implementation techniques for polynomial arithmetic in a multiple-level programming environment. Indeed, certain polynomial data types and algorithms can further take advantage of the features of lower level languages, such as their specialized data structures or direct access to machine arithmetic. Whereas, other polynomial operations, like Grobner basis over an arbitrary field, are suitable for generic programming in a high-level language. We are interested in the integration of polynomial data type implementations realized at different language levels, such as Lisp, C and Assembly. In particular, we consider situations for which code from different levels can be combined together within the same application in order to achieve high-performance. We have developed implementation techniques in the multiple-level programming environment provided by the computer algebra system AXIOM. For a given algorithm realizing a polynomial operation, available at the user level, we combine the strengths of each language level and the features of a specific machine architecture. Our experimentations show that this allows us to improve performances of this operation in a significant manner.

We outline a general theory of graph polynomials which covers all the examples we found in the vast literature, in particular, the chromatic polynomial, various generalizations of the Tutte polynomial, matching polynomials, interlace polynomials, and the cover polynomial of digraphs. We introduce the class of (hyper)graph polynomials definable in second order logic, and outline a research program for their classification in terms of definability and complexity considerations, and various notions of reducibilities.

Recently, Hickernell introduced a new class of low-discrepancy sequences which is an infinite version of good lattice points. His sequences are constructed from multiplying the van der Corput sequence by an integer vector. In this paper, we define the polynomial arithmetic analogue of Hickernell sequences by using polynomials over finite fields GF(b), and show that this new type of sequences constitute a class of digital (t, s)-sequences. Then, we give two versions of matrix representation for their generator matrices, and prove that for the first version, there do not exist (0, s)-sequences for any base b ≥ 2 and any dimension s ≥ 2, and that for the second version, there do not exist (0, s)-sequences in base b = 2 for any s ≥ 2.

Multi-evaluation of the Coulomb potential induced by N particles is a central part of N-body simulations. In 3D, known subquadratic time algorithms return approximations up to given absolute precision. By combining data structures from Computational Geometry with fast polynomial arithmetic, the present work obtains approximations of prescribable relative error e> 0 in time \(\mathcal{O}(\frac{1}{\epsilon}N \cdot {\rm polylog}N)\).

Fast algorithms for arithmetic on real or complex polynomials are well-known and have proven to be not only asymptotically efficient but also very practical. Based on Fast Fourier Transform, they for instance multiply two polynomials of degree up to n or multi-evaluate one at n points simultaneously within quasi-linear time \(\mathcal{O}\)(n · polylog n). An extension to (and in fact the mere definition of) polynomials over fields ℝ and ℂ to the skew-field ℍ of quaternions is promising but still missing. The present work proposes three approaches which in the commutative case coincide but for ℍ turn out to differ, each one satisfying some desirable properties while lacking others. For each notion, we devise algorithms for according arithmetic; these are quasi-optimal in that their running times match lower complexity bounds up to polylogarithmic factors.

In this paper, we study the quotients that arise when the Euclidean algorithm is applied to a primitive polynomial and xs - 1. We analyze the asymptotic behavior of the the number of terms of the quotients as n → ∞. This problem comes from the study of Low-Density Parity-Check codes. We obtain two characterizations of primitive polynomials over the field with two elements that are based on the number of nonzero terms in two polynomials obtained via division and the Euclidean algorithm with polynomials of the form xs - 1. The analogous results do not hold for general finite fields but do restrict the order of the polynomials to a small set of positive integers with specific forms.

We present an algorithm for lattice basis reduction in function fields. In contrast to integer lattices, there is a simple algorithm which provably computes a reduced basis in polynomial time. This algorithm works only with the coefficients of the polynomials involved, so there is no polynomial arithmetic needed. This algorithm can be generically extended to compute a reduced basis starting from a generating system for a lattice. Moreover, it can be applied to lattices over the field of puiseux expansions of a function field. In that case, this algorithm represents one major step towards an efficient arithmetic in Jacobians of curves.

The primary topic of this chapter is the design and analysis of algorithms that solve various problems concerning the symbolic manipulation of polynomials and power series. By symbolic computation we mean procedures for computing the coefficients of the resulting polynomials and power series from the coefficients of the inputs. Among these problems are the multiplication, inversion, division, and composition of polynomials and power series. We shall analyse both the total number of arithmetic operations and the number of nonscalar operations of the algorithms. (In the latter case, addition, subtraction, and scalar multiplication are free of charge.) This gives upper bounds for the total and nonscalar complexity of the problem under investigation. In later chapters we shall see that most of these algorithms are optimal or close to optimal.

NTRU is a new public key cryptosystem proposed at Crypto 96 by Hoffstein, Pipher and Silverman from the Mathematics department of Brown University. It attracted considerable attention, and is being advertised over the Internet by NTRU Cryptosystems. Its security is based on the difficulty of analyzing the result of polynomial arithmetic modulo two unrelated moduli, and its correctness is based on clustering properties of the sums of random variables. In this paper, we apply new lattice basis reduction techniques to cryptanalyze the scheme, to discover either the original secret key, or an alternative secret key which is equally useful in decoding the ciphertexts.

We present space and time efficient algorithms for univariate polynomial arithmetic operations over Z mod n where the modulus n does not necessarily fit into is not a machine word. These algorithms provide the key tools for the efficient implementation of polynomial resultant gcd and factorization computation over Z, without having to write large amounts of code in a systems implementation language.