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
Filter by
Sorted by
Tagged with
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 ...
Omega's user avatar
  • 81
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 ...
Manfred Weis's user avatar
  • 12.6k
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{...
Konstantce's user avatar
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 ...
Breakfastisready's user avatar
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}...
Alexey Ustinov's user avatar
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 \...
mtheorylord's user avatar
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 ...
Rayane B.'s user avatar
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 ...
george's user avatar
  • 554
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 ...
joro's user avatar
  • 24.2k
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 ...
Joseph Van Name's user avatar
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 ...
Joseph Van Name's user avatar
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,...
user35603's user avatar
  • 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 -...
Kamalakshya's user avatar
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....
aleph's user avatar
  • 503
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 ...
Saegusa's user avatar
  • 173
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 ...
Math-fort's user avatar
  • 103
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 $\...
Etsch's user avatar
  • 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)...
Joseph Van Name's user avatar
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 ...
student's user avatar
  • 149
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 ...
Kaveh's user avatar
  • 5,362
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 ...
Damien Zammit's user avatar
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 ...
Simon Pohmann's user avatar
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 ...
Anton Odina's user avatar
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(...
Turbo's user avatar
  • 13.7k
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\...
Joseph Van Name's user avatar
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 ...
Saegusa's user avatar
  • 173
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$, ...
joro's user avatar
  • 24.2k
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,...
joro's user avatar
  • 24.2k
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 ...
joro's user avatar
  • 24.2k
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 ...
ocalex86's user avatar
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 ...
Cesar11031's user avatar
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)$ ...
user100603's user avatar
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 ...
user67451's user avatar
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. ...
letta's user avatar
  • 21
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 ...
Meysam Ghahramani's user avatar
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 ...
joro's user avatar
  • 24.2k
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 ...
Calodeon's user avatar
  • 637
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 ...
math-Student's user avatar
  • 1,109
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 $...
math-Student's user avatar
  • 1,109
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 ...
Turbo's user avatar
  • 13.7k
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 ...
R Artur's user avatar
  • 11
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 ...
TreeBook1's user avatar
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 $\...
joro's user avatar
  • 24.2k
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\...
Yossi Peretz's user avatar
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};...
Manuel Bravi's user avatar
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(...
Joseph Van Name's user avatar
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$ ...
Gerrit Begher's user avatar
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 = ...
jsliyuan's user avatar
  • 651
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 ...
joro's user avatar
  • 24.2k
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)$ ...
Taylor Huang's user avatar