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
2 answers
472 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....
1 vote
2 answers
295 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 &...
2 votes
2 answers
78 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 ...
0 votes
1 answer
76 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 ...
1 vote
0 answers
29 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 ...
2 votes
1 answer
136 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 ...
1 vote
1 answer
84 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 ...
0 votes
0 answers
30 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 ...
2 votes
1 answer
247 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 ...
1 vote
0 answers
85 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 ...
2 votes
1 answer
147 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 ...
1 vote
1 answer
355 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 ...
1 vote
1 answer
82 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?
-1 votes
1 answer
174 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 ...
3 votes
0 answers
106 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 ...
4 votes
1 answer
336 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 ...
0 votes
1 answer
139 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 ...
1 vote
1 answer
128 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 ...
3 votes
2 answers
508 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
0 votes
1 answer
32 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 ...
1 vote
1 answer
73 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 ...
3 votes
1 answer
135 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 ...
2 votes
1 answer
92 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 ...
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 ...
2 votes
1 answer
69 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}...
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 ...
0 votes
0 answers
29 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
43 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 ...
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 ...
7 votes
3 answers
1k 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 ...
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 ...
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 ...
2 votes
1 answer
80 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 ...
-1 votes
2 answers
154 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 vote
1 answer
207 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)/...
3 votes
1 answer
191 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 votes
1 answer
1k views

"Order" in cryptographic terms for generators

Frequently, I have seen people use the term "order" in cryptography (the group-theoretic one). I have a mathematical background and "order" (say, for prime modulus $p$) is defined ...
1 vote
1 answer
190 views

Could someone explain to me, in simple terms, why we need a large order of group G for Diffie-Hellman and what does that mean?

For ElGamal encryption, safe prime $p$ is used such that $p = 2q+1$. However, can someone explain to me, in simple terms, why we would need, in this context, a large order of $G$ and how it will ...
4 votes
1 answer
131 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 ...
2 votes
1 answer
104 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 ...
1 vote
0 answers
55 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 ...
1 vote
1 answer
225 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
85 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
86 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 ...
4 votes
1 answer
3k 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 ...
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 ...
2 votes
2 answers
189 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 vote
2 answers
193 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\...
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 ...
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 ...

1
2 3 4 5
7