# Questions tagged [hardness-assumptions]

Mathematical problems that are thought to be difficult to solve for all cases in polynomial time

153 questions
Filter by
Sorted by
Tagged with
35 views

1 vote
117 views

### What are security reductions of symmetric-key algorithms?

I was reading Wikipedia page of post-quantum cryptography. It says that it is desirable for cryptographic algorithms to be reducible to some particular mathematical problem, that is intractability of ...
• 71
157 views

### Solve DLOG using a probabilistic algorithm for DLOG lsb

Following the question Can I know from a Bitcoin public key if the private key is odd or even? The answer there gives a simple algorithm for solving the Discrete Logarithm Problem when given an oracle ...
• 10.9k
111 views

### Would being able of factoring integers efficiently have some consequences over Elliptic Curve Cryptography?

Let's assume you can factor integers in a very efficient manner. Would that endanger the security of e.g. elliptic curve cryptography, or is there no link between the two ? You can often read that ... 1 vote
304 views

### DDH to DLIN reduction

I read multiple times that it should be feasible to show a reductions from Decisional Diffie Hellmann. Could you give examples? 1 vote
50 views

### Developments in ABE using Pairings

What are the recent developments in Attribute-Based Encryption (ABE) using Pairings assumptions? Is pairings the most viable assumption while designing ABE. What other assumptions are used for ABE ...
34 views

### Group Signature by Camenisch and Stadler

Page 8, Paper: "Efficient Group Signature Schemes for Large Groups" by Camenisch and Stadler (1) I was trying to understand membership certificate part. I am have only basic knowledge of ...
• 141
98 views

• 413
1 vote
49 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 ...
• 413
1 vote
88 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, ...
• 381
107 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$...
• 133
103 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$?
302 views

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 0 answers 77 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\...
• 381
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 ...