Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

3
votes
2answers
586 views

Diffie-Hellman insecure on addition modulo $n$

Assume that the group $G$ is the set $\mathbb{Z}_{n} = \{0,\ldots, n-1\}$ for a 1024 bit integer and $+$ is addition modulo $n$. Then why would Diffie-Hellman key exchange in this group be insecure?
3
votes
1answer
428 views

Discrete logarithm weak group

I'm looking for weak groups in discrete logarithm, that $x$ can be extracted from $Y$ in polynomial time where $Y \equiv g^x \pmod{p}$ . I thought one way is to produce a prime $p$ that $p-1$ is an ...
3
votes
1answer
408 views

How to construct a hash function into a cyclic group such that its discrete log is intractable?

From the Linkable Ring Signatures paper: Let $G = \langle g\rangle$ be a cyclic group of prime order $q$ such that the underlying discrete logarithm problem (DLP) is hard. Let $H_1 : {0, 1}^∗ \to \...
3
votes
1answer
790 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 ...
3
votes
2answers
225 views

Finite fields in elliptic curve

I have an elliptic curve defined over finite field where $S_1=aP$ . Is it valid to say that $S_1P$ can also be computed. $P$ is the generator of the group. What my real question is that. Should '$a$' ...
3
votes
1answer
316 views

On getting beyond LSB in discrete log

In discrete log we employ sophie germain primes $p=2q+1$ where $q$ is a prime. Then we know least significant bit $x_0$ in $$g^{2x+x_0}=h\bmod p$$ where $2x+x_0$ is discrete logarithm of known $h\...
3
votes
1answer
312 views

Can we reduce Diffie-Hellman problem to “Discrete-log inversion” problem?

