Questions tagged [pairings]
Pairing-based cryptography uses bilinear maps to create a gap group that allows efficient constructions of certain primitives.
214
questions
2
votes
1answer
43 views
Hard Problems in Pairings
I want to know whether the following problem is considered as a hard problem in complexity theory or not?
Given $g,g^a,g^b \in G_1$ (for unknown $a,b\in \mathbb{Z}_p^{\ast}$), compute $e(g,g)^{ab^2}\...
4
votes
5answers
3k views
Why do we use groups, rings and fields in cryptography?
I'm a student of Masters in Cyber Security. I have a habit to understand things from their first principles (at the very beginning). Kindly use any simple mathematical example to answer because I have ...
0
votes
1answer
34 views
Software implementation of symmetric and asymmetric bilinear pairings
I have recently read a paper about pairings, which only implemented asymmetric bilinear pairings and it mentiond that $\eta_{T}$ pairing is the most efficient algorithm for symmetric pairings. I ...
0
votes
0answers
26 views
How to prove possession of a CL signature in zero-knowledge?
Assume that we have the following signature scheme CL Signature:
Choose two cyclic groups $G = \langle g \rangle$ and $G_T = \langle g_T \rangle$ of order $q$, that have a pairing $e$.
Uniformly and ...
1
vote
0answers
25 views
How to prove in zero-knowledge that the attributes of Pointcheval Sanders signature is the opening of a commitment?
In anonymous credentials schemes, it is possible to anonymously prove knowledge of a signature. Proposals for anonymous credentials with attributes also include a method for proving statements about ...
1
vote
1answer
83 views
Can you use ECDSA on pairing-friendly curves?
I'm learning about Elliptic curve cryptography. If I understand right, ECDSA and other algorithms used in ECC are dependent on the curve chosen. So, before you want to use ECDSA, you first have to ...
1
vote
1answer
126 views
Is BBS+ 1. a multi-messages signing protocol or 2. a group signature signed by a member of a group anonymously?
There's no doubt that the BBS Signature was born from this classic Short Group Signature paper in 2004. It's capable of Zero-knowledge.
In the paper, section 5, it describes how a member of a group, ...
1
vote
1answer
52 views
Importance of supersingularity of elliptic curves
I'm struggling to understand the high-level idea of "Verifiable Delay Functions from Supersingular Isogenies and Pairings" (https://eprint.iacr.org/2019/166.pdf) by De Feo et al.
I will ...
2
votes
1answer
67 views
In q-SDH problem, where are those points $\frac{1}{\beta+x}g$ or $g_1^\frac{1}{x+c}$ on elliptic curve?
For the q-SDH problem, given the generator $g_1$ as a point on the elliptic curve, I can picture the $\beta g_1, \beta^2g_1, ..., \beta^qg_1$ since we can simply do the point adding $g_1$ multiple of $...
3
votes
1answer
103 views
How to achieve identity authentication without revealing credentials
I am looking at a scenario where I would like to claim to an authority (call it A) that I am indeed me without revealing my identity documents. I am guessing some zero knowledge protocol has to be ...
0
votes
1answer
79 views
Exponentiation Problem of G2 in MNT curve
I made a simple python program in the Charm framework (https://github.com/JHUISI/charm):
...
0
votes
0answers
30 views
Where can I find references to the theory behind PBC library?
I don't know if this is the right place to ask this type of question. Anyway, I'm using PBC library for a project, but I'm a very newbie for what concerns pairing based cryptography. Then I ask some ...
0
votes
0answers
16 views
what is the non_residue value of BN462
I found an algorithm to find the frobenius coeffs here.
Here, the non_residue of BLS12-381 is -1,
And non_residue of BLS12-377 is written -5.
How can I find this value?
And what is the non_residue ...
1
vote
1answer
79 views
Can I convert $F_{q^{12}}$ to $F_q$?
I seeing a paper about Elliptic curve based proxy re-encryption.
And I want to implement this through BLS12-381 Curve.
However, When looking at the documentation for paring or the library, the value ...
1
vote
1answer
155 views
What is different between G1×G1→GT and G1×G2→GT in the bilinear pairing?
It is an implementation of the bls12-381 algorithm known as pairing-friendly, at GitHub.
Looking at this, the pairing parameters are $G_1$ and $G_2$,
$G_1$ is the point of $F_q$, $G_2$ is the point of ...
0
votes
0answers
29 views
How to estimate the computation overhead of ECDSA?
I am using ECDSA as a digital signature scheme. Using Charm, I got the timing for the multiplication, exponentiation, and pairing operations; they take 0.005, 9, and 4.4 ms respectively. I want to ...
1
vote
0answers
34 views
Fixed variable in Groth16
In the paper On the Size of Pairing-based Non-interactive Arguments by Jens Groth, it is always referred in the equations to satisfy that $a_0 = 1$ and the others $a_1, ..., a_m \in \mathbb{F}$.
I am ...
0
votes
0answers
54 views
Can Pedersen commitment be used in pairing groups?
For bilinear groups: $(p,\mathbb{G}_1,\mathbb{G_2},\mathbb{G}_T,e,g_1,h_1,g_2,h_2)$, where $\mathbb{G}_1,\mathbb{G_2},\mathbb{G}_T$ are groups of prime oder $p$. $g_1,h_1$ are generators of $\mathbb{G}...
1
vote
1answer
102 views
Current situation of bilinear pairing protocols
The bilinear pairings are considered as the key enabler for many novel cryptographic protocols, such as three-party one round DH[1], shorter signatures and certificateless (ID-based) crypto[3] , which ...
3
votes
1answer
88 views
Understanding the groups used in bilinear Ate-pairing
The bilinear ate pairing $e:G_1\times G_2 \rightarrow G_T$ is defined over the following groups:
\begin{equation}
\begin{aligned}
& G_1 = E(\mathbb{F}_p)[r] \cap Ker(\pi_p-[1]), \\
& G_2 = E(...
2
votes
0answers
49 views
Groth-Sahai Proof of multi-exponentiation
I want to create a NIZK proof of a multi-exponentiation via Groth-Sahai proofs. In the lectures of Jens Groth in a winter school of Bar-Ilan University, he shows a way to transform multi-...
1
vote
0answers
17 views
Is the k-sum attack efficient in bilinear pairing variants?
From the k-sum definition, the objective is to solve something like:
$\sum_{i=1}^n c_i = v_1$ where $v_1$ is known.
If we use Elliptic Curve Points ($C_i$ and $G$) we can define a bilinear pairing ...
2
votes
1answer
139 views
Bilinear Map over group of unknown order
Is it possible to build a bilinear map where the underlying group is of unknown order?
To maintain context, the original question appears below.
As per poncho's excellent answer, my original idea is ...
1
vote
1answer
61 views
What are the BLS12-381 settings?
I can't find the exact type and settings for the BLS12-381 curve.
Is this type-3 in Symmetric XDH settings ?
0
votes
1answer
100 views
Can BLS aggregate signatures be merged?
In some non-interactive, pairing-friendly signature scheme, such as BLS12-381, is it possible to merge partially-overlapping aggregate signatures?
For example, say you have two aggregate signatures, $...
1
vote
0answers
33 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 ...
4
votes
0answers
66 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
105 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
30 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
32 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 ...
1
vote
1answer
117 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
73 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
56 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 ...
3
votes
0answers
119 views
New Pairing Friendly Curves for SM9
A paper was presented at the INSCRYPT 2018 called: "Searching BN Curves for SM9 (Pay-Walled)"
SM9 is a Chinese National Identity Based Cryptography Standard and was originally published using a 256-...
1
vote
1answer
228 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
514 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
106 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
42 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
50 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
148 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
101 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
59 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
114 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
70 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
141 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 $e : ...
0
votes
0answers
81 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 $e : G ...
5
votes
1answer
194 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
159 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
82 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
142 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. ...
