33 votes
Accepted

What are standard cryptographic assumptions?

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 ...
user avatar
18 votes

Can you give me a summary of cryptographic hardness assumptions?

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 ...
user avatar
  • 19.2k
15 votes
Accepted

Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

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(...
user avatar
15 votes
Accepted

Why is the discrete logarithm problem hard?

Now, I wonder if there are any better arguments. Ultimately, no, not really. We don't have any proof that computing discrete logs is hard. For that matter, we don't have any proof that any problem ...
user avatar
  • 133k
13 votes

Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

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 ...
user avatar
  • 1,119
13 votes
Accepted

Academic breach revealed too late

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 ...
user avatar
12 votes
Accepted

What is a q-type assumption?

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 ...
user avatar
  • 12.1k
10 votes
Accepted

Nash cryptosystem

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 ...
user avatar
  • 1,187
10 votes
Accepted

Extracting $ x $ given $ g^x, g^{x + y}, y $

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^...
user avatar
  • 133k
9 votes
Accepted

Global minimum based cryptography?

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.
user avatar
  • 133k
9 votes
Accepted

Is the one-more discrete log problem hard in the Generic Group Model?

More recent work by Bauer et al. [BFP] claims that the proof in a previous answer is flawed (and that Coretti et al. confirmed this). However, Bauer et al. prove hardness of OMDL in the GGM. They show ...
user avatar
  • 206
8 votes
Accepted

About random self-reducibility of DDH

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 ...
user avatar
7 votes

How hard is Self-DLOG?

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\...
user avatar
7 votes

What are standard cryptographic assumptions?

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 ...
user avatar
7 votes

What is this problem called and is it hard? given $g^x$ output ($g^y, xy$)

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) ...
user avatar
  • 133k
7 votes

Error-correcting Code VS Lattice-based Crypto

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 ...
user avatar
  • 691
7 votes
Accepted

Weak Decisional Diffie-Hellman Problem

Yes it is. It can be formally reduced to the hardness of the decisional square Diffie-Hellman assumption, which states that distinguishing $(g,g^a,g^{a^2})$ from random is hard (this is a well ...
user avatar
6 votes
Accepted

Security of a signature scheme based on both factoring and discrete logarithms

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 ...
user avatar
  • 133k
6 votes
Accepted

How to estimate the hardness of SIS instances?

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$...
user avatar
  • 199
6 votes

How hard is Self-DLOG?

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. ...
user avatar
6 votes
Accepted

Are there post-quantum cryptosystems with a gap between classical and quantum security?

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 ...
user avatar
  • 11.2k
6 votes

Academic breach revealed too late

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 ...
user avatar
  • 10.6k
6 votes

Is the one-more discrete log problem hard in the Generic Group Model?

Yes, this was shown in a recent work of Coretti et al [CDG]. Loosely speaking, the lower bound states that an adversary that makes at most $T$ queries to the GGM oracle succeeds with probability at ...
user avatar
  • 4,503
6 votes
Accepted

MLWE (and RLWE) to LWE reductions proof

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 ...
user avatar
5 votes

How to prove hardness of approximate-GCD problem?

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 ...
user avatar
  • 133k
5 votes

Is this secure?

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 ...
user avatar
  • 4,038
5 votes

How is the matrix A related to the lattice space L in SIS?

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 ...
user avatar
5 votes
Accepted

Hardness of LPN problem with small secret

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 ...
user avatar
  • 11.7k
5 votes

Academic breach revealed too late

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 ...
user avatar
5 votes
Accepted

Error-correcting Code VS Lattice-based Crypto

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. (...
user avatar
  • 1,092

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