Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
34 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 ...
Squeamish Ossifrage's user avatar
23 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 ...
Ella Rose's user avatar
  • 19.6k
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(...
Chris Peikert's 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 ...
poncho's user avatar
  • 148k
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 ...
LeoDucas's user avatar
  • 1,253
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 ...
Squeamish Ossifrage's user avatar
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^...
poncho's user avatar
  • 148k
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 ...
deviantfan's user avatar
  • 1,187
9 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 ...
Yehuda Lindell's user avatar
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.
poncho's user avatar
  • 148k
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 ...
nickler's user avatar
  • 271
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 ...
Geoffroy Couteau's user avatar
7 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$...
blowfish's user avatar
  • 209
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\...
Alexey Ustinov's user avatar
7 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 ...
yyyyyyy's user avatar
  • 12.1k
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 ...
Hilder Vitor Lima Pereira's 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) ...
poncho's user avatar
  • 148k
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 ...
pscholl's user avatar
  • 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 ...
Geoffroy Couteau's user avatar
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. ...
Yehuda Lindell's user avatar
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 ...
Meir Maor's user avatar
  • 11.8k
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 ...
ckamath's user avatar
  • 5,248
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. ...
Geoffroy Couteau's 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 ...
poncho's user avatar
  • 148k
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 ...
Changyu Dong's user avatar
  • 4,178
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 ...
Hilder Vitor Lima Pereira's 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 ...
Samuel Neves's user avatar
  • 12.6k
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 ...
Squeamish Ossifrage's 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. (...
Thomas Prest's user avatar
  • 1,080
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 ...
Mark Schultz-Wu's user avatar
  • 13.3k

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