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
1 vote
0 answers
41 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 ...
user avatar
  • 448
1 vote
1 answer
165 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 ...
user avatar
  • 1,482
1 vote
1 answer
91 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 ...
user avatar
  • 454
6 votes
1 answer
1k 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 ...
user avatar
  • 217
2 votes
1 answer
82 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 ...
user avatar
  • 35
0 votes
0 answers
42 views

Is the kind of definition and analysis of hardness of a problem, using "experiment", standard to complexity analysis of problems?

In Katz's Introduction to Modern Cryptography, there are several hard problems, and for each problem, there is an experiment, where an algorithm generates a problem instance, and another algorithm ...
user avatar
  • 151
1 vote
2 answers
23 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 ...
user avatar
  • 23
1 vote
2 answers
161 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 ...
user avatar
  • 23
3 votes
2 answers
67 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 ...
user avatar
1 vote
1 answer
59 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 ...
user avatar
  • 45
3 votes
1 answer
84 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 ...
user avatar
  • 45
1 vote
2 answers
67 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$ ...
user avatar
0 votes
1 answer
71 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 ...
user avatar
1 vote
1 answer
65 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 ...
user avatar
  • 1,532
2 votes
1 answer
82 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{...
user avatar
1 vote
1 answer
78 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 ...
user avatar
  • 461
1 vote
0 answers
65 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^...
user avatar
1 vote
2 answers
106 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 ...
user avatar
2 votes
1 answer
96 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 ...
user avatar
  • 10.4k
4 votes
1 answer
105 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 ...
user avatar
1 vote
1 answer
294 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?
user avatar
1 vote
1 answer
43 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 ...
user avatar
0 votes
0 answers
27 views

Group Signature by Camenisch and Stadler

Page 8, Paper: "Efficient Group Signature Schemes for Large Groups" by Camenisch and Stadler (1) I was trying to understand membership certificate part. I am have only basic knowledge of ...
user avatar
  • 141
3 votes
1 answer
84 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 $...
user avatar
0 votes
0 answers
51 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?
user avatar
  • 217
1 vote
1 answer
92 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{ ...
user avatar
3 votes
0 answers
109 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://...
user avatar
  • 113
1 vote
1 answer
91 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 ...
user avatar
  • 113
0 votes
1 answer
84 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.
user avatar
  • 345
2 votes
0 answers
69 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 ...
user avatar
  • 113
1 vote
0 answers
79 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 ...
user avatar
  • 11
2 votes
1 answer
173 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.
user avatar
  • 2,183
2 votes
1 answer
55 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 ...
user avatar
  • 349
0 votes
1 answer
59 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 ...
user avatar
2 votes
1 answer
50 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}\...
user avatar
0 votes
1 answer
58 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 ...
user avatar
  • 413
3 votes
3 answers
205 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 ...
user avatar
  • 565
4 votes
1 answer
139 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 ...
user avatar
5 votes
2 answers
178 views

Is this problem with anti-circulant matrices hard?

If there is an obvious way to solve this problem, please give it a chance before downvoting, I beg you. Also, some insight into the resultant asymmetric cryptosystem will be welcomed (described in the ...
user avatar
  • 565
1 vote
0 answers
33 views

what is the probability for an adversary to find the new key after adding new entropy in a group where computational diffie hellman is hard?

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 \{...
user avatar
  • 413
1 vote
0 answers
47 views

How hard will it be to solve an equation in elliptic curve group/ cyclic group where Discrete Logarithm is hard?

Given an Elliptic curve group $E(\mathbb{F}_q)$ where the Discrete Logarithm Problem (DLP) is hard and a base point $G \in E(\mathbb{F}_q)$ with large prime order $n$, what will be the advantage of a ...
user avatar
  • 413
1 vote
1 answer
86 views

Algebraic Variants of NTRU

There are a large number of algebraic NTRU variants: for example, in some (such as ETRU), the underlying ring has been changed to the ring of integers of a certain number field; there is GR-NTRU, ...
user avatar
  • 349
0 votes
1 answer
104 views

CSIDH Squaring Fixing the Base Curve

Consider the following variants of the CSIDH squaring problem. P1. Given $sE, E$ where $s$ is a random ideal class and $E$ is a random curve (reachable from initial $E_0$), find $s^2E$ P2. Given $sE_0$...
user avatar
0 votes
0 answers
94 views

Is inverse polynomial in a finite field NP hard?

In ECC we have: if we know $G$ and $P=kG$, it is very difficult to find $k$. I wonder whether or not in NTRUEncrypt: if we know $h$ and $P=rh$, it is difficult to find $r$?
user avatar
2 votes
1 answer
226 views

The equivalence of SIS and ISIS(Inhomogeneous SIS)

I would like to know whether these two problems are equivalent or not, namely: $SIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}$ find $ e \in \mathbb{Z}_q^{m}$ such that $ Ae = 0$ and and $\|e\| \...
user avatar
1 vote
0 answers
75 views

Solving RLWE modulo a prime ideal

Suppose you have the following set up for RLWE: $K$ is a cyclotomic field of degree $n$ over $\mathbb{Q}$, and $p\in\mathbb{Z}$ is a prime integer that splits as follows in $R = \mathcal{O}_K$: $p\...
user avatar
  • 349
3 votes
0 answers
98 views

Strong Diffie-Hellman Problem

While reading the following paper about the Strong Diffie-Hellman Problem, i got curious about ways to compute $ g^{x^{l}} $ for unknown $x$ in an elliptic curve, without first solving the discrete ...
user avatar
  • 31
4 votes
1 answer
151 views

Are there any public-key encryption schemes based on DLog?

There are public-key encryption schemes based on many different mathematical hardness assumptions, like the hardness of Decisional Diffie-Hellman problem, the hardness of the Factoring problem, the ...
user avatar
0 votes
0 answers
83 views

What one-way functions are there based on the Diffie-Hellman problem?

Mathematical hardness assumptions like that of the factoring problem, the RSA problem, and the discrete log problem all straightforwardly lead to one-way functions. But what about the computational ...
user avatar
3 votes
1 answer
82 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 ...
user avatar
  • 31