Questions tagged [pairings]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
273 views

Are Barreto-Naehrig Curves suitable for pairing-based cryptography?

If Barreto-Naehrig Curves are suitable for pairing-based cryptography, can I use the library available at Optimal ATE Pairing?
2
votes
1answer
282 views

Sextic twist of BN pairing parameters vs security

I've previously asked questions on BN pairing parameters. Here's one more. In the BN construction, one is working in a subgroup of a curve over an extension field $\mathbf{F}_{p^{12}}$ for some ...
0
votes
1answer
80 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. ...
0
votes
0answers
37 views

Pairing-free group based encryption scheme

Can someone explain what is a pairing-free group ? There is encryption schemes, for example 1, that qualify there proposed construction as pairing-free group. However, they use bilinear group in the ...
3
votes
3answers
426 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
40 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
18 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
59 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
115 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
65 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
96 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
29 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
110 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
56 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
104 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
37 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 ...
2
votes
2answers
968 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
45 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
37 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
333 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
68 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 ...
11
votes
0answers
176 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
114 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
69 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
61 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
969 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
189 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
75 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
88 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
87 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
132 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
95 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
100 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
375 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
118 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
214 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
385 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
486 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
299 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
151 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
256 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
202 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
121 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
390 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 ...