Questions tagged [hardness-assumptions]
Mathematical problems that are thought to be difficult to solve for all cases in polynomial time
109
questions
1
vote
0answers
25 views
How to show that a problem is random self-reducible?
I have an example of a problem that is random self-reducible, which is the following:
Show that the following problem is random self-reducible for any group $\langle g\rangle$ of order $n$:
Given $g^x$...
5
votes
2answers
156 views
Is this problem with anti-circulant matrices hard?
If there is an obvious way to solve this problem, please give it a chance before downvoting, I beg you. Also, some insight into the resultant asymmetric cryptosystem will be welcomed (described in the ...
1
vote
0answers
21 views
what is the probability for an adversary to find the new key after adding new entropy in a group where computational diffie hellman is hard?
Let's say I have an Elliptic curve group $E(\mathbb{F}_q)$ with base Point $G$ and large prime order $n$. Computational Diffie-Hellman is assumed to be hard in that group.
$H: \{0,1\}^*\rightarrow \{...
1
vote
0answers
31 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 ...
1
vote
1answer
52 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, ...
0
votes
1answer
84 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$...
0
votes
0answers
71 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$?
2
votes
1answer
54 views
The equivalence of SIS and ISIS(Inhomogeneous SIS)
I would like to know whether these two problems are equivalent or not, namely:
$SIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}$ find $ e \in \mathbb{Z}_q^{m}$ such that $ Ae = 0$ and and $\|e\| \...
1
vote
0answers
54 views
Solving RLWE modulo a prime ideal
Suppose you have the following set up for RLWE: $K$ is a cyclotomic field of degree $n$ over $\mathbb{Q}$, and $p\in\mathbb{Z}$ is a prime integer that splits as follows in $R = \mathcal{O}_K$: $p\...
4
votes
1answer
87 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 ...
0
votes
0answers
39 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 ...
3
votes
0answers
47 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 ...
0
votes
1answer
78 views
Problem related to the discrete logarithm problem
Let $G$ be a generator of a cyclic group in which the discrete logarithm problem is hard and $x$ and $u$ be scalars of the group such that $X = xG$ and $U = uG$, respectively. We want to compute $J = ...
2
votes
0answers
64 views
Are these two assumptions equivalent?
Let $f_a : S \to R$ is a family of functions indexed by $a\in P$.
Consider the assumption that $(a, f_a(x))$ is indistinguishable from uniform, over the distribution of $a\leftarrow U$ (uniform) and $...
2
votes
1answer
104 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 ...
5
votes
2answers
179 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
67 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 $...
8
votes
2answers
258 views
Error-correcting Code VS Lattice-based Crypto
I'm not an expert in PQ-crypto, but as I understand error-correcting code and lattice-based crypto, the cryptographic assumptions are very similar. The key difference for me is the nature of the noise....
7
votes
1answer
106 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 ...
11
votes
1answer
230 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 $...
0
votes
0answers
33 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^{'}, ...
1
vote
1answer
35 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, ...
8
votes
0answers
95 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, $...
0
votes
1answer
77 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 ...
6
votes
3answers
279 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 ...
3
votes
1answer
137 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 ...
4
votes
2answers
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$ ...
1
vote
1answer
168 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
86 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
87 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
241 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
124 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
40 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
125 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^{...
28
votes
2answers
4k 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 ...
3
votes
4answers
370 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 ...
4
votes
1answer
187 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
96 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
82 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
136 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
591 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
291 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
85 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
69 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)?
4
votes
2answers
146 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
45 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
972 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
348 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 ...
3
votes
0answers
164 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....
