Questions tagged [hardness-assumptions]
Mathematical problems that are thought to be difficult to solve for all cases in polynomial time
122
questions
3
votes
0answers
51 views
Decisional Diffie-Hellman Assumption over Group of Quadratic Residue
Consider the Decision Diffie-Hellman (DDH) over $QR_n$ (the quadratic residue group over $n=pq$ where $p$ and $q$ are safe primes).According to Boneh's paper, DDH should be hard over $QR_n$ (https://...
1
vote
1answer
35 views
Linking Decisional Diffie-Hellman, Discrete Logarithm, and Knowledge of Exponent Assumptions
I'm curious about the relation between the Discrete Logarithm and Decisional Diffie-Hellman. Is it safe to have an assumption like the following to link the two?
Given uniformly and independently ...
0
votes
1answer
47 views
Small modulus to noise ration in LWE implies better security
I don't quite understand why a smaller quotient between modulus $q$ and the noise's standard deviation implies better security against known attacks.
2
votes
0answers
56 views
Group of quadratic residue over Blum integer
Let $x$ be a random element from $QR_n$, the quadratic residue group over Blum integer n (where $n=p*q$ and $p$ and $q$ are safe primes), and $g$ a generator of $QR_n$. Are the following ...
1
vote
0answers
33 views
Is there any 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 ...
2
votes
1answer
85 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.
2
votes
1answer
40 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 ...
0
votes
1answer
53 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 ...
2
votes
1answer
48 views
Hard Problems in Pairings
I want to know whether the following problem is considered as a hard problem in complexity theory or not?
Given $g,g^a,g^b \in G_1$ (for unknown $a,b\in \mathbb{Z}_p^{\ast}$), compute $e(g,g)^{ab^2}\...
0
votes
1answer
52 views
Is this an instance of a Diffie-Hellman problem?
Let $\mathbb{G}$ be a cyclic group of order $p$ with generator $g$, and let $m\in\mathbb{G}$.
Problem: Given $c=m.g^{k.a}$ and $v=g^a$, where $k,a \in \mathbb{Z}^*_p$, output $k$.
Is this an instance ...
3
votes
3answers
198 views
Is this asymmetric (public key) cryptosystem based on a 16x16 s-table safe and useful?
May be this is absolutely off-topic, but here is. The cryptosystem description follows. Any hints of what to do with it, or flaws found are welcomed.
This description is here as well.
We will use a ...
5
votes
2answers
171 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
28 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
39 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
67 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
95 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
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$?
2
votes
1answer
87 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
66 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\...
3
votes
0answers
71 views
Strong Diffie-Hellman Problem
While reading the following paper about the Strong Diffie-Hellman Problem, i got curious about ways to compute $ g^{x^{l}} $ for unknown $x$ in an elliptic curve, without first solving the discrete ...
4
votes
1answer
107 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
69 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
1answer
62 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
90 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
70 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 $...
1
vote
2answers
65 views
What are the consequences of Diffie Hellman problem in P?
Computational Diffie Hellman problem wants to know $g^{ab}$ given $g^a$, $g^b$ and $g$ while the discrete logarithm problem wants to know $x$ from $g^x$ and $g$.
The latter resolvable in polynomial-...
2
votes
1answer
110 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
270 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
81 views
In q-SDH problem, where are those points $\frac{1}{\beta+x}g_1$ 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 $...
9
votes
3answers
386 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....
9
votes
2answers
291 views
Is the one-more discrete log problem hard in the Generic Group Model?
In the Generic Group Model (GGM), a concrete cyclic group of (known) order $n$ is replaced with an idealized version: a random encoding for group elements is chosen, and the adversary only gets access ...
7
votes
1answer
132 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
277 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
35 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
39 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
104 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
97 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
320 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
192 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
88 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
212 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
107 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
104 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
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$ ...
0
votes
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$ ...
1
vote
0answers
52 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
130 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^{...
29
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
384 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
199 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 ...
