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
3
votes
1answer
125 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
92 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
146 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
76 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
46 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
58 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
77 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
82 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
41 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
41 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
48 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
33 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
23 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
41 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
57 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
42 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
51 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
50 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
209 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
151 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 ...
0
votes
0answers
23 views

Finding the relationship between generating elements represented by a Hamiltonian cycle of a Cayley graph (like in strong RSA condition)

Consider an undirected Cayley graph of a finite group $\mathbb{Z}_p \times \mathbb{Z}_q$, where $p$ and $q$ are distinct primes. Let the generating set for the Cayley graph be $S=\{g_p, g_q\}$, where $...
0
votes
0answers
20 views

A related question to “relationship between generating elements given by cycles in Cayley graphs”

I am writing this question with reference to the post at Relationship between generating elements given by cycles in Cayley graph When considering the generating elements $g_qg_p$, does it have the ...
4
votes
1answer
76 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 ...
3
votes
1answer
62 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
204 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
85 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
119 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
54 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
181 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
44 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
83 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$ ...
2
votes
1answer
98 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
34 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
129 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
40 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
25 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
52 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
vote
1answer
57 views

number theory question in a group with unknown order

I was reading a paper and I am struggling understanding one part of it. Lets say we have a group $G$ of an unknown order $n$. we know that $B<n<B+C$. both B and C are large values). we choose a ...
1
vote
1answer
32 views

Is there a quick method of listing certain elements of a cyclic group?

I'm studying applied cryptography and stumbled upon the following question to practice the knowledge about Congruence, Groups etc. "List all Elements $x$, where $x^2 = 2$ in $\mathbb{Z}_{31}$ Okay, ...
1
vote
1answer
55 views

How to find a small generator with small inverse? Does it have negative impact to security? (for Schnorr subgroup of $\mathbb{Z}/P\mathbb{Z}$)

Given a prime $P$ with $$P= r \cdot q+1$$ with $q$ prime as well. I'm looking for a generator $g$ of the Schnorr subgroup with order $q$ which is small by value and has a inverse (to $\bmod P$) which ...
1
vote
1answer
87 views

Double discrete logarithm on elliptic curve

Background: I am attempting to implement the paper Publicly Verifiable Secret Sharing. I managed to get it working using modular groups, but when I want to make it more efficient by transferring to ...
0
votes
0answers
110 views

Define a Decryption algorithm on a given group-based Cramer Shoup lite scheme

I am currently working on public key encryption schemes and I want some help to figure out how decryption algorithms work. Suppose we have a public key $pk = (G,p,g,e)$ with $e \in Z^*_p$ . (where $G$ ...
3
votes
2answers
82 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 ...
3
votes
1answer
90 views

Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number?

With $n$ being a prime number I know we can generate groups over multiplication. Is it possible the other way around ($n$ not being a prime)?
0
votes
1answer
175 views

Order of subgroups formed by Elliptic Curves with a Cofactor

In this question: Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation? The answer indicates that the order of all points on the curve over the finite field ...
1
vote
1answer
71 views

Why do we use prime numbers apart from hard factorization?

Why are prime numbers important in cryptographic constructs? I am not interested in RSA examples where factorization is the hard problem itself, that makes sense. However wherever I go I encounter ...
0
votes
1answer
36 views

Multiplying between generators degree

I have to elements of multiplicative group of finite field with generator g - $$g^x,g^y $$ Can I get? $$g^{xy} $$
3
votes
1answer
100 views

Is there another group structure that is suitable for RSA other than $U_{pq}$?

I know that calculating the cardinality of $U_{pq}$ is infeasible and therefore it is extremely hard to break a code using Lagrange's theorem. But later on my studies i realized main principle of RSA ...
0
votes
1answer
41 views

Orthogonal generators of a group in Lelantus protocol

In the Lelantus Paper, the authors mentionned this: In our case, the commitment key ck specifies a prime-order group G and three orthogonal group generators $g, h_1$ and $h_2$. G is mentioned in ...
2
votes
1answer
91 views

Variants of Bilinear Diffie-Hellman Assumption

Could someone point me to the paper/reference where the following variant of q-strong Bilinear Diffie-Hellman assumption was used? Given $s \in \mathbb{Z}_p^*$ and $g, g^{\frac{1}{s}}, g^{s}, g^{s^2},...

1
2 3 4 5