Faster pairings on special Weierstrass curves

This paper presents efficient formulas for computing cryptographic pairings on the curve y 2 = c x 3 + 1 over fields of large characteristic. We provide examples of pairing-friendly elliptic curves of this form which are of interest for efficient pairing implementations.

Fixed argument pairings

A common scenario in many pairing-based cryptographic protocols is that one argument in the pairing is fixed as a long term secret key or a constant parameter in the system. In these situations, the runtime of Miller's algorithm can be significantly reduced by storing precomputed values that depend on the fixed argument, prior to the input or existence of the second argument. In light of recent developments in pairing computation, we show that the computation of the Miller loop can be sped up by up to 37 if precomputation is employed, with our method being up to 19.5 faster than the previous precomputation techniques.

Attractive subfamilies of BLS curves for implementing high-security pairings

Barreto-Lynn-Scott (BLS) curves are a stand-out candidate for implementing high-security pairings. This paper shows that particular choices of the pairing-friendly search parameter give rise to four subfami- lies of BLS curves, all of which offer highly efficient and implementation- friendly pairing instantiations. Curves from these particular subfamilies are defined over prime fields that support very efficient towering options for the full extension field. The coefficients for a specific curve and its correct twist are automat-ically determined without any computational effort. The choice of an extremely sparse search parameter is immediately reflected by a highly efficient optimal ate Miller loop and final exponentiation. As a resource for implementors, we give a list with examples of implementation-friendly BLS curves through several high-security levels.

Fast formulas for computing cryptographic pairings

The most powerful known primitive in public-key cryptography is undoubtedly elliptic curve pairings. Upon their introduction just over ten years ago the computation of pairings was far too slow for them to be considered a practical option. This resulted in a vast amount of research from many mathematicians and computer scientists around the globe aiming to improve this computation speed. From the use of modern results in algebraic and arithmetic geometry to the application of foundational number theory that dates back to the days of Gauss and Euler, cryptographic pairings have since experienced a great deal of improvement. As a result, what was an extremely expensive computation that took several minutes is now a high-speed operation that takes less than a millisecond. This thesis presents a range of optimisations to the state-of-the-art in cryptographic pairing computation. Both through extending prior techniques, and introducing several novel ideas of our own, our work has contributed to recordbreaking pairing implementations.

Variants of waters’ dual system primitives using asymmetric pairings

Waters, in 2009, introduced an important technique, called dual system encryption, to construct identity-based encryption (IBE) and related schemes. The resulting IBE scheme was described in the setting of symmetric pairing. A key feature of the construction is the presence of random tags in the ciphertext and decryption key. Later work by Lewko and Waters removed the tags and proceeding through composite-order pairings led to a more efficient dual system IBE scheme using asymmetric pairings whose security is based on non-standard but static assumptions. In this work, we have systematically simplified Waters 2009 IBE scheme in the setting of asymmetric pairing. The simplifications retain tags used in the original description. This leads to several variants, the first one of which is based on standard assumptions and in comparison to Waters’ original scheme reduces ciphertexts and keys by two elements each. Going through several stages of simplifications, we finally obtain a simple scheme whose security can be based on two standard assumptions and a natural and minimal extension of the decision Diffie-Hellman problem for asymmetric pairing groups. The scheme itself is also minimal in the sense that apart from the tags, both encryption and key generation use exactly one randomiser each. This final scheme is more efficient than both the previous dual system IBE scheme in the asymmetric setting due to Lewko and Waters and the more recent dual system IBE scheme due to Lewko. We extend the IBE scheme to hierarchical IBE (HIBE) and broadcast encryption (BE) schemes. Both primitives are secure in their respective full models and have better efficiencies compared to previously known schemes offering the same level and type of security.

A concrete certificateless signature scheme without pairings

