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 ...
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 ...
  • 19.4k
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(...
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 ...
  • 139k
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 ...
  • 1,149
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 ...
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^...
  • 139k
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 ...
  • 1,187
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.
  • 139k
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 ...
  • 251
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 ...
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\...
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 ...
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) ...
  • 139k
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 ...
  • 701
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 ...
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$...
  • 199
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 ...
  • 139k
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. ...
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 ...
  • 11.9k
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 ...
  • 11.5k
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 ...
  • 4,973
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 ...
6 votes
Accepted

Would being able of factoring integers efficiently have some consequences over Elliptic Curve Cryptography?

This is an interesting, but completely open question. The ability to compute discrete logs in specific well-chosen groups entails the ability to factor, but there is no other known formal relations. ...
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 ...
  • 139k
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 ...
  • 4,098
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 ...
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. (...
  • 1,082
5 votes

$P \ne NP$: a proof relating complexity theory to block ciphers

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 ...
  • 10.5k
5 votes
Accepted

Are there any public-key encryption schemes based on DLog?

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

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