What a lovely hat

Pairing-based arguments offer remarkably small proofs and space-efficient provers, but aggregating such proofs remains costly. Groth16 SNARKs and KZG polynomial commitments are prominent examples of this class of arguments. These arguments are widely deployed in decentralized systems, with millions of proofs generated per day. Recent folding schemes have greatly reduced the cost of proving incremental computations, such as batch proof verification. However, existing constructions require...

Cryptographic protocols such as zkSNARKs use 2-cycles of elliptic curves for efficiency, often relying on pairing computations. However, 2-cycles of pairing-friendly curves are hard to find, and the only known cases consist of an MNT4 and an MNT6 curve. In this work, we prove that a 2-cycle containing an MNT3 curve cannot be pairing-friendly. For other curve families, we have a similar result for cryptographically attractive field sizes. Thus we cannot hope to find new pairing-friendly...

For many pairing-based cryptographic protocols such as Direct Anonymous Attestation (DAA) schemes, the arithmetic on the first pairing subgroup $\mathbb{G}_1$ is more fundamental. Such operations heavily depend on the sizes of prime fields. At the 192-bit security level, Gasnier and Guillevic presented a curve named GG22D7-457 with CM-discriminant $D = 7$ and embedding degree $k = 22$. Compared to other well-known pairing-friendly curves at the same security level, the curve GG22D7-457 has...

Since the advent of pairing based cryptography, many researchers have developed several techniques and variants of pairings to optimise the speed of pairing computations. The selection of the elliptic curve for a given pairing based protocol is crucial for operations in the first and second pairing groups of points of the elliptic curve and for many cryptographic schemes. A new variant of superoptimal pairing was proposed in 2023, namely x-superoptimal pairing on curves with odd prime...

Fully homomorphic signatures are a significant strengthening of digital signatures, enabling computations on \emph{secretly} signed data. Today, we have multiple approaches to design fully homomorphic signatures such as from lattices, or succinct functional commitments, or indistinguishability obfuscation, or mutable batch arguments. Unfortunately, all existing constructions for homomorphic signatures suffer from one or more limitations. We do not have homomorphic signatures with features...

A functional commitment allows a user to commit to an input $\mathbf{x}$ and later, open the commitment to an arbitrary function $\mathbf{y} = f(\mathbf{x})$. The size of the commitment and the opening should be sublinear in $|\mathbf{x}|$ and $|f|$. In this work, we give the first pairing-based functional commitment for arbitrary circuits where the size of the commitment and the size of the opening consist of a constant number of group elements. Security relies on the standard bilateral...

In isogeny-based cryptography, bilinear pairings are regarded as a powerful tool in various applications, including key compression, public-key validation and torsion basis generation. However, in most isogeny-based protocols, the performance of pairing computations is unsatisfactory due to the high computational cost of the Miller function. Reducing the computational expense of the Miller function is crucial for enhancing the overall performance of pairing computations in isogeny-based...

Order-Revealing Encryption (ORE) provides a practical solution for conducting range queries over encrypted data. Achieving a desirable privacy-efficiency tradeoff in designing ORE schemes has posed a significant challenge. At Asiacrypt 2018, Cash et al. proposed Parameter-hiding ORE (pORE), which specifically targets scenarios where the data distribution shape is known, but the underlying parameters (such as mean and variance) need to be protected. However, existing pORE constructions rely...

Pairing-friendly curves with odd prime embedding degrees at the 128-bit security level, such as BW13-310 and BW19-286, sparked interest in the field of public-key cryptography as small sizes of the prime fields. However, compared to mainstream pairing-friendly curves at the same security level, i.e., BN446 and BLS12-446, the performance of pairing computations on BW13-310 and BW19-286 is usually considered ineffcient. In this paper we investigate high performance software...

Since the advent of pairing-based cryptography, various optimization methods that increase the speed of pairing computations have been exploited, as well as new types of pairings. This paper extends the work of Kinoshita and Suzuki who proposed a new formula for the $ \beta$-Weil pairing on curves with even embedding degree by eliminating denominators and exponents during the computation of the Weil pairing. We provide novel formulas suitable for the parallel computation for the...

