# Questions tagged [hardness-assumptions]

Mathematical problems that are thought to be difficult to solve for all cases in polynomial time

160 questions
Filter by
Sorted by
Tagged with
66 views

### What does the "static" assumption mean?

We can prove the security of a cryptographic scheme in standard model and non-standard model. Standard models like using some computational assumptions, on the other hand, non-standard models like ...
66 views

### Special indistinguishability problem

I need some help for the following simple game: An adversary is given a multiplicative group $\mathbb{G}$ and the 4-tuple $(g_1, g_2, g_3, g_1^a \cdot g_2^b \cdot g_3^c)$ where $g_1$, $g_2$ and $g_3$ ...
49 views

### (type-3) Variant of the decisional Diffie-Hellman

At a high level, the Uber assumption states that it is not possible to compute (distinguish) linearly independent elements. In the decisional version, the problem is restricted to $G_T$, but it is ...
385 views

### Average- and worst-case complexity

The terms "average-case", "worst-case" hardness are quite confusing. What do they mean when they say certain problems (like lattices) have an average-case to worst-case ...
90 views

### Given two unrelated generators $G_1$ and $G_2$, and a third with $H = G_1 + G_2$. Is it hard to compute $xG_1$ from $xH$?

Given some group in which both discrete logarithms and the computational Diffie-Hellman problem are hard. Furthermore, two random, unrelated group generators $G_1, G_2$, and a third generator defined ...
499 views

### What's wrong with this simple reduction of discrete logarithms to the Diffie-Hellman problem?

This recent paper shows that discrete logarithms are solvable if you have an oracle for the Diffie–Hellman problem. However, to me, it seems there is a much simpler reduction and I wonder where I am ...
1 vote
73 views

### Is the composite order matrix-DDH secure?

I recently read a paper that proposed a matrix-DDH which is a matrix variant of DDH assumption. The brief definition is follows: Let $G$ be a group of prime order $q$. Then, the matrix-DDH says that ...
1 vote
37 views

### Variant of Decisional Diffie Hellman

Given a cryptographic prime $p$ and a generator $g$ of $\mathbb{F}_p$, the Decisional Diffie Hellman problem asks us to distinguish $(g^a, g^b, g^{ab})$ from $(g^a, g^b, g^z)$ for random $a, b, z$. ...
1 vote
71 views

### Hardness of a modified version of NTRU

Let the modified NTRU be $h=f/g$ such that $f$ is not necessarily a short polynomial, is the NTRU problem still hard in this case?
49 views

### A random access machine with lots of random data on its tape is a stronger assumption than the existence of OWFs

Suppose we have a random access machine with $(n+1)2^n$ random bits on its tape. This assumption is weaker than assuming the existence of a random oracle, but using this assumption we can construct a ...
1 vote
76 views

### Two LWE samples with the same secret

I am considering the following problem related to Learning with Errors. Recall that the LWE assumption is that no adversary can distinguish $(A,As+e)$ from $(A,u)$ with non-negligible advantage, where ...
1 vote
81 views

### When does the need of random data become an assumption?

Suppose an encrypion scheme uses a random string to encrypt and decrypt, which is publicly available, such as an IV or nonce. In all the cases I am aware of, the existence of say an IV is not "...
1 vote
44 views

### Proving stategies for computational properties

