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

Filter by
Sorted by
Tagged with
3 votes
0 answers
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 ...
user avatar
  • 103
2 votes
1 answer
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?
user avatar
  • 13k
4 votes
1 answer
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....
user avatar
  • 425
-1 votes
1 answer
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-...
user avatar
  • 23.4k
5 votes
1 answer
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 ...
user avatar
  • 23.4k
0 votes
1 answer
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 &...
user avatar
  • 23.4k
6 votes
1 answer
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 ...
user avatar
  • 13k
1 vote
0 answers
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?
user avatar
0 votes
1 answer
142 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 $\...
user avatar
  • 115
0 votes
0 answers
82 views

On $g^{2^x}=B$ modulo $p$

Let $p$ be prime and $g$ positive integer. Define $f(g,x)=g^{2^x} \bmod p$. Q1 Given $g,p,B=f(g,X)$, what is the complexity of finding $X$? If necessary assume $\varphi(p-1)$ is smooth. Some ...
user avatar
  • 23.4k
5 votes
2 answers
329 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 $...
user avatar
  • 23.4k
2 votes
2 answers
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 ...
user avatar
  • 23
7 votes
0 answers
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 ...
user avatar
  • 11.1k
1 vote
1 answer
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$ ...
user avatar
  • 539
3 votes
1 answer
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 ...
user avatar
  • 23.4k
5 votes
1 answer
255 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 ...
user avatar
  • 23.4k
1 vote
0 answers
51 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 ...
user avatar
  • 23.4k
2 votes
1 answer
138 views

Are there any homomorphic analog error correction code?

Are there any analog error correction codes that are additively and multiplicatively homomorphic?
user avatar
  • 41
5 votes
2 answers
284 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 ...
user avatar
  • 63
10 votes
1 answer
346 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 $...
user avatar
0 votes
0 answers
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 ...
user avatar
2 votes
0 answers
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)$ ...
user avatar
10 votes
4 answers
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 ...
user avatar
  • 111
3 votes
1 answer
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 ...
user avatar
  • 23.4k
4 votes
1 answer
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$." ...
user avatar
  • 41
4 votes
0 answers
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 ...
user avatar
  • 23.4k
3 votes
0 answers
184 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 $\...
user avatar
  • 131
2 votes
1 answer
107 views

Extending Vigenère method using arbitrary function

Monoalphabetic substitution cipher consists of applying a one letter shift in each letter of plain text. So if $p = p_1 \ldots p_r$ is plain text then encrypted text is $e = q_1 \ldots q_r$ where each ...
user avatar
6 votes
0 answers
144 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{...
user avatar
3 votes
2 answers
175 views

Reference describing supersingular elliptic curves over algebraically closed field in characteristic 2

I'm looking for a reference for the fact that over an algebraically closed field of characteristic two, there is (essentially) only one supersingular elliptic curve. This fact appears on Wikipedia, ...
user avatar
2 votes
1 answer
227 views

Is this model of converting integers to Gray code correct?

The model shown in the figure converts all numbers that have k digits in the binary system to Gray code without any calculation, but I have no proof that guarantees this claim. Here is some ...
user avatar
1 vote
1 answer
252 views

Are there algorithms for deciding or solving conjugacy in integer quaternion rings?

I am doing some research on the quaternions and their role in Non-commutative cryptography. I have found a number of articles, but it is still unclear to me if there is a known solution to the ...
user avatar
3 votes
1 answer
130 views

Given $n, c$ find $a>1,b$ such that $b ^ a \equiv c \pmod n$

Given a natural number $n$ (of unknown factorization) and an arbitrary number $c \in \mathbb{Z}^*_n$ (the set of natural numbers smaller than $n$ and coprime to it), is there an efficient algorithm ...
user avatar
1 vote
0 answers
201 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)$ ...
user avatar
-1 votes
2 answers
155 views

Is there any way to solve this equation without knowing the inverse modulo? [closed]

Suppose I have an arbitrary 256 bit number $m$ another secret number $k$ of the same bit length, and then I multiply them both modulo a 256 bit prime number $p$ to get $c$ as follows: $$ c = (m\cdot k)...
user avatar
0 votes
1 answer
173 views

Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]

Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...
user avatar
3 votes
1 answer
118 views

Subexponential algorithms that apply only one of factoring and discrete logarithm?

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants. What are the subexponential ...
user avatar
  • 13k
1 vote
0 answers
86 views

On relationship between cryptography and operator algebras [closed]

Does quantum cryptography connect two different areas of math operator algebras and Cryptography?
user avatar
1 vote
0 answers
109 views

How to find modulo inverse if two number are not relatively prime for Hill cipher? [closed]

While practicing for Hill Cipher I choose a random Key matrix of $ 2*2 $ given as follows : $ K = \begin{bmatrix}3&2\\1&0\\\end{bmatrix} $ Say the Text to Encrypt is ATTACK By using the ...
user avatar
  • 111
20 votes
1 answer
1k views

Cryptography and elliptic curves

Cryptography sometimes uses elliptic curves over finite fields. Does cryptography also use elliptic curves over $\mathbb{Q}$ or rational points on them?
user avatar
2 votes
0 answers
84 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 ...
user avatar
4 votes
0 answers
444 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 ...
user avatar
3 votes
0 answers
67 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)...
user avatar
0 votes
1 answer
336 views

Reason Coppersmith fails here?

Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$. $P$ has a binary expansion and so does $Q$. We can set the binary $0/1$ variables to be $x_1$ through $x_{\lceil\log P\rceil}$ and $...
user avatar
  • 13k
1 vote
0 answers
173 views

Method of Coppersmith optimal for multivariate?

It is shown that Coppersmith method yields optimal integer root extraction for univariate polynomials in https://arxiv.org/abs/1605.08065 and a follow up work attempts this for bivariate polynomials ...
user avatar
  • 13k
4 votes
1 answer
269 views

Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?

The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...
user avatar
  • 13k
1 vote
1 answer
130 views

Cryptography with general RSA type integers?

Denote $\mathcal N_r=\{n\in\mathbb Z:\exists\mbox{ distinct equal bit primes }p_1,\dots,p_r:n=p_1p_2\dots p_{r-1}p_r\}$. $\mathcal N_1$ refers to primes and $\mathcal N_2$ referes to balanced ...
user avatar
  • 13k
4 votes
1 answer
399 views

Density of integers with a large rough divisor

Let $N < 2^a$ be a positive integer chosen uniformly at random. Let $\tilde{N}$ be the result of removing from $N$ all its prime factors less than $2^b$. What is the probability that $\tilde{N}$ is ...
user avatar
  • 2,759
0 votes
0 answers
90 views

Example of a zero-knowledge protocol for a strictly Pi_n sentence?

I'm looking for an example of a zero-knowledge protocol such that (1) the prover Peggy can demonstrate to the verifier Victor that she has a proof of $P$ (to the usual standards of a zero-knowledge ...
user avatar
4 votes
1 answer
412 views

Is it hard to decide whether a matrix is a square of another matrix?

According to the well-know quadratic residue (QR) theory over integers, we know that it is hard to decide whether a given integer $m\in\mathbb Z_N$ is a quadratic residue (i.e., a square of another ...
user avatar