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).

1
vote
2answers
465 views

RSA keys are multiplicative inverse in mod phi(n), but also in mod n?

I understand that the RSA keys $pk$ and $sk$ are choosen such that one is the multiplicative inverse of the other, in $\mod \phi(n)$ But for the encryption and decryption to work, in other words, ...
1
vote
2answers
233 views

Elliptic Curve Point at Inifnity in Projective Coordinates

I'm implementing an elliptic curve system primarily for ECDSA verification. I've evaluated different point representations and decided that using Jacobian projective coordinates suits best for my ...
1
vote
1answer
307 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 ...
1
vote
1answer
80 views

Permutations coming from RSA

The RSA algorithm can be used to generate a permutation. Given two prime numbers $p$ and $q$, the key length is $n=pq$. If $a$ is the private key, then $b$ is the public key, where $ab \equiv 1 \...
1
vote
1answer
67 views

Understanding Baby-Step Giant-Step Algorithm and discrete logarithm

Studying the Baby-Step/Giant-Step Algorithm, I have some questions: In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\...
1
vote
1answer
227 views

How to select elements randomly from a multiplicative group Zn*

I am working on a problem in which I have two large safe primes say p and q randomly selected each of 512 bits. I have generated ...
1
vote
1answer
443 views

Are the RFC3526 MODP groups Schnorr groups?

I was wondering if a group like the 1536-bit MODP Group from RFC 3526 was a Schnorr group? A Schnorr group must apparently have: $p$ and $q$ being primes $p = q\cdot r+1$ $1 < h < p$ $h^r\not\...
1
vote
1answer
829 views

How is multiplication inverted in IDEA's decryption round?

As we can see in the picture we have a multiplication in this algorithm, we know that two 16 bit inputs should have a 32 bit output, but here we just use 16 bits of the 32 bit output. For decryption ...
1
vote
1answer
142 views

What type of groups does Microsoft's U-Prove use (Schnorr… etc?)

I'm trying to learn more about the Subgroups implementation of Microsoft UProve. I'm unsure if they are Schnorr Groups or use a different foundation? Can anyone point me to the technical reading ...
1
vote
1answer
161 views

Why do elliptic curves require fewer bits for the same security level?

I'm studying the basics of cryptography and I didn't understand why elliptic curves use fewer bits. For example, finite-field Diffie-Hellman needs at least 1024 bit and it's a DLP, but elliptic ...
1
vote
1answer
847 views

ECC Point Multiplication of Product

I can calculate $Q = a\,b\,G$ in several ways: $Q = a \, (b \, G)$ or $Q = b \, (a \, G)$. These give the same result, as expected. But if I do $c = (a \, b) \bmod n$ where $a \, b$ is much greater ...
1
vote
1answer
35 views

How to prove element equality in G1 using Groth-Sahai proofs

In the BeleniosRF e-voting scheme, Groth-Sahai proofs with the "Instantiation based on the SXDH assumption" are used (see https://eprint.iacr.org/2007/155, version 20160411:065033, page 24). In the ...
1
vote
1answer
91 views

Proof one-time pad is perfectly secret with eavesdropping game definition

I have the following definition of perfect secrecy (please assume that the probabilistic version is not available): If we consider the eavesdropping game given by: $$\begin{array}{|r | r|} \...
1
vote
1answer
72 views

Is this problem same as discrete logarithm?

Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds. Take the problem given $g,g',h$ where $g^z\equiv h\...
1
vote
1answer
122 views

bilinear maps rules

A bilinear map has to satisfy this property: $e(aP,bQ) = e(P,Q)^{ab}$ for all $P,Q \in \mathbb{G} , a,b \in \mathbb{Z}_q$ so far so good. My question now is related to this paper: https://eprint....
1
vote
1answer
137 views

Sum probability

if $a,b,c$ are selected at random from a large cyclic group, then what could be the probability that $g^{a+b}$=$g^c$? it simply corresponds to the probability that multiplication of two random ...
1
vote
1answer
262 views

Generating Diffie-Hellman parameters

I'm trying to implement a diffie-hellman key exchange in c++, and I'm struggling with my missing understanding of math / group theory. Let's say I found a large prime number p - how can I find a ...
1
vote
1answer
217 views

Discrete logarithm problem in subgroup of index 2. ElGamal

I need some insight for the following problem in ElGamal encryption procedure. It is stated that ElGamal problem in a group $\mathbb{Z}_p^*$ becomes easier in subgroups. Assume I have a subgroup of ...
1
vote
1answer
328 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 as the smallest integer ...
1
vote
1answer
687 views

ElGamal and Schnorr groups

As I gather, a normal practice for choosing a cyclic group for ElGamal key generation is to find a safe prime $p$ and use a multiplicative cyclic group with modulus $p$ and order $q = (p-1)/2$. ...
1
vote
0answers
32 views

Group Rings on Cryptography

Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This ...
1
vote
0answers
52 views

What can be said about the self-power map on groups based on DLP?

I've been playing with group representation theory some time, concretely representing groups as permutation groups (Cayley's theorem), where the group $G$ has an embedding into the symmetric group. ...
1
vote
0answers
99 views

