Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2008 | Book

Pairings in Trusted Computing Read chapter Read first chapter

Pairing-Based Cryptography – Pairing 2008

Second International Conference, Egham, UK, September 1-3, 2008. Proceedings

Editors: Steven D. Galbraith, Kenneth G. Paterson

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book constitutes the thoroughly refereed proceedings of the Second International Conference on Pairing-Based Cryptography, Pairing 2008, held in London, UK, in September 2008. The 20 full papers, presented together with the contributions resulting from 3 invited talks, were carefully reviewed and selected from 50 submissions. The contents are organized in topical sections on cryptography, mathematics, constructing pairing-friendly curves, implementation of pairings, and hardware implementation.

Table of Contents

Frontmatter

Invited Talks

Pairings in Trusted Computing
Abstract
Pairings have now been used for constructive applications in cryptography for around eight years. In that time the range of applications has grown from a relatively narrow one of identity based encryption and signatures, through to more advanced protocols. In addition implementors have realised that pairing protocols once presented can often be greatly simplified or expanded using the mathematical structures of different types of pairings. In this paper we consider another advanced application of pairings, namely to the Direct Anonymous Attestation (DAA) schemes as found in the Trusted Computing Group standards. We show that a recent DAA proposal can be further optimized by transferring the underlying pairing groups from the symmetric to the asymmetric settings. This provides a more efficient and scalable solution than the existing RSA and pairing based DAA schemes.
Liqun Chen, Paul Morrissey, Nigel P. Smart
Pairing Lattices
Abstract
We provide a convenient mathematical framework that essentially encompasses all known pairing functions based on the Tate pairing and also applies to the Weil pairing. We prove non-degeneracy and bounds on the lowest possible degree of these pairing functions and show how endomorphisms can be used to achieve a further degree reduction.
Florian Hess
The Uber-Assumption Family
A Unified Complexity Framework for Bilinear Groups
Abstract
We offer an exposition of Boneh, Boyen, and Goh’s “uber-assumption” family for analyzing the validity and strength of pairing assumptions in the generic-group model, and augment the original BBG framework with a few simple but useful extensions.
Xavier Boyen

Cryptography I

Homomorphic Encryption and Signatures from Vector Decomposition
Abstract
This paper introduces a new concept, distortion eigenvector space; it is a (higher dimensional) vector space in which bilinear pairings and distortion maps are available. A distortion eigenvector space can be efficiently realized on a supersingular hyperelliptic curve or a direct product of supersingular elliptic curves. We also introduce an intractable problem (with trapdoor) on distortion eigenvector spaces, the higher dimensional generalization of the vector decomposition problem (VDP). We define several computational and decisional problems regarding VDP, and clarify the relations among them. A trapdoor bijective function with algebraically rich properties can be obtained from the VDP on distortion eigenvector spaces. This paper presents two applications of this trapdoor bijective function; one is multivariate homomorphic encryption as well as a two-party protocol to securely evaluate 2DNF formulas in a higher dimensional manner, and the other is various types of signatures such as ordinary signatures, blind signatures, generically (selectively and universally) convertible undeniable signatures and their combination.
Tatsuaki Okamoto, Katsuyuki Takashima
Hidden-Vector Encryption with Groups of Prime Order
Abstract
Predicate encryption schemes are encryption schemes in which each ciphertext Ct is associated with a binary attribute vector https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-85538-5_5/MediaObjects/978-3-540-85538-5_5_IEq1_HTML.png and keys K are associated with predicates. A key K can decrypt a ciphertext https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-85538-5_5/MediaObjects/978-3-540-85538-5_5_IEq2_HTML.png if and only if the attribute vector of the ciphertext satisfies the predicate of the key. Predicate encryption schemes can be used to implement fine-grained access control on encrypted data and to perform search on encrypted data.
Hidden vector encryption schemes [Boneh and Waters – TCC 2007] are encryption schemes in which each ciphertext https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-85538-5_5/MediaObjects/978-3-540-85538-5_5_IEq3_HTML.png is associated with a binary vector https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-85538-5_5/MediaObjects/978-3-540-85538-5_5_IEq4_HTML.png and each key K is associated with binary vector https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-85538-5_5/MediaObjects/978-3-540-85538-5_5_IEq5_HTML.png with “don’t care” entries (denoted with ⋆). Key K can decrypt ciphertext https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-85538-5_5/MediaObjects/978-3-540-85538-5_5_IEq6_HTML.png if and only if https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-85538-5_5/MediaObjects/978-3-540-85538-5_5_IEq7_HTML.png and https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-85538-5_5/MediaObjects/978-3-540-85538-5_5_IEq8_HTML.png agree for all i for which \(y_i\ne \star\).
Hidden vector encryption schemes are an important type of predicate encryption schemes as they can be used to construct more sophisticated predicate encryption schemes (supporting for example range and subset queries).
We give a construction for hidden-vector encryption from standard complexity assumptions on bilinear groups of prime order. Previous constructions were in bilinear groups of composite order and thus resulted in less efficient schemes. Our construction is both payload-hiding and attribute-hiding meaning that also the privacy of the attribute vector, besides privacy of the cleartext, is guaranteed.
Vincenzo Iovino, Giuseppe Persiano

