Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
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 ...
poncho's user avatar
  • 148k
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 ...
Geoffroy Couteau's user avatar
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 ...
Mehdi Tibouchi's user avatar
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 ...
Thomas Prest's user avatar
  • 1,080
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 ...
Yehuda Lindell's user avatar
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....
user93353's user avatar
  • 2,235
8 votes
Accepted

Why is the bilinearity of an elliptic curve pairing shown as multiplicative rather than additive?

For any group, we can write the operation either additively or multiplicatively. If we decide to write it additively, we write the operation as $a + b = c$ If we decide to write it multiplicatively, ...
poncho's user avatar
  • 148k
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: ...
tylo's user avatar
  • 12.7k
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 ...
Geoffroy Couteau's user avatar
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 ...
CurveEnthusiast's user avatar
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 ($\...
dade's user avatar
  • 1,323
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 ...
Conrado's user avatar
  • 6,464
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 ...
DrLecter's user avatar
  • 12.6k
6 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 ...
Geoffroy Couteau's user avatar
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 ...
Conrado's user avatar
  • 6,464
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 ...
Conrado's user avatar
  • 6,464
6 votes
Accepted

What is different between G1×G1→GT and G1×G2→GT in the bilinear pairing?

The most general form of a bilinear map is $e : G_1 \times G_2 \to G_T$. We can categorize a scheme's usage of the bilinear map into 3 standard categories: Type 1: in addition to the bilinear pairing,...
Mikero's user avatar
  • 13.4k
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 ...
fgrieu's user avatar
  • 142k
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 ...
Alin Tomescu's user avatar
  • 1,003
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)$. ...
poncho's user avatar
  • 148k
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). ...
DrLecter's user avatar
  • 12.6k
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 ...
Daira-Emma Hopwood's user avatar
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 ...
CodesInChaos's user avatar
  • 24.9k
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 ...
Conrado's user avatar
  • 6,464
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 $\...
István András Seres's user avatar
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 ...
Wilson's user avatar
  • 929
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)...
poncho's user avatar
  • 148k
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 ...
Conrado's user avatar
  • 6,464
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}$? ...
ckamath's user avatar
  • 5,248
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 ...
Thomas Pornin's user avatar

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