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 ...
- 47.9k
21
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.5k
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(...
- 5,773
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 ...
- 145k
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,203
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 ...
- 47.9k
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^...
- 145k
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.
- 145k
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 ...
- 271
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 ...
- 27.6k
8
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 ...
- 19.1k
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\...
- 558
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) ...
- 145k
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 ...
- 721
7
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 ...
- 19.1k
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. ...
- 27.6k
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
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 ...
- 12k
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.7k
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 ...
- 5,133
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.
...
- 19.1k
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 ...
- 145k
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,148
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 ...
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 ...
- 12.4k
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 ...
- 47.9k
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 ...
- 11.7k
Only top scored, non community-wiki answers of a minimum length are eligible