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
1answer
26 views

Verifiable Delay Function: Trusted Setup

Efficient Verifiable Delay Function paper suggested that there is two way to construct the group. One of them requires trusted setup in the sense whoever constructs the RSA unknown group order needs ...
1
vote
0answers
37 views

Verifiable Delay Function - Fake Proofs

For unknown group order such as RSA groups $ G %$, it takes $T$ sequential steps to compute the below function (time-lock puzzle). $$ y = g^{2^T} mod N$$ This paper states that if $ /Phi(N) $ (Group ...
2
votes
2answers
215 views

VDF / RSA groups

I believe I am overthinking it; however, I need to clear out my doubts. What is exactly RSA groups and how their order is unknown? I know in RSA N is computed by multiplying two prime numbers (p and ...
2
votes
1answer
60 views

Difference between Generic Group Models

I'm trying to understand the difference between the (classical) Generic Group Model as it is described by Shoup [Shoup] and the somewhat restricted Generic Group Model as it is described by Schnorr ...
1
vote
0answers
23 views

Does having CDH oracle breaks El-Gamal signature scheme?

Having a oracle that solves Computational Diffie-Hellman problem which for given values $(g, g^a, g^b)$ outputs $g^{ab}$, is it possible to forge a signature in El-Gamal (wiki) signature scheme?
1
vote
1answer
75 views

Diffie Helman obtaining $g^y \bmod p$ from $g^{xy} \bmod p$ and $g^x \bmod p$

This may seem like a strange question. Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$? I assume I must use modular inverse but I don't know where.
1
vote
2answers
82 views

What are the typical instance parameters of non-commutative cryptographic schemes?

Recently, I grew a tremendous interest for public-key cryptography based on "groupoids", and collaborated with someone on this topic. What I notice afterwards, is that there had been a huge ...
2
votes
2answers
253 views

Prime order elliptic curve groups: Generators and the reason choice

As far as I understand, the elliptic curve group based on BLS12-381 is prime order and cyclic. Thus, any group element could be used to generate all the elements of ...
2
votes
2answers
94 views

ElGamal encryption security

Assume we have 2 prime numbers in form p = 2q + 1. Is it safe to use the cyclic group of order p-1 instead of one with order <...
3
votes
0answers
53 views

Succint, interactive proof that $y^2 = x$ in $\mathbb{Z}^*_p$

Let $p$ be a large prime, such that $(p = 3) \mod{4}$. Let $x$ be an element of $\mathbb{Z}^*_p$ such that, for some $y \in \mathbb{Z}^*_p$, we have $y^2 = x$. It is a well-known result that $y = x^{\...
2
votes
1answer
161 views

How is a generator found for a group, both in case of DH & ECDH?

First step in DH & ECDH is to choose a random prime $p$. Then you choose a generator $g$ for the group $\mathbb Z_p^*$. How do you find a generator? Likewise in ECDH, you would need to find a ...
0
votes
1answer
29 views

Practical use of semi direct product of group in Cryptography

Is there any example of semi-direct product used in any of cryptographic application? Does it help in choosing integers p, q in RSA?
1
vote
2answers
135 views

How to get the order of a group generator in DH?

For a DH parameter prime, if the generator $g$ is 2, how do I get the order $q$?
1
vote
0answers
26 views

Equality with Bilinear Maps

Let e be a bilinear pairing function and $g_1$ and $g_2$ be the generators of $G_1$ and $G_2$ Given $e(a,g_2^x), e(b,g_2^y), g_2^x,g_2^y$ is there a way to find out if $a = b$?
0
votes
0answers
20 views

Is it hard to determine an automorphism when the mapped value by several compositions of the automorphism is given

Generalization of the Discrete logarithm problem to non-abelian groups is discussed by many authors. One of the generalizations is shown in MOR cryptosystem as in the below link, by considering the ...
4
votes
1answer
283 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, ...
1
vote
1answer
131 views

Solving Diffie-Hellman vs DLP

I'm wondering what is the current knowledge regarding the difficulty of solving the Diffie-Hellman problem (DHP). Obvisously solving the DLP (discrete log) is at least as hard as solving the DH ...
5
votes
2answers
216 views

Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?

In discrete logarithm based schemes on finite field we have a prime number $q$ that divides $p-1$ and $q$ is to specify a subgroup with the order $q$. But why do we do that? Why do not we work on the ...
2
votes
1answer
118 views

Why is the point at infinity on Edwards Curve different to Weierstrass curves?

If I understand correctly, the identity point on all elliptic curves is the point at infinity. But on the Edwards curve, this can be written in Affine form? Does this have something to do with the ...
1
vote
0answers
52 views

Schoofs Algorithm

I studied Schoofs Algorithm described by Washington. On page 125 he says that we could write $y'/y$ as a function of $x$, which makes sense since earlier on the page he denotes $y'= r_{2,j}(x)y$. But ...
0
votes
1answer
79 views

Message mapping to elliptic curve in BLS signature

In the BLS signature the subgroup $G$ of elliptic curve constructed with point $P$ with prime order $q$ by $G=\langle P\rangle $. The $h(x)$ is a hash function. The point $S$ is map (image) of $h(m)$ ...
1
vote
1answer
114 views

Safe primes and subgroups

I've been reading about safe primes and their use in: Cryptography Engineering by Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno. Having a safe prime $q$ with $q=2p+1$ where $p$ is a Sophie ...
2
votes
3answers
129 views

Some questions on building permutations from boolean functions

I've seen multiple examples of boolean functions being used as a permutation. For example the Keccak Chi : 2.3.1 function: from https://keccak.team/figures.html Or as a formula: for $i=\{0..4\}$ $A_i=...
2
votes
0answers
66 views

How to efficiently find Schnorr groups that have a generator $g=2$?

A Schnorr group is a multiplicative group of integers modulo an odd prime $p$ of prime order $q$, normally such that $p$ is much greater than $q$. As far as I know, the normal way to find a Schnorr ...
0
votes
0answers
55 views

Elliptic curve group inverse addition in OpenSSL

I am using group P-256 on OpenSSL with C++. My understanding was that, if you have a point $xP$ and then calculate (xP)^(-1) with EC_POINT_invert(group, xP_inv, ctx), then when I calculate: xP + (xP)^(...
1
vote
1answer
62 views

What is the order of the Identity point on prime order elliptic curve groups?

I'm trying to understand how the identity point is represented in a group of prime order. What I think is correct: If the group has even order, then the identity point is in the group, because the ...
0
votes
0answers
34 views

Finding the relationship given by the generating elements of a non-abelian group (for a maximum case) where they correspond to finding cycles

Let $G=(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes_{\phi} \mathbb{Z}_q$, where $p$ and $q$ are odd distinct primes. Let $G$ be generated by the elements $s=(g_1,e_q)$ and $t=(e_p,g_3)$, $g_1,e_p \in \...
0
votes
0answers
24 views

How do I generate a number from a Z* order q set

I would like to generate a random number based on this set, firstly how do I generate the numbers that belong to the Z* order q set. I have the q value and the prime p value. Also if there's a ...
1
vote
1answer
55 views

RSA assumption and relationship given by generating elemts of a Cayley graph

I have read a very interesting description of computation related to the RSA group as follows. "By the Chinese remainder theorem, we have that: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\...
0
votes
2answers
64 views

Collusion resistance in proxy re-encryption scheme depending on bilinear map rules

A proxy re-encryption scheme is collusion resistant, if the proxy and a delegatee are not able to recover the secret key of the delegator. For example, when we have a message that was originally ...
0
votes
0answers
46 views

Computing discrete logarithms in the subgroup generated by 1 + N

When I read about DLP, I found that there are groups where the computation is easy. I found that it is known that computing discrete logarithms in the subgroup generated by 1 + N is easy. For example :...
3
votes
1answer
55 views

Mapping a value $g^x \bmod p$ to a small interval $[1…H]$

My question is in $\mathbb{Z}_p^{*}$ context, where $p=q\cdot k+1$ for two primes $p,q$ and $k \in \mathbb{Z}$; $g$ is the generator of the subgroup $G_q$ of $\mathbb{Z}_p^{*}$, of order $q$. Let's ...
0
votes
1answer
56 views

Are there any zero knowledge protocols which do not rely on a Group?

To me (new), it seems that a lot of cryptography relies on group theory. Are there any zero knowledge protocols which do not rely on a group?
2
votes
1answer
276 views

RSA and the strong RSA assumptions

The RSA assumption: Given a randomly generated RSA modulus $n$, exponent $r$ and a random $z \in \mathbb{Z}_n^{*}$, find $y$ such that $y^r=z$. The strong RSA assumption: Given a randomly chosen ...
5
votes
2answers
155 views

Prime numbers of the form $(2^k)p+1$, for a given prime $p$

Let $p$ be a prime. (say 256 bit) Does there a exist a prime $q$ such that $q = (2^k)p + 1$, for a large $k$ (something like 256), if it does exist, is there a way to find out for which all $k$ such ...
4
votes
1answer
85 views

Relationship between generating elements given by cycles in Cayley graph

The strong RSA assumption is that the following problem is hard to solve. "Given a randomly chosen RSA modulus $n$ and a random $z \in \mathbb{Z}_n^*$, find $r>1$ and $y \in \mathbb{Z}_n^*$ such ...
4
votes
1answer
106 views

Understanding the groups used in bilinear Ate-pairing

The bilinear ate pairing $e:G_1\times G_2 \rightarrow G_T$ is defined over the following groups: \begin{equation} \begin{aligned} & G_1 = E(\mathbb{F}_p)[r] \cap Ker(\pi_p-[1]), \\ & G_2 = E(...
6
votes
1answer
366 views

When using Ristretto or Decaf with Ed25519 and Ed448, do scalars still need pruning/trimming/clamping?

Decaf is a point compression method that builds a prime-order group for (twisted) Edwards curves and Montgomery curves with cofactor $h = 4$ based on the Jacobi quartic [H2015]. The promise is to ...
1
vote
2answers
165 views

All generators for modulo p

so I have to find all generators for modulo p. And I thought: isn't there are rule for it? As far as I remember, every number from {1,...,p-1} is a generator because p is a prime. Is that true? Or am ...
0
votes
2answers
217 views

Why is Multiplicative group used in RSA or Euler's theorem but not additive?

I am on the verge to understanding RSA, but suddenly a question popped into mind. When we are calculating $U(N)$ i.e $U(PQ)$, we are taking invertible elements that are co-prime to $N$. For example, $...
0
votes
1answer
65 views

Research topics related to cryptography and Hamiltonian cycles

I am very interested in pursuing a research where I can show an application of Hamiltonian cycles in Cayley graphs of some group such as reflection groups to the field of cryptography. But currently ...
1
vote
0answers
196 views

Steps to determine the single element generators for a multiplicative group

As student I've been asked the following question: Consider the specific prime $p=17$. Determine the single element generators (by hand or by Java program) of $F^*_{17}$. Recall $F^*_{17}$ is the ...
0
votes
0answers
52 views

FLT is partly applying to RSA equation, and also relation between ED mod phi and Phi + 1 mod N

After numerous attempts from myself and all of you guys, I finally came to understand RSA. I can now prove it and understand how I got there. But I still have some very few polishing questions. 1) We ...
4
votes
2answers
88 views

Protocol for proof of knowledge of $l$-th root

Assume we have Group G in which the adaptive root assumption holds. This assumption states that if we choose an element $w$ and after that, if we receive a prime value $l$ it is hard to find the $u$ ...
3
votes
1answer
131 views

Relation between $N = P \times Q$, and $\Phi(N)$

When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem. I did understand how from invertible finite groups I ...
0
votes
0answers
40 views

Proof of two pairs with same exponent

Lets assume we have a group $G$ with unknown order. And we have a pair $(A_1,K_1), (A_2,K_2)$ in which all $A_1,K_1,A_2,K_2$ are group elements. The claim is $A_1= K_1 ^ x$ and $A_2 = K_2 ^ x$. or ...
1
vote
1answer
210 views

(How) Is DDH generally broken in groups of composite order?

In a somewhat recent lecture a claim was made that I couldn't back up myself but it got me curious whether it actually holds: If the order of the group is not prime, then the DDH assumption does ...
0
votes
0answers
42 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 ...
0
votes
1answer
26 views

Rounding down in the exponent of group element

I have been struggling to find the algorithm $\mathcal{A}$ in the following. Let $(G,g,q)$ be the group parameter, $p << q$, $x\in \mathbb{Z}_q$, can we build the following algorithm: $$\...
0
votes
1answer
54 views

Discrete log problem exponential runtime

I am trying to understand the runtime complexity of the discrete log problem (in the most basic sense). So, if we have $\langle g \rangle = G$ and are trying to find $g^x = a, a \in G, 0 < x < ...

1
2 3 4 5 6