Questions tagged [pairings]

Pairing-based cryptography uses bilinear maps to create a gap group that allows efficient constructions of certain primitives.

1
vote
3answers
409 views

How is it decided if $G_1$ and $G_2$ are two “additive” or “multiplicative” cyclic groups?

According to wiki's definition of Bilinear pairing… Let $G_1$ and $G_2$ be two additive cyclic groups of prime order $q$, and $G_T$ another cyclic group of order $q$ written multiplicatively. A ...
3
votes
1answer
30 views

What's the difference between symmetric and asymmetic multilinear map?

In pairing-based cryptography, we have 3 types, namely Type-I, where $\mathbb{G}_1 = \mathbb{G}_2$, and in Type-II and Type-III we have that $\mathbb{G}_1 \neq \mathbb{G}_2$, however in Type-II we ...
0
votes
0answers
17 views

What is the difference between these pairings classifications?

I know the basic definitions of bilinear groups. For example, there is a bilinear pairing that uses elliptic curves and has the following properties: For $G_1$, and $G_2$ are cyclic groups of prime ...
2
votes
0answers
47 views

New Pairing Friendly Curves for SM9

A paper was presented at the INSCRYPT 2018 called: "Searching BN Curves for SM9" http://xxhb.fjnu.edu.cn/_upload/tpl/06/5d/1629/template1629/papers/88.pdf SM9 is a Chinese National Identity Based ...
1
vote
1answer
89 views

Do Weil, Tate, and Ate pairings exist on all elliptic curves?

I don't know much about the math behind elliptic curves. Do Weil, Tate and Ate pairings exist on all elliptic curves? If the answer is negative, then what pairings do MNT, BN and SS curves have? ...
1
vote
1answer
63 views

Is there a concept of embedding degree for non-pairing based elliptic curves?

From this post, I learned the concept of embedding degree. Intuitively, if embedding degree of an elliptic curve $E(F_p)$ is $k$, it means there is a way to transform points in $E(F_p)$ to $F_{p^k}$. ...
2
votes
1answer
64 views

What does the number 256 in pairing curve BN256 indicate?

There are many pairing based elliptic curves like MNT curves, BN curves, SS curves etc., When we say BN256 curve, what does the number 256 indicate? Is it some group order or number of bits required ...
0
votes
1answer
38 views

Does this equation hold in a bilinear map?

I would like to verify whether or not the following equation holds: $e(a,c)^{c1\cdot c2\cdot c3}e(b,c)^{c1\cdot c2\cdot c4}==e(a,c)^{c2\cdot c3}e(b,c)^{c1^2\cdot c2\cdot c4}$ for appropriately ...
3
votes
0answers
27 views

If curve bn256/bls12 support the isomorphism from $G_2$ to $G_1$?

Is bn256 or bls12 a type-2 pairing-friendly curve? As Dan Boneh said here While in many pairing instantiations this ψ exists naturally, in some instantiations it does not. However I can not find ...
1
vote
1answer
80 views

Are there any NIST curves with pairings?

NIST FIPS.186-4 has standardized 5 ECC curves on field 𝔽𝑝 (P-192, P-224, P-256, P-384, P-521) and 10 elliptic curves on binary fields. None of them seem to have pairings. Are there any standard ...
0
votes
1answer
54 views

Computing a sextic twist

Let $(x,y) \in E'_{\mathbb{F}_{p^2}}$ be a point of the sextic twist. I am currently trying to compute: $\psi : (x, y) \leftarrow (\mu^2x,\mu^3y)$ with $\mu \in \mathbb{F}_{p^{12}}$ the root of $(Y^...
1
vote
0answers
99 views

How do pairings behave on G2/twist points off the prime order subgroup?

$\newcommand{\F}{\mathbb{F}}$ Consider the ate pairing defined on a curve $G_1 = E(\F_q)$ and $G_2 = E'(\F_{q^r})$ where $E'$ is a twist of $E$ with the twisting isomorphism defined over $\F_{q^r}$. ...
2
votes
0answers
31 views

Security strength of JPBC Type A curve compared to SecP curve

I recently encountered some problems when learning about the JPBC library. Does the curve generated by (J)PBC using the method typeAcurvegenerator(160,512) and the ...
0
votes
1answer
64 views

How to change the following commitment scheme to Pedersen commitment?

In my question here Zero knowledge set membership protocol The suggested solution allows a prover to choose a commitment $C$. Then, A trusted third party ($T$) can validate if $C$ is valid or not. ...
2
votes
2answers
928 views

Decisional Diffie-Hellman assumption vs decisional bilinear Diffie-Hellman assumption

For the Decisional Diffie-Hellman (DDH) assumption we know that: Given $g^a$ and $g^b$ for uniformly and independently chosen $a,b \in Z_p$ the value of $g^{ab}$ looks like a random value in group $\...
0
votes
0answers
42 views

Prove that a given signature scheme is secure under random message attacks

