9

If you look at it from the right direction, lattice-based crypto (and the Shortest Vector Problem) can be viewed as a 'global minimization' problem.


6

The problem about fixed points of discrete logarithms is known the Brizolis problem. In particular for the average number of solutions $$N(p)=\frac{1}{\varphi(p-1)}\sum_g\left|\{0\le x\le p-1:g^x=x\pmod p\}\right|$$ is known that (Grechnikov, 2012) $N(p)=1+S(p)$, where $$-C(\varepsilon)p^{-1/4+\varepsilon}\le S(p)\le \exp(C'\mathrm{Li}((\log p)^{c\frac{\...


5

Such a point is something we would call a "fixed point" of the function $f(x) = g^x$. Before talking about finding such a point, the question needs to be asked as to whether such a point even exists. I refer you to the paper Fixed Points for Discrete Logarithms by Levin, Pomerance and Soundararajan, which studies this exact problem (they also have an ...


3

If you are solving a SIS instance $As = 0$ over $\mathbb{Z}_q$ then this can be seen as finding a short non-zero vector from the lattice $\{z \in \mathbb{Z}^m \ \mid Az = 0 \in \mathbb{Z}_q^n\} \subset q \mathbb{Z}^m$. Thus it is not the same as your $L(B)$. On the other hand, showing that SIS is as hard as certain lattice problems is not obvious and ...


3

I want to get a good characterization of the construct so that I may describe it accurately. I would characterize it as "insecure". If someone has a ciphertext, and manages to guess the plaintext it corresponds to, then they can compute: $$\text{gcd}(E_I(M) - M, N)$$ and they'll give then the factor $p$.


2

The problem becomes easy (as in `solvable in polynomial time') if $$\beta \geq \min_{k=1 \dots m} C^k \cdot q^{n/k}$$ for some constant $C$. This follows from: volume $q^{n}$ for the $q$-ary kernel lattice a Hermite approximation factor of $C^k$ for lattice reduction algorithms (LLL/BKZ) over a lattice of dimension $k$ noting that one can `ignore columns' ...


2

About the basis As stated in the other answer, the lattice directly related to SIS is actually the $q$-ary lattice defined as $$\mathcal{L}_q^\bot(A) := \{ u \in \mathbb{Z}^n : Au = 0 \mod q \}.$$ And its basis is not the matrix $A$. To construct a basis to this lattice, one usually suppose that $A$ has $n$ linearly independent columns (let's say, the ...


2

The value $\delta$ characterizes, how short a vector you can expect to find using an algorithm (typically used in the context of lattice reduction). In particular, for a vector $\mathbf{v} \in \Lambda$ (where $\Lambda$ is a lattice), the associated $\delta$ (often also denoted by $\delta_0$) is defined to be such that $\| \mathbf{v} \| = \delta^n \det(\...


2

Elliptic Curve Digital Signature Algorithm admits universal forgery if the Attacker can solve the equation $$z=\frac{\psi_{k-1}(x,y)\psi_{k+1}(x,y)}{\psi_{k}(x,y)^2},$$ where $k$ is unknown, $\psi_{k}(x,y)$ are Division polynomials and $(x,y)$ are the coordinates of a point $P$ on the elliptic curve $ E:y^{2}=x^{3}+Ax+B$. This UF is based on the formula for ...


2

In the currently stated problem, $p$ and $q$ are primes with $p$ secret and $q$ known, $p<q$, it is chosen some number of (I'll assume: uniformly) random $r_i$ with $q/p<r_i<q$, and revealed $x_i=X(r_i)=r_i\times p\bmod q$. The problem is finding $p$ (or otherwise finding some $r_i$, which in practice will lead to $p$). If we replace the selection ...


2

When given a single triple consisting of $(p,q,x)$ with $x = r \cdot p \mod q$, then there is no hard problem. It takes one inversion and one multiplication (both in modular arithmetic) to calculate $r$. If just $x$ is given, then you can choose $p$ and $q$ arbitrarily and calculate a matching $r$ to fullfill $x = rp \mod q$. If the actual question is ...


Only top voted, non community-wiki answers of a minimum length are eligible