nach oben

2014 | Buch

Kapitel lesen Erstes Kapitel lesen

Pairing-Based Cryptography – Pairing 2013

6th International Conference, Beijing, China, November 22-24, 2013, Revised Selected Papers

herausgegeben von: Zhenfu Cao, Fangguo Zhang

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 6th International Conference on Pairing-Based Cryptography, Pairing 2013, held in Beijing, China, in November 2013.

The 14 full papers presented were carefully reviewed and selected from 59 submissions. As in previous years, the focus of Pairing 2013 is on all aspects of pairing-based cryptography, including: cryptographic primitives and protocols, mathematical foundations, software and hardware implementation, as well as applied security.

Inhaltsverzeichnis

Frontmatter

EAGL: An Elliptic Curve Arithmetic GPU-Based Library for Bilinear Pairing

Abstract

In this paper we present the Elliptic curve Arithmetic GPU-based Library (EAGL), a self-contained GPU library, to support parallel computing of bilinear pairings based on the Compute Unified Device Architecture (CUDA) programming model. It implements parallelized point arithmetic, arithmetic functions in the 1-2-4-12 tower of extension fields. EAGL takes full advantage of the parallel processing power of GPU, with no shared memory bank conflict and minimal synchronization and global memory accesses, to compute some most expensive computational steps, especially the conventional-Montgomery-based multi-precision multiplications. At the 128-bit security level, EAGL can perform 3350.9 R-ate pairings/sec on one GTX-680 controlled by one CPU thread. Extensive experiments suggest that performance tradeoffs between utilization of GPU pipeline vs. memory access latency are highly complex for parallelization of pairing computations. Overall, on-chip memory is the main performance bottleneck for pairing computations on the tested GPU device, and the lazy reduction in $ \mathbb{F}_{q^{2}} $ gives the best performance. Increasing the size of on-chip memory, together with caching and memory prefetching modules are expected to offer substantial performance improvement for GPU-based pairing computations.

Shi Pu, Jyh-Charn Liu

Weakness of $\mathbb{F}_{3^{6 \cdot 509}}$ for Discrete Logarithm Cryptography

Abstract

In 2013, Joux, and then Barbulescu, Gaudry, Joux and Thomé, presented new algorithms for computing discrete logarithms in finite fields of small and medium characteristic. We show that these new algorithms render the finite field ${\mathbb{F}}_{3^{6 \cdot 509}} = {\mathbb{F}}_{3^{3054}}$ weak for discrete logarithm cryptography in the sense that discrete logarithms in this field can be computed significantly faster than with the previous fastest algorithms. Our concrete analysis shows that the supersingular elliptic curve over ${\mathbb{F}}_{3^{509}}$ with embedding degree 6 that had been considered for implementing pairing-based cryptosystems at the 128-bit security level in fact provides only a significantly lower level of security. Our work provides a convenient framework and tools for performing a concrete analysis of the new discrete logarithm algorithms and their variants.

Gora Adj, Alfred Menezes, Thomaz Oliveira, Francisco Rodríguez-Henríquez

The Special Number Field Sieve in $\mathbb{F}_{p^{n}}$

Application to Pairing-Friendly Constructions

Abstract

In this paper, we study the discrete logarithm problem in finite fields related to pairing-based curves. We start with a precise analysis of the state-of-the-art algorithms for computing discrete logarithms that are suitable for finite fields related to pairing-friendly constructions. To improve upon these algorithms, we extend the Special Number Field Sieve to compute discrete logarithms in $\mathbb{F}_{p^{n}}$, where p has an adequate sparse representation. Our improved algorithm works for the whole range of applicability of the Number Field Sieve.

Antoine Joux, Cécile Pierrot

Efficient Semi-static Secure Broadcast Encryption Scheme

Abstract

In this paper, we propose a semi-static secure broadcast encryption scheme with constant-sized private keys and ciphertexts. Our result improves the semi-static secure broadcast encryption scheme introduced by Gentry and Waters. Specifically, we reduce the private key and ciphertext size by half. By applying the generic transformation proposed by Gentry and Waters, our scheme also achieves adaptive security. Finally, we present an improved implementation idea which can reduce the ciphertext size in the aforementioned generic transformation.

Jongkil Kim, Willy Susilo, Man Ho Au, Jennifer Seberry

Pairing Inversion via Non-degenerate Auxiliary Pairings

Abstract

The security of pairing-based cryptosystems is closely related to the difficulty of the pairing inversion problem(PI). In this paper, we discuss the difficulty of pairing inversion on the generalized ate pairings of Vercauteren. First, we provide a simpler approach for PI by generalizing and simplifying Kanayama-Okamoto’s approach; our approach involves modifications of exponentiation inversion(EI) and Miller inversion(MI), via an “auxiliary” pairing. Then we provide a complexity of the modified MI, showing that the complexity depends on the sum-norm of the integer vector defining the auxiliary pairing. Next, we observe that degenerate auxiliary pairings expect to make modified EI harder. We provide a sufficient condition on the integer vector, in terms of its max norm, so that the corresponding auxiliary paring is non-degenerate. Finally, we define an infinite set of curve parameters, which includes those of typical pairing friendly curves, and we show that, within those parameters, PI of arbitrarily given generalized ate pairing can be reduced to modified EI in polynomial time.

