Questions tagged [elliptic-curves]

Elliptic curves are algebraic-geometric structures with applications in cryptography. Such a curve consists of the set of solutions to a cubic equation over a finite field equipped with a group operation. Questions relating to elliptic curves and derived algorithms should use this tag and might also consider more specific tags such as discrete-logarithm and ecdsa.

207 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
66 views

ECC - complex multiplication and key agreement

I'd like to ask three questions - 2 of them regard CM method. The last is regarding the ECC domain parameters generation on the fly, see https://eprint.iacr.org/2015/647.pdf What role has ...
2
votes
0answers
295 views

Proving that a point on elliptic curve is smaller than half of group's order

Let's say I have an elliptic curve where generator $G_1$ has prime order $q$. Let's also say I have committed to a point $A_1 = a \cdot G_1$. Could I use the scheme below to prove that $a < \frac{q}...
2
votes
0answers
60 views

Proving key equivalence across different elliptic curves

We can use the technique described in this answer to prove key equivalence across two elliptic curves of different order. I'm wondering if modifying the technique as described below would compromise ...
2
votes
0answers
411 views

j-invariant of an elliptic curve

Given an elliptic curve $(E/\mathbb{K})$ where $char(\mathbb{K}) \ne 2,3$ defined by the Weierstrass equation $y^2=x^3+ax+b$. The $j$-invariant is $j=1728 \frac{4a^3}{4a^3+27b^2}$. I want to ...
2
votes
0answers
52 views

Is my way safe to remove SSL CA Cert by DHT and PoW NodeID for a decentralized system?

To implement a decentralized system, I wrote a TLS like P2P net stack. The main idea is removing CA Cert from the whole system by using a DHT for Naming and Key Exchange. I am not a crypto expert, so ...
2
votes
0answers
193 views

Creating ECC Signature - Is “R” necessary in calculating “S”

After going through the mathematical proof in confirming ECDSA, it doesn't seem apparent to me that "R" is necessary in calculating "S" for the signature. In other words, what's the problem with ...
2
votes
0answers
221 views

What standards of ECC point compression exist?

The method that I used before to decode EC point from public key led me in a dead end. So I just want to know what yet I could try. I've got a public key that I don't know how to decode and I am ...
2
votes
0answers
177 views

Is EC El Gamal the only option?

This question is related to the question I asked here. I'm looking for encryption scheme with the following properties: Given $m$ is a 256-bit value, $pub_a$ and $pub_b$ are public keys, and $priv_a$ ...
2
votes
0answers
67 views

Asymmetric encryption property required in an authentication protocol

We want to choose an asymmetric encryption scheme for use as follows: A device holds its private key, with the corresponding public key known and trusted by all. The device also holds a small $b$-bit ...
2
votes
0answers
670 views

What ECDSA key is used to sign the ECDHE key exchange?

I have a server using TLS1.2 with an ECDSA certificate using secp256r1. The algorithms being used to connect to my browser are TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384 as I expect from my server ...
2
votes
0answers
118 views

Group signature Elliptic curve

I have been doing some research in group and ring signature literature. I am trying to find a ring/group signature which provide the following propriety: Anonymity for the signer Verifiable by a ...
2
votes
0answers
240 views

What pairings are used in PBC and charm-crypto with the proposed elliptic curves?

I'm implementing a pairing-based signature scheme using Charm Crypto and PBC, and I'm struggling to understand the relationship between the curves proposed for use with pairings and the pairings ...
2
votes
0answers
266 views

Frey-Rück Attack (FR-Reduction) - Tate Pairing

I am trying to understand the Frey-Rück attack and found different ways of a possible implementation. Since I am not yet very familiar with the Tate-Lichtenbaum pairing and the theory of divisors I ...
2
votes
0answers
56 views

Efficiently formatting data so that each byte is critical

I'm experimenting with implementing a Fair Exchange Protocol that assumes there is a trusted third party to provide a hash-checksum of the two files for each missing byte, (so that the exchange can ...
2
votes
0answers
261 views

How are Zhang-Safavi-Susilo signatures short?

ZSS signatures have been introduced by Fangguo Zhang, Reihaneh Safavi-Naini, and Willy Susilo: An Efficient Signature Scheme from Bilinear Pairings and Its Applications, in proceedings of PKC 2004. ...
2
votes
0answers
85 views

Is discrete log as hard when given same challenge in both pairing groups, in the case of BN curve and its sextic twist

This is a special case of the question Generalization of the DL-assumption in bilinear group pair, that wasn't answered. Suppose $G_1$ is a BN curve over $F_q$. That is the set of elements $(x,y)\in ...
2
votes
0answers
201 views

