# 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
Filter by
Sorted by
Tagged with
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
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 ...
• 11
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, ...
• 153
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 ...
• 121
165 views

• 13.6k
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
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 ...
49 views

• 24.2k
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$, ...
• 24.2k
94 views

1 vote
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, ...
• 51
1 vote
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 ...
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 ...
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 ...
• 487
1 vote
73 views

• 27.7k
1 vote
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 ...
• 13
89 views

• 13.6k
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....
• 493
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-...
• 24.2k
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 ...
• 24.2k
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 &...
• 24.2k
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 ...
• 13.6k
473 views

• 24.2k
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 ...
• 23
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 ...
• 12.6k
1 vote
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$ ...
• 539
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 ...
• 24.2k