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
2answers
155 views

What could a_0=s in Shamir's secret sharing scheme represent?

What could $a_0=s$ in Shamir's secret sharing scheme represent? As we already know in a $k$ out of $n$ secret sharing scheme, a secret is split in $n$ parts however only $k=t$ parts (of a polynomial ...
0
votes
1answer
41 views

An equivalent definition for shamir secret sharing?

Taking into account this paper I will write here a definition that the authors provide. $\textbf{Definition:}$ (linear secret sharing scheme). A $(t,n)$ secret sharing scheme is a linear secret ...
1
vote
1answer
26 views

Secret sharing questions

I would like to make a few questions about Shamir's secret sharing scheme and. To begin with, I am starting with the next theorem that determines the intuition of the whole theorem. $\textbf{Theorem:}$...
1
vote
1answer
37 views

How to define a cryptosystem when the encryption-decyrption scheme is based on Shamir's secret sharing scheme?

I would like to make a parallelism between Shamir's secret sharing scheme and how to define a cryptosystem where the encryption scheme is based on secret sharing. To begin with I do not know if there ...
0
votes
1answer
22 views

Could we use permutation polynomials for Shamir's secret sharing scheme?

Could we use permutation polynomials for secret sharing scheme like Shamir's? The say that they induce a bijection over $\mathbb{Z}_p$ what does this mean and how does it helps?
3
votes
1answer
100 views

Mathematical formulation for a cryptosystem

I will try to define easily the cryptographic system of this paper. The author designs a communication game for $N$ players. The private information of every player is denoted as $t_i\in T_i$ and ...
0
votes
0answers
31 views

Secure multi-party computation made simple - questions

The scheme that I refer to is from this paper. A secret $s\in D$ is obtained by splitting s into a random sum. We have (actually linear) for any $k$ this $k$-out-of-$k$ secret-sharing scheme: Select $...
0
votes
0answers
21 views

Could you provide the proof of a secure multi - secret sharing scheme that fulfils the requirements of correctness and information-theoretic privacy?

Suppose that we have a multi-secret sharing scheme and let $I$ be the a set of agents. Say that $S$ is the space of the (uniform) random variables $s=(s_1,s_2,\cdots,s_I)\in S$ such that the share $...
2
votes
0answers
51 views

Could anybody help by applying a secure multiparty secret sharing scheme?

Suppose that we have a multi-secret sharing scheme as it is described in the literature Let there be $I$ agents and say that $S$ is the space of the (uniform) random variables $s=(s_1,s_2,\cdots,s_I)\...
1
vote
0answers
21 views

Secret sharing scheme combined with probability theory results?

As a sequel of my previous post I am writing a new one with respect to the secret sharing scheme. I will only cite here the answer because I want to make a question on it. $\textbf{Answer:}$ To be ...
0
votes
0answers
20 views

How to design such a secure multiparty computation scheme with the players using a majority rule

Suppose that $y$ is a uniform random variable that is defined over the field (or group or abelian group) $Y$. Let us suppose that there are $N=\{1,2,\cdots,i\cdots,N\}$ agents and only one of them, ...
0
votes
1answer
42 views

Could this be a secure multiparty secret sharing scheme?

Suppose that $y$ is a uniform random variable that is defined over the field (or group or abelian group) $Y$. Let us suppose that there are $N=\{1,2,\cdots,i\cdots,N\}$ agents and only one of them, ...
1
vote
0answers
29 views

Finding an element of $\mathbb{Z}_p$ if the order of that element is known [duplicate]

I have two prime numbers $p$ (1024 bits) and $q$ (160 bits) such that $q$ divides $p-1$. Now I want to find an element $b$ in $\mathbb{Z}_p$ with the order of $q$. That means that $b^q \equiv 1 \mod p$...
0
votes
1answer
74 views

How are the cipher, the key and the initial message (that is not encrypted) are releted?

Suppose that $m$ is a message that someone player $i$ wants to send to a network of other players $j\neq -i$. The player to prevent his message from cheating by others uses an encyrpstion scheme. Say $...
4
votes
0answers
75 views

Secure multiparty scheme in key (splitting) distribution among the players

Suppose that we have a game with $I$ players and each of them has a private secret say $e_i$. Every player wants to share her secret with the rest of the players but in such a way that she will not be ...
1
vote
0answers
38 views

Could anyone provide any idea of such a protocol?

