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).
64
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 ...
7
votes
0
answers
460
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 ...
7
votes
0
answers
182
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{...
5
votes
0
answers
96
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 ...
5
votes
0
answers
312
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}...
4
votes
0
answers
166
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 \...
4
votes
0
answers
121
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 ...
4
votes
0
answers
122
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 ...
4
votes
0
answers
237
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 ...
4
votes
0
answers
589
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
105
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,...
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 -...
4
votes
1
answer
262
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....
3
votes
0
answers
61
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 ...
3
votes
0
answers
128
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 ...
3
votes
0
answers
268
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 $\...
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
209
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 ...
3
votes
0
answers
253
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 ...
3
votes
0
answers
454
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
64
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 ...
2
votes
0
answers
92
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 ...
2
votes
0
answers
154
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(...
2
votes
0
answers
49
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
33
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 ...
2
votes
0
answers
86
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$, ...
2
votes
0
answers
94
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,...
2
votes
0
answers
121
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 ...
2
votes
0
answers
111
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 ...
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 ...
2
votes
0
answers
255
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)$ ...
2
votes
0
answers
114
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 ...
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. ...
2
votes
0
answers
256
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
142
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 ...
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 ...
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 ...
2
votes
0
answers
62
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
vote
0
answers
56
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 ...
1
vote
0
answers
90
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 ...
1
vote
0
answers
99
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 ...
1
vote
0
answers
97
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 $\...
1
vote
0
answers
53
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\...
1
vote
0
answers
75
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};...
1
vote
0
answers
131
views
The security of one-time digital signatures from a solution to a diophantine equations
I wonder how well arbitrary Diophantine equations can be used to make one time digital signature schemes.
For our one-time digital signature scheme, the public key is a collection of polynomials $f_1(...
1
vote
0
answers
94
views
Reference request: Time and proofs of shared pasts
Is there research about structures for notions of time with distributed systems of information, as with blockchains?
I am thinking of tuples $(I, T, P, A, \prec, s, \eta, u)$ where
$I$, $T$ and $P$ ...
1
vote
0
answers
41
views
If statement in the algebraic group model (AGM)
In the algebraic group model (https://eprint.iacr.org/2017/620.pdf), can one use "if" statement? For example, can one do the following in AGM?
input: x, y, z
if (x = y) then z = x else z = ...
1
vote
0
answers
79
views
Encryption based on boolean satisfiability?
We got sketch of algorithm for public key encryption based on satisfiability
of hidden boolean formula. It is easy to break
in its current form, but we are interested if it can be improved.
Alice ...
1
vote
0
answers
208
views
Generate algorithmically an elliptic curve with its exact class group structure?
Is it possible to generate an elliptic curve $E$ (randomly), together with knowing its class group $\mathrm{Cl}(\mathcal{O})$ structure? where $\mathcal{O}$ is its endomorphism rings $\mathsf{End}(E)$ ...