Tag Info

New answers tagged

3

The (in my opinion) simplest way to proceed about this is: First compute the square root $m:=\sqrt n$ of $n$ in $\mathbb N$; this can, for instance, be done in time $\mathcal O(\log^3n)$ using a binary search. The next step is to compute $\varphi(m)$ from $\varphi(n)$: by the properties of $\varphi$ we have $$\varphi(n) = (p-1)p(q-1)q=\varphi(m)\cdot m ...


4

When decrypting in lattice-based cryptosystems, one computes a value $v \in \mathbb{Z}_q$ that is guaranteed to be congruent to a "small" integer $e \in \mathbb{Z}$, where $e$ encodes the message (e.g., as the parity of $e$ modulo 2). By using the integer representatives between $-q/2$ and $q/2$, one can recover the small integer $e$ (and thereby recover ...


1

My understanding is that the coefficients of polynomials used in lattice crypto are often sampled from a discrete Gaussian distribution. A Gaussian is centered at 0, which would explain why the elements are represented as elements from the set $\{\frac{−(q−1)}{2},…,\frac{(q−1)}{2}\}$, as you mentioned.


1

There is no standard "multiply two group elements" operation in an additive group. So you first need to define what you mean by $P*Q$. From the comments I gather that you want $P*Q = q P = p Q = (p \cdot q) G$. The computational Diffie-Hellman (CDH) problem is: Given $P=pG$ and $Q=qG$ compute $(p\cdot q)G$. which is clearly equivalent to your problem. ...


0

Well the equation $R = P * Q$ simply isn't possible on an elliptic curve. The group of points on the EC is an additive group. Meaning it is only possible to compute $P + Q$ or $[m] P$ for some integer m. Taken $P=p \cdot G$ and $Q=q \cdot G$ you already got the answer yourself: $R=(p \cdot q)G$. Simply add the point $G$ to itself $(p \cdot q)$-times.



Top 50 recent answers are included