Seunghwan Chang, Hoon Hong, Eunjeong Lee, Hyang-Sook Lee

Constructing Symmetric Pairings over Supersingular Elliptic Curves with Embedding Degree Three

Abstract

In the present paper, we propose constructing symmetric pairings by applying the Ate pairing to supersingular elliptic curves over finite fields that have large characteristics with embedding degree three. We also propose an efficient algorithm of the Ate pairing on these curves. To construct the algorithm, we apply the denominator elimination technique and the signed-binary approach to the Miller’s algorithm, and improve the final exponentiation. We then show the efficiency of the proposed method through an experimental implementation.

Tadanori Teruya, Kazutaka Saito, Naoki Kanayama, Yuto Kawahara, Tetsutaro Kobayashi, Eiji Okamoto

Predicate- and Attribute-Hiding Inner Product Encryption in a Public Key Setting

Abstract

In this paper, we propose a reasonable definition of predicate-hiding inner product encryption (IPE) in a public key setting, which we call inner product encryption with ciphertext conversion (IPE-CC), where original ciphertexts are converted to predicate-searchable ones by an helper in possession of a conversion key. We then define a notion of full security for IPE-CC, which comprises three security properties of being adaptively predicate- and attribute-hiding in the public key setting, adaptively (fully-)attribute-hiding against the helper, and usefully secure even against the private-key generator (PKG). We then present the first fully secure IPE-CC scheme, and convert it into the first fully secure symmetric-key IPE (SIPE) scheme, where the security is defined in the sense of Shen, Shi, Waters. All the security properties are proven under the decisional linear assumption in the standard model. The IPE-CC scheme is comparably as efficient as existing attribute-hiding (not predicate-hiding) IPE schemes. We also present a variant of the proposed IPE-CC scheme with the same security that achieves shorter public and secret keys. We employ two key techniques, trapdoor basis setup, in which a new trapdoor is embedded in a public key, and multi-system proof technique, which further generalizes an extended dual system approach given by Okamoto and Takashima recently.

Yutaka Kawai, Katsuyuki Takashima

Fast Symmetric Pairing Revisited

Abstract

During the past decade pairing-based cryptosystems have been through a huge development, and the implementation of bilinear pairings has been improved greatly. Two pairing models, namely symmetric and asymmetric pairings, are widely used and have common cryptographic properties in most cryptosystems. Symmetric pairings are more convenient to construct cryptographic schemes, but asymmetric pairings are more efficient and suitable for implementation due to their flexible embedding degrees. In this paper we revisit symmetric pairings on supersingular elliptic curves over large characteristic fields. We show that a special family of supersingular elliptic curves with embedding degree 3 admits a kind of fast symmetric pairings, whose computational costs might be twice the costs for the current fastest asymmetric pairings.

Xusheng Zhang, Kunpeng Wang

Efficient Leakage-Resilient Identity-Based Encryption with CCA Security

Abstract

Due to the proliferation of side-channel attacks, lots of efforts have been made to construct cryptographic systems that are still secure even if part of the secret information is leaked to the adversary. Recently, many identity-based encryption (IBE) schemes have been proposed in this context, almost all of which, however, are only proved CPA secure. As far as we know, the IBE scheme presented by Alwen et al. is the unique CCA secure and the most practical one in the standard model. Unfortunately, this scheme suffers from an undesirable shortcoming that the leakage parameter λ and the message length m are subject to λ + m ≤ logp − ω(logκ), where κ is the security parameter and p is the prime order of the underlying group. To overcome this drawback, we designed a new IBE scheme based on Gentry’s IBE in this paper, which is λ-leakage resilient CCA2 secure in the standard model where λ ≤ logp − ω(logκ). In contrast, the leakage parameter λ in our proposal is independent of the size of the message space. Moreover, our scheme is quite practical and almost as efficient as the original scheme. To the best of our knowledge, it is the first practical leakage-resilient fully CCA2 secure IBE scheme in the standard model, tolerating up to (logp − ω(logκ))-bit leakage of the private key, the leakage parameter of which is independent of the message length.

Shi-Feng Sun, Dawu Gu, Shengli Liu

Revocable IBE Systems with Almost Constant-Size Key Update

Abstract

Identity-based encryption (IBE) has been regarded as an attractive alternative to more conventional certificate-based public key systems. It has recently attracted not only considerable research from the academic community, but also interest from the industry and standardization bodies. However, while key revocation is a fundamental requirement to any public key systems, not much work has been done in the identity-based setting. In this paper, we continue the study of revocable IBE (RIBE) initiated by Boldyreva, Goyal, and Kumar. Their proposal of a selective secure RIBE scheme, and a subsequent construction by Libert and Vergnaud in a stronger adaptive security model are based on a binary tree approach, such that their key update size is logarithmic in the number of users. In this paper, we show that the key update size could be further reduced to constant with some small amount of auxiliary information, through a novel combination of the Lewko and Waters IBE scheme and the Camenisch, Kohlweiss, and Soriente pairing-based dynamic accumulator.