Measuring efficiency is difficult. In the last decades, several works have contributed in the quest to successfully determine and compare the efficiency of pairing-based attribute-based encryption (ABE) schemes. However, many of these works are limited: they use little to no optimizations, or use underlying pairing-friendly elliptic curves that do not provide sufficient security anymore. Hence, using these works to benchmark ABE schemes does not yield accurate results. Furthermore, most ABE...

An accountable subgroup multi-signature is a kind of multi-signature scheme in which any subgroup $\mathcal{S}$ of a group $\mathcal{G}$ of potential signers jointly sign a message $m$, ensuring that each member of $\mathcal{S}$ is accountable for the resulting signature. In this paper, we propose three novel pairing-based accountable subgroup multi-signature (ASM) schemes, which are secure against existential forgery under chosen-message attacks and computational co-Diffie-Hellman...

A zk-SNARK is a powerful cryptographic primitive that provides a succinct and efficiently checkable argument that the prover has a witness to a public NP statement, without revealing the witness. However, in their native form, zk-SNARKs only apply to a secret witness held by a single party. In practice, a collection of parties often need to prove a statement where the secret witness is distributed or shared among them. We implement and experiment with *collaborative zk-SNARKs*:...

The final exponentiation affects the efficiency of pairing computations especially on pairing-friendly curves with high embedding degree. We propose an efficient method for computing the hard part of the final exponentiation on the KSS18 curve at 192-bit security level. Implementations indicate that the computation of the final exponentiation can be 8.74% faster than the previously fastest result.

Pairing computations on elliptic curves with odd prime degrees are rarely studied as low efficiency. Recently, Clarisse, Duquesne and Sanders proposed two new curves with odd prime embedding degrees: \textit{BW13-P310} and \textit{BW19-P286}, which are suitable for some special cryptographic schemes. In this paper, we propose efficient methods to compute the optimal ate pairing on this types of curves, instantiated by the \textit{BW13-P310} curve. We first extend the technique of lazy...

Pairings have been widely used since their introduction to cryptography. They can be applied to identity-based encryption, tripartite Diffie-Hellman key agreement, blockchain and other cryptographic schemes. The Acceleration of pairing computations is crucial for these cryptographic schemes or protocols. In this paper, we will focus on the Elliptic Net algorithm which can compute pairings in polynomial time, but it requires more storage than Miller’s algorithm. We use several methods to...