Finding the largest gap between the x coordinates of all points on an elliptic curve

Till now all we know is Hasse's theorem, which states that $|\#E(p)-(p+1)| \leq 2\sqrt{p}$, where $\#E(p)$ is the total number of points in $E_p(a,b)$. Is there any other theorem which defines ...
2
votes
0answers
537 views

Feasible attacks on ECRSA cryptosystem

In ECRSA cryptosystem, I want to know the feasible attacks. For illustrations we have two prime $p$ and $q$ such that $p \equiv 2 \pmod 3$, $q \equiv 2 \pmod 3$ and generate key pair as follows: $$n = ...
2
votes
0answers
246 views

Boneh/Franklin Identity based encryption with Tate pairing

Boneh/Franklin developed an identity based encryption scheme based on the Weil Pairing. This algorithm has also been standardised in IEEE P1363.3 . I know that this algorithm can also be implemented ...
2
votes
0answers
195 views

Can we break ECDLP with this machine?

Let $P$ and $Q$ are two points of NIST elliptic curve $E$ (defined over $F_{2^m}$ with prime $m$) and $k$ is a private key such that $k.P=Q$. Also we have a machine that is able to leak some ...
2
votes
0answers
315 views

How to compute projective coordinate Z in elliptic curve cryptography?

I was working on affine coordinates and struggling with the computation time taken for operations and then I was advised to use projective coordinates so that mul-inverse operation can be avoided Can ...
2
votes
0answers
61 views

Construct points with the same discrete logarithm

Assume we have an elliptic curve $E$ with a Tate (or Ate,...) pairing $G_1 \times G_2 \mapsto G_T$ Now the task is to find $g_1, g_1' \in G_1$ and $g_2, g_2' \in G_2$ such that the discrete logarithm $...
2
votes
0answers
391 views

RSA_DH vs ECDH implementation

In ECDH protocol is possible, naturally, to use the same algorithm for calculate a secret key for both communication parties (Alice and Bob for example). It is possible to design also a same algorithm ...
2
votes
0answers
136 views

Generating interactive, secure multiple ECC key pairs deterministically

In Elliptic Curve Cryptography (ECC) assuming user A has a private public key pair of $S$, $P$ accordingly with generator point $G$ which as we know is: $$P=S*G$$ Assuming that user A wants to ...
2
votes
0answers
370 views

Type G Bilinear Pairings

I was reading PBC and its implementations for finding pairing parameters. I am particularly interested in implementing a BLS signature scheme with 20-byte (160-bit) signatures ("short signatures"). So,...
2
votes
0answers
207 views

Hardware Implementation of Pairing over BN curves

I am in the middle of FPGA based Hardware architecture design for the computation of Pairing (particularly R-ate Pairing) over BN curves. Where, the point addition, and point doubling should be ...
2
votes
0answers
107 views

Reliability of a single-pass deniable authentication protocol?

I look for one-pass deniable authentication protocol with a short message payload for my project and find a solution: ...
2
votes
0answers
377 views

Defending hybrid encryption schemes against padding oracle attacks

I intend to use a generic integrated/hybrid encryption scheme for transmitting information between a client and a server. Key encapsulation: a 128-bit symmetric key is generated and asymmetrically ...
2
votes
0answers
371 views

Known vulnerabilities in (EC-)KCDSA

Does anybody know if there's known vulnerabilities in KCDSA/EC-KCDSA? I have been researching for the past few hours and I haven't found anything. Wikipedia has very limited amount of information and ...
2
votes
0answers
605 views

Where can I find examples of ECC implemented in VHDL?