How do pairings behave on G2/twist points off the prime order subgroup?

$\newcommand{\F}{\mathbb{F}}$ Consider the ate pairing defined on a curve $G_1 = E(\F_q)$ and $G_2 = E'(\F_{q^r})$ where $E'$ is a twist of $E$ with the twisting isomorphism defined over $\F_{q^r}$. ...
1
vote
1answer
40 views

How is the generator used in Feldman's Verifiable Secret Sharing scheme determined? [duplicate]

According to the Wikipedia description of Feldman's VSS scheme First, a cyclic group G of prime order p, along with a generator g of G, is chosen publicly as a system parameter. (Typically, one ...
1
vote
0answers
92 views

Drawbacks of Schnorr Authentication that require Fiat-Shamir and Random Oracles?

I've been going through G. Maxwell's paper on the Borromean Ring Signature, and I don't fully understand this part on Schnorr Signature. If some could explain it more intuitively thank you. "...
1
vote
0answers
130 views

discrete logarithm vs normal logarithm [duplicate]

Crypto schemes normally use discrete logarithm instead of normal logarithm. I think this has to do with the fact that discrete logarithm is hard to solve while normal logarithm isn't. Can someone ...
1
vote
0answers
235 views

Can Bitcoin mining solve Graph Isomorphism-related problems?

Given a cryptographic hash $H:\{0,1\}^*\mapsto\{0,1\}^N$ and data $D\in\{0,1\}^*$, the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $x$ such that $H(x\Vert D)$ begins with $d$ leading zeros, ...
1
vote
0answers
144 views

Is there a flaw in this ring signature scheme? [closed]

Having read some papers about RSA accumulators applied to ring signatures schemes, I ended up thinking why would we need to accumulate all the members public keys for our specific use case. So I came ...
1
vote
0answers
44 views

Hash function notations and their corresponding existing cryptographic hash algorithm

I am implementing Role-based access control by referencing the paper Enforcing Role-Based Access Control for Secure Data Storage in the Cloud. In page 6, they have mentioned to choose hash functions $...
1
vote
0answers
154 views

What is the hardness in Decisional Linear Assumption (DLIN)?

I had understood what does the DLIN assumption means and here is a related question. But I fail to understand the 'real hardness' in this problem. I would be grateful if someone can help me to ...
1
vote
1answer
119 views

Converting a number to a member of a multiplicative cyclic group

I am currently trying to make an implementation of the ElGamal encryption for educational purposes. As I understand it, when using the encryption with multiplicative cyclic groups, one generates a ...
1
vote
0answers
58 views

How to understand the Bilinear mapping with an example [duplicate]

An efficient bilinear map is given by $ e $: $G_{1}$ × $G_{1}$ → $G_{T} $. How can i prove this equation with the help of an example.
1
vote
0answers
352 views

Best group if one wants the discrete log problem to be hard?

Suppose one is implementing a cryptographic scheme over a group where one needs the discrete logarithm to be hard - what is the recommended group to use? I'm looking for a group where calculations are ...
0
votes
2answers
829 views

Why is ElGamalEngine in bouncy castle restricting input data to be less than the length of the group parameter p?

I am currently using the ElGamalEngine of bouncy castle to implement exponential ElGamal for the purpose of making ElGamal additively homomorphic. To do this i raise the message to be encrypted to the ...
0
votes
1answer
97 views

If I know an element and it's inverse, can I learn the modulus?

