Tag Info

If both $G_1$ and $G_2$ have prime order $r$, then this means that there are generators $g_1$ and $g_2$; thus, for every $u_1 \in G_1$, there is an integer $x_1$ modulo $r$ such that $u_1 = g_1^{x_1}$. Therefore, every pairing value $e(u_1, u_2)$ is equal to $e(g_1^{x_1},g_2^{x_2}) = e(g_1, g_2)^{x_1x_2}$ by bilinearity. It follows that $e(g_1,g_2)$ is a ...

Joux's work is really summarized by this answer already on Crypto.SE. He discovered a way to generalize Diffie-Hellman to multiple (more than 2) parties. In particular though, he presented a single round protocol for key establishment between 3 parties. Something that until then was thought to be impossible. Boneh and Franklin developed the first fully ...

Crypto based on cyclic groups is (at a very high level) about "hiding" things "in the exponent" and then manipulating those values as they live in the exponent. As an example, in a cyclic group $\langle g\rangle$, you can "hide" a random value $x$ as $g^x$. Without a bilinear pairing, all you can really do "in the exponent" are linear/affine (degree-1) ...

Conventional public-key cryptosystems require key distribution: in order to encrypt a message destined to Bob, you must know Bob's public key with enough certainty (an attacker could try to substitute his own key there). Various systems have been designed for that, e.g. certificates. In practice, key distribution proves complex. With IBE, the name (email ...

I do not know of any general way to create the mapping you want (and if there was, it might turn into an efficient point-counting algorithm, which would be great), but you can do this on some curves. Consider a prime $p$ equal to $2$ modulo $3$. In $\mathbb{Z}_p$, every value has a single cube root (because $3$ is then invertible modulo $p-1$). Then, look ...

To my knowledge the answer is no. Informally, the only known method to construct pairing friendly curve is the CM method, which allows you to find an elliptic curve with strong constraints on its number of points if you put few constraints on the cardinal of the base field, or conversely a curve over a very constrained base field with only little ...

(An addendum to the answers by Thomas and Poncho:) One disadvantage of IBE (or advantage, depending on the point of view) is that the central authority knows (or can generate) all private keys, i.e. it allows a global key escrow. For example, if an email address changes the owner (i.e. there is a new person in a company which now should read the mails ...

Well, the quick answer to what is IBE is "it's public key encryption except that someone's public key can be an arbitrary string, rather than something picked by a key generation process". The first obvious question to above would be "if John Smith can get the private key corresponding to "JohnSmith@company.com", why can't anyone else? The answer is that ...

It's the prime of the prime field. (Note that, if you're also using the curve for pairings, you'll need arithmetic over both $\mathbb{F}_p$ and $\mathbb{F}_{p^{12}}$. The first can be viewed as arithmetic modulo $p$, but the second is slightly more complex, and can be viewed as arithmetic of polynomials over $\mathbb{F}_p$, modulo a reduction polynomial.)

Most pairing-based cryptography (PBC) schemes are based in elliptic curve cryptography (ECC). The main function in PBC is the pairing, which is a function $e$ with two parameters, e.g. $r = e(P, Q)$. The relationship with ECC is that $P$ and $Q$ are points in elliptic curves over finite fields. The value $r$ is an element of a certain finite field (related ...

Antoine Joux announced the computation of discrete logarithm over $\mathbb{F}_{2^{257 \times 24}}$, which is now pretty close to what was being used in pairing-based cryptography. According to Joux, "a direct consequence of this record is that supersingular curves (of genus 1 or 2) defined over GF(2^257) cannot be used securely for pairing-based ...

IBE is advantageous over standard asymmetric methods in one aspect, and that doesn't appear to apply in the case you're interested in. In both cases, IBE and asymmetric methods require an enrollment process (whether to distribute secrets, or authentication data), so there's no real difference there. However, when Alice wants to send a message to Bob, with ...

That depends on the protocol being used, but most pairing-based protocols assume that the Bilinear Diffie-Hellman (BDH) problem is hard: given $P, aP, bP, cP$ for group element $P$ and integers $a, b, c$ it is hard to compute $e(P, P)^{abc}$ for a given pairing $e$. There are many related problems that, if broken, could be used to break the BDH: the ...

Yao's garbled circuit is simple to understand. First of all, note that if we can securely compute $\mathsf{NAND/NOR}$ of two input bit, we can perform any boolean operation. Yao's garbled circuit tries to achieve the same. Lets look at scrambled $\mathsf{OR}$ gate. Alice creates a set of four keys, $K_{x=0},K_{x=1},K_{y=0},K_{y=1}$ She then creates 4 ...

What I think your looking for is this paper. It's a modficiation of Cocks-Pinch that was published by Stanford last year. It allows for it to be defined for most k's inside of your extension field.

Well, assuming the equation holds, $\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$ must also hold, due to the bilinearity of $e$. (Conversely, the equation only holds mod |G_1|.) To see why, recall that the fact that the mapping $e$ is bilinear translates into $e(g^a,h^b)=e(g,h)^{a*b}$ for all elements $g$ and $h$ in $G$ and for all integers $a$ and $b$. ...

Let's take your latter example. We will use the Weil pairing here, since that was the original MOV approach. Let's pick some arbitrary points in your curve: $$ \begin{eqnarray} P &=& (6116 : 2715) \\ Q &=& (3034 : 462) \end{eqnarray} $$ From now on, we'll actually work in an extension field of $\mathbb{F}_{8111}$, namely ...

I don't think $h^l$ where l is a float number is a well defined operation in a finite group, regardless of what context you want to use this group for. A group is a set of elements G with a binary operation $\cdot$ (multiplication) defined, often denoted as (G,$\cdot$) satisfying four properties. You can find more information here: ...

Generally it is not advisable to create your own cryptographic operations on a smart card. When programming a smart card you need to understand the risks of side-channel attacks and perturbation attacks. For instance, you may need to program your way around DPA (Differential Power Analysis) and LFI attacks (Laser Fault Injection). Normally you program on ...

If you can find such an efficiently computable function (other than the trivial solution $\hat{e}( x, y ) = 1\ \ $ for all $x$, $y$), then you have shown that the decisional Diffie-Hellman problem is easy. That is, given $g$, $g^a$, $g^b$, $g^c$, you can check whether $$ab = c$$ simply by testing: $$\hat{e}( g^a, g^b ) = \hat{e}( g, g^c)$$ The ...

I think you have a lack of knowledge on pairings and finite fields. Your definition of the pairing $e(X,Y)=g^{XY} \bmod p$ is not correct. A pairing is defined as a map $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ with the property \begin{align}\text{for all }g_1 \in \mathbb{G}_1 \text{ and } g_2 \in \mathbb{G}_2: e(g_1^a,g_2^b) = ...

If $N$ is the order of the group $\mathbb{G}_T$, then for any element $x \in \mathbb{G}_T$ we have that $x^N = 1$. This follows from the Lagrange theorem. Since $e(g,g) \in \mathbb{G}_T$, the same applies to it.

A composite order group is like having a 2-dimensional vector space, because of the Chinese Remainder Theorem. More concretely in the context of a bilinear map, if $g$ is a generator with order $N=pq$, then $g_p = g^q$ generates an order-$p$ subgroup, and $g_q = g^p$ generates an order-$q$, and $e(g_p, g_q) = 1$. They cancel each other out, and so you can ...