# Tag Info

## Hot answers tagged hardness-assumptions

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 ...

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 ...

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"  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

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 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

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

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

No, this problem is not hard. Here is algebraic reformulation which leads to efficient key recovery. Ring representation Let $R = \mathbb{F}_p[X]/(X^4-1)$. We identify any $a \in S$ with an element of $R$ as follows: $$R(a) = a_0 + a_1X+a_2X^2+a_3X^3.$$ From now on assume that we work with elements of $R$. Let $rev$ denote the polynomial reciprocal ...

2

First, I've attempted to create a similar but quadratic sbox over $\mathbb{Z}_{17}$, and found that all non-trivial candidates are linear. While I'm not yet able to find a proof that all functions meeting the "restricted-commutative" requirement are all isomorphically linear, I think it may have some serious implication on the security of your ...

2

Your mixing function is an isomorphism of some group that's representable using matrices, and it's generally not difficult to find inverses of matrices (even ones with the determinant value 0) unless the dimension is too high. It took months for my hair to re-grow after this. For example, the permutation representation of the 0'th row $p(x) = f(0,x)$ can be ...

2

There is a generalisation of the Diffie-Hellman problem to multi-linear groups known as the multi-linear Diffie-Hellman problem (MDHP, see this paper for example). Specifically, for a group $G_1$ endowed with an $n$-multi-linear map $e$ to a group $G_2$ the MDHP is: given $g, g^{a_1}, g^{a_2},\ldots, g^{a_{n+1}}\in G_1$ compute $e(g,g,\ldots,g)^{a_1a_2\cdots ... 2 The paper The Relationship between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms contains some results of interest, although they are somewhat technical. Specifically, it needs: Smoothness Assumption: For$n\in\mathbb{N}$, define$\nu(n)$to be the minimum, over$d\in [n-2\sqrt{n}+1, n+2\sqrt{n}+1]$of the largest prime factor of$d$... 1 Section 4 of [P16] is perhaps the key section to read. I quote it below: We stress that all these insecure instantiations—excepting [EHL14], for which the following conclusions still apply—are for the “non-dual” version of Ring-LWE with spherical Gaussian errors relative to$R$(in the canonical embedding). By contrast, the definition of Ring-LWE from [... 1 This is not related to your particular factorization problem (I believe), but is related to a hard matrix factorization problem (I believe). It is known as the "Lattice Isometry Problem" (or perhaps it is the "Lattice isomorphism problem" --- I will call it LIP either way). Stated in matrix terms, this problem is, given two matrices$\...

1

As stated the problem is insoluble as zero-knowledge of $k$ is provided (unless we know something about $m$). To see this, let $x$ be any integer $0\le x\le p-1$ and let $m':= m\cdot v^{-x}$ then we see that $c=m'\cdot g^{(k+x)a}$ and we see that $k+x\pmod p$ is an equally valid output unless we have some reason to choose $m$ over $m'$.

1

$f$ is defined using matrix multiplication, which is associative, as $f(A,B)=MAB$. Matrix $M$ is anti-circulant, with $MM$ the identity. For all anti-circulant 4×4 matrices $A$, $B$, $C$, it holds $ABC=CBA$, and that's an anti-circulant matrix. This explains $f(f(A,B),f(C,D))=MMABMCD=MMACMBD=f(f(A,C),f(B,D))$. Now, the question's $s_i$ becomes $$\begin{array}... 1 If one expands the discussion to include LWE-type schemes, isn't Module-LWE naturally a "non-commutative" hardness assumption which has practical applications? For example, the Kyber NIST PQC candidate is an MLWE scheme, and is a round 3 finalist. In general though, I mostly see lattices over "exotic" (at least more so than things like ... 1 If you have a solver for P1, then it can also solve P2, so the problems are comparable: P2 is easier. P1 is assumed hard, and is used as the basis of, e.g. https://eprint.iacr.org/2020/1012. P1 is known to be generically equivalent to P3 (see https://hal.archives-ouvertes.fr/hal-02373179 and https://eprint.iacr.org/2020/1012), however P2 is probably not ... 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

Just to add another quick answer, but one can add "Mersenne Prime"-based crypto to this list, which was initially concieved as a variant of lattice-based crypto where one does "big-int" arithmetic rather than polynomial arithmetic (see this paper). Some authors have tried to formalize the abstract sense in which these are all similar, for ...

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