Let $G$ be a cyclic multiplicative group of order $n$. Let $g$ be a (public) generator of $G$. The Diffie-Hellman (DH) problem asks: Given $g^x, g^y\in G$ for $x, y\in \mathbb{Z}^*_n$, to compute $g^{...
3
votes
1answer
541 views

Diffie-Hellman key exchange using addition instead of multiplication?

I know that the additive finite group $(Zp,+)$ of prime order $p$ when I perform the Diffie-Hellman key exchange (DHKE) protocol is insecure. I didn't however find many sources online explain why it ...
3
votes
1answer
245 views

Number generation for Fujisaki-Okamoto commitment scheme parameters

I need to implement the Fujisaki-Okamoto commitment scheme for a project such that I can demonstrate performance of various zero-knowledge proofs in relation to one another, for example Boudot's "...
3
votes
2answers
978 views

Why does Diffie-Hellman need be a cyclic group?

Why is Diffie-Hellman defined on a cyclic group? Doesn't it work for any commutative operation which the inverse is hard to find? Say Alice and Bob agree in a public prime $c$ and both choose a ...
3
votes
1answer
355 views

Modular Arithmetic in RSA

Consider the following the following RSA public key $pk = (N, e) = (1457, 1307)$. (a) Knowing that $187^2 \equiv 1 \pmod {1457}$ find the factorization of $N$. (b) Given the factorization of $N$ ...
3
votes
1answer
607 views

Generator for Group $QR_{N}$

Let $N=PQ$, where $P=2p+1$ and $Q=2q+1$. $P,Q,p,q$ are prime numbers. $QR_{N}$ is the set of quadratic residues modulo $N$. Please help me to prove $QR_{N}$ is a cyclic group. Note: $QR_{P}$ and $...
3
votes
1answer
74 views

Question about the location of the r-torsion in the quotient group used in the Tate pairing

I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the Tate pairing. He defines $rE = \{r*P | P \in E(\mathbb{F}_{q^k})\}$ and then forms the quotient group $E(\...
3
votes
1answer
145 views

Why work in a subgroup for Naor and Pinkas oblivious transfer?

In section 4 (protocol 4.1) of the paper by Naor and Pinkas [1], why did the authors decide to operate in a subgroup? When they say "the messages are in the subgroup" does that mean $x, y, z_0, z_1$, $...
3
votes
1answer
81 views

Does pairings based cryptography inherently require a CRS/trusted setup?

In all algorithms I've seen that rely on pairings-based cryptography (some examples: snarks without PCPs, more snarks, sublinear ring signatures), a common reference string is required. Is this always ...
3
votes
1answer
114 views

How is a group element converted into a key?

I've only just started research on cryptography so I apologize if this is a basic question or I'm getting terms confused. I'm researching braid group cryptography and currently looking at the Anshel-...
3
votes
0answers
71 views

Doubt in computing $g^\frac{1}{\delta+x}$ where $x \in \mathbb{Z}$

I was going through Zero Knowledge Set Membership and came across the following: Given $x \in \mathbb{Z}$ and $g$ is the generator of a multiplicative group $\mathbb{G}$ how do we compute $g^\frac{1}{...
3
votes
0answers
32 views

EC non-shared cryptosystems - different group for every party

Efficient Identity Based Parameter Selection for Elliptic Curve Cryptosystems by Arjen K. Lenstra contains a proposal for a non-shared elliptic curve cryptosystem. Every party chooses its own field ...
3
votes
0answers
55 views

Is there a bilinear map on a non abelian group or non cyclic group?

I've recently been studying a pairing map on cryptography. In usual definition, a pairing map is always defined on the cyclic group G. Is it possible to construct a bilinear map on a non-abelian group ...
3
votes
0answers
94 views

Why does the new encryption scheme proposed by authors stop an adversary from guessing the subspace of the secret key?

In this paper, the authors construct an encryption scheme that is supposed to be resilient to tampering and leaking (as opposed to just leaking). Specifically this scheme: If you look at the ...
2
votes
1answer
1k views

why are non singular curves used in elliptic curve cryptography?

It is not possible to draw tangent at all the points of a singular curve. What is the specialty of this and how it is related to cryptography and elliptic discriminant?
2
votes
2answers
242 views

Given $g$, $b$, $g^{ab}$, is finding $g^a$ a hard problem?

As in the title, given $g$, $g^{ab}$ are big elements in a prime group $Z_p$ and $b$ in prime group $Z_r$ ($p > r$, $g$ is one generator of $Z_p$). $a$ is unknown and also in $Z_r$, is finding $g^a$...
2
votes
2answers
851 views

What does the linear assumption over bilinear groups mean?

In the abstract of "Cryptography with Tamperable and Leaky Memory", at the end of the 3rd paragraph, the authors say: In both schemes we rely on the linear assumption over bilinear groups. What ...
2
votes
2answers
1k views

Factoring large $N$ given oracle to find square roots modulo $N$

When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $\mathbb Z_N^\ast$ have either zero or four square roots. A quarter of the points have four square roots; the rest have no square ...
2
votes
2answers
1k views

Simple example to describe Bilinear mapping

Notation : $\mathbb{G}$ is an additive group and $\mathbb{G}_T$ is multiplicative group of prime order $q$. Bilinear mapping $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$ has to satisfy ...
2
votes
2answers
68 views

Rational exponents on group generators

In elementary concepts, mostly scalar exponents shows up in group operations: $g^x$ As one may encounter in more advanced papers, there are rational exponents over generators. Simply seems like: $g^...
2
votes
1answer
4k views

How to find the generator of an elliptic curve? [duplicate]

If the elliptic curve has prime order of points, then all of its points are generator. Is this true? If so, how can I find the optimized generator(which generates more number of points) among them?
2
votes
1answer
421 views

Why is only one generator stated in literature for elliptic curve group P-256?

I refer to elliptic curve groups over prime fields and their application in cryptography. If the order of a group is prime, it follows (am I wrong?) that: the group is cyclic and every element ...
2
votes
1answer
165 views

Hash “Preimage by product” resistance

Let H() be a hash function that achieves collision resistance as well as first and second preimage resistance. Let's equip the output set of H of a multiplicative group structure, more precisely a ...
2
votes
1answer
807 views

Diffie-Hellman on additive group

Given the finite cyclic, additive group (G, +), with |G| = n and generator = g, what are the computations and exchanged messages for Diffie-Hellman? What I tried myself: Alice chooses a private $a$ ...
2
votes
3answers
2k views

RSA finding the inverse of the public exponent

I have a very basic doubt in RSA key generation and its usage. In RSA key generation you choose two large prime numbers of a very large order. Then you multiply them.(eq $p \cdot q = N$) Now, $\phi(N)...
2
votes
1answer
53 views

What does the number 256 in pairing curve BN256 indicate?

There are many pairing based elliptic curves like MNT curves, BN curves, SS curves etc., When we say BN256 curve, what does the number 256 indicate? Is it some group order or number of bits required ...
2
votes
2answers
260 views

How to determine proportion of quadratic residues in elliptic curve group?

I'm using a 'try and increment' method to hash to an Elliptic Curve point, explained below. With security parameter $k$, EC equation $y^2 = x^3 + ax + b \mbox{ mod } q$, we have: $ u = sha256(\mbox{...
2
votes
1answer
342 views

Is Triple-DES a group?

I know for a fact that DES is not a group, but are any of the Triple-Des versions a group? Why, or why not?
2
votes
1answer
70 views

How to compare the order of elements in cyclic groups?

In a cyclic group with randomly looking behavior like the one used in secp256k1, is there any known efficient algorithm to compare the order of two randomly given elements $P_1$ and $P_2$ and find out ...
2
votes
1answer
436 views

What's dh-composite test on badssl.com?

The site badssl.com provides examples of bad (red icon) and good (green icon) uses of TLS for the purpose of testing TLS implementations. I'm a bit confused by the test called dh-composite. This ...
2
votes
2answers
537 views

How can I find the generator of a composite group and $Z_p*$?

I was doing some research on elliptic curves. I know how to find the generator of $Z_p$ (this is a prime group). But I came across the term $Z_p*$ (group containing elements that relatively prime to $...
2
votes
1answer
122 views

In a additive group is it hard to calculate $bg$ given $ag, g, abg$

The ECDH problem defined that given $g,ag,bg$ it is difficult to calculate $abg$. But it is also difficult to calculate $bg$ given $ag,g,abg$. where $g$ is generator and a,b are elements of group.
2
votes
1answer
38 views

Is the CONF key sharing Problem equivalent to discrete log problem?

If there a proof in the literature which says the CONF Problem is equivalent to solving the discrete log ? Let $g$ be a generator of a cyclic group $\mathbb{G}$ of prime order $q$ CONF problem: ...
2
votes
1answer
273 views

Generators and Multiplicative group $\mathbb{Z_7}$

In the multiplication table for $\mathbb{Z^*_7}$, each row has all the elements of the set My questions are: is each element a generator here? if not why? is an element considered as ...
2
votes
1answer
191 views

What role does Representation Theory play in Cryptography?

Shannon said that every cryptosystem can be expressed as a system of linear equations with a large number of unknowns of complex type. In cryptography groups are used since they are a natural ...
2
votes
1answer
156 views

What is the correct elliptic curve representation?

I'm studing the basics of elliptic curve from various resource some more mathematical someone more practical. I know that the equation where the elliptic curves come from is the Weistraß equation $$...
2
votes
1answer
73 views

LSB of the Exponent in the DL Problem Can Be Efficiently Computed for Groups of Even Order

I am studying a script on the mathematical foundations of cryptography as part of which I am currently trying to wrap my head around some basic cryptographic reductions. I am stuck on one problem that ...
2
votes
1answer
231 views

Additive proof of discrete log?

Let's say someone has $K$, and I want to prove to them that I know $k$ such $K = k*g$ (where $g$ is some sort of group element). I can use a Schnorr signature. Is there some protocol for mergable ...
2
votes
1answer
191 views

Elliptic Curve ElGamal and DSA - smooth group order and element of large prime order

In regular ElGamal and DSA, we choose large primes $p$ and $q$ such that $p\equiv 1\pmod{q}$, and a group element $g$ of order $q$ by computing $a^{(p-1)/q}$ for some random $a$. This is to prevent ...
2
votes
1answer
224 views

Given $g,g^t$ in a cyclic group of order $pq$, is it hard to compute $g^{t^{-1}}$?

Suppose we have a group $G$ cyclic of order $pq$ , where $p,q$ are primes. Let $g$ be a generator of $G$ and $t\in \mathbb{Z}_{pq}$. Having $g$ and $g^t$, it seems to be very hard to find $g^{t^{-1}}$,...
2
votes
2answers
465 views

How to compute two EC point multiplication?

I would like to know how to compute multiplication of two valid EC points over a curve E with generator G. i.e. Given only P and Q points then how to compute R = P * Q where $P = p G$, $Q = q G$ and ...
2
votes
0answers
60 views

Is this an error in the Pinocchio Protocol paper

I am going through the Pinocchio protocol paper and I need 2 clarifications in the section Protocol 1 (Verifiable Computation from strong QAP). The part that explains the Verify process, which ...
2
votes
0answers
134 views

BLS signatures in the G-valued Random Oracle Model

This paper on semi-generic algorithms considers "non-standard properties of the employed hash function". For BLS signatures whose main group is $G$, I'm curious what can be shown when the hash ...
1
vote
3answers
392 views

How is it decided if $G_1$ and $G_2$ are two “additive” or “multiplicative” cyclic groups?

According to wiki's definition of Bilinear pairing… Let $G_1$ and $G_2$ be two additive cyclic groups of prime order $q$, and $G_T$ another cyclic group of order $q$ written multiplicatively. A ...