# Tag Info

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

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

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

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

6

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

5

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

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

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

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

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

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

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

3

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

3

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

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

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

An attack against the signature scheme over some group where DDH is easy, can be turned into a solver for the CDH problem over the same group, as is shown in Section 2.3 in the Asiacrypt paper you refer to. So what you are really asking is: In what groups where DDH is easy is CDH still hard? I would not use elliptic curves over extension fields of low ...

2

Ok, I took a look at the paper now. Thomas described the DLIN assumption, which is, however, not the assumption used in the paper you are looking at. Furthermore, what Thomas describes is the 2-DLIN assumption, which can be generalized to the $d$-DLIN assumption in a straightforward manner: $d$-DLIN Assumption: Given a group $G$ of prime order $p$, the ...

2

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

2

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

2

You need to recall how the extension is built. $\mathbb{F}_{p^{12}}$ is built on top of $\mathbb{F}_{p^2}$ using the reduction polynomial $f(x) = x^6 - \xi$, where $\xi \in \mathbb{F}_{p^2}$ is a non-square and non-cube (using the notation from the paper). In other words, this is the set of polynomials with coefficients in $\mathbb{F}_{p^2}$, modulo $f(x)$. ...

1

Your misunderstanding comes from the fact that often in pairing based crypto there is a "slight" abuse of notation. I will use symmetric pairings in the following for simplicity. Often one finds $e: G\times G\rightarrow G_T$ be a pairing, the groups $G,G_T$ are of prime order $p$ and $G$ is generated by $g$. This may mislead you to think that one works in a ...

1

A pairing is a non degenerate and bilinear map from $G_1\times G_2$ to $G_T$. This means that if $g_1$, $g_2$ are generators of $G_1$ and $G_2$ then: By non-degeneracy, $e(g_1,g_2)\neq 1$ and, in fact, $g_T=e(g_1,g_2)$ is a generator of $G_T$ By bilinearity, for any $h_1=a_1g_1$ and $h_2=a_2g_2$, we have $e(h_1,h_2)=g_T^{a_1a_2}$. Note that you don't need ...

1

I point this out because a fair number of practicing cryptographers aren't aware: PBC is slow and outdated and a pain to work with. MIRCAL and RELIC are the two main alternatives.

1

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

1

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

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