Certificateless public key cryptography was introduced to avoid the inherent key escrow problem in identity-based cryptography, and eliminate the use of certificates in traditional PKI. Most cryptographic schemes in certificateless cryptography are built from bilinear mappings on elliptic curves which need costly operations. Despite the investigation of certificateless public key encryption without pairings, certificateless signature without pairings received much less attention than what it deserves. In this paper, we present a concrete pairing-free certificateless signature scheme for the first time. Our scheme is more computationally efficient than others built from pairings. The new scheme is provably secure in the random oracle model assuming the hardness of discrete logarithm problem.

Pairings: Quintets and Duos from the Collaborative Piano Repertoire

Chamber music with piano comprises some of the greatest masterpieces in the Western canon. The works range from duo sonatas with various instruments through septets. In regard to duo sonatas, the violin is the instrument most frequently paired with the piano. Of all the chamber works for larger ensembles, the most popular is the quintet. In this dissertation, I will be exploring the similarities and differences between the duo sonatas and quintets of a given composer. I will be surveying Robert Schumann’s Piano Quintet in E-flat Major, Op. 44 along with his Violin and Piano Sonata in A Minor, Op. 105. The next pairing will be Johannes Brahms’ Piano Quintet in F Minor, Op. 34 and his Piano and Violin Sonata in D Minor, Op. 108. Dmitri Shostakovich’s Piano Quintet in G Minor, Op. 57 and his Cello and Piano Sonata in D Minor, Op. 40 will be the last two works examined in this dissertation. This dissertation project consisted of three recitals, presented in the Gildenhorn Recital Hall at the Clarice Smith Performing Arts Center of the University of Maryland. The recitals featured works by Johannes Brahms, Robert Schumann and Dmitri Shostakovich and took place on March 14, 2014, February 13, 2015 and November 22, 2015. All three recitals were recorded on compact discs, which can be accessed at the Digital Repository at the University of Maryland (DRUM) and at the University of Maryland Hornbake Library.

A rolling-gliding wear simulator for the investigation of tribological material pairings for application in total knee arthroplasty

Background: Material wear testing is an important technique in the development and evaluation of materials for use in implant for total knee arthroplasty. Since a knee joint induces a complex rolling-gliding movement, standardised material wear testing devices such as Pin-on-Disc or Ring-on-Disc testers are suitable to only a limited extent because they generate pure gliding motion only.Methods: A rolling-gliding wear simulator was thus designed, constructed and implemented, which simulates and reproduces the rolling-gliding movement and loading of the knee joint on specimens of simplified geometry. The technical concept was to run a base-plate, representing the tibia plateau, against a pivoted cylindrical counter-body, representing one femur condyle under an axial load. A rolling movement occurs as a result of the friction and pure gliding is induced by limiting the rotation of the cylindrical counter-body. The set up also enables simplified specimens handling and removal for gravimetrical wear measurements. Long-term wear tests and gravimetrical wear measurements were carried out on the well known material pairings: cobalt chrome-polyethylene, ceramic-polyethylene and ceramic-ceramic, over three million motion cycles to allow material comparisons to be made.Results: The observed differences in wear rates between cobalt-chrome on polyethylene and ceramic on polyethylene pairings were similar to the differences of published data for existing material-pairings. Test results on ceramic-ceramic pairings of different frontal-plane geometry and surface roughness displayed low wear rates and no fracture failures.Conclusions: The presented set up is able to simulate the rolling-gliding movement of the knee joint, is easy to use, and requires a minimum of user intervention or monitoring. It is suitable for long-term testing, and therefore a useful tool for the investigation of new and promising materials which are of interest for application in knee joint replacement implants. © 2010 Richter et al; licensee BioMed Central Ltd.

Deniable Authenticated Key Establishment for Internet Protocols

We propose two public-key schemes to achieve “deniable authentication” for the Internet Key Exchange (IKE). Our protocols can be implemented using different concrete mechanisms and we discuss different options; in particular we suggest solutions based on elliptic curve pairings. The protocol designs use the modular construction method of Canetti and Krawczyk which provides the basis for a proof of security. Our schemes can, in some situations, be more efficient than existing IKE protocols as well as having stronger deniability properties.

Avoiding full extension field arithmetic in pairing computations