Le Su, Hoon Wei Lim, San Ling, Huaxiong Wang

Pseudo 8–Sparse Multiplication for Efficient Ate–Based Pairing on Barreto–Naehrig Curve

Abstract

According to some recent implementation reports on Ate–based pairings such as optimal ate pairing with Barreto–Naehrig curve whose embedding degree is 12, sparse multiplication accelerates Miller’s loop calculation in a pairing calculation. Especially, 7–sparse multiplication is available when the implementation uses affine coordinates, where 7–sparse means that the multiplicand or multiplier has 7 zeros among 12 coefficients. This paper extends it to pseudo 8–sparse multiplication. Then, some experimental results together with theoretic calculation costs are shown in order to evaluate its efficiency.

Yuki Mori, Shoichi Akagi, Yasuyuki Nogami, Masaaki Shirase

Adaptable Ciphertext-Policy Attribute-Based Encryption

Abstract

In this paper, we introduce a new cryptographic primitive, called adaptable ciphertext-policy attribute-based encryption (CP-ABE). Adaptable CP-ABE extends the traditional CP-ABE by allowing a semi-trusted proxy to modify a ciphertext under one access policy into ciphertexts of the same plaintext under any other access policies; the proxy, however, learns nothing about the underlying plaintext. With such “adaptability” possessed by the proxy, adaptable CP-ABE has many real world applications, such as handling policy changes in CP-ABE encryption of cloud data and outsourcing of CP-ABE encryption.

Specifically, we first specify a formal model of adaptable CP-ABE; then, based on the CP-ABE scheme by Waters, we propose a concrete adaptable CP-ABE scheme and further prove its security under our security model.

Junzuo Lai, Robert H. Deng, Yanjiang Yang, Jian Weng

Algorithms for Pairing-Friendly Primes

Abstract

Given an integer n > 1 and a square-free $\varDelta<0$, we present a general method of generating primes p and q such that q |Φ_n(p) and q |p + 1 − t, where $|t| \leq 2\sqrt{p}$ and $4p-t^2=-\varDelta f^2$ for some integers f, t. Such primes can be used for implementing pairing-based cryptographic systems.

Maciej Grześkowiak

PandA: Pairings and Arithmetic

Abstract

This paper introduces PandA, a software framework for Pairings and Arithmetic. It is designed to bring together advances in the efficient computation of cryptographic pairings and the development and implementation of pairing-based protocols. The intention behind the PandA framework is to give protocol designers and implementors easy access to a toolbox of all functions needed for implementing pairing-based cryptographic protocols, while making it possible to use state-of-the-art algorithms for pairing computation and group arithmetic. PandA offers an API in the C programming language and all arithmetic operations run in constant time to protect against timing attacks. The framework also makes it easy to consistently test and benchmark the lower level functions used in pairing-based protocols.

As an example of how easy it is to implement pairing-based protocols with PandA, we use Boneh-Lynn-Shacham (BLS) signatures. Our PandA-based implementation of BLS needs only 434640 cycles for signature generation and 5832584 cycles for signature verification on one core of an Intel i5-3210M CPU. This includes full protection against timing attacks and compression of public keys and signatures.

Chitchanok Chuengsatiansup, Michael Naehrig, Pance Ribarski, Peter Schwabe

Backmatter

Titel: Pairing-Based Cryptography – Pairing 2013
herausgegeben von: Zhenfu Cao
Fangguo Zhang
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-04873-4
Print ISBN: 978-3-319-04872-7
DOI: https://doi.org/10.1007/978-3-319-04873-4

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

EAGL: An Elliptic Curve Arithmetic GPU-Based Library for Bilinear Pairing

Weakness of $\mathbb{F}_{3^{6 \cdot 509}}$ for Discrete Logarithm Cryptography

The Special Number Field Sieve in $\mathbb{F}_{p^{n}}$

Efficient Semi-static Secure Broadcast Encryption Scheme

Pairing Inversion via Non-degenerate Auxiliary Pairings

Constructing Symmetric Pairings over Supersingular Elliptic Curves with Embedding Degree Three

Predicate- and Attribute-Hiding Inner Product Encryption in a Public Key Setting

Fast Symmetric Pairing Revisited

Efficient Leakage-Resilient Identity-Based Encryption with CCA Security

Revocable IBE Systems with Almost Constant-Size Key Update

Pseudo 8–Sparse Multiplication for Efficient Ate–Based Pairing on Barreto–Naehrig Curve

Adaptable Ciphertext-Policy Attribute-Based Encryption

Algorithms for Pairing-Friendly Primes

PandA: Pairings and Arithmetic

Backmatter

Premium Partner