As far as I understand, a property is computational if it holds in a computationally-bounded context, so for ANY computationally-bounded involved entity (even if an unbounded one could discover the ...
1 vote
232 views

### Models and assumptions in the post quantum world

I'm currently trying to get an overview of post-quantum cryptography. Now I'm struggling with correlations and adjustments of the PQ-world and the Modern-world of cryptography. My Questions: Can you ...
1 vote
141 views

### What kind of assumptions usually go into the design of block ciphers?

What are some standard assumptions made in showing the security of a block cipher? For example, is it commonly assumed that $P\not=NP$? To this end, are there any block ciphers whose security does ...
2k views

### Why is the discrete logarithm problem hard?

Why is the discrete logarithm problem assumed to be hard? Someone else asked the same question but the answers only explain that exponentiation is in $O(\log(n))$ while the fastest known algorithms to ...
158 views

### Breaking CDH also breaks DHI

I am trying to show that by breaking the Computational Diffie-Hellmann (CDH) assumption one also breaks the Diffie-Hellmann inverse assumption. Unfortunately, I am a bit stuck and do not know where to ...
1 vote
47 views

### Definition of Multilin DDH

I am on the abbreviation mutlin. DDH, which probably stands for mutliniear Decision Diffie Hellmann. I am currently looking for a definition for this term, but unfortunately cannot find a source. Can ...
1 vote
418 views

### Definition of the strong Diffie Hellman problem

I am looking for the definition of the strong Diffie Hellmann problem. However, I can only find definitions for the $\ell$ or $q$-strong Diffie Hellmann. Is it possible that the strong Diffie Hellman ...
205 views

### LWE with the matrix A repeated

Consider the following version of Learning With Errors. You are either given $(A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k)$ or $(A, u_1, u_2, \ldots, u_k)$, where $A$ is an $m \times n$ matrix ...
1 vote
79 views

### Can Shor's algorithm factor over finite fields/rings/groups?

Shor's algorithm can (efficiently) solve equations of the form: $$n = pq$$ and $$n = x^{2} + y^{2}$$ This question is simple: Can Shor's algorithm solve these equations in polynomial time when they ...
133 views

### Can Shor's algorithm factor over the gaussian integers?

This is related to this question about solving the following expression: $$x^{2} + y^{2}$$ This can be factored over the gaussian integers as $$(x + iy)(x - iy)$$ If one could factor a sum of two ...
1 vote
315 views

### Why RLWE is lighter than LWE and why we can pick $a_i$ as a permutation of $a_1$ in RLWE but not LWE?

In LWE, we have $$<a_1,s> + e + \mu_1\in \mathbb{Z}_q$$ for a secret key $s\in \{0,1\}^n$ and $a_1\in \mathbb{Z}_q^n$ This is an encryption of a number $\mu_1$. If we want to encrypt $n$ ...
132 views

### What does hard instance mean in cryptography?

I'm learning cryptography recently. I read that for game-based formal security analysis, it is important to embed the hard instance during reduction. Does "hard instance" mean hard-to-solve ...
1 vote
73 views

### The existence of OWFs vs $\mathbf{EXP} \neq \mathbf{BPP}$

In CRYPTO 2021, Liu and Pass published a paper with title "On the Possibility of Basing Cryptography on $\mathbf{EXP} \neq \mathbf{BPP}$. One of the main results of this work can be interpreted ...
178 views

### LWE and extended trapdoor claw free functions

Let $q \geq 2$ be a prime integer. Consider two functions, given by: $$f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q),$$ $$g(b, x) = Ax + b \cdot (As + e') + e~~~(\text{mod}~q),$$ where we have: \begin{...
1 vote
122 views

### Hardness of a variant of the CDH problem

Given $g$, a generator of a multiplicative group (over some finite field or elliptic curve), and the group elements $\left( g^x, g^a, g^b, g^c, g^{x(a+b)}, g^{x(b+c)} \right)$, is possible to ...
1 vote
72 views

105 views

### Does breaking CDH also break DLP? [duplicate]

Does breaking the computational Diffie-Hellman problem in a group also always break discrete logarithms in that group?
1 vote
175 views

Let $G$ be a finite group of prime order $p$, and $g$ a generator of $G$. The standard DDH is hard to distinguish two distributions $$\{ (g, g^a, g^b, g^{ab}) : a, b \leftarrow \mathbb{Z}_p\} \text{ ... 3 votes 0 answers 220 views ### Decisional Diffie-Hellman Assumption over Group of Quadratic Residue Consider the Decision Diffie-Hellman (DDH) over QR_n (the quadratic residue group over n=pq where p and q are safe primes).According to Boneh's paper, DDH should be hard over QR_n (https://... 1 vote 1 answer 199 views ### Linking Decisional Diffie-Hellman, Discrete Logarithm, and Knowledge of Exponent Assumptions I'm curious about the relation between the Discrete Logarithm and Decisional Diffie-Hellman. Is it safe to have an assumption like the following to link the two? Given uniformly and independently ... 0 votes 1 answer 415 views ### Small modulus to noise ration in LWE implies better security I don't quite understand why a smaller quotient between modulus q and the noise's standard deviation implies better security against known attacks. 2 votes 0 answers 92 views ### Group of quadratic residue over Blum integer Let x be a random element from QR_n, the quadratic residue group over Blum integer n (where n=p*q and p and q are safe primes), and g a generator of QR_n. Are the following ... 1 vote 0 answers 175 views ### Is there any relation between Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption? We have DCRA and ECSQRT assumptions. ECSQRT: Square roots in elliptic curve groups over Z/nZ Definition: Let E(Z/nZ) be the elliptic curve group over Z/nZ. Given a point Q ∈ E(Z/nZ). Compute all ... 2 votes 1 answer 422 views ### Gap between DLog and CDH Is there any concrete group in which one CDH is exponentially easier (even it's still hard) than DLog. 2 votes 1 answer 76 views ### Choosing rings for PLWE In [ELOS15], the authors give an attack on RLWE, and claim that "the hardness of Ring-LWE is... dependent on special properties of the number field" chosen; whereas, responding to prior ... 0 votes 1 answer 95 views ### Hard instances of matrix factorization Are there any hard problems related to matrix factorization? Suppose E is hermitian with public eigenvectors such that U^T\Lambda U = E with U public but E,\Lambda secret. Given X secret, we ... 2 votes 1 answer 64 views ### Hard Problems in Pairings I want to know whether the following problem is considered as a hard problem in complexity theory or not? Given g,g^a,g^b \in G_1 (for unknown a,b\in \mathbb{Z}_p^{\ast}), compute e(g,g)^{ab^2}\... 0 votes 1 answer 62 views ### Is this an instance of a Diffie-Hellman problem? Let \mathbb{G} be a cyclic group of order p with generator g, and let m\in\mathbb{G}. Problem: Given c=m.g^{k.a} and v=g^a, where k,a \in \mathbb{Z}^*_p, output k. Is this an instance ... 3 votes 3 answers 268 views ### Is this asymmetric (public key) cryptosystem based on a 16x16 s-table safe and useful? May be this is absolutely off-topic, but here is. The cryptosystem description follows. Any hints of what to do with it, or flaws found are welcomed. This description is here as well. We will use a ... 4 votes 1 answer 248 views ### Weak Decisional Diffie-Hellman Problem Is this problem still hard? Given$$(g,g^a,g^b,c) decide if $c=a\cdot b$? If there is an adversary that solves the standard Decisional Diffie-Hellman Problem then it can solve my new problem. But I ...
Let's say I have an Elliptic curve group $E(\mathbb{F}_q)$ with base Point $G$ and large prime order $n$. Computational Diffie-Hellman is assumed to be hard in that group. \$H: \{0,1\}^*\rightarrow \{...