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
2
votes
1answer
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 ...
4
votes
2answers
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?
2
votes
1answer
57 views

In q-SDH problem, where are those points $\frac{1}{\beta+x}g$ or $g_1^\frac{1}{x+c}$ on elliptic curve?

For the q-SDH problem, given the generator $g_1$ as a point on the elliptic curve, I can picture the $\beta g_1, \beta^2g_1, ..., \beta^qg_1$ since we can simply do the point adding $g_1$ multiple of $...
7
votes
2answers
199 views

Error Correcting Code VS Lattice

I'm not an expert in PQ-Crypto. As I understood Error Correcting Code and Lattice based crypto. The cryptographic assumptions are very similar. And the key-difference for me is the nature of the noise....
3
votes
1answer
103 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 ...
3
votes
2answers
242 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 ...
7
votes
1answer
90 views

Is phi-hiding assumption as hard as integer factorization?

Phi-hiding assumption can be simply stated as (wrt hardness) It is difficult to find small factors of $\varphi(m)$ where $m$ is a number whose factorization is unknown and $\varphi$ is Euler's ...
1
vote
1answer
322 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 ...
11
votes
1answer
205 views

What is this problem called and is it hard? given $g^x$ output ($g^y, xy$)

Assume that $G$ is any cyclic group where the discrete log problem is hard, such as the elliptic curve group. Let $g$ be some generator of $G$. The problem is as follows: Given $(g, g^x)$ for unknown $...
5
votes
3answers
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 ...
0
votes
0answers
31 views

Password-based chosen-basis computational Diffie-Hellman assumption

In Simple Password-Based Encrypted Key Exchange Protocols, the authors proposed a hard assumption as follows. Experiment $Exp^{pccdh}_{\mathbb{G}, n}(\mathcal{A}, M, N, X^{'}, \mathcal{P})$ $(Y^{'}, ...
7
votes
0answers
89 views

Hardness of iterated squaring in Pailler group

The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $\leftarrow$ denotes sampling uniformly at random: Input: $(N,x,T)$, where $N$ is the RSA modulus, $...
1
vote
1answer
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, ...
3
votes
3answers
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 ...
5
votes
2answers
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 ...
0
votes
1answer
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 ...
17
votes
4answers
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 ...
3
votes
2answers
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 ...
4
votes
2answers
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$ ...
1
vote
1answer
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 ...
-1
votes
1answer
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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$ ...
0
votes
0answers
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$ ...
1
vote
0answers
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 ...
2
votes
1answer
121 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
28 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 ...
28
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
349 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
0answers
196 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
183 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
84 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 ...
-2
votes
1answer
78 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
102 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
129 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
436 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
236 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
77 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
61 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
132 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
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 ...
10
votes
2answers
957 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
1k 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 \...
3
votes
0answers
141 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
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 ...
5
votes
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:...
2
votes
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)$...
4
votes
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 ...
9
votes
1answer
145 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", "...