Questions tagged [hard-problem]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-2
votes
1answer
68 views

Is permutation conjugate search problem many answer? Are there many answer equal? [on hold]

If conjugate search problem of permutation is difficult , then there are next cryptosystem will appear. A=XYX−1,B=XZX−1,Y and Z are public key.And X is secret permutation. then encryption is C=...
-1
votes
0answers
59 views

How to prove which complexity class a problem belongs?

How to prove that a problem is computationally hard? For example, how to proved that the problem of integer factoring into two prime numbers is difficult? How to prove that the decoding problem of a ...
1
vote
2answers
91 views

From the product of two permutation matrices raised to the same power, is it easy to find the power?

Let $A$ and $B$ be two public permutation matrices. If $r$ is a secret power of large number, can we easily find $r$ from $A^rB^r$?
0
votes
1answer
107 views

Is Permutation conjugate problem hard?

Let $x$,$y$,$z$ be permutations. Then public key is $z=xyx^{−1}$ and $y$. Is permutation conjugate search problem easy? if yes, how to find $x$ from $z$ and $y$? Let be a is Alice's secret key as ...
6
votes
1answer
110 views

When does the SIS (Short Integer Solution) Lattice-problem start becoming easy (According to the parameters size)?

SIS (Short Integer Solution) Problem : Given $m$ uniformly random vectors $a \in Z_q^n$, grouped as the columns of a matrix $A \in Z_q^{n.m}$, find a nonzero integer vector $z \in Z^m$ with $||z|| \...
2
votes
1answer
60 views

Can I connect the hardness of a linear short integer solution problem to that of SIS problem?

As we know, SIS problem is defined as: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $\mathbb{Z}_q^{r \times n}$, it is hard to find elements $s \in \mathbb{Z}_q^{n}$ ...
3
votes
2answers
160 views

How is the matrix A related to the lattice space L in SIS?

Is the matrix $A= (b_1|,...,|b_m)$ where B=$(b_1,...,b_m)$ is the basis of the lattice space, $L$(B)? Not sure if the answer is trivial however I'm having trouble seeing how SIS is a lattice hard ...
4
votes
1answer
69 views

Global minimum based cryptography?

When using the Back propagation Algorithm for Machine Learning, it is often said finding the global minimum of a cost function over $\mathbb{R}^n$ is very hard, and as $n$ increases it gets even more ...
8
votes
2answers
195 views

How hard is Self-DLOG?

This question while asking for something different brings up an intriguing problem: If you can find $x$ such that $x\equiv R^x\pmod p$ then you can break DSA. Now I thought that one might be able to ...
2
votes
1answer
154 views

Universal forgery based on mathematical problem

It is known that DSA admits universal forgery under assumption that the Attacker can solve the equation $x\equiv R^x\pmod p.$ Are there any other protocols admitting universal forgery based on non-...
2
votes
2answers
192 views

More general - what is the hard problem of recovering r from r*p mod q?

I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that ...
1
vote
1answer
68 views

What is the hard problem for this algebraic encryption construct?

I would like to know what cryptographic hard problem this reduces to. Select two large prime numbers $p$ and $q$, and let $N=pq$. Select a random positive integer $r$. Compute the encryption of ...
3
votes
1answer
418 views

How to estimate the hardness of SIS instances?

The Short Integer Solution (SIS) problem is to find, given a matrix $A \in \mathbb{F}_q^{n \times m}$ with uniformly random coefficients, a vector $\mathbf{x} \in \mathbb{Z}^m \backslash \{\mathbf{0}\}...