If I know an element $x$ in a group, and it's inverse $x^{-1}$, can I guess the modulo, or with a probability?
0
votes
1answer
189 views

Show How to Efficiently Solve the Computational Diffie-Hellman Assumption given an Algorithm that Solves the Square-DH Problem

Let $q$ prime number, $G$ a cyclic group with order $q$ and let $g \in G$ be a generator of $G$. Suppose that you have an algorithm $A$ who takes input the element $g^a$ of $G$ and gives as output the ...
0
votes
3answers
2k views

Generation of a cyclic group of prime order

I am trying to implement a cyclic group generator in Java, but I am running into some issues. In many cryptosystems, the following phrase is expressed during the key generation stage. Let G be ...
0
votes
2answers
52 views

A Question about Notations and Groups

Please consider the following question: Determine the order of all the elements of the following multiplicative groups. You can write a C or Java program to do this. a. $Z_{21}^*$ b. $Z_{23}^*$ Now ...
0
votes
2answers
162 views

Pairing - Is it possible to map two $r$-torsion points to a $r^2$-torsion point?

Let $E(\mathbb F_{q^k})$ be an elliptic curve on finite field $\mathbb F_{q^k}$, where $\mathbb F_{q^k}$ is an extension of $\mathbb F_q$ with $k>1$. Let $e: G_1 \times G_2 \rightarrow G_t$ be a ...
0
votes
1answer
57 views

Key exchange protocols non-reducible to groups

Some questions I have ended up wondering about while reading through many of key-exchange protocols are: Is there an intrinsic reason, why most key exchange protocols use group-based approaches apart ...
0
votes
1answer
70 views

What does the “description of group $G$” includes?

I was reading here:second discrete log meaning in the solution and also here:key generation, first point where the say given $G$ (or its description). My question is what does this description ...
0
votes
1answer
123 views

Derive $x$ when given $g,g^x$ and $g^{(1/x)}$?

If an adversary has access to the generator g of a group G and is given access to $g^{x}$ and $g^{(1/x)}$, will it make it any easier to derive the value of $x$ compared to when he had access to only $...
0
votes
2answers
267 views

Is solving a modular linear equation a hard problem when the coefficient is not an invertible element?

Assume that we have a linear equation like this: $$ax=b \pmod n$$ when $x$ is the unknown, and $a$ is not an invertible element in $n$. is finding $x$ a hard problem? (by solving I mean finding an ...
0
votes
1answer
183 views

What's the number of unique possible Cayley tables in a 16*16 grid for XOR'ing single hex characters?

A few days ago, I designed and s-box then derived the following Cayley table of all possible XOR outputs of hex digits in the range of ${2^4}$ and was curious how many such "valid" possible ...
0
votes
2answers
44 views

Elliptic curves - operations in larger groups - performance

According to my measurements and to this work, it seems that operations, for example scalar multiplication, are more expensive in larger groups. If I have, for example, an 80-bit elliptic curve and an ...
0
votes
2answers
98 views

Can someone explain the definition of four square roots as it pertains to groups in Z*p?

So I'm given the following as a problem: When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $Z^∗_N$ have either zero or four square roots. A quarter of the points have four square ...
0
votes
1answer
639 views

What is Group in Diffie-Hellman?

I understand how Diffie-Hellman key-exchange works. Mainly, two parties agrees in a prime $p$ and a generator $g$. Then one party selects its private exponenet $x$, computes its public value $g^x \...
0
votes
1answer
454 views

Pollard's Rho - Constructing the random function

Suppose we are aiming to solve the discrete logarithm problem $\alpha^x=\beta$ in some cyclic group $G=<\alpha>$. Then we are looking for a (uniformly) random sequence of elements of the form $\...
0
votes
2answers
891 views

Elliptic curve group over a prime finite field $F_p$

If $p$ is a big prime, and the elliptic curve $E$ is defined over $F_p$ by the equation $y^2=x^3+ax+b$ where $a,b\in F_p$. The point on $E/F_p$ together with the infinite point $\mathcal{O}$ form a ...
0
votes
1answer
60 views

Operation Table for Permutation Group

I cannot seem to figure out how the operation table for this permutation is formed. Is it multiplying each index and doing modulus? I can't seem to figure out. This is a Table 4.2 found in "...