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

174 questions
130 views

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

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 ...
39 views

How many different subgroups exist in composite order groups? [on hold]

For a composite order group $G$ of order $N$, s.t. $N = pq$ where $p$ and $q$ are prime numbers. By the Lagrange's theorem, the order of every element should either be $p$ or $q$ or $N$. Every such ...
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 ...
49 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. ...
85 views

why a group used in cipher based on DLP must be Abelian group?

I can't understand it because $(g^x)^y=(g^y)^x$ in nonabelian group too. thank you very much for read my question
55 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 ...
26 views

Is there any property of the product you can predict before using $n$-times generator $g$ $\mod P$? Can any $n$'th element have a certain property?

Given a value $v$ which is in same group as the generator $g$ modulo prime $P$. The group size is a prime $s$. $v = g^a \mod P$ Only known values are $v,g,P,s$. Some (possible) computation of other ...
29 views

Which is the fastest way to find a member of a subgroup with known size modulo prime $P$, with know factorization of $P-1$?->$x$ with $x^s \mod P = 1$

Assuming you know the factorization of used prime $P-1$ $P-1 = s \cdot f_2\cdot f_3...f_i$ Now you want to find a member of a subgroup $\mathbb{Z}_s$. This means any $x$ with $x^s \equiv 1 \mod P$ ...
71 views

160 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 ...
26 views

How does the order of a group, it's torsion subgroup and the co-factor link?

Given an elliptic curve that defines some group of non-prime order, with co-factor h. Would it then have a h-torsion subgroup? What are the implications for ECC ...
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 ...
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 ...
795 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 ...
2k views

How to find the order of a generator on an elliptic curve?

I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm: Choose random point $P$ on the curve. Find the order of a ...
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 ...
42 views

What are some potential applications of trilinear mappings?

In "Applications of Multilinear Forms to Cryptography" Boneh and Silverberg give "one-round n-way Diffie-Hellman key exchange protocol" as a potential application of n-multilinear mappings. If we ...
56 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 ...
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|} \...
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 ...
127 views

38 views

Algorithm to compute DLOG for elliptic curve $E(F_p)$ with order p

I was reading about elliptic curves in this pdf. Page 55 of the pdf states that if number of points on elliptic curve #$E(F_p) = p$, then there exists a p-adic logarithmic map that homomorphically ...
278 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 ...
171 views

Size of group for Elliptic curves vs RSA for equal security

For my research, I would like to compare the efficiency of a scheme when instantiated with Elliptic curves and RSA. So, I would like to know a "latest" comparison (as of 2018) on what group sizes of ...
192 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 ...
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 ...
4k views

Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective. RSA labs makes a similar statement: The discrete logarithm problem bears the same ...
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 "...
91 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. "...
62 views

What is the difference between these cyclic groups

$\mathbb{Z}^*_p$ vs $\mathbb{Z}^*_{p-1}$ vs $\mathbb{Z}^*_{p^2}$ vs $\mathbb{Z}^+_{p^2}$ I know $p$ is the value. The value create must be coprime to $p$. Does that mean that the value create must be ...
72 views

3k views

What are Cryptographic Multi-linear Maps?

I've encountered this term many times in the fields of Fully-Homomorphic Encryption and Obfuscation. I want to learn those subjects and Cryptographic Linear Maps seems to be an obstacle in the way. ...