This is a follow up to my previous question. Consider the following signature scheme: $\operatorname{KeyGen} (1^k$) : On input of a security parameter $k$, choose a symmetric bilinear group with $...
0
votes
0answers
34 views

Prove that a signature scheme is RUF-NMA and not EUF-CMA

I am working on the following exercise: Now, assume the following signature scheme: $\operatorname{KeyGen} (1^k$) : On input of a security parameter $k$, choose a symmetric bilinear group with ...
0
votes
1answer
36 views

Elliptic Curves for Pairings

how can is possible to know if an elliptic curve is suitable for protocols that adopt pairing? For example, in Certificateless Cryptography with pairing, is it possible to know if all elliptic curves ...
3
votes
1answer
320 views

Complex Numbers on Elliptic Curves & Usage in Tate Pairing

I'm working with understanding the internals of the Tate Pairing. I was going through an example of the curve $E: y^2 = x^3 + 3x$ over $\mathbb{F_{11}}$. The author is showing the computation of $e(P,...
2
votes
0answers
62 views

Is this an error in the Pinocchio Protocol paper

I am going through the Pinocchio protocol paper and I need 2 clarifications in the section Protocol 1 (Verifiable Computation from strong QAP). The part that explains the Verify process, which ...
10
votes
0answers
163 views

Proving multiple products “in the exponent”

I'm trying to come up with a small-sized (non-interactive) proof for a Diffie-Hellman-like statement. I'll start by giving an example. The prover has $g^a, g^b, g^c, g^{ac}, g^{ab}, g^{bc}, g^{abc}$. ...
0
votes
0answers
113 views

Sextic twist maps to q Eigenspace of Frobenius

Let $E(p)$ be a Barretto-Naehrig elliptic curve with r-torsion and embedding degree 12 and $E'$ a sextic twist with homomorphism $\psi$. How to show, that $E'$ has a unique r-torsion group $\psi$ ...
1
vote
1answer
63 views

How to apply lagrange interpolation on bilinear pairings?

I have seen in some places applications of Shamir secret sharing and lagrange interpolation mixed with bilinear pairings, however I fail to understand how this works. For instance, here I find the ...
3
votes
0answers
56 views

Is there a bilinear map on a non abelian group or non cyclic group?

I've recently been studying a pairing map on cryptography. In usual definition, a pairing map is always defined on the cyclic group G. Is it possible to construct a bilinear map on a non-abelian group ...
1
vote
1answer
960 views

Variant of the Decisional Bilinear Diffie Hellman problem

I am working on a cryptographic scheme and I need to rely on the following problem, which I have nicknamed the "Hybrid Decisional Bilinear Diffie Hellman (hDBDH)" problem: Let $e: \mathbb G_1 \...
1
vote
1answer
180 views

the decryptNode function for leaf nodes in CP-ABE

Can someone please explain to me why decryptNode gives as result $e(g,g)^rq(0)$ for leaf nodes, I don't understand how they went from the second step to the third (here is the article: Ciphertext-...
0
votes
0answers
15 views

Are compressed pairings used for Barreto-Naehrig curves in practice?

In 2009 Galbraith and Lin wrote the article "Computing Pairings Using x-Coordinates Only" https://link.springer.com/article/10.1007/s10623-008-9233-3, where they proposed to compute pairings on ...
0
votes
2answers
74 views

Does this pairing-based signature scheme work?

Suppose $g$ is a pairing-friendly elliptic curve with subgroup generators $G_1$ and $G_2$. Suppose also that $M$ is the message I want to sign. Setup Compute $A = a \cdot G_1$ and $P = p \cdot G_2$, ...
2
votes
1answer
84 views

Can we use PHE or SWHE instead of bilinear pairings in ZK-SNARKS?

In ZK Snarks bilinear pairings are used to do "encrypted computation". I was wondering if we can use Partial Homomorphic Encryption or Somewhat Homomorphic Encryption instead of bilinear pairings. Can ...
0
votes
0answers
82 views

NIST ECC Curves without pairings

NIST FIPS.186-4 has standardized 5 ECC curves on field $\mathbb{F}_p$ (P-192, P-224, P-256, P-384, P-521) and 10 elliptic curves on binary fields. I need to use ECC curves without pairings for my ...
3
votes
1answer
119 views

Order of twisted curve in pairings

We are doing optimal Ate pairings using a Barreto-Naehrig curve, and I am trying to make sure that an observation I made generalizes. We define $E$ as $y^2 = x^3 + 3$ and use the tower of extensions \...
1
vote
1answer
91 views

Pairing-based cryptography VS ZK-proofs: what's more efficient for threshold systems?

