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).
338
questions
2
votes
1
answer
231
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 ...
- 368
1
vote
0
answers
71
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
336
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 ...
- 175
1
vote
1
answer
81
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?
- 123
-1
votes
1
answer
157
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 ...
- 409
3
votes
0
answers
98
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
297
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 ...
- 409
0
votes
1
answer
126
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 ...
- 409
1
vote
2
answers
273
views
PAGE 2: Can I move elements from cyclic subgroup to its cyclic parent group?
We will continue our previous topic here⬇️ for clarity...
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/...
- 21
1
vote
2
answers
230
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 &...
- 21
1
vote
1
answer
89
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 ...
- 135
3
votes
2
answers
391
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
- 31
0
votes
1
answer
28
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 ...
2
votes
1
answer
110
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 ...
- 21
1
vote
1
answer
69
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
3
votes
1
answer
122
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 ...
- 181
2
votes
1
answer
90
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 ...
- 339
2
votes
1
answer
67
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}...
- 363
0
votes
0
answers
25
views
Where is the cryptography library that support group signature?
Finding a cryptography library to implement various application features is not difficult nowadays, thanks to options like NaCl, Google Tink, PyCA, and OpenSSL.
However, I've been struggling to find a ...
1
vote
1
answer
42
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
2
votes
1
answer
70
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 ...
- 785
2
votes
1
answer
67
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 ...
- 75
1
vote
1
answer
178
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)/...
- 173
3
votes
1
answer
184
views
How will the ability to do comparison or modulo efficiently in Finite Cyclic Groups break Elliptic Curve Cryptography?
This is from Vitalik Buterin's post.
Here he says
Note that modulo (%) and comparison operators (<, >, ≤, ≥) are NOT
supported, as there is no efficient way to do modulo or comparison
directly ...
- 2,179
4
votes
1
answer
125
views
Difficulty of Shor's algorithm in a Schnorr group as a function of the modulus
Consider a Schnorr group with order a prime $q$ sized for security against current computers (like $q$ of 256 bit); modulus a prime $p=q\,r+1$ large enough (e.g. 3072 to 32768-bit) that the algorithms ...
- 138k
2
votes
1
answer
101
views
Modulus for reduction in BLS Signature Scheme
I'm currently working with BLS Signature Schemes in the field of publicly verifiable Compact Proofs of Retrievability by Shacham and Waters.
So for creating the Sigmas the following function is ...
- 75
1
vote
0
answers
48
views
ddh and statistical distance
Let $\mathbb{G}$ be a cyclic group of prime order q and generated by g. Let $D$ be the uniform distribution over $\mathbb{G}^3$. Let $D_{dh}$ be the uniform distribution over the set of all DH-triples ...
- 93
1
vote
1
answer
186
views
Hidden order groups any pointers to reading material?
Hey I got a pointer a while ago to hidden order groups and I found papers like https://eprint.iacr.org/2006/178.pdf dating way back using this, but I couldn't find any elementary read on what can and ...
0
votes
1
answer
71
views
Galois field problem in Cryptography [closed]
This problem is related to Fields in Cryptography, My Question is why there is no multiplicative inverse for 2, isn't it 0.5?? or matters are diffrent if it was related to galois field ? I don't quite ...
2
votes
0
answers
84
views
Create random element from group G in BLS Scheme
I hope this question is not too basic. I'm currently trying to implement compact proofs of retrievability that are publicly verifiable by BLS scheme as described in this paper Compact Proofs of ...
- 75
1
vote
0
answers
50
views
Compact Proofs of Retrievability publicly verifiable with RSA
I'm currently trying to implement compact proofs of retrievability that are publicly verifiable by RSA as described in this paper Compact Proofs of Retrievability in GO. I'm currently struggling on ...
- 75
2
votes
2
answers
176
views
Proving in zero-knowledge the "sign" of a discrete logarithm in groups of unknown order
Suppose we have the description of a group $\mathbb{G}$, a group of unknown order: the size of the group is unknown. For instance, an RSA group ($\mathbb{Z}^{*}_N,$ where $N=pq$ for unknown primes $p$ ...
- 1,164
0
votes
1
answer
40
views
Why would be the use of such hash function definition? What would be the input of these functions?
$ G \space is \space an \space elliptic \space curve \space group \space G \space with \space order \space q$
and three hash functions are defined as this:
$$
H_1: \{0,1\}^*\times G \rightarrow Z^*_q
...
- 73
2
votes
0
answers
118
views
If $e(aP, bP) = e(P, P)^{ab}$ then how can we solve $e(P^a, P^b)$?
I'm a bit confused regarding the bilinear pairing operation. Let's say I have a Public key of a receiver $P_r = P^x$ and I want to create a symmetric key using KEM with a pairing operation. If I chose ...
- 51
0
votes
1
answer
242
views
What are Key Size requirements (rather than modulus size) for different Asymmetric Algorithms for 112-bit security?
A lot of writeups, books & webpages say that to get 112 bit security (i.e $2^{112}$ steps), you need to use RSA or DH with 2048 key size or ECDH with 224 key size. In reality, I think what is ...
- 2,179
1
vote
2
answers
171
views
Proof that checking if $g^k\bmod p\ne1$ finds a generator of a cyclic group
In this post the top answer says that for $\mathbb Z_p^*$, $k$, the order of an element $g$, divides p-1. Then it was concluded that this entails we can check if $g$ is a generator by checking if $g^k\...
- 113
1
vote
1
answer
145
views
What is the problem with having a hash to group function where you can find a discrete log relation between 2 different hashes?
I was reading some notes on a naive hash to a group function.
Consider a cryptographic Hash function $$H: \{0,1\}^{*}\to \{0,1\}^{k}$$
Consider a Discrete Log Hard Group $G$ with a generator $g$. We ...
- 2,179
1
vote
3
answers
156
views
Are the structures (groups/rings) that RSA operations are performed on actually R-modules?
Paolo, in Algebra: chapter 0, defines a left-$R$-module as a ring, $R$, an abelian group, $M$, and a map $(R \times M \rightarrow M)$ such that:
$r(m+n) = rm+rn$
$(r+s)m = rm+sm$
$(rs)m = r(sm)$
$1m = ...
- 151
5
votes
3
answers
672
views
When working in a subgroup of EC in EdDSA (especially Ed255190), how is it OK to use operations different from that of the main group?
Ed25519 uses a composite order Elliptic Curve but works in the prime order subgroup of the main group. As per group theory, the subgroups use the group operation.
However, as per this, Ed25519 ...
- 2,179
4
votes
1
answer
276
views
Why such a complicated way of cofactor clearing?
I thought I understood cofactor clearing before I read this write-up which generally seems quite popular (lot of other sites link to it) - Cofactor Explained: Clearing Elliptic Curves' dirty little ...
- 2,179
0
votes
1
answer
184
views
Trying out the small subgroup attack on a group of non-prime order using a simple additive group instead of an Elliptic Curve Group?
This is the attack I am talking about - Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation?
An elliptic curve group of order $8p$ where $p$ is a prime.
Let $G$ be the ...
- 2,179
0
votes
1
answer
51
views
Unexpected Behavior Working in Prime Order Subgroup with Java BigInteger Class
I'm implementing a searchable symmetric encryption scheme, developed by others, for my own personal enrichment. The original research is located at the link: https://eprint.iacr.org/2013/169. I'm ...
- 3
1
vote
1
answer
74
views
Does a list of discrete log equations reveal information?
Given public generator $g$ of some cyclic group, a secrets $x\in Z_q$, and public pairs $(a_1,b_1),...,(a_n,b_n)$ (where $a_1,...,a_n$ are selected at random from a big set), and prime p, that ...
- 99
1
vote
1
answer
108
views
Distribution of elliptic curves with rank 2?
An elliptic curve defined over a finite field is either cyclic, or a direct sum of two cyclic groups. In cryptography, we use exclusively the former. I was wondering if there is any result on how ...
- 119
0
votes
1
answer
60
views
If we can solve discrete log with on $\frac{1}{poly(n)}$ instances, then we can solve, with high probability, for all instances
I am trying to prove the following:
Given an ensemble $\{p_n, g_n\}$ ($p_n$ is an $n$-bit prime and $g_n \in \mathbb{Z}^*_{p_n}$ is a generator), if $A$ is a deterministic polynomial time algorithm ...
- 383
5
votes
1
answer
1k
views
Can there be identical elliptic curve groups of points from different irreducible polynomials in binary extension fields?
Let $E$ be an elliptic curve over a binary extension field $GF(2^m)$, with constructing polynomial $f(z)$ be an irreducible, primitive polynomial over $GF(2)$, and let $G(x_g,y_g)$ be a generator ...
- 115
3
votes
1
answer
112
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 ...
- 9,001
6
votes
1
answer
2k
views
Why is the discrete logarithm problem hard?
Why is the discrete logarithm problem assumed to be hard?
Someone else asked the same question but the answers only explain that exponentiation is in $O(\log(n))$ while the fastest known algorithms to ...
- 217
1
vote
1
answer
54
views
Division by $2$ or principal root with DH oracle
Assume $g$ is generator of multiplicative group modulo prime $p=2q+1$ where $q$ is prime.
Assume we know $g^{2t}\bmod p$ and $g^{2}\bmod p$ and assume we can have access to a Diffie-Hellman oracle.
...
- 908
0
votes
2
answers
120
views
How to know if a power is a permutation of an inverse group?
Consider the group $$ℤ^*_{55}$$
Is exponentiating to the 3rd power a permutation of: $$ℤ^*_{55}$$ And exponentiation to the 5th power?
I'm trying to solve this problem related to groups, but I don't ...
