Questions tagged [polynomial]
The polynomial tag has no usage guidance.
13 questions
2
votes
1
answer
33
views
Understanding Canonical-embedding vs Coefficient-embedding in Ideal Lattices: Relation to NTT?
I'm trying to understand the relationship between different representations of ideal lattices, particularly the canonical embedding and coefficient embedding. While studying these concepts, I noticed ...
- 85
0
votes
0
answers
48
views
LSFR polynomial next term example
I’m struggling with the mathematical representation of an LFSR as polynomials, and I’d like to understand where I go wrong.
In my example, I use an LFSR with a 5-bit shift to the left and feedback on ...
-1
votes
2
answers
78
views
Finding (lagrange) interpolation polynomial modulo p
I'm trying to find an interpolation polynomial degree $t$ less than the number of $n$ points for modulo prime $p$. Additionally, the results of this polynomial should be in small intervals (i.e. in $[...
- 31
2
votes
0
answers
63
views
How efficient is Coron's bivariate Coppersmith algorithm in practice?
The paper by Coron on bivariate coppersmith in https://iacr.org/archive/crypto2007/46220372/46220372.pdf states the complexity of the algorithm is $O(\log^{11}W)$ where $W$ usually is on order of the ...
- 1,025
2
votes
1
answer
135
views
How to find a polynomial with small coefficients that has a given root over a prime field?
Let $\mathbb{Z}_p$ be a prime field, $r \leftarrow \mathbb{Z}_p$ be a random number, $w=w_0w_1...w_{K-1}$ be a 0-1 string, and
$$v = \sum_{k=0}^{K-1} r^kw_k \mod p.$$
Is it possible to find another ...
- 57
0
votes
0
answers
55
views
Hash-based Polynomial Commitment Scheme for Small Polynomials
I am building a SNARK project which needs to use PCS (polynomial commitment scheme). Because of some constraints, I want the field of PCS to have no additional structures and thus I only want to use ...
- 1
2
votes
0
answers
60
views
Succinct proof of evaluation of known polynomial
Consider the zeroes polynomial
$$
zeroes_n(X) = \prod_{0\leq i< n} (X-i) .
$$
Fix a large prime $p$, and fix some $n$ that is less than $p$ but which may still be very large (e.g. $p\approx 2^{256}...
- 131
1
vote
0
answers
50
views
Is a cryptosystem based on hardness of factorization of polynomials, as defined below valid? [closed]
I'm proposing a cryptosystem as defined below:
Private Key: $(R, A, R^{-1})$, where $R = \left(\mathbf{r_1}, \cdots, \mathbf{r_n}\right)$ is full-rank, with $n \geq 4$, even; $A = \left(a_1\mathbf{...
- 69
2
votes
2
answers
114
views
Probabilistic proof of multiplying two elements from non-prime finite field
I was reading this paper, and there, they use the ring $\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$ for all their operations. And that looks like a construction of finite field $\mathbb{F}_{\...
- 147
0
votes
0
answers
49
views
One-way function constructed by multivariable polynomials
Although the conjecture regarding the existence of one-way functions remained open, there are numerous NP-based methods for constructing diverse one-way functions, including DL, lattice, and subset ...
- 456
0
votes
0
answers
56
views
What do we mean when we say we need more than polynomial time many cipher texts
What does it mean when we say something like „we need more than polynomial time many cipher texts“? I understand it as „an adversarial can run for polynomial time and try as many messages as possible ...
- 1
2
votes
0
answers
62
views
Inefficient double-lengthening PRG
I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$
My current approach is to bound the number of poly-time non-uniform ...
- 123
0
votes
0
answers
59
views
Convert an arbitrary array of integers to super increasing sequence
I have an arbitrary array $X = (x_1, x_2, \dots, x_n)$ of disjoint integers. I want to determine whether there exists a prime number, $p$, and a value $y < p$ such that the sequence
$$Y = \left(y_1,...
- 557