13
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) ...
13
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'$ ...
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 ...
12
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 ...
11
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 ...
9
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
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
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
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
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
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
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 ...
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
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 ...
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
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 $\...
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
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
For all efficient pairings we are aware of and actually use in cryptography, the groups $G_1$ and $G_2$ are elliptic curve groups (which are traditionally additively written, i.e., additive groups). However, as writing down protocols or schemes using multiplicative notation for groups is more compact and often more convenient to read, many people simply ...
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 ...
4
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 ...
4
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 we ...
4
In your setting this is assumed to be hard. It is exactly the task of producing a forgery for message $s$ of the weakly secure Boneh-Boyen signature scheme (Sec. 3.1) under public key $g^{e_1}$ (note that the scheme is presented in the asymmetric setting but can equally be instantiated in the symmetric setting under the $q$-SDH assumption).
In other words, ...
4
It is very hard to give a concrete, "apples-to-apples" comparison of lattice-based and pairing-based IBE schemes. There are many reasons: the research surrounding concrete secure parameters for LWE is still evolving, efficient implementations of operations used in lattice-based IBE (e.g., discrete Gaussian sampling) are still works in progress, one can ...
4
First of all, let us simplify the equation by replacing things that the attacker can compute with known constants. We come up with:
$$a \cdot b^x = y$$
where the attacker knows $a$ (which is $e(g,h)^k$) and $b$ (which is $e(g, h)$, which he can compute, as he knows $g, h$), and the attacker solves for $x, y$.
If it is sufficient for an attacker to find a ...
Only top voted, non community-wiki answers of a minimum length are eligible
