Is it secure to compute the exponentiation and the LWE operation?

Question

1. Suppose Alice and Bob have specified an elliptic curve, for example, secp256k1. Alice has a secret number $s$ (can be seen as secret key), Bob choose a point $g$ on the curve and send it to Alice. After receiving the point, Alice computes $g^s$ and sends it the Bob. $\text{Whether the interaction will reveal Alice's secret key?}$

2. Similarly, in a RLWE system, Alice has a secret polynomial $s\in R_q$ ($R_q=\mathbb{Z}_q[x]/(x^n+1)$),Bob chooses a polynomial $a\in R_q$ and sends it to Alice, Alice compute $as+e$, where $e\leftarrow \chi$ is a secure distribution in RLWE, then in this situation, whether Bob will learn the secret $s$? Intuitively, if Bob chooses some polynomial $a$ satisfied $ab=0$ for some $b$, then it seems that Bob could learn the $s$, but does Alice have some methods to judge if the polynomial $a$ come from Bob has the property?

Answer 1

For the second question, it depends on whether we can trust Bob to generate $a$ uniformly at random and without any “hidden structure.” If we can trust him, then this is secure assuming RLWE is hard; what Bob gets is merely one properly distributed RLWE sample.

However, if Bob may choose $a$ in a malicious or “sneaky” way, then there can be attacks. For example, Bob can choose $a$ as an NTRU public key, as $a=f \cdot g^{-1} \pmod{q}$ for “short” polynomials $f,g$ of a certain form that constitute the secret key. Then, giving Bob $s \cdot a + e$ for short $s,e$ is essentially just NTRU encryption, and Bob can use $f,g$ to recover $s,e$. Moreover, such an $a$ doesn’t even seem to “look suspicious,” since it’s commonly conjectured that NTRU keys constructed in this way are indistinguishable from uniformly random. So Alice can’t even hope to catch Bob being sneaky in this way.

If Bob doesn’t care about “acting suspiciously,” then there is an even simpler attack: Bob can choose $a=p$ for some small scalar integer $p$ that will be slightly bigger than the coefficients of $e$. Then, giving Bob $b =s \cdot a + e = ps + e$ makes it easy for Bob to recover $e$ (just reduce $b$ modulo $p$) and then $s$.

Answer 2

1. Whether the interaction will reveal Alice's secret key?

I'm reading this like, Bob chose the base point $G$ and sends it to Alice then Alice sends back to Bob $[s]G$. The reason is simple, the elliptic curves use scalar multiplication, not exponentiation. This notation is used for multiplicative groups.

This commitment now turns into a discrete logarithm problem on the curve. The current record on the curve is 114-bit interval and broken on 16 June 2020 by Aleksander Zieniewicz (zielar) and Jean Luc Pons (JeanLucPons) for Bitcoin Puzzle Transactions Challenge. They have published their software that is limited to a 125-bit interval search.

They used the Pollard's Kangaroos and that has complexity $\mathcal{O}(\sqrt{b-a})$ so they have achieved a complexity of $2^{56}$. The generic cost is $2^{128}$ due to the Pollards Rho attack. As you can see this is far from the current capabilities.

One might consider that, can Bob use the basepoint to their advantage? The answer is no!. Consider that Bab chose the base $G$ deliberately that they can solve it easily. There is a simple approach for them to solve for any basis $G'$;

1. Solve DLog $G'$ to base $G$ to obtain $G' = [k]G$.
2. Now given $[x]G'$ solve it in the base $G$ to obtain $r$ such that $[x]G'=[r]G$
3. To get the $x$ just compute $x = r\cdot k^{-1} \pmod n$ where $n$ is the group order.

The conclusion is Alice's secp256k1 DLog commitment is safe from Bob since the secp256k1 is still secure for DLog.

2. Alice has some methods to judge if the polynomial a come from Bob has the property?

The RLWE search problem is stated as, let;

• $a_i(x)$ be a set of random but known polynomials from $\mathbf{F}_q[x]/\Phi(x)$ with coefficients from all of $\mathbf{F}_q$.

• $e_i(x)$ be a set of small random and unknown polynomials relative to a bound $b$ in the ring $\mathbf{F}_q[x]/\Phi(x)$.
• $s(x)$ be a small unknown polynomial relative to a bound $b$ in the ring $\mathbf{F}_q[x]/\Phi(x)$.
• $b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)$.

Then finding the unknown polynomial $s(x)$ given the list of polynomial pair $( a_i(x), b_i(x) )$ is the seach version of the RLWE problem.

So, as longs as the parameters are correct and Bob is not malicious, then the secret and the noise will protect the commitment from Bob. If Bob is malicious - and there is nothing to prevent him to be one, then Bob can insert a hidden structure inside $a_i(x)$ to solve the commitment. That is actually turns into NTRUencrypt. See Chris Peikert's correct answer for this.

Answer 3

Correction to kelalaka's answer:

Bob chooses a polynomial $a\in R_q$ and sends it to Alice, Alice compute $as+e$, where $e\leftarrow \chi$ is a secure distribution in RLWE, then in this situation, whether Bob will learn the secret $s$?

If Bob is limited to a single interaction, then no, Bob cannot recover $s$ (with the RLWE assumption, of course). However, if Bob is allowed to perform a number of exchanges (with Alice using the same $s$), then yes, he can.

Bob can probe $s$; he can submit $a$ and $a+\Delta$ (where $\Delta$ is the vector with the value $\delta$ in the first position, and zeros elsewhere); and get the two answers $as + e$ and $(a+\Delta)s + e'$; subtracting them gives $\Delta s + (e - e') = \delta s + (e - e')$, that is, the secret array $s$ multiplied by a known scalar, and a (slightly larger) error vector. By performing this several times (with different $\delta$ values), we can recover the exact value of $s$.