All Questions
Tagged with cryptography gr.group-theory
12 questions
1
vote
1
answer
207
views
A candidate for one-way functions
For every $n \geq 3$ consider a bipartite random $3$-regular graph $G_n$ with two parts $X=\{x_1, \dotsc, x_n\}$ and $Y=\{y_1, \dotsc, y_n\}$. For any $i \leq n$ assign either 0 or 1 to each vertex $...
- 11
4
votes
0
answers
169
views
Square hidden number problem
Suppose I have a mystery number $m$ modulo $p$ that I wish to find. I know the value of $m+x_i^2$ where $x_i$ is randomly chosen modulo $p$ for some large number of different $x_i$, $N$ many, $N \gg \...
- 591
2
votes
0
answers
91
views
A variant of hidden subgroup problem (HSP)
I read some materials more general about HSP such as 1,2,3. I wonder that if it would be possible to have a faster quantum algorithm when our goal was just to find a non-trivial element of the hidden ...
- 253
6
votes
1
answer
417
views
Groups in which Computational Diffie Hellman is in $P$ but Discrete Logarithm is not known to be in $P$
The Computational Diffie Hellman (CDH) problem is to compute $g^{XY}$ given $g^X$ and $g^Y$ where $g$ generates the group. The Discrete Logarithm (DLOG) problem is to compute $X$ given $g^X$. The ...
- 13.9k
3
votes
0
answers
285
views
RSA as a hidden subgroup problem
The Hidden Subgroup Problem (HSP) covers several known problems (e.g. Integer Factorization Problem, Discrete Logarithm Problem) as a special case:
Definition [Hidden Subgroup Problem (HSP)] Let $\...
- 131
2
votes
0
answers
88
views
Example of action of an infinitely countable group that has important ergodic/statistical property?
I work in probability and I am looking for an important example of action of an amenable countable group in other areas of math for which the (pointwise) ergodic theorem is actually quite important. ...
- 21
2
votes
0
answers
275
views
Is conjugacy problem hard in braid group?
Recently I studied the braid group and conjugacy problem. It is believed that conjugacy problem is hard on braid group. My friend gave me an EXE file, and I use it for solving conjugacy problem, as an ...
4
votes
0
answers
107
views
Do the normal forms for braid groups really conceal information about better than randomly applying the braid relations?
In braid based cryptography, one typically wants to conceal the way a certain braid $b$ has been obtained. One therefore puts $b$ into some normal form. Since every braid has a unique normal form, the ...
4
votes
0
answers
264
views
Polynomial dynamical systems
The question is somewhat related to the theory of permutation polynomials. Let $\mathbb{F}_p$ be a finite field of $p$ elements ($p$ is prime) and $\mathcal{V} = \mathbb{F}_p^2 = \{ (t_1,t_2)\::\: t_1,...
- 411
9
votes
4
answers
1k
views
The "interplay" between additive and multiplicative structure in a field
A field is an ordered triple $(F, +,\cdot)$ of a set $F$ and binary operations $+,\times$ on $F$ such that $(F,+)$ and $(F\backslash 0,\times)$ are abelian groups satisfying the distributive laws
$\...
- 2,075
9
votes
1
answer
756
views
Any nice examples of small cancellation theory appearing in applied mathematics?
Are there any nice discussions of applications of small cancellation theory, or other cases of the word problem, in applied mathematics or algorithms for seemingly non-group theoretic problems?
I ...
- 565
6
votes
5
answers
6k
views
Analog to the Chinese Remainder Theorem in groups other than Z_n.
The idea hit me when I was in my Elliptic Curve Cryptography class. $Z_n \leftrightarrow Z_{f_1} \times Z_{f_2} \times ...$ where $f_1 \times f_2 \times ... = n$ and $\{f_1, f_2, ...\}$ are pairwise ...
- 359