Mathematics

The Hidden Root Problem
Abstract
In this paper we study a novel computational problem called the Hidden Root Problem, which appears naturally when considering fault attacks on pairing based cryptosystems. Furthermore, a variant of this problem is one of the main obstacles for efficient pairing inversion. We present an algorithm to solve this problem over extension fields and investigate for which parameters the algorithm becomes practical.
Frederik Vercauteren
Evaluating Large Degree Isogenies and Applications to Pairing Based Cryptography
Abstract
We present a new method to evaluate large degree isogenies between elliptic curves over finite fields. Previous approaches all have exponential running time in the logarithm of the degree. If the endomorphism ring of the elliptic curve is ‘small’ we can do much better, and we present an algorithm with a running time that is polynomial in the logarithm of the degree. We give several applications of our techniques to pairing based cryptography.
Reinier Bröker, Denis Charles, Kristin Lauter
Computing the Cassels Pairing on Kolyvagin Classes in the Shafarevich-Tate Group
Abstract
Kolyvagin has shown how to study the Shafarevich-Tate group of elliptic curves over imaginary quadratic fields via Kolyvagin classes constructed from Heegner points. One way to produce explicit non-trivial elements of the Shafarevich-Tate group is by proving that a locally trivial Kolyvagin class is globally non-trivial, which is difficult in practice. We provide a method for testing whether an explicit element of the Shafarevich-Tate group represented by a Kolyvagin class is globally non-trivial by determining whether the Cassels pairing between the class and another locally trivial Kolyvagin class is non-zero. Our algorithm explicitly computes Heegner points over ring class fields to produce the Kolyvagin classes and uses the efficiently computable cryptographic Tate pairing.
Kirsten Eisenträger, Dimitar Jetchev, Kristin Lauter

Constructing Pairing Friendly Curves