The most costly operations encountered in pairing computations are those that take place in the full extension field Fpk . At high levels of security, the complexity of operations in Fpk dominates the complexity of the operations that occur in the lower degree subfields. Consequently, full extension field operations have the greatest effect on the runtime of Miller’s algorithm. Many recent optimizations in the literature have focussed on improving the overall operation count by presenting new explicit formulas that reduce the number of subfield operations encountered throughout an iteration of Miller’s algorithm. Unfortunately, almost all of these improvements tend to suffer for larger embedding degrees where the expensive extension field operations far outweigh the operations in the smaller subfields. In this paper, we propose a new way of carrying out Miller’s algorithm that involves new explicit formulas which reduce the number of full extension field operations that occur in an iteration of the Miller loop, resulting in significant speed ups in most practical situations of between 5 and 30 percent.

Faster pairing computations on curves with high-degree twists

Research on efficient pairing implementation has focussed on reducing the loop length and on using high-degree twists. Existence of twists of degree larger than 2 is a very restrictive criterion but luckily constructions for pairing-friendly elliptic curves with such twists exist. In fact, Freeman, Scott and Teske showed in their overview paper that often the best known methods of constructing pairing-friendly elliptic curves over fields of large prime characteristic produce curves that admit twists of degree 3, 4 or 6. A few papers have presented explicit formulas for the doubling and the addition step in Miller’s algorithm, but the optimizations were all done for the Tate pairing with degree-2 twists, so the main usage of the high- degree twists remained incompatible with more efficient formulas. In this paper we present efficient formulas for curves with twists of degree 2, 3, 4 or 6. These formulas are significantly faster than their predecessors. We show how these faster formulas can be applied to Tate and ate pairing variants, thereby speeding up all practical suggestions for efficient pairing implementations over fields of large characteristic.

Delaying mismatched field multiplications in pairing computations

Miller’s algorithm for computing pairings involves perform- ing multiplications between elements that belong to different finite fields. Namely, elements in the full extension field Fpk are multiplied by elements contained in proper subfields F pk/d , and by elements in the base field Fp . We show that significant speedups in pairing computations can be achieved by delaying these “mismatched” multiplications for an optimal number of iterations. Importantly, we show that our technique can be easily integrated into traditional pairing algorithms; implementers can exploit the computational savings herein by applying only minor changes to existing pairing code.

Encryption schemes and key exchange protocols in the certificateless setting

The contributions of this thesis fall into three areas of certificateless cryptography. The first area is encryption, where we propose new constructions for both identity-based and certificateless cryptography. We construct an n-out-of- n group encryption scheme for identity-based cryptography that does not require any special means to generate the keys of the trusted authorities that are participating. We also introduce a new security definition for chosen ciphertext secure multi-key encryption. We prove that our construction is secure as long as at least one authority is uncompromised, and show that the existing constructions for chosen ciphertext security from identity-based encryption also hold in the group encryption case. We then consider certificateless encryption as the special case of 2-out-of-2 group encryption and give constructions for highly efficient certificateless schemes in the standard model. Among these is the first construction of a lattice-based certificateless encryption scheme. Our next contribution is a highly efficient certificateless key encapsulation mechanism (KEM), that we prove secure in the standard model. We introduce a new way of proving the security of certificateless schemes based that are based on identity-based schemes. We leave the identity-based part of the proof intact, and just extend it to cover the part that is introduced by the certificateless scheme. We show that our construction is more efficient than any instanciation of generic constructions for certificateless key encapsulation in the standard model. The third area where the thesis contributes to the advancement of certificateless cryptography is key agreement. Swanson showed that many certificateless key agreement schemes are insecure if considered in a reasonable security model. We propose the first provably secure certificateless key agreement schemes in the strongest model for certificateless key agreement. We extend Swanson's definition for certificateless key agreement and give more power to the adversary. Our new schemes are secure as long as each party has at least one uncompromised secret. Our first construction is in the random oracle model and gives the adversary slightly more capabilities than our second construction in the standard model. Interestingly, our standard model construction is as efficient as the random oracle model construction.