# Questions tagged [hardness-assumptions]

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

76 questions
Filter by
Sorted by
Tagged with
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 ...
113 views

100 views

98 views

106 views

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 \...
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 ...
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. ...
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; ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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). ...
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-...