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

160 questions
Filter by
Sorted by
Tagged with
89 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 ...
161 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?
128 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....
134 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-...
517 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 ...
73 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 &...
240 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 ...
1 vote
49 views

### On bounded discrete logarithm

Given $g^x=h\bmod p$ where x is known to size $p^{2/3}$ we need to find $x$. Is solving this in $P$ known?
142 views

187 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 ...
372 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
82 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$ ...
228 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 ...
255 views

105 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 ...
160 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)$ ...
937 views

### Number theory in symmetric cryptography

One of the most famous application of number theory is the RSA cryptosystem, which essentially initiated asymmetric cryptography. I wonder if there are applications of number theory also in symmetric ...
546 views

### Is strictly harder than NP-hard cryptography possible?

Looks like there is cryptography based on NP-hard problem, e.g. McEliece cryptosystem. The algorithm is an asymmetric encryption algorithm and is based on the hardness of decoding a general linear ...
89 views

### On the average density of non-zero digits of NAFs of fixed length

An NAF is a non-adjacent form of a positive integer $k$. One of the five properties of NAFs is "The average density of non-zero digits among all NAFs of length $l$ is approximately $1/3$." ...
220 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 ...