In some papers (e.g. 1, 2) the authors approve that pairings are more efficient than classic zk-proofs (e.g. proof of discrete logarithm knowledge) for the described applications (threshold encryption,...
1
vote
0answers
89 views

Security of BLS under additional information on the secret key

Question A Is the BLS signature scheme still secure if an adversary in addition to the public key $ pk = g_2 \, sk \in \mathbb{G}_2 $ also obtains additional information on the private key $ sk $, ...
1
vote
0answers
14 views

The multi-linear maps are prone to zeroizing attack. Can anyone explain how the zeroizing attack breaks the computational assumptions?

I read that many cryptographic schemes based on multi-linear mapping are not secure because the zero testing procedure and zero encoding help an adversary to reveal the secrets and because of it, many ...
4
votes
1answer
322 views

Simple explanation of Miller's algorithm

Could someone explain to me in few lines (even one sentence) what Miller's algorithm computes? Without talking about divisors and all the other concepts, I would like to be able to explain it to ...
2
votes
1answer
113 views

Type of values that can be accumulated in bilinear map (multiplicative) accumulator reg

Is there any restriction that the members to be accumulated in bilinear map (multiplicative) accumulator need to be relatively prime to $P$, where $P$ is the order of the group.
1
vote
0answers
54 views

What should I change in my implementation to pass from a curve $y^2=x^3+1$ to $y^2=x^3+x$

I tried to change my implementation of pairing in curves $y^2 = x^3 + 1$ to use curves of the type $y^2 = x^3 + x$ but it didn't work. I thought the only thing I had to change in my code was the ...
3
votes
1answer
197 views

How to find a primitive cube root of unity

I would like some help to understand how to compute a distortion map and the result of a pairing. I know that with this equation : $E : y^2 = x^3 + 1$ over some $\mathbb{F}_p$ we have a distortion ...
4
votes
1answer
357 views

Bilinear pairing arithmetic - cryptographic accumulators

For calculating accumulated values for set of elements chosen randomly from, say, $\{e_1 ,e_2,...e_n\}\subseteq X$ we use the formula $acc= g^{f(e,s)}$ where $f(e,s)= (e_1+s)(e_2+s).....(e_n+s)$. ...
6
votes
1answer
453 views

Elliptic curves with pairings at 128-bit security in libpbc?

I am using Ben Lynn's libpbc to implement a BLS threshold signature scheme and I am aiming for 128-bit security (i.e., a forgery attack should take around $2^{128}$ ...
4
votes
0answers
90 views

Can cryptographically useful pairings only be used with elliptic curves?

As far as I understand one big advantage of ECC is that we can use pairings on the group of torsion points of the curve. I was wondering if it is possible to construct pairings from general finite ...
3
votes
1answer
253 views

Why “pairings on elliptic curve” are used?

I'm just curious why do we use pairings on elliptic curve cryptography. There is a lot of information about how to use it, but I cannot find information about why to use it. Can somebody help?
0
votes
1answer
141 views

Understanding the big picture with regard to how anonymous credentials work

I'm trying to learn about anonymous credential systems. I started with Lysyanskaya's thesis, which gives an outline of how to build an AC system given some particular primitives (signature scheme, ...
1
vote
1answer
236 views

Weil pairing of P and Q

it the following example for page 56 of the book http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf I could not understand how the author found the Weil pairing of two points p and Q. I ...
1
vote
2answers
194 views

DDH and pairings are not contradictory in RingCT 2.0?

As I know DDH assumption and bilinear pairings are contradictory, but I see this in a paper, RingCT 2.0. How could this be ok? Linkable ring signature will be attacked by bilinear pairings.
1
vote
1answer
112 views

Linkable Ring Signatures on Pairing-Friendly curves

I'm working on a pairing-friendly (Barreto-Naehrig) elliptic curve. If I understand correctly, one consequence of this is that the Decisional Diffie-Hellman assumption no longer holds, but the ...
1
vote
1answer
386 views

Can the precompiles in Ethereum Byzantium for pairings be used for implementation of BLS verification?

I asked this in the Ethereum StackExchange yesterday but I figured it would be more appropriate to ask it here. I am looking into implementing some operations for the BLS signature scheme in ...
1
vote
0answers
51 views

Complexity lower bound in Uber-Assumption family

I try to wrap my head around calculating of complexity lower bound using Corollary 1 from The Uber-Assumption Family by X.Boyen (http://www.academia.edu/download/30698012/...
4
votes
3answers
496 views

Can you help me understand pairing $e:G \times G \to G_T$ and ( Decision) BDH assumption?

From DrLecter's comment, I know that DDH problem can be efficiently solved with this $$e(g^a,g^b)\stackrel{?}{=} e(g,g^z).$$ I have some trouble to understand this map $e:G \times G \to G_T$. Am I ...
1
vote
1answer
115 views

co-DHP* in G2 for type 3 pairing

In type 3 pairing ($e:G_1 \times G_2\rightarrow G_\tau$ where $G_1\ne G_2$ and no isomorphism from $G_2$ to $G_1$ is known) we have co-DHP* problem: Given $H, aP \in G_1$ and $aQ\in G_2$ calculate $...