# Tag Info

## Hot answers tagged hardness-assumptions

32

I am struggling to understand what is meant by "standard cryptographic assumption". ‘Standard assumption’ broadly means an assumption that has withstood the scrutiny of many smart cryptanalysts for a long time. Examples: We think that, for uniform random 1024-bit primes $p$ and $q$, solving $y = x^3 \bmod pq$ for uniform random $x$ is hard given $pq$ and $... 18 One of the links in the comments points to this paper, which has a very extensive list of various hardness assumptions used in cryptography. At the end of this post is an addendum that includes problems not found in the mentioned paper. The following is basically the table of contents from the paper: Discrete logarithm problem DLP: discrete logarithm ... 14 The first inequality at the bottom of page 3 of the paper is false. For example, Conway and Thompson proved the existence of "self-dual"$n$-dimensional lattices$L$(i.e.,$L^* = L$) where$\lambda_1(L) = \lambda_1(L^*) = \Omega(\sqrt{n})$, hence$\eta_{2^{-n}}(L) = O(1)$but$\tilde{bl}(L) \geq \lambda_1(L) = \Omega(\sqrt{n})$. The statement and proof of ... 14 In 2004, Xiaoyun Wang's team first publicly reported collisions in MD5, and in 2007, Marc Stevens, Arjen Lenstra, and Benne de Weger reported a chosen-prefix collision attack on MD5. Around the same time, the governments of the United States and Israel developed the the Flame malware to sabotage Iran's nuclear program. Part of the scheme involved forging a ... 13 Independently of the algorithmic claim, I indeed have serious doubts about Theorem 2. Here is a counterargument (using standard techniques) cooked up with Yang Yu and Wessel van Woerden: Suppose that$q$is prime, and suppose that the minimum distance in the 2-norm is indeed bounded by$b=O(1)$. There are at most$Binom[m,b] \cdot (2b+1)^b = poly(m)$... 12 The classic standard assumptions (such as DDH, CDH) are not parametrized and always have constant size (are static). Consequently, the assumption when used in a reductionist proof is independent of any system parameters or oracle queries and only related to the security parameter. In contrast, non-static ($q$-type) assumptions as already mentioned by ... 10 Two things first: Even in 1955, Nash's encryption algorithm (I'll call it NEA) was rejected by the NSA because they deemed it not secure enough. So do not use it in real life. Like eg. AES, NEA is not based on any of the usual hard algorithms like factorization etc. NEA is a symmetric stream cipher, ie. there's just one key for both encrypting and ... 10 Ok, I gave the answer in my comment; however so that you can accept an answer (and so close this question out), I'll repeat my answer here. Yes, it is still hard to find the discrete log, given$g, g^x, g^{x+y}, y$. The reasoning is simple; if that were an easy problem, that is, if we had an oracle that, given$g, g^x, g^{x+y}, y$, recover$x$, we could ... 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. 8 You are absolutely right! The random self-reducibility goes in the other direction, and this variant of the DDH assumption does not follow from it. I have no idea what the author was thinking when he wrote it :-). In any case, the paper has now been updated in ePrint and fixed. Thank you for catching this. I include the proof of this variant here: Consider ... 7 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{\... 7 Differential cryptanalysis In 1990 Eli Biham and Adi Shamir discovered a powerful technique capable of breaking a wide range of ciphers. When they applied it to the DES cipher developed by IBM and the NSA in 1975 it became apparent the designers of DES were aware of this technique. In 1994 this was confirmed. Evidently IBM discovered this in 1974 and was ... 7 There is no formal definition of standard assumption, but we usually say that an assumption is standard if it has already been used in several cryptographic schemes and if it is well-accepted in the crypto community. It usually also implies that several researchers tried to solve the problem and were not able to find efficient ways of doing so, therefore, ... 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 Although I can't see any immediate weaknesses, I also don't see how it adds significant value over DSA (while being significantly slower). It claims to be based on two hard problems, discrete log and factoring. However, it doesn't give any particular proof that if you could forge signatures, you can solve both problems. It also doesn't look particularly ... 6 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 ... 6 Here's an example where the best known quantum attack is, in a sense, just "halfway" between the best known classical attack on one side, and a complete break on the other: Inverting a cryptographic group action such as CSIDH. Let G be a (finite) commutative group G acting on a set X, i.e., we consider a map$$ \ast\colon\; G\times X\to X$$that is ... 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 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(\... 5 I am stuck at the point where I proved that the complexity is O(2^\rho) using brute-force approach. How shall I proceed? Well, a proof that assumed a specific attack strategy is of limited use, as that proof would be inapplicable if the attacker used some other strategy. Instead, what we typically do in a proof is assume that the adversary had some ... 5 No this is not CPA secure. You can compute \bar{c}=\frac{c_1c_2c_3c_4}{c0}, and \bar{c} is deterministic with regard to m, which is \frac{(a_1y_1+a_2y_2)^2(a_1y_1’+a_2y_2’)^2}{m}. The adversary can easily distinguish ciphertexts of m_0,m_1 by querying m_1 first, then sends m_0,m_1 to the oracle, and outputs 1 if \bar{c} from the returned ... 5 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 first$...

5

There is a simple trick (known in the LWE literature as the Hermite normal form of the problem) that takes an existing LPN problem and transforms it into a problem in which the secret has the same Bernoulli distribution as the error. This trick is proved in Lemma 2 of Applebaum et al. for a more general case, or on the (Ring-)LPN attacks of Kirchner (Section ...

5

In the early 2000s, Certicom and/or NSA developed Dual_EC_DRBG, a pseudorandom number generator built out of public-key elliptic-curve cryptography—which these days ‘everyone’ knows means built with a back door (after all, that's what a private key is!). At the time, however, elliptic-curve cryptography had a certain mystique around it, and many people fell ...

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

Is DDH hard in the subgroup of order $2q$ of $\mathbb{Z}_p^*$ No, it is not. If you define the function $F(x) = x^{q} \bmod p$, then for any $x$ is\n the group of order $2q$, we have $F(x)= 1$ if $x$ is a member of the proper subgroup of order $q$, and $-1$ if it is not. And, exactly half of the elements will be in that subgroup. You will always have an ...

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

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

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