7

This problem is equivalent to the CDH problem: Here is how to solve CDH given an Oracle that solves this problem: Given $g, g^x$, we can compute $g^{x^{-1}}$ (which is equivalent to the CDH problem) by doing the following: Call the Oracle with $g, g^x$; the Oracle gives us a pair $g^{y}, xy$ We compute $(g^{y})^{(xy)^{-1}} = g^{x^{-1}}$, hence showing one ...


7

Broadly speaking, it's true that the main difference between "code-based cryptography" assumptions and "lattice-based" assumptions is the noise distribution. There are of course exceptions, e.g. code-based cryptosystems using the rank metric, or binary LPN, where the noise can be described as either small Hamming weight or small Euclidean ...


6

There is no known reduction from LWE to MLWE (or to RLWE). That is, it could be that both MLWE and RLWE are broken, yet LWE is secure. However, this seems highly unlikely. To support the security of LWE, we have reductions showing that breaking the average-case hardness of LWE requires breaking the worst-case hardness of some lattice problems - which would ...


5

and the elf model proves a secure block cipher exists It is worth mentioning that lower bounds in computationally limited settings do not "lift" [1] to lower bounds in computationally stronger settings. For example, there are lower bounds of $\Omega(\sqrt{|G|})$ on DL in the generic group model. This does not prove that DL is hard in "real ...


4

Regarding your first paragraph, I would not say that the key difference is the type of noise, because lattice-based cryptography (LBC) uses a lot of different noises: Gaussian, binary, ternary, etc. (also see this SE thread: Uniform vs discrete Gaussian sampling in Ring learning with errors). However, something extremely useful in LBC is that you can play ...


4

TL;DR: No, that problem is not hard. Synopsis: After remapping of $\Bbb Z_p$ by an involution $x\to\overline x$, the function $(x,y)\to\overline{-f(\overline x,\overline y)}$ is mostly associative. We massage it into an Abelian finite group $(\mathcal S,\boxplus)$. This makes $\overline{r_n}$ a linear function of $\overline a$ and $\overline b$ with known ...


4

It is a major open research question whether such a scheme exists, and how to construct one (see, for example, Open Problem 9.10). Of course, we do have schemes like (hashed) ElGamal, which are based on the conjectured hardness of the (computational or decisional) Diffie-Hellman problem. But it is unknown whether either of these problems is equivalent to the ...


3

This is not correct. It could be not binding since you can open a commitment into two options. You can quite easily construct such a scheme artificially. For example, take any perfectly binding scheme $C_b$ and any perfectly hiding scheme $C_h$. Then, commit to a message $m$ by committing to $C_b(m)||C_h(0)$ or by committing to $C_b(\overline{m})||C_h(1)$. ...


3

The immediately obvious solution would be this simple cut-and-choose protocol: Prover: selects a random value $v$ and sends the value $y = v^\ell$ Verifier: selects and sends a random bit $b$ Prover: if $b=0$, sends the value $t_0=v$. If $b=1$, sends the value $t_1=vu$ Verifier: if $b=0$, then verify that $t_0^\ell = y$. If $b=1$, then verify that $t_1^\...


3

The claim is completely false. The security of DDH over appropriate composite-order elliptic curves is not only believed to hold, the assumption that it holds has been widely used in cryptography. To give a single famous example, the BGN cryptosystem was initially defined over composite-order elliptic curves (with a pairing), before being generalized a few ...


3

This problem is equivalent to the Computational Diffie Hellman problem; this remains true even if we know $u$. See this paper for details; in summary: Suppose we have an oracle that, given $G$, $X = xG$ and either (depending on the oracle type) $U = uG$ or $u$, gives us the value $J = x^{-1}uG$. Then, we can use this Oracle to construct a second Oracle ...


2

The linked paper is not about Elliptic Curves which relies on additive groups. It is about the multiplicative groups. For both of them the discrete logarithm is defined. There are common notations that confuse people about them. In the multiplicative version, the division is actually not a division like in the reals. It is the inverse in the group and ...


2

Firstly, the phi-hiding assumption [CMS,KK] states that it is computationally-hard to distinguish the cases $(e,\phi(N))=1$ (where $(\cdot,\cdot)$ denotes the GCD) and $e|\phi(N)$ for a given RSA modulus $N$ and "small" prime $e>2$ ($e\ll N^{1/4}$, to be precise). In the former case, the exponentiation map $x\mapsto x^e\bmod{N}$ is injective (i....


2

No, it is not possible. To think that it would be possible is surely to make a category error. Mining Bitcoin is not an issue of finding the shortest possible route between successful mining events, nor, by the way, is it encryption (strictly speaking). There is a common feature, of course, between the TSP and Bitcoin mining: the need to save time. But a ...


1

Write $A = [A_1 ~~ A_2]$ with $A_1 \in \mathbb{Z}_q^{n\times m'}$ and $A_2 \in \mathbb{Z}_q^{n\times (m-m')}$. Likewise, $e = (e_1 ~~ e_2)$ with $e_1 \in \mathbb{Z}_q^{m'}$ and $e_2 \in \mathbb{Z}_q^{m-m'}$. Then, $$Ae = 0 \bmod q \iff A_2e_2 = -A_1e_1 \bmod q.$$ So, given an instance of SIS, that is, an $n\times m$ matrix $A$, if you have an oracle to solve ...


1

One area that tries to address such questions is fine-grained cryptography [DVV]. Here the working assumption is that the protocols should be secure "against adversaries with an a-priori bounded polynomial amount of resources but the honest algorithm requires less resources than the adversaries they are designed to fool". A classical example of such a ...


1

"Deep coins" protocol by Guillou and Quisquater: https://link.springer.com/content/pdf/10.1007/3-540-45961-8_11.pdf


1

In the $(\gamma, \eta, \rho)$-AGCD problem, all the samples are of the form $$x_i := pq_i + r_i$$ for $q_i$ uniform from $[0, 2^\gamma / p [ ~ \cap \mathbb Z$; $r_i$ uniform from $]-2^\rho, 2^\rho [ ~ \cap \mathbb Z$; and $p$ a fixed random prime of $\eta$ bits. This problem is believed to be quantum secure. See, for instance, this paper published in PKC ...


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