I am looking into implementing ECDSA signature and ECDH key agreement in a Xilinx FPGA. All the examples I have found of VHDL implementations skip over how to construct the low level ECC primitives (...
1
vote
0answers
34 views

Elliptic curve subgroup with $p$ elements in field of characteristic $p$

Are there any elliptic curves defined over a finite field $\mathrm{GF}(p^k)$ with a subgroup of order $p$ where the discrete log (and preferably DDH) problem is hard? Elliptic curve with prime ...
1
vote
0answers
43 views

Schoofs Algorithm

I studied Schoofs Algorithm described by Washington. On page 125 he says that we could write $y'/y$ as a function of $x$, which makes sense since earlier on the page he denotes $y'= r_{2,j}(x)y$. But ...
1
vote
1answer
41 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 ...
1
vote
0answers
42 views

Example for point addition using Jacobi transformation and small integers

This video explanation is great because it shows an example using small numbers, if it wasn't for that example my code would be wrong. Still: the code takes 0.5 seconds to calculate 300 point ...
1
vote
0answers
61 views

Quantum computers and elliptic curves

I know, that quantum computers can theoretically break the discrete logarithm problem using the shor algorithm. The problem with quantum computers is not the time, but the space ( the needed qubits ). ...
1
vote
0answers
53 views

Pohlig-Hellman on ECDLP over extension field $\mathbb{F_p}^6$

Suppose there is an elliptic curve $E$ in form $y^2=x^3+b$ defined over $\mathbb{F_p}$, where $p$ is large prime. #$E(\mathbb{F_p})$ is also a large prime but #$E(\mathbb{F_p})\ne p$. ECDLP on this ...
1
vote
0answers
30 views

How do Edward curves scale better in computation time compared to Weierstrass curves?

I see people talk about Edward curves (when I discuss Ed25519) as better curves than Weierstrass for computations. Now I get that Edward curves have the nice addition formula, but if we have a ...
1
vote
0answers
39 views

Non-interactively share secret with group without revealing to generator?

Imagine someone knows a set of $n$ ECC public keys $\mathcal R = \{K_1, K_2, ... K_n\}$ but they don't know the corresponding private keys $k_1$, $k_2$ ... $k_n$. They wish to create a public key $sG$ ...
1
vote
0answers
41 views

How many 2-torsion points in an elliptic curve?

N torsion points have the structure ker([n]) ≅ Zn×Zn , so ker([2]) ≅ Z2×Z2 , gives us 3 2-torsion points. but ker([4]) ≅ Z4×Z4 ,this means we have 5 subgroup of order 4 . In each subgroup , there is ...
1
vote
0answers
33 views

Determining order of the group for an elliptic curve defined over a finite field

I need to find out the order of the group for an elliptic curve. See the image for the question. The inequality condition after simplification leads to $-2 \sqrt{p} \leq m \leq2 \sqrt{p}.$ Also, the ...
1
vote
1answer
55 views

MOV attack when $E(\mathbb{F}_q)$ is cyclic

Suppose $P\in E(\mathbb{F}_q)$ and $R=dP$. In the MOV attack, we compute $\alpha=e(P,T)$ and $\beta=e(R,T)$ and try to solve the discrete logarithm problem for $\alpha$ and $\beta$ in the finite ...
1
vote
0answers
46 views

How to maintain the width of the cipher image in ECC Image Encryption from Singh and Singh (2015)?

I am a beginner in cryptosystems and I hope I would be accepted in the community. I was trying to implement Singh and Singh (2015) ECC image encryption algorithm on Matlab. I have been able to ...
1
vote
0answers
69 views

How to Reduce a Quaternion Ideal into Power Smoothness?

(TL;DR) How exactly do we reduce a quaternion ideal into another powersmooth one? Given a supersingular elliptic curve, it is known that its endomorphism ring is non-commutative. Specifically, there ...
1
vote
0answers
53 views

How to find Y on an elliptical curve in a finite field?

For example, let's use secp256k1, the curve used by bitcoin, y^2 = x^3 + 7, and x=12. Over the real numbers, that calculation is trivial - I can simply use a calculator. But in a finite field, how ...
1
vote
0answers
77 views

Elliptic Curve (Point Counting)

I am studying elliptic curves in particular point counting. If I have coordinates P and 2P, is there a way to calculate the total points in between P and 2P using either curve parameters or algorithm? ...
1
vote
0answers
32 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 ...
1
vote
0answers
78 views

is forward secrecy irrelevant for non-streaming applications?

I asked a question yesterday about the Keybase key model and got no answers, unfortunately. Let me rephrase the question to make it clearer: in the case, if 2 users just want to send each other low-...
1
vote
0answers
67 views

Trying to understand Keybase's key model and replacing PGP with device keys

I am exploring Keybase and I thought it was merely a wrapper for gpg and connecting its public key with social accounts (e.g. github, twitter, etc...). But after reading the very short and unclear ...
1
vote
0answers
59 views

Verifying the ownership of curve25519 public keys

Let's say we have a group of users, authenticated by a server that providers the service, communicating on a secure channel (e.g. over HTTPS/TLS) and each user has a corresponding curve25519 key pair. ...
1
vote
0answers
51 views

Need help understanding SPAKE2 setup values

I am trying to write a simulation of the SPAKE2 protocol in python (just so I can get a better understanding of the protocol altogether). I am reading through the ietf draft here: Datatracker. There'...