Questions tagged [pairings]
Pairing-based cryptography uses bilinear maps to create a gap group that allows efficient constructions of certain primitives.
194
questions
0
votes
0answers
22 views
Bilinear pairings with groups of safe prime order
I am looking for a curve with a bilinear pairing of safe prime order.
I.e. a bilinear map $G \times G \rightarrow G_T$ where $|G| = p$, $p = 2q +1$, and $p,q$ are both prime.
Is it feasible to find ...
0
votes
0answers
25 views
Pair-friendly elliptic curves vs non friendly
Group law operations on pair-friendly elliptic curves are slower than in non friendly elliptic curves, but how much slower? Can't seem to find a performance comparison between the two for a given ...
0
votes
0answers
18 views
Schnorr signature verification via Pairing-Based Cryptography?
Let $e: G^{\dagger}_{1} \times G_{2} \mapsto G_{T}$ define the pairing.
Assuming an output $\sigma = (c, p)$ similar to a Schnorr signature:
$s \times Y \mapsto Y_{s}$ and $m \times G \mapsto M$
$c = ...
3
votes
0answers
36 views
Are all MNT curves assumed to hold XDH?
For one of my projects, I need a pairing group which holds the External co-Diffie-Hellman assumption. I am trying to implement it using Charm crypto python modules which provides support for MNT ...
2
votes
1answer
61 views
Variants of Bilinear Diffie-Hellman Assumption
Could someone point me to the paper/reference where the following variant of q-strong Bilinear Diffie-Hellman assumption was used?
Given $s \in \mathbb{Z}_p^*$ and $g, g^{\frac{1}{s}}, g^{s}, g^{s^2},...
1
vote
0answers
25 views
What to learn in order to understand Weil Divisors
My current role as a software developer is leading into areas of research in elliptic-curve-cryptography that keeps bringing me back to bilinear pairings. This includes BLS Signatures, CL Signatures ...
1
vote
1answer
25 views
Group Signatures with VLR Revocation Check
I was reading the paper by Boneh et al. Link. The scheme describes what is called a Verifier Local Revocation Technique. The Scheme assumes that a Revocation List [RL] allows each verifier to check ...
0
votes
0answers
32 views
Accumulation of elements with a bilinear (pairing-based) accumulator
My question concerns accumulation of new elements in bilinear (pairing-based) accumulators.
Suppose you have a pairing $e:\mathbb{G}_1\times \mathbb{G}_2 \longrightarrow \mathbb{G}_T$ with ...
1
vote
1answer
94 views
Calculation of the order of the cosets used in defining the Tate Pairing
I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the preamble to the Tate pairing. (See p. 70 ff., section 5.2 of of the PDF.). I'm having trouble following a ...
0
votes
0answers
47 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
1answer
48 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
20 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
70 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
157 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?
...
2
votes
1answer
191 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 ...
1
vote
1answer
96 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}$. ...
0
votes
1answer
40 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
35 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
121 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
67 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^...
2
votes
0answers
46 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 ...
1
vote
0answers
112 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}$. ...
0
votes
1answer
46 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 ...
0
votes
0answers
65 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
53 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 ...
5
votes
1answer
133 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 ...
1
vote
1answer
105 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
68 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 ...
0
votes
1answer
100 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
2answers
79 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
121 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
104 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
155 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
105 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
108 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
15 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
514 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 ...
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
237 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 ...
13
votes
1answer
230 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}$.
...
1
vote
0answers
42 views
Can the precompiles in Byzantium for pairings be used for implementation of BGLS verification?
BGLS [1] is an aggregate signature scheme by Boneh et al., that allows aggregation of BLS signatures on n different messages from n different signers. What I want to achieve is to verify such ...
4
votes
1answer
383 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?
1
vote
1answer
181 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
282 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
214 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
0answers
53 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/...
1
vote
1answer
130 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 $...
0
votes
1answer
480 views
Pairing in Cryptography [closed]
I am having problems in doing pairing in cryptography. I have tried the PBC library but seems like it doesn't work and I do not understand the documentation because it uses C++ language.
Is there a ...
2
votes
0answers
389 views
Functional signatures with ECDSA Verifier
Functional signatures use some master key to create a functional signature key. The functional key can be used to sign messages, but only if the message is accepted by some predicate function. For ...
3
votes
0answers
93 views
Pairings over elliptic curves on rings
Looking at this presentation, Boneh says that elliptic curves could be defined over $\mathbb{Z}/n\mathbb{Z}$ and not necessarily over a prime field $\mathbb{F}_p$ and hence we could define pairings ...
