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).
353
questions
1
vote
0
answers
32
views
Are there real-world applications of point halving on an elliptic curve over a finite field of prime characteristic?
Let $E\!: y^2 = x^3 + ax + b$ be an elliptic curve over a finite field $\mathbb{F}_{\!q}$ of prime characteristic $p$ (mostly, $q = p$ in practice). It is well known that in the $\mathbb{F}_{\!q}$-...
- 425
0
votes
0
answers
19
views
Cryptography in the symmetric group
I'm looking for a way for two players $P_1$ and $P_2$, only interacting with each other, to come up with elements $g_1,g_1',g_2,g_2'\in \Sigma_n$ such that
$g_1g_2=g_2'g_1'$;
For each $i=1,2$, $P_i$ ...
- 173
7
votes
2
answers
3k
views
Why Abstract Algebra in Cryptography?
I come from an engineering background, but not from computer science or anything to do with pure math. I studied applied math in college--never abstract algebra, number theory, or discrete math, ...
- 101
1
vote
2
answers
205
views
Why using q = (p - 1)/2 for discrete log Diffie-Hellman scalar operations and not p?
As defined in RFC 3526 the prime $p$ and generator $g$ are known. The prime $p$ defined there is a safe prime, which can also be expressed as $p=2q+1$ with $q$ prime. The amount of elements in this ...
- 144k
2
votes
1
answer
198
views
Parameters needed for Chaum-Pedersen Protocol
I've came across a Stackexchange question about the Chaum-Pedersen Protocol which is based on the generalised schnorr protocol. As I understand it, it uses discrete logs and cyclic groups of prime ...
CommunityBot
- 1
2
votes
1
answer
125
views
Is it possible to use abstract groups to generalize DSA, ECDSA and EdDSA signature creation and verification?
It is known, that
DSA algorithm is defined as:
Bob
Creates private $x$ and public $Y=G^x\bmod p$ keys, where $G$ - generator, $p$ - group prime order
Selects random value $k$ from $1
\le k\le q-1$
$...
- 144k
0
votes
1
answer
132
views
Using Sagemath, how to exactly find out what the order of a point of an elliptic curve in the twisted Edwards form is?
Simple question and I’m fully aware of the other question, but I need the answer for curves in the twisted Edwards form and I suppose converting the curve and the point to the Weierstrass form would ...
- 144k
3
votes
2
answers
536
views
Is ElGamal homomorphic encryption using additive groups works only for Discrete Log ElGamal? What about EC ElGamal?
It is known that in Discrete Log ElGamal encryption, the ciphertext $E$ is encrypted as:
$a\ =\ g^k$, where $k$ - random scalar from $[0,\ p)$, $g$ - group generator
$b\ =\ (Y^k*m)\mod\ p$, where $Y$ -...
- 144k
0
votes
3
answers
357
views
Can I move elements from cyclic subgroup to its cyclic parent group?
The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b.
I know that elements of a non-prime order cyclic group G can be moved to its subgroup H by a process called &...
- 150k
2
votes
1
answer
169
views
Is it possible to abstract an ElGamal encryption for EC and Discrete Log by using a Group Law?
ElGamal encryption for Discrete Log is defined as:
Bob side does:
$Y\ =\ (g^x)\ mod\ P$, where $g$ - generator, $x$ - random value among the group elements and $P$ - prime number, typically ultra ...
- 144k
1
vote
0
answers
67
views
Is the following Inverse Computational co-Diffie-Hellman problem hard?
Let $\langle g \rangle \stackrel{\Delta}{=} \mathbb{G}$ and $\langle h \rangle \stackrel{\Delta}{=} \mathbb{H}$ be groups of prime order $p$. Given $( p, g, g^\delta, g^{\delta^{-1}}, h, h^\delta )$, ...
3
votes
2
answers
217
views
Size of $E$ over $\mathbb{F}_p$ contains $p+1$ points
I am struggling to prove this claim:
I proved that the map $x\mapsto x^3+1$ is a bijection from $\mathbb{F}_p$ to itself if we have that $p\equiv 2\bmod{3}$. We have to use this fact to prove that ...
- 49.3k
4
votes
3
answers
2k
views
Why does Diffie-Hellman need be a cyclic group?
Why is Diffie-Hellman defined on a cyclic group? Doesn't it work for any commutative operation which the inverse is hard to find?
Say Alice and Bob agree in a public prime $c$ and both choose a ...
- 21
1
vote
1
answer
169
views
What’s the fastest known Koblitz curve addition law for FPGA that maximizes the per-LUT throughput?
The addition or multiplication laws used by large mainstream libraries achieve faster speed by using many many more operations in order to avoid larger numbers. And my problem is here: faster speeds ...
- 144k
2
votes
1
answer
93
views
Small subgroup attack when using a Schnorr group for DHKE
One uses a Schnorr group both for Schnorr signature (or DSA), and for Diffie-Hellman Key Exchange. They target 128-bit security, and choose prime $q$ that's 256-bit, prime $p=q\,r+1$ that's 3072-bit, ...
- 144k
11
votes
1
answer
3k
views
Is every point on an elliptic curve of a prime order group a generator?
If the order of elliptic group is prime then every point is a generator of that group.
I tested the above statement on some elliptic curves and found it true.
Does that really work on all curves?
Is ...
- 1
22
votes
3
answers
10k
views
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective.
RSA labs makes a similar statement:
The discrete logarithm problem bears the same ...
- 60
3
votes
1
answer
731
views
Is AES a group?
The question I'm wondering is whether the AES cipher is a closed cipher (which is equivalent to AES being a group). And this question interests me due to the lack of understanding of whether it is ...
- 23.1k
1
vote
1
answer
106
views
Secret sharing in different groups; Rounding down of elements
I have the following problem:
A secret $x \in \mathbb{Z}_q$ is secret shared (additive secret sharing) between $n$ parties, now is it possible to compute the secret shares of $y = \lfloor x \rfloor ...
CommunityBot
- 1
-2
votes
2
answers
513
views
How to map elements from subgroup to larger subgroup of its parent group?
The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b.
pls read carefully-
I am looking for a function/formula/algorithm that can be applied on any curve, say for e....
- 144k
2
votes
2
answers
103
views
One group element hybrid encryption for El Gamal
I am really curious about this one problem 10.12 from Katz/Lindell's book. It goes as follows:
I am quite sure we can assume that $\textsf{Enc}_k(m) \in \mathbb{G}$, as the authors devoted the whole ...
1
vote
0
answers
53
views
Grow-only set homomorphic hash function from semigroup?
I have been exploring Bellare and Micciancio's "randomize-then-combine" paradigm for deriving set homomorphic hashing functions. I am particularly interested in grow-only sets, such that ...
- 131
2
votes
1
answer
146
views
Proof of Lagrange's Theorem?
In the book Cryptography Engineering, Design Principles and Practical Applications, by Niels Ferguson, Bruce Schneier and Tadayoshi Kohno, in a section discussing multiplicative groups, the authors ...
- 150k
1
vote
1
answer
125
views
Mapping two different elliptic curve on same finite field
There exist two such question but I have noticed my question is fundamentally different as it asks for mapping between two different curves, rather two different prime field like this.
Given a finite ...
- 49.3k
0
votes
0
answers
36
views
Safe use of bilinear pairing, using one way function in the exponent
Given a generator $g$ of a cyclic group, I am trying to look for a case where I use pairing over an element that has an exponent which is a one-way function, e.g., $g^{x^2\mod n}$ (here $x$ in the ...
- 99
2
votes
1
answer
282
views
Is there an algebra group (or ring) in which computing the inverse element is hard without some trapdoor information?
Specifically, I want an algebra group $G$ (or ring $R$) features:
Given elements $g,h\in G$ (or $R$ ), computing $g\cdot h \in G$ (or $R$ ) is easy.
Given an element $g \in G$ (or $R$ ), finding the ...
- 144k
1
vote
0
answers
102
views
Understanding Gentry's initial FHE construction based on ideal lattices
I am trying to understand the encryption procedure in Craig Gentry's initial construction for FHE described in Fully Homomorphic Encryption Using Ideal Lattices. Unfortunately after repeated attempts ...
- 111
1
vote
1
answer
411
views
DHKE: Why using safe prime gives us "safe" subgroups?
I come from the question here: Safe primes subgroup in Diffie–Hellman key exchange
Where the accepted answer states that there are only 4 possible outcomes for the order of a subgroup when using a ...
- 2,569
1
vote
1
answer
83
views
Why exclude the last group element when picking Elgamal secret key
Christof Paar explains in his lectures that Elgamal encryption scheme picks the private key from $\{2, \ldots, p-2\}$, is there a reason for excluding the last and first elements?
- 144k
-1
votes
1
answer
242
views
Why don't secp256k1 use a prime order subgroup?
Using a prime order subgroup prevents mounting a Pohlig–Hellman algorithm attack. Meanwhile, secp256k1 doesn't use a ...
- 49.3k
3
votes
0
answers
113
views
Effective key length in Enigma encryption
Each Enigma machine setting induces a certain encryption in the sense of a function from the space of plain texts to the set of cipher texts.
The number of different Enigma machine settings can be ...
- 139
4
votes
1
answer
418
views
How does the Legendre symbol reveal if $g^a$ is odd or even for Finite Field Diffie-Hellman
According to wikipedia(markdown is striped below) for Decisional Diffie–Hellman assumption:
the DDH assumption does not hold in the multiplicative group $Z(p)$,
where $p$ is prime. This is because if ...
- 93.9k
0
votes
1
answer
193
views
Safe primes subgroup in Diffie–Hellman key exchange
I'm trying to understand how the safe primes numbers are used in Diffie–Hellman key exchange. According to wiki:
The order of G should have a large prime factor to prevent use of the
Pohlig–Hellman ...
- 150k
1
vote
1
answer
260
views
Fast Algorithms for generalized Discrete Logarithm?
I know the standard algorithms for D-log. Pollard-rho, Baby-step-big-step, Pollig-Hellman, index calculus, etc.
I'm looking for fast algorithms to find a relation for the generalized discrete ...
- 1,212
3
votes
2
answers
855
views
How to check if a number is a generator of a cyclic multiplicative group
Suppose I have a 2048 bit prime number p. Now for the group $Z_p$, could someone please tell me an efficient algorithm to check whether a randomly chosen number is a generator for the group or not
- 144k
0
votes
1
answer
36
views
What is a efficient algorithm to compute e(u, v) in bilinear map
My problem is about this paper Efficient k-out-of-n oblivious transfer scheme with the ideal communication cost https://www.sciencedirect.com/science/article/pii/S0304397517309143
I don't know what is ...
- 25.1k
1
vote
1
answer
78
views
Hidden Subgroup Problem: Embedding $G$ in a complex hilbert space $H$
In general or in specific examples, how is the group used in an instance of the hidden subgroup problem embedded into a complex Hilbert space in order to apply the quantum fourier transform needed to ...
- 13.7k
3
votes
1
answer
164
views
Division of two Elliptic curve points in KZG polynomial commitment scheme!
I have some issue to understand the verify round of the KZG polynomial commitment scheme. The following diagram is associated to the scheme. I appreciate any help.
To verify, the verifier should ...
- 939
2
votes
1
answer
103
views
Given two unrelated generators $G_1$ and $G_2$, and a third with $H = G_1 + G_2$. Is it hard to compute $xG_1$ from $xH$?
Given some group in which both discrete logarithms and the computational Diffie-Hellman problem are hard. Furthermore, two random, unrelated group generators $G_1, G_2$, and a third generator defined ...
- 361
3
votes
1
answer
114
views
Linearization attack on group with automorphism
Recently, I've had an exchange with Lorenz Panny about Xifrat. He says, that the quasigroup that I use can be linearized and then attacked, and he provided a script that linearized the quasigroup. His ...
CommunityBot
- 1
2
votes
1
answer
73
views
What is the space that exponents of ElGamal encryption scheme live?
It is a bit stupid question, but I am so confused. Please examine my explanation. What is the space that exponents the generator $g$ of a cyclic group $G$ of prime order $p$?
I think it is $\mathbb{Z}...
- 25.1k
15
votes
2
answers
8k
views
Cycle attack on RSA
I originally posted this question in the mathematics section, you can see it here.
Let $p$ and $q$ be large primes, $n=pq$ and $e : 0<e<\phi(n), \space gcd(e, \phi(n))=1$ the public encyption ...
CommunityBot
- 1
1
vote
1
answer
45
views
Can some cryptographic conclusions in the prime field be applied to the Galois field？
Such as integer factorization problem and discrete logarithm problem. Assuming a large polynomial is obtained by multiplying two generated polynomials, is it NP hard to decompose it into these two ...
- 23.1k
30
votes
2
answers
14k
views
How to determine the order of an elliptic curve group from its parameters?
Let $\quad E:\; y^2 = x^3 + ax + b \quad$ be an elliptic curve defined over a finite field $\mathbb F_q$ where $q = p^n$, $a,b \in \mathbb F_q$ and $p \neq 2, 3$. By Hasse's theorem we know that the ...
9
votes
3
answers
2k
views
How to decide if a point on a elliptic curve belongs to a group generated by a generator $g$?
In the elliptic curve encryption scheme, there is a cyclic group generated by a base point $G$ on the elliptic curve.
Given a random point on the elliptic curve, is there a way to decide if the random ...
- 2,625
4
votes
3
answers
2k
views
Elliptic Curve - Divide by 2
Can anyone tell me the specific equations and steps for dividing a point on an elliptic curve by 2?
For instance, I have the point $(P_x, P_y)$, and I would like to find the point $(R_x, R_y)$ which ...
- 144k
2
votes
1
answer
75
views
Conceal time-based GUIDs with an affine-cipher?
I'd like to create a custom type of sortable GUID by concatenating an 8-byte nanosecond timestamp, 6 random bytes, a 1-byte node number, and a 1-byte counter. But, such a precise timestamp can be used ...
- 266
2
votes
1
answer
118
views
Importance of non-degeneracy property of bilinear map for cryptography
I'm currently looking into pairing-based cryptography and I stumbled upon the definition of the properties bilinearity, computability and non-degeneracy.
Now I have a problem with understanding the ...
- 25.1k
-1
votes
2
answers
156
views
How are the cipher, the key and the initial message (that is not encrypted) are releted?
Suppose that $m$ is a message that someone player $i$ wants to send to a network of other players $j\neq -i$. The player to prevent his message from cheating by others uses an encyrpstion scheme. Say $...
- 1,122
1
vote
1
answer
437
views
Proving the generator criterion for group $Zp$
I am trying to understand how to find a generator of Zp. How to find generator $g$ in a cyclic group?.
I have heard that we can pick random a Zp and for each primitive d| p-1 check wether:
a^[(p-1)/...
- 939