The problem of securely outsourcing the computation of a bilinear pairing has been widely investigated in the literature. Designing an efficient protocol with the desired functionality has, however, been an open challenge for a long time. Recently, Di Crescenzo et al. (CARDIS’20) proposed the first suite of protocols for securely and efficiently delegating pairings with online inputs under the presence of a malicious server. We progress along this path with the aim of LOVE (Lowering the cost...

Hardware security tokens have now been used for several decades to store cryptographic keys. When deployed, the security of the corresponding schemes fundamentally relies on the tamper-resistance of the tokens – a very strong assumption in practice. Moreover, even secure tokens, which are expensive and cumbersome, can often be subverted. We introduce a new cryptographic primitive called Encryption schemes with Password-protected Assisted Decryption (EPAD schemes), in which a user’s...

The best existing pairing-based traitor tracing schemes have $O(\sqrt{N})$-sized parameters, which has stood since 2006. This intuitively seems to be consistent with the fact that pairings allow for degree-2 computations, yielding a quadratic compression. In this work, we show that this intuition is false by building a tracing scheme from pairings with $O(\sqrt[3]{N})$-sized parameters. We additionally give schemes with a variety of parameter size trade-offs, including a scheme with...

Pairings are a powerful tool to build advanced cryptographic schemes. The most efficient way to instantiate a pairing scheme is through Pairing-Friendly Elliptic Curves. Because a randomly picked elliptic curve will not support an efficient pairing (the embedding degree will usually be too large to make any computation practical), a pairing-friendly curve has to be carefully constructed. This has led to famous curves, e.g. Barreto-Naehrig curves. However, the computation of the discrete...

Inner product encryption is a powerful cryptographic primitive, where a private key and a ciphertext are both associated with a predicate vector and an attribute vector, respectively. A successful decryption requires the inner product of the predicate vector and the attribute vector to be zero. Most of the existing inner product encryption schemes suffer either long private key or heavy decryption cost. In this manuscript, an efficient inner product encryption is proposed. The length for a...

There have been notable improvements in discrete logarithm computations in finite fields since 2015 and the introduction of the Tower Number Field Sieve algorithm (TNFS) for extension fields. The Special TNFS is very efficient in finite fields that are target groups of pairings on elliptic curves, where the characteristic is special (e.g.~sparse). The key sizes for pairings should be increased, and alternative pairing-friendly curves can be considered. We revisit the Special variant of TNFS...

We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to proving that an inner pairing product is correctly evaluated with respect to committed vectors of $n$ source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by $6 \log n$ target group exponentiations. Proofs are of size $6 \log n$ target group elements, computed using $6n$...

We address the problem of speeding up isogeny computation for supersingular elliptic curves over finite fields using untrusted computational resources like third party servers or cloud service providers (CSPs). We first propose new, efficient and secure delegation schemes. This especially enables resource-constrained devices (e.g. smart cards, RFID tags, tiny sensor nodes) to effectively deploy post-quantum isogeny-based cryptographic protocols. To the best of our knowledge, these new...

Non-interactive arguments of knowledge are powerful cryptographic tools that can be used to demonstrate the faithful execution of arbitrary computations with publicly verifiable proofs. Increasingly efficient protocols have been described in recent years, with verification time and/or communication complexity that is sublinear in the size of the computation being described. These efficiencies can be exploited to realize recursive proof composition: the concept of proofs that attest to the...

The isogeny-based protocols SIDH and SIKE have received much attention for being post-quantum key agreement candidates that retain relatively small keys. A recent line of work has proposed and further improved compression of public keys, leading to the inclusion of public-key compression in the SIKE proposal for Round 2 of the NIST Post-Quantum Cryptography Standardization effort. We show how to employ the dual isogeny to significantly increase performance of compression techniques, reducing...

Multi-signatures allow a group of signers to jointly sign a message in a compact and efficiently verifiable signature, ideally independent of the number of signers in the group. We present the first provably secure forward-secure multi-signature scheme by deriving a forward-secure signature scheme from the hierarchical identity-based encryption of Boneh, Boyen, and Goh (Eurocrypt 2005) and showing how the signatures in that scheme can be securely composed. Multi-signatures in our scheme...

Anonymous credential (AC) schemes are protocols which allow for authentication of authorized users without compromising their privacy. Of particular interest are non-interactive anonymous credential (NIAC) schemes, where the authentication process only requires the user to send a single message that still conceals its identity. Unfortunately, all known NIAC schemes in the standard model require pairing based cryptography, which limits them to a restricted set of specific assumptions and...

Several appealing features of cloud computing such as cost-effectiveness and user-friendliness have made many users and enterprises interested to outsource their sensitive data for sharing via cloud. However, it causes many new challenges toward data confidentiality, access control , scalability, and flexibility. Ciphertext-policy Hierarchical attribute-based encryption (CP-HABE) can be a promising solution to the mentioned problems. But, the existing HABE schemes have several...

Since the seminal paper on Fully Homomorphic Encryption (FHE) by Gentry in 2009, a lot of work and improvements have been proposed, with an amazing number of possible applications. It allows outsourcing any kind of computations on encrypted data, and thus without leaking any information to the provider who performs the computations. This is quite useful for many sensitive data (finance, medical, etc.). Unfortunately, FHE fails at providing some computation on private inputs to a third...

We address the problem of secure and verifiable delegation of general pairing computation. We first analyze some recently proposed pairing delegation schemes and present several attacks on their security and/or verifiability properties. In particular, we show that none of these achieve the claimed security and verifiability properties simultaneously. We then provide a fully verifiable secure delegation scheme ${\sf VerPair}$ under one-malicious version of a two-untrusted-program model...

Group signature schemes (GSS) represent an important privacy-enhancing technology. However, their practical applicability is restricted due to inefficiencies of existing membership revocation mechanisms that often place a too large computational burden and communication overhead on the involved parties. Moreover, it seems that the general belief (or unwritten law) of avoiding online authorities by all means artificially and unnecessarily restricts the efficiency and practicality of...

The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF($p^n$) where $n$ is a small integer greater than $1$. Though less studied than the small characteristic case or the prime field case, the difficulty of this problem is at the heart of security evaluations for torus-based and pairing-based cryptography. The best known method for solving this problem is the Number Field Sieve (NFS). A key ingredient in this algorithm is the ability to find good...

Attribute-based methods provide authorization to parties based on whether their set of attributes (e.g., age, organization, etc.) fulfills a policy. In attribute-based encryption (ABE), authorized parties can decrypt, and in attribute-based credentials (ABCs), authorized parties can authenticate themselves. In this paper, we combine elements of ABE and ABCs together with garbled circuits to construct attribute-based key exchange (ABKE). Our focus is on an interactive solution involving a...

Pairing based cryptography is in a dangerous position following the breakthroughs on discrete logarithms computations in finite fields of small characteristic. Remaining instances are built over finite fields of large characteristic and their security relies on the fact the embedding field of the underlying curve is relatively large. How large is debatable. The aim of our work is to sustain the claim that the combination of degree 3 embedding and too small finite fields obviously does not...

Many pairing-based protocols require the computation of the product and/or of a quotient of n pairings where n > 1 is a natural integer. Zhang et al.[1] recently showed that the Kachisa-Schafer and Scott family of elliptic curves with embedding degree 16 denoted KSS16 at the 192-bit security level is suitable for such protocols comparatively to the Baretto- Lynn and Scott family of elliptic curves of embedding degree 12 (BLS12). In this work, we provide important corrections and improvements...

In order to assess the security of cryptosystems based on the discrete logarithm problem in non-prime finite fields, as are the torus-based or pairing-based ones, we investigate thoroughly the case in $GF(p^6)$ with the Number Field Sieve. We provide new insights, improvements, and comparisons between different methods to select polynomials intended for a sieve in dimension 3 using a special-q strategy. We also take into account the Galois action to increase the relation productivity of the...

Recently Attrapadung (Eurocrypt 2014) proposed a generic framework for fully (adaptively) secure predicate encryption (PE) based on a new primitive, called pair encodings. The author shows that if the underlying pair encoding scheme is either perfectly secure or computationally (doubly-selectively) secure, then the PE scheme will be fully secure. Although the pair encodings were solely introduced for PE, we show that these can also be used to construct predicate signatures, a signature...

The security of pairing-based crypto-systems relies on the difficulty to compute discrete logarithms in finite fields GF(p^n) where n is a small integer larger than 1. The state-of-art algorithm is the number field sieve (NFS) together with its many variants. When p has a special form (SNFS), as in many pairings constructions, NFS has a faster variant due to Joux and Pierrot. We present a new NFS variant for SNFS computations, which is better for some cryptographically relevant cases,...

Since their introduction in 1985, by Goldwasser, Micali and Rackoff, followed by Feige, Fiat and Shamir, zero-knowledge proofs have played a significant role in modern cryptography: they allow a party to convince another party of the validity of a statement (proof of membership) or of its knowledge of a secret (proof of knowledge). Cryptographers frequently use them as building blocks in complex protocols since they offer quite useful soundness features, which exclude cheating players. In...

Montgomery modular multiplication constitutes the "arithmetic foundation" of modern public-key cryptography with applications ranging from RSA, DSA and Diffie-Hellman over elliptic curve schemes to pairing-based cryptosystems. The increased prevalence of SIMD-type instructions in commodity processors (e.g. Intel SSE, ARM NEON) has initiated a massive body of research on vector-parallel implementations of Montgomery modular multiplication. In this paper, we introduce the Cascade Operand...

Self-pairings are a special subclass of pairings and have interesting applications in cryptographic schemes and protocols. In this paper, we explore the computation of the self-pairings on supersingular elliptic curves with embedding degree $k = 3$. We construct a novel self-pairing which has the same Miller loop as the Eta/Ate pairing. However, the proposed self-pairing has a simple final exponentiation. Our results suggest that the proposed self-pairings are more efficient than the other...

In this paper, we use the theory of theta functions to generalize to all abelian varieties the usual Miller's algorithm to compute a function associated to a principal divisor. We also explain how to use the Frobenius morphism on abelian varieties defined over a finite field in order to shorten the loop of the Weil and Tate pairings algorithms. This extend preceding results about ate and twisted ate pairings to all abelian varieties. Then building upon the two preceding ingredients, we...

At Pairing 2010, Lauter et al's analysis showed that Ate pairing computation in affine coordinates may be much faster than projective coordinates at high security levels. In this paper, we further investigate techniques to speed up Ate pairing computation in affine coordinates. On the one hand, we improve Ate pairing computation over elliptic curves admitting an even twist by describing an $4$-ary Miller algorithm in affine coordinates. This technique allows us to trade one multiplication in...

Recently, Xiong et al. [H. Xiong, Z. Guan, Z. Chen, F. Li, An efficient certificateless aggregate signature with constant pairing computations, Information Science, 219, pp. 225–235, 2013] proposed an efficient certificateless signature (CLS) scheme and used it to construct a certificateless aggregate signature (CLAS) scheme with constant pairing computations. They also demonstrated that both of the two schemes are provably secure in the random oracle model under the computational...

Taking advantage of a technique that allows to safely distribute a private key among decryption servers we introduce a new identity-based threshold scheme, proven secure in the random oracle model. This new paring-based scheme features a lot of improvements compared to other schemes that can be found in the literature. Among them the two most noticeable ones are, the efficiency, by reducing the number of pairing computations, and the ability for a user to generate and share a private key...

The prospect of outsourcing an increasing amount of data storage and management to cloud services raises many new privacy concerns for individuals and businesses alike. The privacy concerns can be satisfactorily addressed if users encrypt the data they send to the cloud. If the encryption scheme is homomorphic, the cloud can still perform meaningful computations on the data, even though it is encrypted. In fact, we now know a number of constructions of fully homomorphic encryption schemes...

The existing identity-based encryption (IBE) schemes based on pairings require pairing computations in encryption or decryption algorithm and it is a burden to each entity which has restricted computing resources in mobile computing environments. An IBE scheme (MY-IBE) based on a trapdoor DL group for RSA setting is one of good alternatives for applying to mobile computing environments. However, it has a drawback for practical use, that the key generation algorithm spends a long time for...

This paper deals with the differential power attack on a pairing cryptoprocessor. The cryptoprocessor is designed for pairing computations on elliptic curves defined over finite fields with large prime characteristic. The work pinpoints the vulnerabilities of such pairing computations against side-channel attacks. By exploiting the power consumptions, the paper experimentally demonstrates such vulnerability on FPGA platform. A suitable counteracting technique is also suggested to overcome...

This paper describes a new method in pairing-based signature schemes for identifying the invalid digital signatures in a batch after batch verification has failed. The method more efficiently identifies non-trivial numbers, $w$, of invalid signatures in constrained sized, $N$, batches than previously published methods, and does not require that the verifier possess detailed knowledge of $w$. Our method uses ``divide-and-conquer'' search to identify the invalid signatures within a batch,...

In this work, we are interested in arithmetic in large prime field and their extensions of small degree. We explain why it is very interesting to use RNS arithmetic for the base field ${\mathbb F}_p$ when computations in ${\mathbb F}_{p^k}$ have to be done, essentially thanks to lazy reduction. This is for example the case for pairing computations on ordinary curves (as MNT or BN curves). We prove that using RNS can considerably decrease the number of basic operations required for a pairing...

We propose new squaring formulae for cyclotomic subgroups of certain finite fields. Our formulae use a compressed representation of elements having the property that decompression can be performed at a very low cost. The squaring formulae lead to new exponentiation algorithms in cyclotomic subgroups which outperform the fastest previously-known exponentiation algorithms when the exponent has low Hamming weight. Our algorithms can be adapted to accelerate the final exponentiation step of...

A publicly verifiable secret sharing (PVSS) scheme, proposed by Stadler in \cite{DBLP:conf/eurocrypt/Stadler96}, is a VSS scheme in which anyone, not only the shareholders, can verify that the secret shares are correctly distributed. PVSS can play essential roles in the systems using VSS. Achieving simultaneously the following two features for PVSS is a challenging job: \begin{itemize} \item Efficient non-interactive public verification. \item Proving security for the public verifiability in...

Online/Offline signcryption is a cryptographic primitive where the signcryption process is divided into two phases - online and offline phase. Most of the computations are carried out offline (where the message and the receiver identity are unavailable). The online phase does not require any heavy computations like pairing, multiplication on elliptic curves and is very efficient. To the best of our knowledge there exists three online/offline signcryption schemes in the literature : we...

We consider the problem of securing inter-flow network coding with multiple sources. We present a practical homomorphic signature scheme that makes possible to verify network coded packets composed of data originating from different sources. The multi-source signature scheme allows to circumvent the need of a secret key shared by all sources. Our solution is an extension of the pairing based homomorphic signature scheme by Boneh et al. We prove the security of the extended scheme by showing...

An identity-based online/offline encryption (IBOOE) scheme splits the encryption process into two phases. The first phase performs most of the heavy computations, such as modular exponentiation or pairing over points on elliptic curve. The knowledge of the plaintext or the receiver's identity is not required until the second phase, where the ciphertext is produced by only light computations, such as integer addition/multiplication or hashing. This division of computations makes encryption...

Miller's algorithm for computing pairings involves performing multiplications between elements that belong to different finite fields. Namely, elements in the full extension field $\mathbb{F}_{p^k}$ are multiplied by elements contained in proper subfields $\mathbb{F}_{p^{k/d}}$, and by elements in the base field $\mathbb{F}_{p}$. We show that significant speedups in pairing computations can be achieved by delaying these ``mismatched'' multiplications for an optimal number of iterations....

The most costly operations encountered in pairing computations are those that take place in the full extension field $\mathbb{F}_{p^k}$. At high levels of security, the complexity of operations in $\mathbb{F}_{p^k}$ 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...

In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zero-knowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to a number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and manage to improve significantly the complexity of proof verification. We give explicit batch...

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...

This paper presents the first study of pairing computation on curves with embedding degree $15$. We compute the Ate and the twisted Ate pairing for a family of curves with parameter $\rho~1.5$ and embedding degree $15$. We use a twist of degree 3 to perform most of the operations in $\F_p$ or $\F_{p^5}$. Furthermore, we present a new arithmetic for extension fields of degree $5$. Our computations show that these curves give very efficient implementations for pairing-based cryptography at...

This paper describes new methods in pairing-based signature schemes for identifying the invalid digital signatures in a batch, after batch verification has failed. These methods efficiently identify non-trivial numbers of invalid signatures in batches of (potentially large) numbers of signatures. Our methods use “divide-and-conquer” search to identify the invalid signatures within a batch, but prune the search tree to substantially reduce the number of pairing computations required. The...

We present low complexity formulae for the computation of cubing and cube root over $\F_{3^m}$ constructed using special classes of irreducible trinomials, tetranomials and pentanomials. We show that for all those special classes of polynomials, field cubing and field cube root operation have the same computational complexity when implemented in hardware or software platforms. As one of the main applications of these two field arithmetic operations lies in pairing-based cryptography, we also...

ID-based ring signcryption schemes (IDRSC) are usually derived from bilinear parings, a powerful but computationally expensive primitive. The number of paring computations of all existing ID-based ring signcryption schemes from bilinear pairings grows linearly with the group size, which makes the efficiency of ID-based schemes over traditional schemes questionable. In this paper, we present a new identity-based ring signcryption scheme, which only takes four pairing operations for any group...

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.

In this paper, we present some new variants based on the Weil pairing for efficient pairing computations. The new pairing variants have the short Miller iteration loop and simple final exponentiation. We then show that computing the proposed pairings is more efficient than computing the Weil pairing. Experimental results for these pairings are also given.

In this paper, based on the scheme proposed by Barreto et al in ASIACRYPT 2005, an identity-based signcryption scheme in multiple Private Key Generator (PKG) environment is proposed, which mitigates the problems referred to users' private keys escrow and distribution in single PKG system. For security of the scheme, it is proved to satisfy the properties of message confidentiality and existential signature-unforgeability, assuming the intractability of the q-Strong Diffie-Hellman problem and...

This technical report describes a novel certificateless signature scheme suitable for aggregation that requires no pairing computations for signing and only 3 pairing computations for signature verification. We provide proofs for the security of single and aggregate signatures.

In this paper, we will describe efficient implementations of the Tate and Ate pairings over ordinary elliptic curves of embedding degrees 8 and 10. We will discuss the possible curve-dependent optimizations that can be applied to evaluate the pairings. We pay particular attention to the use of elliptic curve twists and the denominator elimination method to make computations more efficient. Our main goal is to draw together the best possible optimizations that can be used to efficiently...

In this paper we present a certificateless signature (CLS) scheme secure in the Random Oracle Model. This scheme requires no pairing computations for signature generation and only two for signature verification. As far as we know, this is the only CLS scheme to require less than four pairing computations on signature verification.

Hyperelliptic curves of small genus have the advantage of providing a group of comparable size as that of elliptic curves, while working over a field of smaller size. Pairing-friendly hyperelliptic curves are those whose order of the Jacobian is divisible by a large prime, whose embedding degree is small enough for computations to be feasible, and whose minimal embedding field is large enough for the discrete logarithm problem in it to be difficult. We give a sequence of $\F_q$-isogeny...

Though the implementation of the Tate pairing is commonly believed to be computationally more intensive than other cryptographic operations, such as ECC point multiplication, there has been a substantial progress in speeding up the Tate pairing computations. Because of their inherent parallelism, the existing Tate pairing algorithms are very suitable for hardware implementation aimed at achieving a high operation speed. Supersingular elliptic curves over binary fields are good candidates for...

For the Tate pairing computation over hyperelliptic curves, there are developments by Duursma-Lee and Barreto et al., and those computations are focused on {\it degenerate} divisors. As divisors are not degenerate form in general, it is necessary to find algorithms on {\it general} divisors for the Tate pairing computation. In this paper, we present two efficient methods for computing the Tate pairing over divisor class groups of the hyperelliptic curves $y^2 = x^p - x + d, ~ d = \pm 1$ of...

Identity-based (ID-based) cryptosystems eliminate the need for validity checking of the certificates and the need for registering for a certificate before getting the public key. These two features are desirable especially for the efficiency and the real spontaneity of ring signature, where a user can anonymously sign a message on behalf of a group of spontaneously conscripted users including the actual signer. In this paper, we propose a novel construction of ID-based ring signature which...

In this paper, we present two forward secure signature schemes based on gap Diffie-Hellman groups and prove these schemes to be secure in the sense of slightly stronger security notion than that by Bellare and Miner in the random oracle model. Both schemes use the same key update strategy as the encryption scheme presented by Canetti, Halevi and Katz. Hence, our schemes outperform the previous tree-based forward secure signature scheme by Bellare and Miner in the key generation and key...

The output of the Tate pairing on an elliptic curve over a finite field may be viewed as an element of an algebraic torus. Using this simple observation, we transfer techniques recently developed for torus-based cryptography to pairing-based cryptography, resulting in more efficient computations, and lower bandwidth requirements. To illustrate the efficacy of this approach, we apply the method to pairings on supersingular elliptic curves in characteristic three.

The pairings on elliptic curves have been applied for realizing the secure ID based cryptosystems that can be invulnerable to the collusion attacks. The computation of the pairing are necessary for the cryptosystems, though the computation of the pairing requires high cost compared with the computation cost for the power operation over the finite fields or on the elliptic curve when the parameters are securely to be provided. In this paper we propose an efficient method for a class of ID...