# Tag Info

12

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

10

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

8

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

8

Your problem seems to be at least as hard as the 2-weak Bilinear Diffie-Hellman Inversion Problem (2-wBDHI problem): Given $g, g^x, g^{x^2}, g^y \in \mathbb G$, and $T \in \mathbb G_T$ to determine whether or not $T = e(g,g)^{x^3 y}$. Proof: We first need to define an equivalent version of your problem, where we take some generator $h$ so $g = h^b$. ...

7

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

7

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

7

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

7

Note that you do not have an efficiently computable homomorphism from $G_1$ to $G_2$, but in Type-2 you have an efficiently computable homomorphism $\psi: G_2 \rightarrow G_1$ and in Type-3 you do not have one. But what I don't understand is what is the use of the homomorphism in cryptography? Well, if you have a tuple $(aP',bP',cP')\in G_2^3$ with ...

6

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

6

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

6

What the authors of the paper cited by you certainly mean by secure is "treat the hash function to $G_2$ as a random oracle". The problem is that hashing to $G_2$ can only be realized by taking some point in the group and multiplying it with a scalar (which is for instance the output of a full domain hash mapping to integers in $Z_{ord(G_2)}^*$). See for ...

5

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

5

Type-1 (symmetric pairings) are dead for curves over fields of small characteristic. Over prime fields of large prime characteristic they are not really dead, but as they only offer small embedding degrees ($k=2$), they are not really attractive from a performance point of view. You have to choose very large curves (which makes the curve arithmetic slow) ...

5

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

4

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

4

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

4

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

4

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

4

The problem you are referring to seems to be the Decisional Linear Assumption (DLIN), which states that given $(u,v,u^a,v^b)\in \mathbb{G}^4$, it is hard to distinguish a couple $(h,h^{a+b}) \in \mathbb{G}^2$ from a totally random couple $(h,h') \in \mathbb{G}^2$. There is also the Computational Linear Assumption (CLIN), which states that it is hard to ...

4

There really isn't a difference. It is just author preference in notation. Some authors prefer to write the pairing operations multiplicatively $e(P^a, Q^b)=e(P,Q)^{ab}$ while others prefer to write it additively $e(aP,bQ)=e(P,Q)^{ab}$. This comes from the fact that in $e : \mathbb{G}_1\times \mathbb{G}_2\to\mathbb{G}_T$, $\mathbb{G}_1$ and $\mathbb{G}_2$ ...

4

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.

3

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

3

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

3

I use multiplicative notation for $\mathbb{G}_1$ and $\mathbb{G_2}$ (as in your question) as this may make it a bit clearer for you. Lets say the groups are of prime order $p$ and and lets consider your elements w.r.t. bases $g_1$ and $g_2$. Lets write your elements $x_1$ and $x_3$ as $g_1^{a_1}$ and $g_1^{a_2}$ and $x_2$ and $x_4$ as $g_2^{b_1}$ and ...

3

For clarity, I will use an additive notation in the groups $\mathbb{G}_1$ and $\mathbb{G}_2$, and denote group elements with the "$x$" letter, not "$e$". For all $x_1, x_3 \in \mathbb{G}_1$ and $x_2, x_4 \in \mathbb{G}_2$, we have the following: \begin{eqnarray*} e(x_1 + x_3, x_2 + x_4) &=& e(x_1, x_2 + x_4) e(x_3, x_2 + x_4) \\ &=& e(x_1, ...

3

As I said above, I feel the question is bit off-topic here. However, there does not seem to be too good a place in SE for questions that combine mathematics and programming on VHDL, where target is obviously something cryptography related. Most questions regarding FPGA are seen in electronics.stackexchange.com. Montgomery reduction in Wikipedia is useful ...

3

If we are to summarize things in one sentence, let's say that pairings allow for three-party mathematical protocols. Consider for instance identity-based encryption. In a classical public-key cryptography system for encrypting messages (e.g. emails), the sender must know the recipient's public key in order to encrypt the message. Distribution of public keys ...

3

Thats a bit outdated as for your choice of setting (with $k=6$) the 170 bit will give you 1020 bit security in the subgroup of $F_{q^6}^*$. In your case for embedding degree 6 I would at least take 224 bits which would give you 1344 bits in the multiplicative subgroup of $F_{q^6}^*$ or you even go to 256 bits which will give you 1536 bits. Anyways the ...

3

Pairings in cryptography is a very important tool, the introduction of which has developed a new field, that is pairing-based cryptography. After the independent pioneering work by Joux and by Sakai et al.("Cryptosystems based on pairing"), many pairing-based crypto-systems emerged. In cryptography, pairings are often treated as "black-box", and then we ...

3

The problem can be simplified to the following problem, since the standard argument doesn't really take into account that you can't generate all the polynomials of the given maximum degree : Assume that we have sampled a random point $\vec{x}\in \mathbb{F}_p^n$. We let an adversary adaptively choose polynomials of degree at most $d$ and after each choice ...

Only top voted, non community-wiki answers of a minimum length are eligible