Constructing Brezing-Weng Pairing-Friendly Elliptic Curves Using Elements in the Cyclotomic Field
Abstract
We describe a new method for constructing Brezing-Weng-like pairing-friendly elliptic curves. The new construction uses the minimal polynomials of elements in a cyclotomic field. Using this new construction we present new “record breaking” families of pairing-friendly curves with embedding degrees of k ∈ {16,18,36,40}, and some interesting new constructions for the cases k ∈ {8,32}.
Ezekiel J. Kachisa, Edward F. Schaefer, Michael Scott
Constructing Pairing-Friendly Elliptic Curves Using Factorization of Cyclotomic Polynomials
Abstract
The problem of constructing pairing-friendly elliptic curves has received a lot of attention. To find a suitable field for the construction we propose a method to find a polynomial u(x), by the method of indeterminate coefficients, such that Φ k (u(x)) factors. We also refine the algorithm by Brezing and Weng using a factor of Φ k (u(x)). As a result, we produce new families of parameters using our algorithm for pairing-friendly elliptic curves with embedding degree 8, and we compute some explicit curves as numerical examples.
Satoru Tanaka, Ken Nakamula
A Generalized Brezing-Weng Algorithm for Constructing Pairing-Friendly Ordinary Abelian Varieties
Abstract
We give an algorithm that produces families of Weil numbers for ordinary abelian varieties over finite fields with prescribed embedding degree. The algorithm uses the ideas of Freeman, Stevenhagen, and Streng to generalize the Brezing-Weng construction of pairing-friendly elliptic curves. We use our algorithm to give examples of pairing-friendly ordinary abelian varieties of dimension 2 and 3 that are absolutely simple and have smaller ρ-values than any previous such example.
David Freeman
Pairing-Friendly Hyperelliptic Curves with Ordinary Jacobians of Type y 2 = x 5 + ax
Abstract
An explicit construction of pairing-friendly hyperelliptic curves with ordinary Jacobians was firstly given by D. Freeman. In this paper, we give other explicit constructions of pairing-friendly hyperelliptic curves with ordinary Jacobians based on the closed formulae for the order of the Jacobian of a hyperelliptic curve of type y 2 = x 5 + ax. We present two methods in this paper. One is an analogue of the Cocks-Pinch method and the other is a cyclotomic method. By using these methods, we construct a pairing-friendly hyperelliptic curve y 2 = x 5 + ax over a finite prime field \({\mathbb F}_p\) whose Jacobian is ordinary and simple over \({\mathbb F}_p\) with a prescribed embedding degree. Moreover, the analogue of the Cocks-Pinch produces curves with ρ ≈ 4 and the cyclotomic method produces curves with 3 ≤ ρ ≤ 4.
Mitsuru Kawazoe, Tetsuya Takahashi

Implementation of Pairings

Integer Variable χ–Based Ate Pairing
Abstract
In implementing an efficient pairing calculation, it is said that the lower bound of the number of iterations of Miller’s algorithm is log2 r/ϕ(k), where ϕ(·) is the Euler’s function. Ate pairing reduced the number of the loops of Miller’s algorithm of Tate pairing from \(\lfloor\log_2r\rfloor\) to \(\lfloor \log_2(t-1)\rfloor\). Recently, it is known to systematically prepare a pairing–friendly elliptic curve whose parameters are given by a polynomial of integer variable “χ”. For the curve, this paper gives integer variable χ –based Ate pairing that achieves the lower bound by reducing it to \(\lfloor\log_2\chi\rfloor\).
Yasuyuki Nogami, Masataka Akane, Yumi Sakemi, Hidehiro Kato, Yoshitaka Morikawa
Pairing Computation on Twisted Edwards Form Elliptic Curves
Abstract
A new form of elliptic curve was recently discovered by Edwards and their application to cryptography was developed by Bernstein and Lange. The form was later extended to the twisted Edwards form. For cryptographic applications, Bernstein and Lange pointed out several advantages of the Edwards form in comparison to the more well known Weierstraß form. We consider the problem of pairing computation over Edwards form curves. Using a birational equivalence between twisted Edwards and Weierstraß forms, we obtain a closed form expression for the Miller function computation.
Simplification of this computation is considered for a class of supersingular curves. As part of this simplification, we obtain a distortion map similar to that obtained for Weierstraß form curves by Barreto et al and Galbraith et al. Finally, we present explicit formulae for combined doubling and Miller iteration and combined addition and Miller iteration using both inverted Edwards and projective Edwards coordinates. For the class of supersingular curves considered here, our pairing algorithm can be implemented without using any inversion.
M. Prem Laxman Das, Palash Sarkar
Exponentiation in Pairing-Friendly Groups Using Homomorphisms
Abstract
We present efficiently computable homomorphisms of the groups G 2 and G T for pairings G 1 ×G 2 →G T . This allows exponentiation in G 2 and G T to be accelerated using the Gallant-Lambert-Vanstone method.
Steven D. Galbraith, Michael Scott
Generators for the ℓ-Torsion Subgroup of Jacobians of Genus Two Curves
Abstract
We give an explicit description of the matrix representation of the Frobenius endomorphism on the Jacobian of a genus two curve on the subgroup of ℓ-torsion points. By using this description, we can describe the matrix representation of the Weil-pairing on the subgroup of ℓ-torsion points explicitly. Finally, the explicit description of the Weil-pairing provides us with an efficient, probabilistic algorithm to find generators of the subgroup of ℓ-torsion points on the Jacobian of a genus two curve.
Christian Robenhagen Ravnshøj
Speeding Up Pairing Computations on Genus 2 Hyperelliptic Curves with Efficiently Computable Automorphisms
Abstract
Pairings on the Jacobians of (hyper-)elliptic curves have received considerable attention not only as a tool to attack curve based cryptosystems but also as a building block for constructing cryptographic schemes with new and novel properties. Motivated by the work of Scott, we investigate how to use efficiently computable automorphisms to speed up pairing computations on two families of non-supersingular genus 2 hyperelliptic curves over prime fields. Our findings lead to new variants of Miller’s algorithm in which the length of the main loop can be up to 4 times shorter than that of the original Miller’s algorithm in the best case. We also implement the calculation of the Tate pairing on both a supersingular and a non-supersingular genus 2 curve with the same embedding degree of k = 4. Combining the new algorithm with known optimization techniques, we show that pairing computations on non-supersingular genus 2 curves over prime fields use up to 55.8% fewer field operations and run about 10% faster than supersingular genus 2 curves for the same security level.
Xinxin Fan, Guang Gong, David Jao
Pairings on Hyperelliptic Curves with a Real Model
Abstract
We analyse the efficiency of pairing computations on hyperelliptic curves given by a real model using a balanced divisor at infinity. Several optimisations are proposed and analysed. Genus two curves given by a real model arise when considering pairing friendly groups of order dividing p 2− p + 1. We compare the performance of pairings on such groups in both elliptic and hyperelliptic versions. We conclude that pairings can be efficiently computable in real models of hyperelliptic curves.
Steven D. Galbraith, Xibin Lin, David J. Mireles Morales

