# 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).

189
questions

5
votes

0
answers

94
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 ...

1
vote

0
answers

83
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 ...

4
votes

1
answer

236
views

### Is there a category theoretic definition of a cryptographic commitment scheme?

I'm trying to come up with a composeable framework for cryptographic commitment schemes, where inclusion proofs can be combined in different ways. I'm thinking this can be done with category theory, ...

2
votes

0
answers

88
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 ...

4
votes

0
answers

165
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 \...

2
votes

0
answers

151
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(...

4
votes

0
answers

114
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 ...

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 ...

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 ...

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 ...

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 $\...

2
votes

0
answers

85
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,...

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

2
answers

180
views

### Distribution of "good" and "bad" basis in lattice families?

I'm trying to learn more about lattice based cryptosystems.
One of the fundamental ideas behind lattice based cryptosystems is that there can be many equivalent basis for a single lattice.
Formally, ...

1
vote

1
answer

108
views

### Deduce kernel of isogeny from action on torsion points

I'm stuck with the following problem:
In Petit's work "Faster Algorithms for Isogeny Problems using Torsion Point Images", p. 8, he says that we can deduce $\ker \psi_{N_2}$ knowing the ...

3
votes

1
answer

217
views

### What is meant by a meet-in-the-middle approach?

I'm studing C. Petit's work "Faster algorithms for isogeny problems using torsion point images" (link) and he talks about meet-in-the-middle approach/strategy for solve some isogenies ...

8
votes

2
answers

385
views

### Knot Diffie–Hellman

Here's an idea for a knot-based Diffie–Hellman exchange:
Public: random (oriented) knot $P$.
Private: random (oriented) knots $A$ and $B$.
Exchange: Alice sends (randomized or canonical ...

1
vote

0
answers

73
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};...

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

106
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 ...

1
vote

0
answers

129
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

2
answers

245
views

### Method to solve system of exponential sums of the form $a^x+b^x=c$ given more equations than variables [closed]

Cross post with mse
For example, let's say I have the following equations.
\begin{gather*}
a^{x-1}+b^{x-1}=337 \\
a^{x}+b^{x}=1267 \\
a^{x+1}+b^{x+1}=4825 \\
a^{x+2}+b^{x+2}=18751.
\end{gather*}
What ...

2
votes

1
answer

89
views

### Proving that a function is a trapdoor function

I am working on a problem that involves an iterative application of a function I think might be a trapdoor function.
Formally, I have a function $f:X \to X$ that can be described as
$$
[x_{1,N+1}, ...,...

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 ...

4
votes

0
answers

118
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 ...

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

67
views

### What is the complexity of elgamal cryptosystem? [closed]

Its clear generation of keys based
On cyclic group and its generator for z_p
So my question
Does finding the generator efect on complexity
Moreove does the size of message M effect on the complexity?

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 = ...

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 ...

2
votes

1
answer

166
views

### On roots of irreducible quadratics modulo composites

Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$
Is this problem equivalent to any hardness results?

4
votes

1
answer

256
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....

-1
votes

1
answer

179
views

### Public key cryptography based on non-invertible matrices, part II

Closely related to this question
and extending comment
of R. van Dobben de Bruyn.
Working over $\mathbb{F}_p$ and all matrices of square $n \times n$.
Alice chooses invertible $X_A$ and non-...

5
votes

1
answer

549
views

### Public key cryptography based on non-invertible matrices?

Added Wed 13 Apr 2022
I have written a short note with experimental data,
which shows not all pseudo keys are good keys.
Public key cryptography based on non-invertible matrices
We got public key ...

0
votes

1
answer

114
views

### Are there trapdoor functions breakable by moderate polynomial degree complexity algorithm?

Trapdoor function
is a function $f$ that is easy to compute in one direction,
yet difficult to compute in the opposite direction (finding its inverse)
$f^{-1}$ without special information, called the &...

6
votes

1
answer

350
views

### Groups in which Computational Diffie Hellman is in $P$ but Discrete Logarithm is not known to be in $P$

The Computational Diffie Hellman (CDH) problem is to compute $g^{XY}$ given $g^X$ and $g^Y$ where $g$ generates the group. The Discrete Logarithm (DLOG) problem is to compute $X$ given $g^X$. The ...

0
votes

1
answer

473
views

### A good approximation for collision probability between (two) sets of random variables

We face many places to find the collision probability of two sets (or more) in my case the cryptographic hash functions. We can formalize as;
Given two sets of random variables $\mathbf{A}$ and $\...

5
votes

2
answers

491
views

### Diffie Hellman cryptography based on graph isomorphism?

We got a cryptographic algorithm and computer implementation
based on graph isomorphism.
An isomorphism between two graphs is a bijection between their vertices that pre
serves the edges.
For a graph $...

2
votes

2
answers

603
views

### Difference between Shannon entropy and min-entropy

I would like to construct a sequence of discrete random variable $X_2, X_3,...,X_n,...$, where $X_n \in\{0,1,2,...,n-1\}$. Given any $\epsilon \in (0,1)$, its Shannon entropy and min-entropy should ...

7
votes

0
answers

455
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 ...

1
vote

1
answer

87
views

### Can a polynomial be evaluated from evaluations of partial interpolations? (Or: can the unique solution of congruences be written in a certain way?)

Formally, let $K$ be a field, $a \in K[x]$, $D \subseteq K$, and $E = \{(x_i, a(x_i)) \mid x_i \in D\}$ be distinct evaluations of $a$ where $\lvert E\rvert > \operatorname{deg}(a)$ (so $E$ ...

3
votes

1
answer

257
views

### p-adic logarithms with fixed precision

Probably this is easy, but we would like to see it on paper.
Let $p$ be prime and $D,g,n$ positive integers.
Let $A=g^n \bmod p^D$.
Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$.
In ...

5
votes

1
answer

329
views

### Discrete logarithm and the sequence $a(n)=(g^n \bmod p)^{p-1} \bmod p^2$

Let $p$ be prime and $g,n$ integers.
Define $a(n)=(g^n \bmod p)^{p-1} \bmod p^2$
By mod p we don't mean congruence, but the reduction modulo $p$ operator. $A \bmod ...

1
vote

0
answers

78
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 ...

2
votes

1
answer

225
views

### Are there any homomorphic analog error correction code?

Are there any analog error correction codes that are additively and multiplicatively homomorphic?

5
votes

2
answers

396
views

### Maximum number of vectors with upper bound on pairwise inner products

I have a collection $\{v_1,...,v_k\}$ of vectors in $\{\pm 1\}^n$ with the property that for all $i\neq j$ we have $\langle v_i, v_j \rangle \le c\log_2(n)$. I am looking for an upper bound on $k$ in ...

2
votes

2
answers

436
views

### A p-adic logarithm as a limit of discrete logs

I've been searching for something similar to the argument below for about a week now and I just must be missing out on the right key words. Can someone point me in the right direction and/or let me ...

10
votes

1
answer

555
views

### Discrete logarithm for polynomials

Let $p$ be a fixed small prime (I'm particularly interested in $p = 2$), and let $Q, R \in \mathbb{F}_p[X]$ be polynomials.
Consider the problem of determining the set of $n \in \mathbb{N}$ such that $...

0
votes

0
answers

120
views

### Can factorization of very large numbers be aided by associating them with a series (described below) of quadratic polynomials?

My name is J. Calvin Smith. I graduated in 1979 with a Bachelor of Arts in Mathematics from Georgia College in Milledgeville, Georgia. My Federal career (1979-2012) in the US Department of Defense led ...