# Questions tagged [hardness-assumptions]

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

94 questions
Filter by
Sorted by
Tagged with
61 views

### $P \ne NP$: a proof relating complexity theory to block ciphers

I started thinking about P vs NP after reading another question on this stack exchange. Here I propose a proof that relates P vs NP to the existence of a secure block cipher in the elf model. Let's ...
102 views

### MLWE (and RLWE) to LWE reductions proof

In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?
57 views

239 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$ or $c=4$. Is it hard to find $m$ under the RSA assumption (or any of ...
31 views

34 views

### Assumption of difficulty of attack in restricted short time

As well known, different assumptions of difficulty of some problems are used in provable security. E.g., if some crypto-scheme is breakable only in case the attacker finds preimages for hash function, ...
79 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 ...
392 views

### Discrete Logarithm problem with inverse

Let $\mathbb G$ be a cyclic group of order $q$. The Discrete Logarithm Problem (DLP) is, given $g, g^x \in \mathbb G$, to compute $x \in \mathbb Z_q$. I'm interested to know if there is a known ...
47 views

### Computational binding implies Perfect hiding?

Given a commitment scheme which is computationally binding (based on some conjectured hard problem, say), does it also imply that the scheme is unconditionally hiding? My idea was: Since the scheme ...
9k 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 ...
996 views

### Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?

Suppose that we are given $\mathbb{Z}_{N}$ and an element $x^u \in \mathbb{Z}_{N}$ with $u \in (0,l]$ where $l$ is the bit-size of $N$. Is it difficult to recover $x$ by knowing $u$ without knowing ...
80 views

### Protocol for proof of knowledge of $l$-th root

Assume we have Group G in which the adaptive root assumption holds. This assumption states that if we choose an element $w$ and after that, if we receive a prime value $l$ it is hard to find the $u$ ...
110 views

### (How) Is DDH generally broken in groups of composite order?

In a somewhat recent lecture a claim was made that I couldn't back up myself but it got me curious whether it actually holds: If the order of the group is not prime, then the DDH assumption does ...
68 views

### Is it possible to depict the bitcoin mining problem as a TSP-metric problem?

I wonder if someone can represent the blockchain encryption problem (used to mine bitcoins) as a TSP-metric problem (where TSP = Traveling-Salesman Problem). Any approach or intuition of the idea to ...
82 views

### Can quantum algorithms solve the approximate GCD hard problem efficiently?

Some cryptographic schemes are based on the hardness of this problem. The answer to this question determines if those schemes are quantum resistant or not. There are a number similar questions but ...
232 views

### Is this problem on $\mathbb{Z}_p$ really hard?

I just want to know if there's something obvious that renders this hard problem useless. Not a full cryptoanalisys. Any hint on whatever is welcomed. We will work with the Ring $\mathbb{Z}_{p}$, $p$ ...
109 views

### Define a Decryption algorithm on a given group-based Cramer Shoup lite scheme

I am currently working on public key encryption schemes and I want some help to figure out how decryption algorithms work. Suppose we have a public key $pk = (G,p,g,e)$ with $e \in Z^*_p$ . (where $G$ ...
34 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 ...
121 views

236 views

132 views

$\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.... 1answer 88 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 ... 1answer 258 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:... 0answers 147 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)$... 1answer 74 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 ...
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", "...