Hardware Implementation

Faster Implementation of η T Pairing over GF(3 m ) Using Minimum Number of Logical Instructions for GF(3)-Addition
Abstract
The η T pairing in characteristic three is implemented by arithmetic in GF(3)={0,1,2}. Harrison et al. reported an efficient implementation of the GF(3)-addition by using seven logical instructions (consisting of AND, OR, and XOR) with the two-bit encoding { (0,0) ↦0, (0,1) ↦1, (1,0) ↦ 2 }. It has not yet been proven whether seven is the minimum number of logical instructions for the GF(3)-addition. In this paper, we show many implementations of the GF(3)-addition using only six logical instructions with different encodings such as { (1,1) ↦0, (0,1) ↦1, (1,0) ↦2 } or { (0,0) ↦0, (0,1) ↦1, (1,1) ↦2 }. We then prove that there is no implementation of the GF(3)-addition using five logical instructions with any encoding of GF(3) by two bits. Moreover, we apply the new GF(3)-additions to an efficient software implementation of the η T pairing. The running time of the η T pairing over GF(3509), that is considered to be realized as 128-bit security, using the new GF(3)-addition with the encoding { (0,0) ↦0, (0,1) ↦1, (1,1) ↦2 } is 16.3 milliseconds on an AMD Opteron 2.2-GHz processor. This is approximately 7% faster than the implementation using the previous GF(3)-addition with seven logical instructions.
Yuto Kawahara, Kazumaro Aoki, Tsuyoshi Takagi
A Comparison between Hardware Accelerators for the Modified Tate Pairing over $\mathbb{F}_{2^m}$ and $\mathbb{F}_{3^m}$
Abstract
In this article we propose a study of the modified Tate pairing in characteristics two and three. Starting from the η T pairing introduced by Barreto et al. [1], we detail various algorithmic improvements in the case of characteristic two. As far as characteristic three is concerned, we refer to the survey by Beuchat et al. [5]. We then show how to get back to the modified Tate pairing at almost no extra cost. Finally, we explore the trade-offs involved in the hardware implementation of this pairing for both characteristics two and three. From our experiments, characteristic three appears to have a slight advantage over characteristic two.
Jean-Luc Beuchat, Nicolas Brisebarre, Jérémie Detrey, Eiji Okamoto, Francisco Rodríguez-Henríquez

