15
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 ...
12
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) ...
12
The facts you mention regarding the embedding degree show that FourQ is not a pairing-friendly curve, and hence you cannot compute a pairing on it efficiently. Indeed, the representation of group elements both in the source group on the “other side” and in the target group involve something like $2^{246}$ coefficients over $\mathbb{F}_q$, so you cannot even ...
11
(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 ...
11
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 $P'$ ...
10
I am just going to answer regarding identity-based encryption (IBE): I don't know much about the situation for attribute-based encryption.
Also, I am just answering based on today's situation: recent IBE constructions may prove to be very efficient (or not) in the future, and if you want to consider only post-quantum schemes you will have to discard IBEs ...
10
Although the question is a bit broad, I think it's an interesting one.
Giving a bit of context helps with the explanations. In the 80's, many cryptographic primitives have been design, based on group structures (usually relying on variants of the discrete logarithm assumption over this group). The rationale behind the initial introduction of elliptic curves ...
9
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
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 ...
8
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 ...
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$. Your ...
8
I purposefully did not look at the details of the change you are proposing because whatever the change is, the answer is a resounding YES. If you make any change to a cryptographic construction, then you must prove the security of the modified scheme. If you are lucky, you may be able to reduce the security of the modified scheme to the original scheme, or ...
7
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 ...
7
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 ...
7
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 ...
7
Pairings, or bilinear maps, have indeed found a great deal of applications in crypto; hence, researchers have soon pointed out that further "degrees" of linearity (trilinear maps, etc.) would provide even more powerful applications.
Nowadays, multilinear maps are one of the most powerful cryptographic primitives. They are at the heart of ...
7
A BN-curve over a 256-bit prime field $\mathbb{F}_p$ has, being an elliptic curve, a 256-bit group attached to it, say of order $N$. As the best known attacks take $\approx\sqrt{N}$ times, this gives us 128-bits security against discrete logarithm attacks.
The curves also have embedding degree 12. That means we can use a pairing to map a discrete logarithm ...
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
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 $\mathbb{F}_{8111^3}...
6
BLS signatures work in any so called gap group, i.e., a group where the computational version of the Diffie-Hellman (DH) problem - the CDH - is hard, but the decisional version of the DH problem - the DDH - is easy. Below I'm using the notation from the wikipedia article on BLS.
Just recall, that the DDH in a group $(G, g, r)$ (where $g$ is a generator and ...
6
Notation is basically a free choice of the author, as they describe functionally the same. And there is no fixed definition for this. However, common practice in mathematical publications is:
Multiplicative notation for arbitrary groups
Additive notation for commutative groups
This can be found here: math-SE, wolfram
Wikipedia also states, that additive ...
5
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 ...
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
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 ...
5
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 ...
5
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$ ...
5
This can be calculated by dividing $f(e,s)/(e_k+s)$ (assuming all $e_i$'s and $s$ are known to me) and raising $g$ to it.
First, if the prover knows $s$, it doesn't need to know the $e_i$'s to create membership witnesses.
It can simply raise the accumulator $\mathsf{acc}$ to $1/(e_k + s)$:
\begin{align*}
\mathsf{wit}_{e_k} &= \mathsf{acc}^{\frac{1}{e_k ...
5
No, it is not possible.
By the definition of bilinearity, we have $e( kG, H ) = k \cdot e( G, H )$. If the order of $G$ is $r$ (that is, $rG = 0$, we have $e( rG, H ) = e( 0, H ) = r \cdot e(G, H)$. We know $e(0, H) = 0$ (as bilinear functions maps the identity to the identity), and hence we have $r \cdot e(G, H) = 0$; that is, the order of $e(G, H)$ must ...
5
The embedding degree specifies how many times bigger the finite-field you map to is compared to the field the curve is defined over.
For example for BN(2,254) the degree is 12, mapping to a 3000 bit field, which matches the security level of the curve (~128 bits of security for both) and is reasonably efficient (you can perform a couple of hundred ...
5
For the following explanation, let $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$. It depends on the setting you are using whether DDH can hold or not. In the symmetric setting ($\mathbb{G}_1 = \mathbb{G}_2$, i.e., Type 1 pairings) the pairing serves as a DDH oracle for both, $\mathbb{G}_1$ and $\mathbb{G}_2$ and DDH can neither hold in $\...
Only top voted, non community-wiki answers of a minimum length are eligible
