# Tag Info

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

### 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
Accepted

• 139k
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
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
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
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.2k

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

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

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

### 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
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 ...
• 18.2k
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
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

### 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.2k
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

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

### 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
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 ...
• 18.2k
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. ...
• 18.2k

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

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

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

### $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