Cryptography II

One-Round ID-Based Blind Signature Scheme without ROS Assumption
Abstract
In this paper, we propose the first one-round identity-based blind signature (IDBS) scheme without ROS assumption, which supposes that it is infeasible to find an overdetermined, solvable system of linear equations modulo q with random inhomogenities [25]. Our construction has the following features. First, it achieves the optimal bound of round complexity for blind signatures, i.e., each signature can be generated with one round (or two moves) of message exchanges between the signer and signature requesting user. Second, the proposed IDBS scheme is provably secure against generic parallel attack without relying on the ROS assumption. This means our scheme can guarantee the same security level with smaller security parameter, in contrast to some IDBS schemes with ROS assumptions, such as the IDBS deduced from the blind Schnorr signature. Third, our construction is based on bilinear pairings from scratch (i.e. without using existing identity-based signature schemes, and without using existing computational assumptions). Finally, the security of our IDBS is based on a new formalized assumption, called one-more bilinear Diffie-Hellman inversion (1m-BDHI) assumption.
Wei Gao, Guilin Wang, Xueli Wang, Fei Li
Tracing Malicious Proxies in Proxy Re-encryption
Abstract
In 1998, Blaze, Bleumer and Strauss put forth a cryptographic primitive, termed proxy re-encryption, where a semi-trusted proxy is given some piece of information that enables the re-encryption of ciphertexts from one key to another. Unidirectional schemes only allow translating from the delegator to the delegatee and not in the opposite direction. In all constructions described so far, although colluding proxies and delegatees cannot expose the delegator’s long term secret, they can derive and disclose sub-keys that suffice to open all translatable ciphertexts sent to the delegator. They can also generate new re-encryption keys for receivers that are not trusted by the delegator. In this paper, we propose traceable proxy re-encryption systems, where proxies that leak their re-encryption key can be identified by the delegator. The primitive does not preclude illegal transfers of delegation but rather strives to deter them. We give security definitions for this new primitive and a construction meeting the formalized requirements. This construction is fairly efficient, with ciphertexts that have logarithmic size in the number of delegations, but uses a non-black-box tracing algorithm. We discuss how to provide the scheme with a black box tracing mechanism at the expense of longer ciphertexts.
Benoît Libert, Damien Vergnaud
Security and Anonymity of Identity-Based Encryption with Multiple Trusted Authorities
Abstract
We consider the security of Identity-Based Encryption (IBE) in the setting of multiple Trusted Authorities (TAs). In this multi-TA setting, we envisage multiple TAs sharing some common parameters, but each TA generating its own master secrets and master public keys. We provide security notions and security models for the multi-TA setting which can be seen as natural extensions of existing notions and models for the single-TA setting. In addition, we study the concept of TA anonymity, which formally models the inability of an adversary to distinguish two ciphertexts corresponding to the same message and identity but generated using different TA master public keys. We argue that this anonymity property is a natural one of importance in enhancing privacy and limiting traffic analysis in multi-TA environments. We study a modified version of a Fujisaki-Okamoto conversion in the multi-TA setting, proving that our modification lifts security and anonymity properties from the CPA to the CCA setting. Finally, we apply these results to study the security of the Boneh-Franklin and Sakai-Kasahara IBE schemes in the multi-TA setting.
Kenneth G. Paterson, Sriramkrishnan Srinivasan
Backmatter
Metadata
Title
Pairing-Based Cryptography – Pairing 2008
Editors
Steven D. Galbraith
Kenneth G. Paterson
Copyright Year
2008
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-85538-5
Print ISBN
978-3-540-85503-3
DOI
https://doi.org/10.1007/978-3-540-85538-5

Premium Partner

    Image Credits