# Tag Info

30

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 $... 29 The problems: The Discrete Logarithm problem: Given$y$, find$x$so that$g^x = y$. The Computational Diffie-Hellman problem: Given$y_1 = g^{x_1}$and$y_2 = g^{x_2}$(but not$x_1$and$x_2$), find$y = g^{x_1·x_2}$. The Decisional Diffie-Hellman problem: Given$y_1, y_2, y_3$, decide if they are of the form$y_1 = g^{x_1}$,$y_2 = g^{x_2}$and$y_3 = g^{...

17

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

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

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

10

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.

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 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, ... 6 It means that if you have an oracle access to CDH, then you can solve DDH, but we do not know if there exists a reduction the other way round. Technically, suppose \mathsf{CDH} is an oracle that finds g^{xy}, given (g^x,g^y), then for a DDH instance, say (a,b,c), you can feed \mathsf{CDH} with (a,b) and output 1 if output of \mathsf{CDH} ... 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 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 ... 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 ... 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 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 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 ... 5 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 ... 4 In addition to Jalaj's correct answer, I also want to dispute one of your statements: "From my understanding, since the Discrete Log(DL) Problem is considered hard, then so is CDH" Actually, that's not the case. Now, if you can solve the DL problem, the CDH problem is easy (and so the CDH problem is no harder than the DL problem). However, there's no ... 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 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 ... 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 ... 3 I want to get a good characterization of the construct so that I may describe it accurately. I would characterize it as "insecure". If someone has a ciphertext, and manages to guess the plaintext it corresponds to, then they can compute:$$\text{gcd}(E_I(M) - M, N) and they'll give then the factor $p$.

3

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(\... 3 Actually, that problem is exactly equivalent to the standard DLOG problem (assuming that you know the group order, and that it is prime). Here's the reduction: suppose that we have an Oracle that can solve your problem with nontrivial probability. Then, given a value$g$and$h$, we can find$x$with$g^x = h$with nontrivial probability by: Create random ... 3 What you present is a generalized version of the so called fixed-argument pairing inversion (FAPI) problem. The FAPI problem is given an element$z\in G_T$and an element$h\in G$to compute$f\in G$such that$e(h,f)=z$. Note, that FAPI is implied by the computational Diffie Hellman problem: Given$(g,g^a,g^b)\in G^3$, call the FAPI oracle with$z\gets e(...

3

In a type-3 group, after an oracle query you get to see $(g_1^a, g_1^{at}, g_1^{as+axst}, g_1^{ax}, g_1^{axt})$ but not $g_1^s$ or $g_1^t$ (those are in $G_2$). Suppose you had a homomorphism $G_2 \to G_1, g_2 \mapsto g_1$ so you could recover $g_1^s$ and $g_1^t$. Call your tuple from the oracle $(A, B, C, D, E)$ and compute \$(Ag_1^r, B(g_1^t)^r, C(g_1^s)^r,...

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