Skip to main content

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
1 vote
1 answer
147 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 ...
user2284570's user avatar
2 votes
1 answer
86 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, ...
fgrieu's user avatar
  • 142k
3 votes
1 answer
724 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 ...
Ss1996's user avatar
  • 53
2 votes
2 answers
95 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 ...
Michael Hammer's user avatar
1 vote
0 answers
39 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 ...
Carson Farmer's user avatar
2 votes
1 answer
141 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 ...
divaconhamdip's user avatar
1 vote
1 answer
109 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 ...
madhurkant's user avatar
0 votes
0 answers
32 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 ...
Doron's user avatar
  • 99
2 votes
1 answer
264 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 ...
X.H. Yue's user avatar
  • 392
1 vote
0 answers
98 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 ...
Parham's user avatar
  • 111
1 vote
1 answer
388 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 ...
Ymi's user avatar
  • 175
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?
synack's user avatar
  • 123
-1 votes
1 answer
205 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 ...
pacman's user avatar
  • 459
3 votes
0 answers
112 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 ...
maya's user avatar
  • 139
4 votes
1 answer
398 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 ...
pacman's user avatar
  • 459
0 votes
1 answer
167 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 ...
pacman's user avatar
  • 459
-2 votes
2 answers
508 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....
Homer's user avatar
  • 7
1 vote
2 answers
313 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 &...
Homer's user avatar
  • 7
1 vote
1 answer
225 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 ...
mtheorylord's user avatar
3 votes
2 answers
782 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
Ankeet Saha's user avatar
0 votes
1 answer
33 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 ...
Rongkuan He's user avatar
2 votes
1 answer
181 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 ...
Jason L. B.'s user avatar
1 vote
1 answer
76 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 ...
kipawaa's user avatar
  • 13
3 votes
1 answer
151 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 ...
tesoke's user avatar
  • 181
2 votes
1 answer
98 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 ...
RobinLinus's user avatar
2 votes
1 answer
71 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}...
Lee Seungwoo's user avatar
1 vote
1 answer
44 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 ...
ZhuJerry's user avatar
2 votes
1 answer
73 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 ...
aiootp's user avatar
  • 814
2 votes
1 answer
108 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 ...
unsigned_int2's user avatar
1 vote
1 answer
359 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)/...
tonythestark's user avatar
3 votes
1 answer
200 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 ...
user93353's user avatar
  • 2,245
4 votes
1 answer
136 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 ...
fgrieu's user avatar
  • 142k
2 votes
1 answer
111 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 ...
unsigned_int2's user avatar
1 vote
0 answers
63 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 ...
Cristie's user avatar
  • 93
1 vote
1 answer
291 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 ...
ConfusedPhdStudent's user avatar
0 votes
1 answer
110 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 ...
Mohamed Mohamed Mourad Abdel W's user avatar
2 votes
0 answers
88 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 ...
unsigned_int2's user avatar
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 ...
unsigned_int2's user avatar
2 votes
2 answers
214 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$ ...
István András Seres's user avatar
0 votes
1 answer
41 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 ...
Abol_Fa's user avatar
  • 73
2 votes
0 answers
119 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 ...
Alia's user avatar
  • 51
0 votes
1 answer
511 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 ...
user93353's user avatar
  • 2,245
1 vote
2 answers
237 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\...
John Rawls's user avatar
1 vote
1 answer
183 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 ...
user93353's user avatar
  • 2,245
1 vote
3 answers
221 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 = ...
Grifball's user avatar
  • 181
5 votes
3 answers
748 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 ...
user93353's user avatar
  • 2,245
5 votes
1 answer
366 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 ...
user93353's user avatar
  • 2,245
0 votes
1 answer
288 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 ...
user93353's user avatar
  • 2,245
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 ...
Alex R's user avatar
  • 3
1 vote
1 answer
75 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 ...
Doron's user avatar
  • 99

1
2 3 4 5
7