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
0answers
23 views

If they exist a relation between decisional Diffie-Hellman assumption and composite decisional residuosity assumption

From the cryptographic hardness assumptions, we have DDH and CDR assumptions. It is known that the composite decisional residuosity assumption is related to a factoring problem, while the DDH is ...
2
votes
1answer
113 views

Is this problem based on discrete polynomials modulo $(x^3-1)$ strong?

We start working with the Ring $R=\left(\mathbb{Z}/p\mathbb{Z}\right)\left[x\right]/\left(x^{3}-1\right)$, $p$ prime, i.e. degree two polynomials with coefficients modulo $p$ modulo $x^{3}-1$. As $x^{...
0
votes
0answers
21 views

What is the current state of the Conjugacy Search Problem in Matrix and Permutation Groups?

It results that I have come with a mathematical approach to solve the CSP (Conjugacy Search Problem) where the platform group $G$ is either a permutation group or a Matrix Group. From my part I ...
13
votes
4answers
8k views

What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?

How are the three problems Discrete Logarithm, Computational Diffie-Hellman and Decisional Diffie-Hellman related? From my understanding, since the Discrete Log (DL) Problem is considered hard, then ...
26
votes
2answers
3k views

What are standard cryptographic assumptions?

I am struggling to understand what is meant by "standard cryptographic assumption". The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first ...
2
votes
4answers
317 views

Academic breach revealed too late

Do you know if is has already happened (since 1980), that someone (academic or not) has "broken" (even in a weak sense) some cryptographic assumption, but has chosen to not first publish and directly ...
3
votes
2answers
192 views

How is the matrix A related to the lattice space L in SIS?

Is the matrix $A= (b_1|,...,|b_m)$ where B=$(b_1,...,b_m)$ is the basis of the lattice space, $L$(B)? Not sure if the answer is trivial however I'm having trouble seeing how SIS is a lattice hard ...
3
votes
0answers
189 views

Is the ring learning with errors problem still hard if the errors are drawn from some subspace?

Let $R=\mathbb{Z}_p[x]/x^n+1$ be the ring used in normal RLWE, which is linear space over $\mathbb{Z}_p$ with dimension of $n$, let $S$ be a linear subspace of $R$ which described by linear ...
4
votes
1answer
163 views

Are there post-quantum cryptosystems with a gap between classical and quantum security?

Is there a gap between classical attacks and quantum attacks against some post-quantum security assumptions? (I'm particularly interested in asymmetric cryptography.) I understand that there is no ...
3
votes
1answer
60 views

General factoring and one-way functions

Let a function $f$ be one-way, if there exists a probabilistic polynomial time algorithm to find the preimage of $y = f(x)$ for uniformly chosen $x$ with non-negligible probability. Define the ...
1
vote
1answer
246 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 ...
-2
votes
1answer
70 views

Is permutation conjugate search problem many answer? Are there many answer equal? [closed]

If conjugate search problem of permutation is difficult , then there are next cryptosystem will appear. A=XYX−1,B=XZX−1,Y and Z are public key.And X is secret permutation. then encryption is C=...
1
vote
2answers
92 views

From the product of two permutation matrices raised to the same power, is it easy to find the power?

Let $A$ and $B$ be two public permutation matrices. If $r$ is a secret power of large number, can we easily find $r$ from $A^rB^r$?
0
votes
1answer
116 views

Is Permutation conjugate problem hard?

Let $x$,$y$,$z$ be permutations. Then public key is $z=xyx^{−1}$ and $y$. Is permutation conjugate search problem easy? if yes, how to find $x$ from $z$ and $y$? Let be a is Alice's secret key as ...
6
votes
1answer
147 views

When does the SIS (Short Integer Solution) Lattice-problem start becoming easy (According to the parameters size)?

SIS (Short Integer Solution) Problem : Given $m$ uniformly random vectors $a \in Z_q^n$, grouped as the columns of a matrix $A \in Z_q^{n.m}$, find a nonzero integer vector $z \in Z^m$ with $||z|| \...
2
votes
1answer
100 views

Bit-strength of discrete logarithm for a group of integers modulo a safe prime

Preliminaries Let $p$ be a safe prime number. Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$. We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ . Let $g \...
2
votes
1answer
65 views

Can I connect the hardness of a linear short integer solution problem to that of SIS problem?

As we know, SIS problem is defined as: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $\mathbb{Z}_q^{r \times n}$, it is hard to find elements $s \in \mathbb{Z}_q^{n}$ ...
0
votes
1answer
51 views

finding sha256 preimage or secp256k1 private key, which is harder?

Is finding a public key that matches hash of pre-commited public key (second layer security) more computationally hard than finding private key to a known public key (attacking secp256k1)?
2
votes
2answers
1k views

Decisional Diffie-Hellman assumption vs decisional bilinear Diffie-Hellman assumption

For the Decisional Diffie-Hellman (DDH) assumption we know that: Given $g^a$ and $g^b$ for uniformly and independently chosen $a,b \in Z_p$ the value of $g^{ab}$ looks like a random value in group $\...
4
votes
2answers
98 views

Hardness of LPN problem with small secret

The Learning Parity with Noise (LPN) assumption states that, for a fixed secret $s$ chosen uniformly from $\{0,1\}^n$, then the distribution that outputs $(a,a\cdot s+e)$, where $a$ is uniform in $\{0,...
2
votes
0answers
41 views

Assumptions underlying the soundness of STARKs

STARKs have recently received quite a lot of attention due to their small proof size and supposedly simple assumptions. The paper introduction itself seems to mainly state that their construction is ...
10
votes
2answers
914 views

Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

A recent eprint paper claims to bound $\lambda_1(\Lambda^\perp(\mathbf{A}))$ for $\mathbf{A}\in\mathbb{Z}^{n\times m}$, a uniformly random matrix, by $O(1)$, specifically by $4$. This has applications ...
1
vote
1answer
991 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 \...
2
votes
0answers
106 views

What are the known attacks on $\phi$-hiding assumption? How to chose its parameters?

$\phi$-hiding assumption states the following. Sample 2 random primes $e_0$ and $e_1$ in the range $[5, 2^{\lambda/4}]$. Sample $N = pq$ of length $\lambda$ ($p$ and $q$ are large primes of length $0....
2
votes
1answer
71 views

Does DDH hold in $Z_N^*$ where N is product of 2 large primes

I know that DDH does not hold in $Z_p^*$ because given $g, g^a, g^b, x$, we can compute legendre symbols of $g^a, g^b$ and compare it with legendre symbol of $x$. The same attack doesn't work when we ...
4
votes
1answer
220 views

Is there a group where CDH is easy but DLog is hard?

The question is quite simple: Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard? Refresher on the problems: CDH:...
2
votes
0answers
129 views

Efficient way of knowing large factors of $\phi(n)$ given small prime factors and $n$

Knowing large prime factor$(r > n^{1/4})$ of $\phi(n)$ can easily factorize n and hence learn $\phi(n)$. If we have knowledge on all small prime factors $(2< r_i << n^{1/4})$ of $\phi(n)$...
4
votes
1answer
71 views

Global minimum based cryptography?

When using the Back propagation Algorithm for Machine Learning, it is often said finding the global minimum of a cost function over $\mathbb{R}^n$ is very hard, and as $n$ increases it gets even more ...
9
votes
1answer
126 views

Sum of two squares problem

I would like to know if there is any existing research on the following problem: $$\text{For }a, b \in \mathbb Z \text{, given }n = a^2 + b^2, \text{output }a, b$$. Searching for "sum of squares", "...
1
vote
1answer
73 views

Proving impossibility for a stronger primitive

I have a primitive $A$ which is impossible to prove under some hardness assumption in a black-box way. Now, if another primitive $B$ is stronger than $A$ - in other words $B$ implies $A$ - will it ...
3
votes
0answers
74 views

Assuming the difference between success probabilities to be positive

Context: I am currently studying Theorem 3.1 in the paper Number-Theoretic Constructions of Efficient Pseudo-Random Functions by Naor and Reingold. The theorem basically states the randomized self-...
1
vote
1answer
99 views

Is DDH hard over this group?

I'm new to DDH. Reading this survey, I noticed that DDH is (believed to be) hard in many groups, but most of them are prime-order groups (the only one that is not is the cyclic subgroup of order $(p-...
3
votes
1answer
115 views

Is this secure?

I have an encryption scheme where the secret keys are $(\alpha_1, \alpha_2)$ and $(y_1, y_2)$. $(y_1', y_2')$ are public information. The ciphertext is: \begin{align*} \mathit{ct}_1 &= r_1 \...
-2
votes
1answer
67 views

Diffie Hellman Key Exchange Security wrt the hardness of discrete Logarithm

Hi I am very new to this field and I was wondering how one would prove or disprove the following statements: 1) if the DH key exchange protocol is secure for a finite cyclic group G, then computing ...
1
vote
2answers
88 views

Proving security of an encryption scheme

I have an encryption scheme $Enc(pk, m)$ which outputs ciphertext of the form $c_1 = (pk)^r, c_2 = g^r \cdot m$; where $pk$ is the public key of the form $g^a$, $a$ being the corresponding secret key. ...
0
votes
1answer
69 views

Arguing security of an encryption scheme

I have an encryption scheme which masks the message m by multiplying it with a secret random group element i.e $g^r \cdot m$. I should allow decryption and get $g^r$ if I have a valid secret key; ...
1
vote
1answer
462 views

Comparing stronger vs. weaker assumptions

If I have to argue that an assumption A is stronger than B, should I argue this way:- An adversary breaking the security of A does not translate to breaking the security of B. But, if an adversary ...
14
votes
1answer
1k views

Can you give me a summary of cryptographic hardness assumptions?

Until recently, I had a link to a website which summarizes up-to-date cryptographic hardness assumptions. But, unfortunately I cannot find it. The webpage is categorized well problems such as, DL ...
2
votes
0answers
39 views

Size of $q$ in reductions from lattice problems to R-SIS

The Short integer solution problem is parameterized by four values: $n$, the dimension of the vectors that must be added $m$, the number of samples (dimension of the solution) $\beta$, upper-bound ...
2
votes
1answer
468 views

How to generate hard subset sum instances

A subset sum problem can be defined as: Given a set of integers $S$ A target integer $x$ Find some subset of elements $s \in S$ such that $\sum_0^{n}s_i = x$ The "density" of a subset sum problem ...
3
votes
1answer
216 views

How hard is the following q-Strong Diffie-Hellman problem?

From On the $q$-Strong Diffie-Hellman Problem, the following problem is well-known to be hard. For an randomly chosen element $x \in \mathbb{Z}_p$ and a random generator $g \in \mathbb{G}$, the ...
3
votes
1answer
58 views

Is a composition of computational hardness problems still hard?

It is well known that both $g^x$ and $x^2$ are computational hardness problems in certain rings. But I wonder if the composition of them is still hard? Namely, given $(g, g^x, x^2)$ in a ring $Z_n$ ...
8
votes
2answers
201 views

How hard is Self-DLOG?

This question while asking for something different brings up an intriguing problem: If you can find $x$ such that $x\equiv R^x\pmod p$ then you can break DSA. Now I thought that one might be able to ...
1
vote
2answers
64 views

Is there any Information on the “Modular Approximate Greatest Divisor” problem?

The Approximate Greatest Common Divisor (AGCD) problem is the difficulty of obtaining the value $\ p\ $ when given samples of $\ pq_i + e_i$ for secret values $p, q_i, e_i$. I would like to know how ...
4
votes
2answers
112 views

What is the computational cost of guessing symmetric keys for two ciphers that decrypt to the same input?

A message m is encrypted with two symmetric keys, resulting in two ciphers c, c1 = encrypt(m, key1) c2 = encrypt(m, key2) What is the computational cost of guessing symmetric keys for both ciphers ...
1
vote
1answer
232 views

Difficulty of generating a string “The (md5|sha1) hash of this string is (x)” that hashes to (x) vs. regular hash collision between files?

I know that collisions in md5 and sha1 have been demonstrated in particular pairs of files (by incrementing some none viewable portion of a PDF, etc). Would generating the above string be ...
1
vote
1answer
79 views

Naor Pinkas OT - senders security; reduction to DDH

This question concerns the security of the sender in the Naor Pinkas OT. The protocol can be found here. We can reduce the security to the DDH assumption. How exactly is this done? Can someone ...
6
votes
2answers
936 views

What is a q-type assumption?

I've seen the term "$q$-type assumption" used in a few papers without a definition. A Google search doesn't seem to come up with anything useful either (except the same papers without a definition). ...
2
votes
1answer
163 views

Universal forgery based on mathematical problem

It is known that DSA admits universal forgery under assumption that the Attacker can solve the equation $x\equiv R^x\pmod p.$ Are there any other protocols admitting universal forgery based on non-...
0
votes
0answers
127 views

Random self-reducibility and NP

I was reading the Wikipedia page https://en.m.wikipedia.org/wiki/Random_self-reducibility and it states: "If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy ...