Questions tagged [hardness-assumptions]
Mathematical problems that are thought to be difficult to solve for all cases in polynomial time
92
questions
2
votes
1answer
55 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
197 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....
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 ...
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 $...
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^{'}, ...
1
vote
1answer
33 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, ...
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, $...
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 ...
5
votes
3answers
237 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
102 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
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
107 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
67 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 ...
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
83 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
431 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
234 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)?
4
votes
2answers
131 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
956 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
321 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
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 ...
3
votes
2answers
240 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 ...
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", "...
1
vote
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 ...
1
vote
1answer
149 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-...
3
votes
1answer
117 views
Is this secure?
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 \...
-2
votes
1answer
79 views
Diffie Hellman Key Exchange Security wrt the hardness of discrete Logarithm
Hi I am very new to this field and I was wondering how one would prove or disprove the following statements:
1) if the DH key exchange protocol is secure for a finite cyclic group G, then computing ...
1
vote
2answers
130 views
Proving security of an encryption scheme
I have an encryption scheme $Enc(pk, m)$ which outputs ciphertext of the form $c_1 = (pk)^r, c_2 = g^r \cdot m$; where $pk$ is the public key of the form $g^a$, $a$ being the corresponding secret key. ...
0
votes
1answer
71 views
Arguing security of an encryption scheme
I have an encryption scheme which masks the message m by multiplying it with a secret random group element i.e $g^r \cdot m$. I should allow decryption and get $g^r$ if I have a valid secret key; ...
2
votes
1answer
1k views
Comparing stronger vs. weaker assumptions
If I have to argue that an assumption A is stronger than B, should I argue this way:-
An adversary breaking the security of A does not translate to breaking the security of B. But, if an adversary ...
2
votes
0answers
50 views
Size of $q$ in reductions from lattice problems to R-SIS
The Short integer solution problem is parameterized by four values:
$n$, the dimension of the vectors that must be added
$m$, the number of samples (dimension of the solution)
$\beta$, upper-bound ...
2
votes
1answer
634 views
How to generate hard subset sum instances
A subset sum problem can be defined as:
Given a set of integers $S$
A target integer $x$
Find some subset of elements $s \in S$ such that $\sum_0^{n}s_i = x$
The "density" of a subset sum problem ...
