# Tag Info

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