Questions tagged [hardness-assumptions]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
148 views

Is the discrete root considered a hard problem?

I know that in groups from large prime order the discrete log problem is considered hard. For example, it is hard to compute $x$ from $g^x$ and $g$. Does the same holds for the root problem? For ...
3 votes
1 answer
668 views

KEA assumption details

In order to understand the construction of a zK-SNARK, I have recently been trying to understand the KEA1 assumption in The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols by ...
1 vote
1 answer
76 views

cryptographic assumptions with bilinear pairings

Hi I have two statements which I think are correct: $\beta, s$ are unknown. Only $g^\beta$ is known to the prover but not any of $g^{\beta s^i}$ for $i \ge 1$. If the prover is able to find group ...
0 votes
0 answers
51 views

Inquiries on Strong Diffie-Hellman assumption

According to the SDH assumption, it is hard for an adversary to output a pair $(c,g_1^{\frac{1}{c+\alpha}})$ given a $q+2$ tuple ($g_1$,$g_2$,$g_2^{\alpha}$, ...,$g_2^{{\alpha}^q}$) Now, consider $g_1$...
5 votes
2 answers
574 views

What is the notion of an interactive assumption?

In this paper: Sequential Aggregate Signatures with Short Public Keys: Design, Analysis and Implementation Studies the authors sell the paper as the first who propose Aggregate signatures without ...
2 votes
1 answer
53 views

Learning the LWE secret with advice

I am trying to argue about the hardness of LWE, but in a setting that is different from the standard one. Consider the task of learning the LWE secret $s$ from noisy samples. The specifications of the ...
1 vote
2 answers
503 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 ...
4 votes
1 answer
85 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 ...
0 votes
1 answer
69 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$ ...
4 votes
4 answers
462 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 ...
0 votes
1 answer
53 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 ...
10 votes
0 answers
149 views

Hardness of iterated squaring in Paillier group

The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $\leftarrow$ denotes sampling uniformly at random: Input: $(N,x,T)$, where $N$ is the RSA modulus, $...
2 votes
1 answer
93 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 ...
6 votes
1 answer
537 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
0 answers
79 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
0 answers
40 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
1 answer
75 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?
2 votes
1 answer
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
0 answers
143 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 ...
1 vote
2 answers
352 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$ ...
1 vote
0 answers
84 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
1 answer
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
0 answers
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
1 answer
241 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 ...
5 votes
4 answers
467 views

Reductionist proofs of computational problems to decisional

Are they any reductionist proofs where an attacker $\mathcal{I}$ for a well established computationally "hard" problem $\mathsf{Π}$ is employing an attacker $\mathcal{A}$ who we assume is able to ...
6 votes
1 answer
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 ...
2 votes
1 answer
185 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
2 answers
48 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 ...
3 votes
2 answers
248 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
1 answer
83 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 ...
3 votes
1 answer
136 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 ...
0 votes
1 answer
141 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
1 answer
74 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 ...
1 vote
1 answer
195 views

The security of DDH with multiple instances?

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{ ...
2 votes
1 answer
197 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
1 answer
135 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
0 answers
74 views

Which of the following is considered cryptographically hard/easy?

Which of the following are easy, if any? Which are hard? and why. Case 1) Given $x^3 \bmod N$, where $N$ is a composite number and we don't know any of the factors of $N$, find $x$. Case 2) Given $x^...
1 vote
2 answers
187 views

What are security reductions of symmetric-key algorithms?

I was reading Wikipedia page of post-quantum cryptography. It says that it is desirable for cryptographic algorithms to be reducible to some particular mathematical problem, that is intractability of ...
4 votes
1 answer
268 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 ...
2 votes
1 answer
384 views

Solve DLOG using a probabilistic algorithm for DLOG lsb

Following the question Can I know from a Bitcoin public key if the private key is odd or even? The answer there gives a simple algorithm for solving the Discrete Logarithm Problem when given an oracle ...
4 votes
1 answer
123 views

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

Let's assume you can factor integers in a very efficient manner. Would that endanger the security of e.g. elliptic curve cryptography, or is there no link between the two ? You can often read that ...
6 votes
3 answers
415 views

Decrypting small integers under RSA

Let $(n,e)$ be an RSA public key. Suppose $c = m^e \pmod n$, where $c>1$ is a very small integer. For concreteness, say $c=2$ and that $e = 65537$. Is it hard to find $m$ under the RSA assumption (...
2 votes
4 answers
2k views

Variant of the Decisional Bilinear Diffie Hellman problem

I am working on a cryptographic scheme and I need to rely on the following problem, which I have nicknamed the "Hybrid Decisional Bilinear Diffie Hellman (hDBDH)" problem: Let $e: \mathbb G_1 \...
1 vote
1 answer
417 views

DDH to DLIN reduction

I read multiple times that it should be feasible to show a reductions from Decisional Diffie Hellmann. Could you give examples?
1 vote
1 answer
79 views

Developments in ABE using Pairings

What are the recent developments in Attribute-Based Encryption (ABE) using Pairings assumptions? Is pairings the most viable assumption while designing ABE. What other assumptions are used for ABE ...
3 votes
1 answer
218 views

Strong Diffie Hellman in bilinear groups

The $n$-strong Diffie Hellman assumption state that given the subset $\{g, g^s,\cdots,g^{s^n}\} \subseteq \mathbb{G}$ in a cyclic group $\mathbb{G}$ of prime order $p$, a PPT algorithm cannot output $...
0 votes
0 answers
110 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?
3 votes
1 answer
550 views

Proof by reduction definition in "Serious Cryptography": Cipher reduced to hardness problem or other way around?

In Serious Cryptography by Jean-Philippe Aumasson on p. 46, paragraph "Provable Security", it says: Provable security is about proving that breaking your crypto scheme is at least as hard as ...
3 votes
1 answer
94 views

Boneh DDH Paper - Sampling Integers in Random Reduction

I've been reading Dan Boneh's DDH paper, in particular section 3.1 which covers DDH randomized reduction. The first two sentences of theorem 3.1 state: Let $\Bbb G = \{G_p\}$ be a family of finite ...
2 votes
0 answers
96 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 ...