# Questions tagged [hardness-assumptions]

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

98 questions
Filter by
Sorted by
Tagged with
70 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 ...
31 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 ...
46 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 ...
66 views

103 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 ...
139 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?
61 views

32 views

64 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 ...
275 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 ...
108 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 ...
83 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$ ...
130 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 ...
69 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 ...
85 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 ...
233 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$ ...
110 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

257 views

44 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 ...
962 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 ...
337 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 ...
$\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 92 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 ... 2answers 248 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 ... 1answer 269 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 ... 1answer 153 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", "... 1answer 76 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 ... 1answer 172 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-...
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 \...