Could anybody provide the seminal paper and/or every specific manual in mathematics that describes a secure multiparty computation procedure, where the players will exchange encrypted messages (...
1
vote
0answers
22 views

Sharing information scheme of cryptography - operations in modular arithmetic

Taking into account my previous question here and the answer about the proposed encryption-decryption scheme. I am trying to understand how to make possible operations in modular arithmetic for a ...
1
vote
1answer
37 views

computation time of pairing operations and their securities

Suppose G1 is an elliptic group and G2 be a multiplicative group and they are of same prime order p and e is a bilinear pairing, e: G1 X G1 -> G2. The operations e(p,q)r and e(pr,q) gives equal ...
1
vote
2answers
98 views

In AES-256, what exactly forms the extension field $GF(2^8)$?

My question is a little difficult to describe, so let me first start with an analogy In an elliptic curve over a finite field, there are 2 groups - the first group is a finite field over which the ...
5
votes
3answers
564 views

How to decide if a point on a elliptic curve belongs to a group generated by a generator g?

In the elliptic curve encryption scheme, there is a cyclic group generated by a base point $G$ on the elliptic curve. Given a random point on the elliptic curve, is there a way to decide if the random ...
3
votes
1answer
309 views

problem with a discrete logarithm/cyclic groups example... can anyone clarify this concept for me?

I was watching this really short video about the discrete logarithm example: https://www.youtube.com/watch?v=SL7J8hPKEWY and at 0:38 they show all the possible values that you can get if $p = 17$ and $...
2
votes
1answer
114 views

How to have a hash function that maps from a group element to a binary string of a certain size in charm-crypto?

I am facing a problem in programming with the charm-crypto library. The hash functions for pairing group elements in charm-crypto can only map from a string to a specific field: $\mathbb Z_r$, $G_1$ ...
0
votes
1answer
91 views

zkSnark Intro by Maksym Petkus: Is the polynomial defined over $Z$ or is it defined over $Z_n$?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf Here he has a polynomial $p(x) = x^3 − 3x^2 + 2x$ and the homomorphic ...
0
votes
1answer
54 views

Structure of composition of permutations

If $P_1, P_2$ are finite permutations, what can we say about $P_3 = P_1 \cdot P_2$? That is, what properties of the composition of permutations can be inferred from the properties of the permutations ...
1
vote
1answer
30 views

Generation of the order $\lambda$ (which is lcm((p-1),(q-1))) element g in modified paillier, why $-a^{2n}$?

As the question states, in variants of paillier cryptosystem, such as CS01 and DT-PKC, when they want an element $g$ of order $\lambda$, they choose a random number $a$ from group $Z^*_{n^2}$ and ...
1
vote
1answer
119 views

How to find integer point of a ec curve in a given range?

I was looking inside the basics of ecc and found the examples from Internet either uses continuous domain curve or use a very small prime number p like 17 in a ...
0
votes
1answer
98 views

Setting up the discrete logarithm framework

The discrete logarithm problem over prime cyclic groups consist of finding $x$ satisfying $g^x\equiv h\bmod p$ where $g$ is generator of multiplicative group $\mathbb Z/p\mathbb Z$ at a large prime $p$...
6
votes
2answers
124 views

Does Poly1305 have weak keys like GCM/GHASH?

Some block cipher keys are weak when used with GCM; see this question. This happens when the multiplier $H$ decided by the key ends up in a small-order subgroup of $\mathbb{F}_{2^{128}}$. Poly1305 ...
4
votes
1answer
103 views

Why does Index Calculus work?

I understand how the Index Calculus algorithm works - I know & understand the steps. I understand how the steps are derived. However, I am not able to figure out why it works. I can understand why ...
0
votes
1answer
48 views

what does "product of two cyclic groups" mean

I am reading "Elliptic curve cryptosystems" and the link is here(https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/S0025-5718-1987-0866109-5.pdf). I don't understand ...
1
vote
0answers
28 views

A finite group with a threshold functionality

I am trying to find a generator of a finite group that its powers devides the group into two parts. For example look at the last row of this table that shows the powers of 10 in the group Z_19. You ...
0
votes
0answers
116 views

Using random invertible matrices over finite fields to define the hash of a list

This is a follow-up to a prior question Does matrix multiplication of hash digests admit manipulation of the result?; this formulation failed because it admitted singular matrices and therefore ...
0
votes
0answers
26 views

Checking whether a particular group has an efficient, faithful representation as a matrix group

There are cryptographic protocols being developed for non-abelian groups. For some protocols it is necessary to know whether the group has an efficient representation as a matrix group (say, a matrix ...
2
votes
1answer
107 views

Representation theory in cryptography/coding theory

How can representation theory be used in cryptography and/or coding theory? I am studying a MSc in pure mathematics and I am currently working on things related to biset functors, but cryptography and ...
1
vote
1answer
54 views

Do groups generated by round functions generate the alternating group?

Let $K,X$ be sets and let $F:K\times X\rightarrow X$ be a function. For each $k\in K$, let $f_{k}:X\rightarrow X$ be the function where $f_{k}(x)=F(k,x)$ whenever $k\in K,x\in X$. Assume that each $f_{...
1
vote
2answers
96 views

Different modulus in the exponent

Given two values $g^{a_1}, g^{a_2}$ where $a_1, a_2 \in \mathbb{Z}_q$ and $g$ is a generator of group $\mathbb{G}$ of order $q$. Discrete logarithm is assumed to be hard in $\mathbb{G}$. Is there a ...
1
vote
1answer
53 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
40 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
259 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
0answers
31 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
88 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
92 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
272 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
147 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
54 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
236 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
32 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
182 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$?
4
votes
1answer
746 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
2 3 4 5 6