Questions tagged [cryptography]
Questions concerning the mathematics of secure communication. Relevant topics include elliptic curve cryptography, secure key exchanges, and public-key cryptography (eg. the RSA cryptosystem).
71 questions with no upvoted or accepted answers
8
votes
0
answers
1k
views
Question on randomness extractors
Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.
The adversary doesn't ...
- 81
7
votes
0
answers
524
views
Zero-knowledge proofs for answers to the $P=NP$ question
Are there zero-knowledge proofs for every answer to the $P=NP$ question?
For instance, if you have a polynomial-time algorithm of moderate complexity for the graph-coloring problem, then it is easy to ...
- 13.2k
7
votes
0
answers
199
views
Polynomial representation of modular arithmetic in finite fields
Let $n \in \mathbb{N}$ be a predefined integer. Consider the following bijection (between the ring of integers modulo $2^n$ and finite field with $2^n$ elements:
$$ \phi: \mathbb{Z}_{2^n} \to \mathbb{...
- 81
6
votes
0
answers
130
views
Bent vectors and $\pm 1$ eigenvectors with respect to non-Sylvester Hadamard matrices
A Hadamard matrix is an $n\times n$-matrix $H$ where each entry in $H$ is $\pm 1$ and where $H/\sqrt{n}$ is orthogonal. It is well-known that if $H$ is an $n\times n$-Hadamard matrix, then $n<3$ or ...
5
votes
0
answers
110
views
Equidistribution of Hecke points and Steinitz classes
Let $K$ be a number field and $\mathcal{P}$ be a prime ideal of $K$. Let $k_{\mathcal{P}}$ be the residue field $\mathcal{O}_K/\mathcal{P}$.
Consider the following construction used very often in ...
- 885
5
votes
0
answers
317
views
Elliptic curve sequences needed for universal forgery
Elliptic Curve Digital Signature Algorithm (ECDSA) admits universal forgery (UF) if the Attacker can solve the equation
$$z=\frac{f_{k-1}(x,y)f_{k+1}(x,y)}{f_{k}(x,y)^2},$$
where $k$ is unknown, $f_{k}...
- 12.3k
4
votes
0
answers
169
views
Square hidden number problem
Suppose I have a mystery number $m$ modulo $p$ that I wish to find. I know the value of $m+x_i^2$ where $x_i$ is randomly chosen modulo $p$ for some large number of different $x_i$, $N$ many, $N \gg \...
- 591
4
votes
0
answers
143
views
Road map for learning about the computational/general theory of modular curves/isogenies of abelian varieties for cryptography
I am a graduate math/crypto student. So I've had some free time last year and I heard about elliptic curves in cryptography and how a resilient cryptosystem got demolished by a spectacular attack ...
- 41
4
votes
0
answers
137
views
Lattice reduction of basis with non-integer coefficients
Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$.
I would like to perform lattice ...
- 554
4
votes
0
answers
245
views
Can we make cryptography signature algorithm based on hardness of isomorphism?
In public key cryptography, Alice knows functions $f$ and its inverse
$f^{-1}$. $f$ is public and $f^{-1}$ is secret. To sign a message
$m$, she gives $(m,a=f^{-1}(m))$. To verify a signature, the ...
- 25.4k
4
votes
0
answers
601
views
What solutions to useful computational problems could be rewarded through cryptocurrency smart contracts?
What kinds of cryptocurrency smart contracts could be used to reward people for solving specific kinds of useful computational problems?
Background
In this question, I asked for proposals for useful ...
4
votes
0
answers
107
views
Do the normal forms for braid groups really conceal information about better than randomly applying the braid relations?
In braid based cryptography, one typically wants to conceal the way a certain braid $b$ has been obtained. One therefore puts $b$ into some normal form. Since every braid has a unique normal form, the ...
4
votes
0
answers
264
views
Polynomial dynamical systems
The question is somewhat related to the theory of permutation polynomials. Let $\mathbb{F}_p$ be a finite field of $p$ elements ($p$ is prime) and $\mathcal{V} = \mathbb{F}_p^2 = \{ (t_1,t_2)\::\: t_1,...
- 411
4
votes
0
answers
214
views
factorising an integer with certain bound on the factors
Can we count the no. of $x$ where $ p^{\alpha -1} < x < p^{\alpha}$ , $gcd(x, 2p)=1$ and if $d |x$ and $d < p ^{\beta}$ for some $1< \beta<\alpha-1$ then $ \frac {x} {d} > p^{\alpha -...
- 897
4
votes
1
answer
309
views
Discrete logarithms and primitive elements in finite fields
The recent papers:
R. Granger, T. Kleinjung, J. Zumbragel, "On the Discrete Logarithm
Problem in Finite Fields of Fixed Characteristic," Trans. Amer. Math.
Soc., 370(5) (2018), 3129–3145.
T....
- 503
3
votes
0
answers
85
views
When is the number-theoretic transform of small vectors again small?
I am currently working on an idea in the context of lattice-based cryptography, but the problem that I am currently stuck on seems to have almost nothing to do with lattices anymore.
In particular, my ...
- 131
3
votes
0
answers
67
views
Efficiently finding solutions to the Rainbow cryptosystem using quotient spaces
Repost of a mathematics stackexchange question here as this concerns my research and it went unanswered on there.
In this paper, Ward Beullens gives another way to look at the Rainbow cryptosystem. In ...
- 173
3
votes
0
answers
151
views
determine degree of boolean polynomial given as black box
I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
- 103
3
votes
0
answers
285
views
RSA as a hidden subgroup problem
The Hidden Subgroup Problem (HSP) covers several known problems (e.g. Integer Factorization Problem, Discrete Logarithm Problem) as a special case:
Definition [Hidden Subgroup Problem (HSP)] Let $\...
- 131
3
votes
0
answers
72
views
What is the computational complexity of equivalence up to a critical point in the one generator free self-distributive algebra?
Suppose that there exists a rank-into-rank cardinal. Then let $R$ be the relation on the set of terms in the language of self-distributive algebras (or LD-monoids) on one generator where we set
$R(s,t)...
3
votes
0
answers
215
views
Why we are interested in p>3 Schoof's algorithm
In the Schoof's algorithm we are particularly interested in $char(K)>3$, where $K$ is the field. I know Schoof's algorithm is mostly used over large prime fields. Also, when we are transforming ...
- 149
3
votes
0
answers
257
views
Oracle separating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on DDH)
Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP?
Such an oracle ...
- 5,502
3
votes
0
answers
458
views
Does this algorithm exist - a secret secret?
I'm not quite sure how to phrase this question mathematically, so I am going to express it in words first:
Let us suppose I have a secret $m_1$ and a plausible innocent secret $m_2$. Is there an ...
2
votes
0
answers
110
views
How to apply Pohlig Hellman using a very limited set of auxiliary inputs in that case?
So I was reading about Talotti, Paier, and Miculan - ECC’s Achilles’ Heel: Unveiling Weak Keys in Standardized Curves. The underlying idea is to lift the discrete logarithm problem to $\mathrm{prime}−...
- 87
2
votes
0
answers
78
views
Partitions of bent vectors
Let $H=\frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1 \\ 1 & -1\end{bmatrix}.$ Let $A^{\otimes N}$ denote the tensor product of the matrix $A$ with itself taken $N$ times. We say that a vector $v$ of ...
2
votes
0
answers
116
views
Pollard's rho algorithm for ECDLP using supersingular elliptic curves over a field with characteristic equal to a Mersenne prime
I have been playing with Pollard's rho algorithm for elliptic curves over finite fields. I have noticed after some experimenting, that the algorithm almost always 'fails' for supersingular elliptic ...
- 121
2
votes
0
answers
184
views
Will Coppersmith's method work for this bivariate modular polynomial shape?
I have a bivariate modular polynomial of shape
$$f(x,y)=x^2y-g(x)\equiv 0\bmod q$$
where
$q=(2p-1)(2p+1)$ is a product of two primes $2p-1$ and $2p+1$,
$g(x)\in\mathbb Z[x]$ is of degree four and
$f(...
- 13.9k
2
votes
0
answers
50
views
Counting permutations of $X^2$ that induce 4 quasigroup operations up to isotopy
Let $X$ be a finite set. Recall that a binary operation $\ast$ on $X$ is said to be a quasigroup operation if there are binary operations $/,\backslash$ where $(x/y)\ast y=(x\ast y)/y=x$ and $x\ast(x\...
2
votes
0
answers
38
views
Criterion for unicity and existence of pre-image in multivariate cryptography
Repost from math.stackexchange since no one could help me there and it concerns my research.
I am reading Ding's Multivariate Public Key Cryptosystems and in the book the author explains the so-called ...
- 173
2
votes
0
answers
87
views
Complexity of finding solutions of trapdoored polynomial?
Related to this question Cryptography signature scheme based on hardness of finding points on varieties.
Working over $K=\mathbb{Q}[x_1,...,x_n,y_1,...y_m]$.
By abuse of notation, for polynomial $f$, ...
- 25.4k
2
votes
0
answers
96
views
Cryptography signature scheme based on hardness of finding points on varieties?
Related to this question Complexity of finding solutions of trapdoored polynomial.
I am trying to build signature scheme based on hardness
of finding points on varieties.
Let $K$ be field and $M=K[x_1,...
- 25.4k
2
votes
0
answers
91
views
A variant of hidden subgroup problem (HSP)
I read some materials more general about HSP such as 1,2,3. I wonder that if it would be possible to have a faster quantum algorithm when our goal was just to find a non-trivial element of the hidden ...
- 253
2
votes
0
answers
123
views
On choosing the correct square root of $g^{4n}$ modulo primes
Let $p$ be prime congruent to $3$ modulo $4$.
The discrete logarithm problem asks: given $g,a,p$
such that $g^x \equiv a \pmod{p}$, find $x$.
Assume $g$ is of maximal multiplicative order.
In an ...
- 25.4k
2
votes
0
answers
132
views
Solving efficiently a quadratic equation in a large finite field of characteristic two
I'm trying to solve efficiently a quadratic equation in the finite field $\text{GF}(2^{128})$ represented as $(\mathbb{Z}/2\mathbb{Z})[x] / (x^{128} + x^7 + x^2 + x + 1)$.
Until now, I came across ...
- 21
2
votes
0
answers
41
views
Linkable Ring Signatures test
I did a work that uses LRS to sign documents. LRS is a ring signatures model in which the feature of linking signatures made by the same signer is added. Using LRS two messages m1 and m2 are signed ...
- 21
2
votes
0
answers
309
views
Merel's theorem on uniform bound for torsion of all elliptic curves
I am reading Silverman's book on Arithmetic of elliptic curves. There he mentions a theorem of Merel (Thm 7.5.1) which reads like this.
Thm: For every integer $d \geq 1$, there is a constant $N(d)$ ...
- 313
2
votes
0
answers
121
views
How to choose a prime p s.t. n-th cyclotomic polynomial splits into as much as possible irreducible polynomials while p is almost constant size?
The reason I ask this question is that cyclotomic polynomial is critical to the construction of lattice-based cryptography. In most of the existing lattice-based cryptographic schemes, $n$ is usually ...
- 33
2
votes
0
answers
88
views
Example of action of an infinitely countable group that has important ergodic/statistical property?
I work in probability and I am looking for an important example of action of an amenable countable group in other areas of math for which the (pointwise) ergodic theorem is actually quite important. ...
- 21
2
votes
0
answers
275
views
Is conjugacy problem hard in braid group?
Recently I studied the braid group and conjugacy problem. It is believed that conjugacy problem is hard on braid group. My friend gave me an EXE file, and I use it for solving conjugacy problem, as an ...
2
votes
0
answers
145
views
Showing that a crypto hash function is not permutation, possibly conditionally?
Let $f$ be some crypto hash function, say MD5 with output $n$ bits. Restrict the input to $n$ bits.
Cryptographer told me it is open problem if such restricted collision
exists, i.e. $f(x)=f(y),x \ne ...
- 25.4k
2
votes
0
answers
132
views
Genus 2 hyperelliptic cryptography : typical discriminant and class number
As far as I know, there is no standard yet for cryptography based on the DLP over Jacobians of genus 2 curves. Yet, what can we say about the class number, and the discriminant of the complex ...
- 647
2
votes
0
answers
44
views
largest size for a randomness extractor
I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature.
Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...
- 1,109
2
votes
0
answers
63
views
Private Randomness extractor
Suppose we are given two random variables $X$ and $Y$ with fixed marginal and joint distribution. What is the maximum randomness that we can extract from $Y$ that is independent from $X$, that is, if $...
- 1,109
1
vote
0
answers
69
views
Is it in theory possible to perform general Miller’s algorithm inversion as used with the optimal ate pairing with large trace in subexponential time?
Let’s I have the following :
2 curves $G_1$ defined on $F_p$ and $G_2$ being the $G_1$ curve’s twist defined on $F_p^2$ both having the same prime order ; a large trace ; and $F_p^{12}$ as their ...
- 87
1
vote
0
answers
69
views
If we allow DH operations in addition to exponentiation and multiplication can we get a lower bound for discrete logarithm?
In https://crypto.stackexchange.com/questions/72969/proof-dlog-is-hard-in-generic-group-model/ it is shown if we allow only exponentiation and multiplication we can get an exponential complexity lower ...
- 13.9k
1
vote
0
answers
133
views
Select random point on elliptic curve
If I have an elliptic curve $E$ over some finite field $F_p$ what is a step by step algorithm to pick a random point that lays on this curve? There is definitely a naive approach to brute force all ...
- 11
1
vote
0
answers
102
views
Question on definition of inverse number theoretic transformation
In the paper Porkodi and Arumuganathan - Public key cryptosystem based on number theoretic transforms I found the following statement on the second page regarding the Inverse Number Theoretic ...
- 11
1
vote
0
answers
98
views
Hardness of solving $0=\sum_{i=1}^k \operatorname{linear}_i(x_1,\ldots,x_n)^D$ over the rationals
This is related to cryptography and this question
and another question.
In short, we are asking about decomposing multivariate polynomial
as sum of perfect powers of linear polynomials.
Working over $\...
- 25.4k
1
vote
0
answers
56
views
Over a given finite field, how many couples of matrices there are, for which their minimal polynomials are co-prime?
Let ${\mathbb F}_{q}$ be a given finite field. How many couples of $n\times n$ matrices $\left(A,B\right)$ over ${\mathbb F}_{q}$, such that $\gcd\left(\mu_{A}\left(\lambda\right),\mu_{B}\left(\lambda\...
- 21
1
vote
0
answers
109
views
Why is the kernel cyclic if and only if the walk does not backtrack?
I'm reading Mathematics of Isogeny Based Cryptography by Luca De Feo. At some point (pg. 32), he says
"A walk of length $e_A$ in the $l_A$-isogeny graph corresponds to a kernel of size $l_A^{e_A};...
- 73