Tag Info

Hot answers tagged

10

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


9

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


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

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


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

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


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


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

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

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


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

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

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


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

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

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


3

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


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

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


2

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.


2

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.


2

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


2

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


2

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


2

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



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