Questions tagged [group-theory]

Groups are an abstract algebraic concept based on a set and a group law (a binary function which closes the set).

Filter by
Sorted by
Tagged with
2
votes
1answer
161 views

What is the correct elliptic curve representation?

I'm studing the basics of elliptic curve from various resource some more mathematical someone more practical. I know that the equation where the elliptic curves come from is the Weistraß equation $$...
1
vote
1answer
163 views

Why do elliptic curves require fewer bits for the same security level?

I'm studying the basics of cryptography and I didn't understand why elliptic curves use fewer bits. For example, finite-field Diffie-Hellman needs at least 1024 bit and it's a DLP, but elliptic ...
3
votes
1answer
75 views

Question about the location of the r-torsion in the quotient group used in the Tate pairing

I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the Tate pairing. He defines $rE = \{r*P | P \in E(\mathbb{F}_{q^k})\}$ and then forms the quotient group $E(\...
3
votes
1answer
147 views

Why work in a subgroup for Naor and Pinkas oblivious transfer?

In section 4 (protocol 4.1) of the paper by Naor and Pinkas [1], why did the authors decide to operate in a subgroup? When they say "the messages are in the subgroup" does that mean $x, y, z_0, z_1$, $...
7
votes
1answer
690 views

When to use safe prime or Schnorr group

Protocols that use $\mathbb{Z}_{p}^*$ arithmetic often choose $p$ to be a safe prime ($p = 2q + 1$, for prime $q$) or to have the Schnorr group form ($p = rq + 1$, for prime $q$). I understand that ...
1
vote
0answers
237 views

Can Bitcoin mining solve Graph Isomorphism-related problems?

Given a cryptographic hash $H:\{0,1\}^*\mapsto\{0,1\}^N$ and data $D\in\{0,1\}^*$, the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $x$ such that $H(x\Vert D)$ begins with $d$ leading zeros, ...
1
vote
1answer
137 views

Sum probability

if $a,b,c$ are selected at random from a large cyclic group, then what could be the probability that $g^{a+b}$=$g^c$? it simply corresponds to the probability that multiplication of two random ...
11
votes
0answers
259 views

Finding $x$ such that $g^x\bmod p<p/k$?

In a Schnorr group as used for DSA, of prime modulus $p$, prime order $q$, generator $g$ (with $p/g$ small), how can we efficiently exhibit an $x$ with $0<x<q$ such that $g^x\bmod p<p/k$, for ...
1
vote
0answers
147 views

Is there a flaw in this ring signature scheme? [closed]

Having read some papers about RSA accumulators applied to ring signatures schemes, I ended up thinking why would we need to accumulate all the members public keys for our specific use case. So I came ...
0
votes
1answer
70 views

What does the “description of group $G$” includes?

I was reading here:second discrete log meaning in the solution and also here:key generation, first point where the say given $G$ (or its description). My question is what does this description ...
3
votes
1answer
81 views

Does pairings based cryptography inherently require a CRS/trusted setup?

In all algorithms I've seen that rely on pairings-based cryptography (some examples: snarks without PCPs, more snarks, sublinear ring signatures), a common reference string is required. Is this always ...
1
vote
2answers
234 views

Elliptic Curve Point at Inifnity in Projective Coordinates

I'm implementing an elliptic curve system primarily for ECDSA verification. I've evaluated different point representations and decided that using Jacobian projective coordinates suits best for my ...
0
votes
1answer
285 views

Number of generators of an elliptic curve

Consider the elliptic curve E:$y^2 = x^3 + 3x + 11\,\, mod\,\, 19$. Two questions: Let the cardinality of the set of points on the elliptic curve( including $O$ ) be $|E| = 25$. How many points are ...
3
votes
1answer
329 views

On getting beyond LSB in discrete log

In discrete log we employ sophie germain primes $p=2q+1$ where $q$ is a prime. Then we know least significant bit $x_0$ in $$g^{2x+x_0}=h\bmod p$$ where $2x+x_0$ is discrete logarithm of known $h\...
0
votes
2answers
52 views

A Question about Notations and Groups

Please consider the following question: Determine the order of all the elements of the following multiplicative groups. You can write a C or Java program to do this. a. $Z_{21}^*$ b. $Z_{23}^*$ Now ...
1
vote
2answers
477 views

RSA keys are multiplicative inverse in mod phi(n), but also in mod n?

I understand that the RSA keys $pk$ and $sk$ are choosen such that one is the multiplicative inverse of the other, in $\mod \phi(n)$ But for the encryption and decryption to work, in other words, ...
-1
votes
1answer
217 views

Abelian groups in Elliptic curves [closed]

Do every elliptic curve defined over a prime field forms an abelian group?
0
votes
2answers
101 views

Can someone explain the definition of four square roots as it pertains to groups in Z*p?

So I'm given the following as a problem: When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $Z^∗_N$ have either zero or four square roots. A quarter of the points have four square ...
9
votes
1answer
330 views

How hard is the DLP in that simple group?

Let $p=4q-1$ be a prime with $q$ an odd prime. Let $G=\{0,1,\dots,p-1,\infty\}$. The following law $*$ makes $(G,*)$ a commutative group of order $4q$ with neutral element $\infty$: $$a*b=\begin{cases}...
6
votes
1answer
247 views

Elliptic Curve Cryptography - When to use p and when to use n

Im currently playing around with ECC, in particular the ECDSA scheme on a brainpool P256R1 curve. While implementing the signature verification function, I've stumbled upon a few problems. So far I'...
-1
votes
1answer
105 views

Order of the curve and generator

Does the order of the curve and the order of generator should be coprime for an elliptic curve defined over a prime field?
6
votes
1answer
925 views

Groups for which DDH is easy but CDH is hard

For prime p, is $\mathbb{Z}^{*}_{p}$ a group for which the Decision Diffie-Hellman problem is easy (because one can compute the Legendre symbol of ($g^{ab}$) while CDH is thought to be hard? Of course,...
7
votes
1answer
2k views

How to find the order of a generator on an elliptic curve?

I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm: Choose random point $P$ on the curve. Find the order of a ...
2
votes
1answer
441 views

What's dh-composite test on badssl.com?

The site badssl.com provides examples of bad (red icon) and good (green icon) uses of TLS for the purpose of testing TLS implementations. I'm a bit confused by the test called dh-composite. This ...
2
votes
2answers
550 views

How can I find the generator of a composite group and $Z_p*$?

I was doing some research on elliptic curves. I know how to find the generator of $Z_p$ (this is a prime group). But I came across the term $Z_p*$ (group containing elements that relatively prime to $...
4
votes
1answer
154 views

$L^3$ Grover search of NTRU variants

I was reading a text on cryptology by Wayne Patterson and came across the $L^3$ algorithm which reduces integer lattices with respect to their base. I've also read on the NIST CFP A8 that attacks ...
2
votes
1answer
4k views

How to find the generator of an elliptic curve? [duplicate]

If the elliptic curve has prime order of points, then all of its points are generator. Is this true? If so, how can I find the optimized generator(which generates more number of points) among them?
2
votes
1answer
1k views

why are non singular curves used in elliptic curve cryptography?

It is not possible to draw tangent at all the points of a singular curve. What is the specialty of this and how it is related to cryptography and elliptic discriminant?
9
votes
2answers
1k views

Why are elliptic curves constructed using prime fields and not composite fields?

I come across this: Numbers mod composite number does not form a field rather it forms a ring and every number has a multiplicative inverse under integer mod prime Maybe these are the reasons ...
-1
votes
1answer
258 views

Elliptic curve points addition is not associative [closed]

I've found an article that says how to add points in projective coordinates.But in my implementation these points don't form a group. Fields: ...
0
votes
2answers
164 views

Pairing - Is it possible to map two $r$-torsion points to a $r^2$-torsion point?

Let $E(\mathbb F_{q^k})$ be an elliptic curve on finite field $\mathbb F_{q^k}$, where $\mathbb F_{q^k}$ is an extension of $\mathbb F_q$ with $k>1$. Let $e: G_1 \times G_2 \rightarrow G_t$ be a ...
2
votes
2answers
268 views

How to determine proportion of quadratic residues in elliptic curve group?

I'm using a 'try and increment' method to hash to an Elliptic Curve point, explained below. With security parameter $k$, EC equation $y^2 = x^3 + ax + b \mbox{ mod } q$, we have: $ u = sha256(\mbox{...
2
votes
1answer
74 views

LSB of the Exponent in the DL Problem Can Be Efficiently Computed for Groups of Even Order

I am studying a script on the mathematical foundations of cryptography as part of which I am currently trying to wrap my head around some basic cryptographic reductions. I am stuck on one problem that ...
1
vote
1answer
266 views

Generating Diffie-Hellman parameters

I'm trying to implement a diffie-hellman key exchange in c++, and I'm struggling with my missing understanding of math / group theory. Let's say I found a large prime number p - how can I find a ...
5
votes
2answers
2k views

Why must an elliptic curve group for ECC have prime order?

What is the deeper reason, a group must have prime order for usage in cryptography?
2
votes
1answer
433 views

Why is only one generator stated in literature for elliptic curve group P-256?

I refer to elliptic curve groups over prime fields and their application in cryptography. If the order of a group is prime, it follows (am I wrong?) that: the group is cyclic and every element ...
1
vote
1answer
218 views

Discrete logarithm problem in subgroup of index 2. ElGamal

I need some insight for the following problem in ElGamal encryption procedure. It is stated that ElGamal problem in a group $\mathbb{Z}_p^*$ becomes easier in subgroups. Assume I have a subgroup of ...
3
votes
1answer
544 views

Diffie-Hellman key exchange using addition instead of multiplication?

I know that the additive finite group $(Zp,+)$ of prime order $p$ when I perform the Diffie-Hellman key exchange (DHKE) protocol is insecure. I didn't however find many sources online explain why it ...
5
votes
1answer
646 views

How is the order of a point calculated for elliptic curves over GF(p)

My question is about elliptic curves over $GF(p)$: How is the order of a generating element $G$ (which is to my knowledge also the order of the cyclic subgroup $G^n$) calculated? Taking P-256 as an ...
4
votes
2answers
3k views

Find the generators of multiplicative group of units efficiently?

Say you're give some prime numbers $p_{1},p_{2},p_{3}, p = 2p_{1}p_{2}p_{3} + 1$ (which is assumed to be also prime) and a list of numbers $L$ and you're asked to find the generators of the ...
1
vote
1answer
80 views

Permutations coming from RSA

The RSA algorithm can be used to generate a permutation. Given two prime numbers $p$ and $q$, the key length is $n=pq$. If $a$ is the private key, then $b$ is the public key, where $ab \equiv 1 \...
3
votes
1answer
428 views

How to construct a hash function into a cyclic group such that its discrete log is intractable?

From the Linkable Ring Signatures paper: Let $G = \langle g\rangle$ be a cyclic group of prime order $q$ such that the underlying discrete logarithm problem (DLP) is hard. Let $H_1 : {0, 1}^∗ \to \...
3
votes
1answer
807 views

What is a cyclic group of prime order q such that the DLP is hard?

On the original paper on Linked Ring Signatures, in order to construct its scheme, the author relies on this: Let $G = \langle g\rangle$ be a cyclic group of prime order $q$ such that the ...
3
votes
3answers
420 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 ...
2
votes
1answer
238 views

Additive proof of discrete log?

Let's say someone has $K$, and I want to prove to them that I know $k$ such $K = k*g$ (where $g$ is some sort of group element). I can use a Schnorr signature. Is there some protocol for mergable ...
0
votes
1answer
57 views

How to find g in Factoring-Based Trapdoor Hash Function

Please explain how to find a value of $g$ if $p,q$ are safe primes having $p'=(p-1)/2$ and $q'=(q-1)/2$ are also primes $n=p*q$ $\lambda(𝑛) = \operatorname{lcm}(𝑝 − 1, 𝑞 − 1) = 2𝑝'𝑞'$. How to ...
0
votes
1answer
649 views

What is Group in Diffie-Hellman?

I understand how Diffie-Hellman key-exchange works. Mainly, two parties agrees in a prime $p$ and a generator $g$. Then one party selects its private exponenet $x$, computes its public value $g^x \...
4
votes
1answer
1k views

Elliptic curve and embedding degree

I am new to ECC. I am confused about what the embedding degree in an elliptic curve group represents and what is the impact of its values on the curve and security (small values or large values?) ...
1
vote
0answers
45 views

Hash function notations and their corresponding existing cryptographic hash algorithm

I am implementing Role-based access control by referencing the paper Enforcing Role-Based Access Control for Secure Data Storage in the Cloud. In page 6, they have mentioned to choose hash functions $...
0
votes
1answer
123 views

Derive $x$ when given $g,g^x$ and $g^{(1/x)}$?

If an adversary has access to the generator g of a group G and is given access to $g^{x}$ and $g^{(1/x)}$, will it make it any easier to derive the value of $x$ compared to when he had access to only $...