Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hardness-assumptions]

The tag has no usage guidance.

9
votes
2answers
715 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
0answers
48 views

KEA assumption details

Recently I have been looking to understand the KEA1 assumption in The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols by Mihir Bellare and Adriana Palacioy. In order to ...
2
votes
0answers
86 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
49 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 ...
4
votes
1answer
146 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
107 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)$...
9
votes
1answer
107 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
67 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
49 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
113 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
47 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
77 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
67 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; ...
1
vote
1answer
74 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
26 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
231 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 ...
3
votes
1answer
148 views

How hard is the following q-Strong Diffie-Hellman problem?

From On the $q$-Strong Diffie-Hellman Problem, the following problem is well-known to be hard. For an randomly chosen element $x \in \mathbb{Z}_p$ and a random generator $g \in \mathbb{G}$, the ...
4
votes
1answer
55 views

Is a composition of computational hardness problems still hard?

It is well known that both $g^x$ and $x^2$ are computational hardness problems in certain rings. But I wonder if the composition of them is still hard? Namely, given $(g, g^x, x^2)$ in a ring $Z_n$ ...
1
vote
2answers
64 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 ...
3
votes
0answers
70 views

Assuming the difference between success probabilities to be positive

Context: I am currently studying Theorem 3.1 in the paper Number-Theoretic Constructions of Efficient Pseudo-Random Functions by Naor and Reingold. The theorem basically states the randomized self-...
4
votes
2answers
97 views

What is the computational cost of guessing symmetric keys for two ciphers that decrypt to the same input?

A message m is encrypted with two symmetric keys, resulting in two ciphers c, c1 = encrypt(m, key1) c2 = encrypt(m, key2) What is the computational cost of guessing symmetric keys for both ciphers ...
1
vote
1answer
153 views

Difficulty of generating a string “The (md5|sha1) hash of this string is (x)” that hashes to (x) vs. regular hash collision between files?

I know that collisions in md5 and sha1 have been demonstrated in particular pairs of files (by incrementing some none viewable portion of a PDF, etc). Would generating the above string be ...
1
vote
1answer
62 views

Naor Pinkas OT - senders security; reduction to DDH

This question concerns the security of the sender in the Naor Pinkas OT. The protocol can be found here. We can reduce the security to the DDH assumption. How exactly is this done? Can someone ...
8
votes
2answers
171 views

How hard is Self-DLOG?

This question while asking for something different brings up an intriguing problem: If you can find $x$ such that $x\equiv R^x\pmod p$ then you can break DSA. Now I thought that one might be able to ...
0
votes
0answers
91 views

Random self-reducibility and NP

I was reading the Wikipedia page https://en.m.wikipedia.org/wiki/Random_self-reducibility and it states: "If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy ...
2
votes
1answer
278 views

q-Strong Bilinear Diffie-Hellman

I'm having trouble finding the first paper that introduced the $q$-Strong Bilinear Diffie-Hellman ($q$-SBDH) assumption which, roughly speaking, is: Let $\mathbb{G},\mathbb{G}_T$ be two groups of ...
2
votes
1answer
527 views

Is factorization modulo a product of primes an NP-hard problem?

For example, let, $p$ and $q$ be two large prime numbers. We set $n = p \cdot q$. Now, let $a \cdot b = c \pmod n$. Given $c$ and $n$, is finding the factors $a$ and $b$ computationally difficult? I ...
1
vote
1answer
97 views

Extracting $ x $ given $ g^x, g^{x + y}, y $

Given a cyclic group $ G $ of prime order $ q $ with generator $ g $ in which computing the discrete logarithm is hard. Is it (still) hard to find the discrete logarithm $ dlog_g(g^x) = x $ if the ...
4
votes
1answer
169 views

Does the following Diffie-Hellman problem hold in bilinear groups $G\times G \rightarrow G_T$

For every PPT distinguisher A there exists a negligible function $neg(·)$ such that for all $\lambda$ $|\Pr[A(1^\lambda, g,g_1^a,g_1^b,g_1^{ab}) = 1] - \Pr[A(1^\lambda, g,g_1^a,g_1^b,g_1^z) = 1]| \...
6
votes
1answer
290 views

Is $a b + e \mod P$ hard to invert?

