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).
203 questions
6
votes
1
answer
417
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.9k
0
votes
1
answer
643
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 $\...
- 115
5
votes
2
answers
534
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 $...
- 25.4k
2
votes
2
answers
739
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
7
votes
0
answers
524
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 ...
- 13.2k
1
vote
1
answer
89
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
3
votes
1
answer
266
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 ...
- 25.4k
5
votes
1
answer
359
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 ...
- 25.4k
1
vote
0
answers
80
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 ...
- 25.4k
2
votes
1
answer
262
views
Are there any homomorphic analog error correction code?
Are there any analog error correction codes that are additively and multiplicatively homomorphic?
- 41
5
votes
2
answers
496
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 ...
- 63
2
votes
2
answers
546
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 ...
- 2,235
10
votes
1
answer
637
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 $...
- 12.4k
0
votes
0
answers
135
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 ...
2
votes
0
answers
309
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)$ ...
- 313
10
votes
4
answers
1k
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 ...
- 111
3
votes
1
answer
708
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 ...
- 25.4k
4
votes
1
answer
103
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$."
...
- 41
4
votes
0
answers
245
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 ...
- 25.4k
3
votes
0
answers
285
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 $\...
- 131
2
votes
1
answer
128
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 ...
- 79
7
votes
0
answers
199
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{...
- 81
3
votes
2
answers
360
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, ...
- 31
2
votes
1
answer
315
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 ...
1
vote
1
answer
261
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 ...
- 19
3
votes
1
answer
138
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 ...
- 271
1
vote
0
answers
212
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)$ ...
- 181
-1
votes
2
answers
164
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)...
- 117
0
votes
1
answer
210
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 ...
- 1
3
votes
1
answer
137
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 ...
- 13.9k
1
vote
0
answers
116
views
On relationship between cryptography and operator algebras [closed]
Does quantum cryptography connect two different areas of math operator algebras and Cryptography?
- 677
1
vote
0
answers
139
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 ...
- 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?
- 281
2
votes
0
answers
121
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 ...
- 33
4
votes
0
answers
601
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 ...
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)...
0
votes
1
answer
431
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 $...
- 13.9k
1
vote
0
answers
276
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 ...
- 13.9k
4
votes
1
answer
288
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 ...
- 13.9k
1
vote
1
answer
142
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 ...
- 13.9k
4
votes
1
answer
448
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 ...
- 2,967
0
votes
0
answers
92
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 ...
- 1,155
4
votes
1
answer
425
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 ...
- 475
2
votes
1
answer
152
views
How to compute Weber polynomials efficiently?
Given $\tau\in H$ (up-half plane) and $q=e^{2\pi i \tau}$, Weber polynomail is defined as
$$f(\tau)=q^{-\frac{1}{48}}\prod_{i=0}^{\infty}(1+q^{i-\frac{1}{2}}).$$
My question is: How can I compute a ...
- 475
1
vote
1
answer
138
views
How to compute the Müller modular polynomials?
According to R.A.Kazmi's dissertation "Isogenies and Cryptography" (Page 22), given an isogeny degree $l$, the Müller modular polynomials are defined as
$$G_l(x,y)=\sum_{r=0}^{l+1}\sum_{k=0}^{v}a_{...
- 475
6
votes
1
answer
441
views
Minimum number of operations necessary to arrive at any configuration
Let $k \geq 2$ and $N_1, N_2, ..., N_k$ be positive integers.
Let $S=\{(a_1,a_2,...,a_k) \in \mathbb{Z}^k:1 \leq a_i \leq N_i\}$ and $A=\{1,2,...,\prod_{i=1}^{k} N_{i}\}$.
Given a bijective map $f:...
- 3,153
5
votes
0
answers
317
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}...
- 12.3k
5
votes
1
answer
148
views
Elliptic curves: for $P = aG$ for some $a$, what is $Q = a^{-1}G$?
Given an elliptic curve group with a generator $G$ where $G$ has a prime order, p.
Given a point $P=aG$ for some unknown $a$. Is it possible to efficiently calculate $Q=a^{-1}G$ without a discrete ...
- 71
10
votes
1
answer
1k
views
Cryptographic Secret Santa
Is there a protocol for conducting a Secret Santa without a central authority? Precisely, we want to sample uniformly a permutation that has no one-cycles and reveal to each member his or her ...
- 101
1
vote
1
answer
119
views
Number of iterations required for a transposition cipher to yield the original input
I have asked this question on math.stackexchange.com but received no response; hoping someone on here can help.
Suppose a function $f$, representing what I call a "dynamic transposition cipher" ...
