15
votes
Why do we use groups, rings and fields in cryptography?
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 ...
13
votes
Accepted
Why "pairings on elliptic curve" are used?
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 ...
12
votes
Accepted
Pairing on FourQ
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 ...
11
votes
Accepted
Are pairings still the most efficient implementation for identity and attribute-based encryption?
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 ...
8
votes
Do I need to prove this?
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 ...
8
votes
Why do we use groups, rings and fields in cryptography?
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....
7
votes
Accepted
Multilinear Pairing in Cryptography
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 ...
7
votes
Accepted
How is it decided if $G_1$ and $G_2$ are two “additive” or “multiplicative” cyclic groups?
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:
...
7
votes
Accepted
BN-Curves for 256-bit symmetric security
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 ...
7
votes
Accepted
DDH and pairings are not contradictory in RingCT 2.0?
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 ($\...
6
votes
Are Barreto-Naehrig Curves suitable for pairing-based cryptography?
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 ...
6
votes
How does Boneh–Lynn–Shacham work?
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 ...
6
votes
Accepted
What does the number 256 in pairing curve BN256 indicate?
It's the size of the prime number of the underlying field in G1, G2 and GT.
In BN256, G1 is $E(\mathrm{GF}(p))$, G2 is a subgroup of $E(\mathrm{GF}(p^{12}))$ (or $E'(\mathrm{GF}(p^{2}))$ when using a ...
6
votes
Accepted
Current situation of bilinear pairing protocols
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 ...
6
votes
Accepted
Is pairing-based crypto post-quantum secure?
Is pairing-based crypto post-quantum secure?
No. That's because solving the Discrete Logarithm Problem in one of the pairing's source groups breaks the pairing's security, and Shor's algorithm ...
5
votes
Bilinear pairing arithmetic - cryptographic accumulators
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 ...
5
votes
How is it decided if $G_1$ and $G_2$ are two “additive” or “multiplicative” cyclic groups?
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). ...
5
votes
Pairing - Is it possible to map two $r$-torsion points to a $r^2$-torsion point?
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)$. ...
5
votes
Does pairings based cryptography inherently require a CRS/trusted setup?
No. For example, these pairing-based protocols don't require trusted setup:
BLS signatures;
tripartite Diffie-Hellman, as mentioned in Elias' answer;
some identity-based encryption schemes (when ...
5
votes
Accepted
Can Curve25519 be used for pairing-based cryptography?
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 ...
5
votes
Accepted
Simple explanation of Miller's algorithm
Miller's algorithm maps two points in a elliptic curve into a element of a finite field. So, if you have a point $P$ and a point $Q$, then Miller's algorithm (which we'll denote $e$) will compute some ...
5
votes
Accepted
Can we use PHE or SWHE instead of bilinear pairings in ZK-SNARKS?
Yes it is possible, and in fact, it has been done, with partial homomorphic encryption (for example in this paper) and somewhat homomorphic encryption (here and here).
The main difference is that a ...
5
votes
Accepted
Is this pairing-based signature scheme secure?
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 $\...
5
votes
Division of two Elliptic curve points in KZG polynomial commitment scheme!
In this lecture, they use multiplicative notation for the pairing groups instead of additive notation. Thus, division is well-defined. Division is just the inverse of the group operation.
The choice ...
4
votes
How to compare performances of lattice-based and pairing-based IBE schemes
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 ...
4
votes
Is the Discrete logarithm problem suitable for this pairing scheme?
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)...
4
votes
Accepted
Elliptic curves with pairings at 128-bit security in libpbc?
The security of pairing-based cryptography relies on the security of the elliptic curve (which is linked to the size of underlying finite field, or "base field") and of the finite extension field ...
4
votes
Accepted
Usage of pairings in proxy re-encryption algorithm
Is $Z^{ak}$ the same as $e(g^a,g^k)=e(g,g)^{ak}$?
That's correct: by the bilinearity property of the pairing $Z^{ak}=e(g,g)^{ak}=e(g^a,g^k)$.
And is $mZ^k$ the same as $e(g^k,g^k)=e(g,g)^{k^2}$?
...
4
votes
Accepted
Order of twisted curve in pairings
Summary: no, this does not hold for all curves. It does hold for all Barreto-Naehrig curves, though; however, there are some subtleties.
First, some definitions. In order to define the question with ...
4
votes
Accepted
Does this pairing-based signature scheme work?
Your proposed signature scheme falls to universal forgeries under a known message attack (UF-KMA).
The adversary $\mathcal{A}$ receives the public key $(A,P)$, a single message signature pair $(M,C)$ ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
pairings × 296elliptic-curves × 119
group-theory × 26
diffie-hellman × 20
signature × 19
zero-knowledge-proofs × 19
identity-based-encryption × 15
discrete-logarithm × 14
encryption × 13
bls-signature × 13
public-key × 12
commitments × 12
hardness-assumptions × 11
abe × 11
implementation × 10
provable-security × 9
finite-field × 8
elliptic-curve-generation × 7
anonymity × 6
accumulators × 5
hash × 4
reference-request × 4
snarks × 4
cryptanalysis × 3
homomorphic-encryption × 3