15
Kindly, let me know what was the actual problem which leads us to use groups in cyptogrpahy?
Well, we use groups and other similar mathematical constructs because:
We found there are problems that appeared to be difficult to solve with those groups
We found ways to translate the difficulty of solving those problems into the cryptographical strength of ...
14
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 ...
8
Groups have properties which are useful for many cryptographic operations
When you multiply 2 numbers in a cryptographic operation you want the result of the multiplication also to be in the same set. For e.g. if you are multiplying something which fits in a byte (or n bytes) by something similar, you also want the result also to fit in a byte (or n bytes). ...
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
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
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
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
You can, with the right parameter sizes (384-bit prime instead of the older 256-bit).
Pairings can be attacked in two fronts: the elliptic curve or the extension finite field. The security of the pairing will be the the one that is easiest to break.
Previously, a BN curve using an elliptic curve over a 256-bit prime provided 128 bits of security; it was ...
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 ...
5
That paper is misleading in several ways:
The DSA vs BB comparison: it is unfair because it compares DSA with the "full" BB scheme, which does not produce shorter signatures. The same BB paper describes a "basic" scheme that has a signature that is half the size of DSA. That's the whole point of short signature schemes (being shorter ...
5
The proposed digital signature scheme is not secure! More precisely, it is not existentially unforgeable under an adaptive chosen-message attack.
Let's consider the following efficient adversary $\mathcal{A}$: it queries the $\mathsf{Sign}_{sk}(\cdot)$ oracle for the digital signatures on $m_1,m_2$, where $m_2:=m_1+1$. The received signatures are $\sigma_1=...
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, ...
Only top voted, non community-wiki answers of a minimum length are eligible
