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
3
votes
0
answers
151
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 ...
- 10.4k
2
votes
1
answer
172
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?
- 13.9k
4
votes
1
answer
309
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....
- 10.4k
8
votes
1
answer
723
views
Is this obfuscation scheme unbreakable?
I've just come across this popular article about a breakthrough (which can be purchased here), published in Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium by a team of ...
- 2,821
6
votes
1
answer
566
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 ...
- 25.4k
-1
votes
1
answer
186
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-...
- 12.9k
0
votes
1
answer
123
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 &...
- 879
6
votes
1
answer
418
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 ...
- 2,183
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 $...
20
votes
2
answers
2k
views
Bitcoin Research
I have recently been assigned to advise a student on a senior thesis. She has taken linear algebra, introductory real analysis, and abstract algebra. Her interest is in cryptography. And she has a ...
3
votes
3
answers
4k
views
Recovering $\Phi(n)$ from a multiple?
I've been attending a series of lectures on Cryptography from an engineering perspective, which means that most of the assertions made are supplied without proof... here's one that the lecturer couldn'...
9
votes
1
answer
756
views
Any nice examples of small cancellation theory appearing in applied mathematics?
Are there any nice discussions of applications of small cancellation theory, or other cases of the word problem, in applied mathematics or algorithms for seemingly non-group theoretic problems?
I ...
- 35.5k
2
votes
2
answers
740
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 ...
- 10.4k
17
votes
3
answers
23k
views
Which hard mathematical problems do you have to solve to earn bitcoins ?
A virtual currency called bitcoins has been in the news recently. It is said that in order to "mine" bitcoins, you have to solve hard mathematical problems.
Now, there are two kinds of mathematical ...
CommunityBot
- 1
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 ...
- 1,127
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 ...
CommunityBot
- 1
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$ ...
- 12.9k
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 ...
- 34.4k
2
votes
2
answers
235
views
On fixed point probability in discrete logarithm
Fix an integer $n>2$.
Question. What is the probability that, for a given $h\in\Bbb Z_n,$ there is no $$x\in[0,\varphi(n)-1]\cap\Bbb Z$$ such that
$h^{x\bmod\varphi(n)}\equiv x\bmod n$?
- 66.3k
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?
- 12.3k
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
10
votes
1
answer
638
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 $...
- 1,362
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 ...
- 63.9k
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
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, ...
- 879
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 ...
- 4,943
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
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 ...
- 879
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
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$."
...
- 85.6k
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
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
2
votes
1
answer
316
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 ...
- 34.4k
0
votes
0
answers
262
views
Lattice basis reductions and finding minimal values
While reading several articles about lattice basis reduction I am left with a few questions.
For one, I came across this piece of text
Let $\alpha$ and $\beta \in \mathbb{R}$. Also let $X>0$ and $...
- 4,713
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)$ ...
- 63.9k
-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)...
- 1
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 ...
- 7,059
8
votes
1
answer
579
views
Inverting a function
I posted this question on crypto.SE but got no answer:
Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$
Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-i} } $ be the ...
- 30.3k
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 ...
- 3,486
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?
- 7,377
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
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 $...
CommunityBot
- 1
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
3
votes
1
answer
286
views
PRNG and coding theory
Let $k, n \in \mathbb{N}$, $k = (1 - \epsilon)n$ where $1 >\epsilon > 0$.
I want to find $f: \{0,1\}^k \to \{0, 1\}^n$
such that:
1) $f(a) \not= f(b)$ if $a \not=b $
2) for any $x \in \{0,1\}...
- 10.4k