# Questions tagged [hardness-assumptions]

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

115 questions
Filter by
Sorted by
Tagged with
0answers
11 views

### if they exist a 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 ...
1answer
76 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.
1answer
34 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 ...
1answer
51 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 ...
1answer
48 views

0answers
37 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 ...
1answer
65 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, ...
1answer
94 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$...
0answers
83 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$?
1answer
78 views

1answer
101 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 ...
0answers
67 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 ...
0answers
50 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 ...
1answer
88 views

1answer
107 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 ...
2answers
241 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?
1answer
80 views

0answers
35 views

1answer
90 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 ...
3answers
299 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 ...
1answer
184 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 ...
2answers
87 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$ ...
1answer
207 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 ...
1answer
106 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 ...
1answer
99 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 ...
1answer
250 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$ ...
0answers
127 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$ ...
0answers
49 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 ...
1answer
130 views

1answer
347 views