Given $a, p$, $c$ where $c = a b + e \mod p$, can $e$ be recovered? Additional details: $p$ is prime $a, p$ are re-used across many instances of the problem $b, e$ (and by extension $c$) are always ...
2
votes
2answers
185 views

More general - what is the hard problem of recovering r from r*p mod q?

I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that ...
1
vote
1answer
63 views

What is the hard problem for this algebraic encryption construct?

I would like to know what cryptographic hard problem this reduces to. Select two large prime numbers $p$ and $q$, and let $N=pq$. Select a random positive integer $r$. Compute the encryption of ...
1
vote
1answer
760 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 $\...
9
votes
1answer
338 views

Nash cryptosystem

In 1955, Nash proposed a cryptosystem in a declassified handwritten letters sent to the National Security Agency. The letters also include a conjecture which is equivalent to the famous $P \ne NP$ ...
4
votes
2answers
224 views

About converting Leveled FHE to Pure FHE and the Circular Security Assumption

As it was pointed out in one answer of this question, the BGV paper has a footnote that says One can obtain a "pure" FHE scheme (with a constant-size public key) from these leveled FHE schemes by ...
1
vote
1answer
62 views

Is DL difficult under the group of Unimodular matrices?

Is discrete logarithm assumed to be computationally hard in a non-abelian group as the subgroup of the general linear group under matrix multiplication formed by the unimodular matrices? The two ...
2
votes
1answer
107 views

Security model scalar multiplication in NaCl

I'm having trouble understanding what the “security model” for “scalar multiplication” in NaCl is. Security model crypto_scalarmult is designed to be strong ...
2
votes
0answers
148 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 ...
9
votes
1answer
378 views

About random self-reducibility of DDH

In Section 8 of this, Lindell presents a construction of an oblivious transfer protocol which is secure in the malicious model under the following variant of the DDH assumption (page 53): [F]or ...
4
votes
1answer
207 views

How to prove hardness of approximate-GCD problem?

I am trying to prove the security of my system using the hardness assumption of the approximate-GCD problem using contradiction, i.e. If the attacker is able to break in our scheme, then attacker ...
4
votes
1answer
107 views

Is there any IND-CPA secure stream cipher with a “standard” hardness assumption?

I've read our recent question: "One-time pad using RSA and Diffie-Hellman functions" which asks about the security of a particular way to convert RSA and discrete exponentiation into a stream cipher. ...
14
votes
1answer
989 views

Can you give me a summary of cryptographic hardness assumptions?

Until recently, I had a link to a website which summarizes up-to-date cryptographic hardness assumptions. But, unfortunately I cannot find it. The webpage is categorized well problems such as, DL ...
3
votes
1answer
176 views

Generalization of the DL-assumption in bilinear group pair

When thinking about a pairing-based cryptographic scheme, I encountered the following problem. Let $e \colon G_1, G_2 \to G_T$ be a Type 3 pairing. Then: Given $P, zP \in G_1$ and $Q, zQ \in G_2$, ...
2
votes
1answer
189 views

Bilinear map assumpion

Is there an assumption that says from a tag $k\cdot e(g,g_1)^{rx}$ ($k,r$ are secret) it is difficult to forge it with some x': $k\cdot e(g,g_1)^{rx'}$, as long as you cannot solve DL in $\mathbb{G}_1$...
2
votes
2answers
231 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 ...
2
votes
1answer
230 views

What is the notion of an interactive assumption?

In this paper: Sequential Aggregate Signatures with Short Public Keys: Design, Analysis and Implementation Studies the authors sell the paper as the first who propose Aggregate signatures without ...
1
vote
1answer
85 views

Security of a signature scheme based on both factoring and discrete logarithms

I have seen this paper: A New Signature Scheme Based on Multiple Hard Number Theoretic Problems by Ismail and Tahat: In this paper, we propose a new signature scheme based on two hard number ...
1
vote
0answers
144 views

What is the hardness in Decisional Linear Assumption (DLIN)?

I had understood what does the DLIN assumption means and here is a related question. But I fail to understand the 'real hardness' in this problem. I would be grateful if someone can help me to ...
2
votes
1answer
250 views

Strong LRSW assumption for type 3 pairing groups

Why does the "strong LRSW" assumption by Ateniese et al. [Untraceable RFID Tags via Insubvertible Encryption, CCS'05] hold ONLY for type 3 pairings and NOT for symmetric pairings? Whereas, the LRSW ...
1
vote
2answers
402 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 ...