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
2answers
297 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 ...
1
vote
1answer
117 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 ...
1
vote
2answers
93 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$?
1
vote
1answer
92 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
1answer
103 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-...
1
vote
2answers
96 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. ...
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 ...
1
vote
1answer
83 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
94 views

Is this discrete log generalization a well known cryptographic assumption?

Assume you have a finite group $\mathbb{G}$ and an integer $n$. Given $g_1,\dots,g_n,t$ chosen uniformly from $\mathbb{G}$, consider the problem of finding a vector $(a_1,\dots,a_n)\in \mathbb{Z}^n$ ...
1
vote
1answer
287 views

Hardness of problem related to bilinear pairings

Let $e: \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$ be an efficient bilinear pairing. Note that the pairing is symmetric (i.e., Type 1). The problem is, given $g \in \mathbb G_1$ and $e(g,...
1
vote
1answer
74 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
237 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
81 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 ...
1
vote
1answer
511 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 ...
1
vote
1answer
72 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 ...
1
vote
1answer
267 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 ...
1
vote
0answers
163 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 ...
1
vote
1answer
999 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 \...
0
votes
1answer
53 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)?
0
votes
1answer
117 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 ...
0
votes
1answer
69 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; ...
0
votes
0answers
92 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$ ...
0
votes
0answers
26 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 ...
0
votes
0answers
22 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 ...
0
votes
0answers
129 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
70 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 ...
-2
votes
1answer
70 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=...