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).
2
votes
0answers
43 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)...
1
vote
1answer
51 views
encryption with wavelet transform
I need to know about an article, book or other reference that deals with encryption using Fourier transform and the Wavelet. (I plan to use matlab or other recommended software.)
0
votes
1answer
262 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 ...
0
votes
0answers
103 views
Does Coppersmith technique suffice to factor?
Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$. Is there evidence that no extension of Coppersmith technique will accomplish factoring $N=PQ$ in polynomial time?
Technically I am ...
1
vote
0answers
50 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 ...
4
votes
1answer
219 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 ...
1
vote
1answer
106 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 ...
4
votes
1answer
330 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 ...
0
votes
0answers
83 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 ...
4
votes
1answer
390 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 ...
2
votes
1answer
91 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 ...
1
vote
1answer
102 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_{...
6
votes
1answer
376 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:...
5
votes
0answers
218 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}...
5
votes
1answer
105 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 ...
10
votes
1answer
984 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 ...
1
vote
1answer
91 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" ...
44
votes
1answer
16k views
Conjecturally unsafe RSA primes $p=27a^2+27a+7$
We got strong numerical evidence that primes of the form $p=27a^2+27a+7$
are unsafe for cryptographic purposes since they can be found in the factorization.
Consider the following generic factoring ...
2
votes
2answers
134 views
On fixed point probability in discrete logarithm?
Given integer $n>2$ 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$?
3
votes
2answers
135 views
Breaking the rotate-then-substitute alphabetic cipher
My question is not typical for MathOverflow, and arises in my teaching rather than research, but I think there will be readers who can give interesting answers.
Identify $\{\mathrm{A}, \ldots, \...
3
votes
0answers
175 views
Why we are interested in p>3 Schoof's algorithm
In the Schoof's algorithm we are particularly interested in $char(K)>3$, where $K$ is the field. I know Schoof's algorithm is mostly used over large prime fields. Also, when we are transforming ...
3
votes
1answer
209 views
Zero Knowledge Proof - Offline Information [closed]
I've been reading about Zero Knowledge Proofs with some interest, but I'm still unclear if it can be used to solve my real-life problem.
I'm wondering if someone can help me understand a little ...
-3
votes
1answer
154 views
SAT problem in Gödel numbering [closed]
I am working on a cryptography project and I have come up with this problem.
Let's say I have a boolean expression L with $k$ variables $A_{1},..., A_{k}$. Let's assume this boolean expression is ...
67
votes
13answers
4k views
What computational problems would be good proof-of-work problems for cryptocurrency mining?
What computational mathematics problems that could be used as proof-of-work problems for cryptocurrencies? To make this question easier to answer, I want proof-of-work systems that work in ...
1
vote
0answers
58 views
Varieties with potential key exchanges
I am looking for varieties $V$ that satisfy an identity of the form
$$f(\mathbf{a},g_{1}(\mathbf{b},\mathbf{x}),...,g_{m}(\mathbf{b},\mathbf{x}))
=r(\mathbf{b},s_{1}(\mathbf{a},\mathbf{x}),...,s_{n}(\...
2
votes
0answers
84 views
Example of action of an infinitely countable group that has important ergodic/statistical property?
I work in probability and I am looking for an important example of action of an amenable countable group in other areas of math for which the (pointwise) ergodic theorem is actually quite important. ...
2
votes
0answers
203 views
Is conjugacy problem hard in braid group?
Recently I studied the braid group and conjugacy problem. It is believed that conjugacy problem is hard on braid group. My friend gave me an EXE file, and I use it for solving conjugacy problem, as an ...
3
votes
1answer
229 views
Using High Level Probability Theory (eg Markov Chain Mixing) in Cryptography/Cryptanalysis
I'm currently doing a PhD in probability theory, specifically (discrete space) Markov chains and their mixing properties. As well as my current main project, I'm looking to have a side project, eg to ...
0
votes
1answer
148 views
Prime divisors on the Jacobian of a genus 2 curve over $\mathbb{F}_q$ under the $n$ map
Let $H$ be a hyperelliptic curve geometrically irreducible of genus 2 over $\mathbb{F}_q$ with a rational point $\infty$ given by the model $y^2=f(x)$, where $f$ is monic of degree 5.
Consider the ...
3
votes
1answer
192 views
The best linear approximation of a random function
Let $\mathcal{F}_n$ be the set of all boolean functions of $n$ variables and let $\xi$ be a random variable with values in the set $\mathcal{F}_n$ with the uniform distribution. We define a new random ...
2
votes
0answers
59 views
A question related to Boolean functions? [closed]
Let $Z_2=\{0,1\}$, $Z_2^r=Z_2\times Z_2 \times...\times Z_2,$ $S_1\subset Z_2^{n_1}$ and $S_2\subset Z_2^{n_2}$, $S=(S_2,S_1)\subset Z_2^{n_1+n_2}$, I'd like to construct $S_1$ and $S_2$ s.t the ...
2
votes
1answer
109 views
How to enumerate the extended affine equivalence classes of bent functions of degree 4 in 8 variables?
"There are 536 class of quartic forms Q (header) [in 8 boolean variables] providing bent functions of the form Q+f where f is a cubic functions."
Philippe Langevin, 2008.
What is the current ...
1
vote
0answers
183 views
Textbook on Cryptography [closed]
I am proposing (and will be teaching next year) a new math elective on Cryptography in our curriculum here at Illinois State University. In addition to standard topics including RSA public key and ...
8
votes
1answer
221 views
Are there any unitary matrices which satisfy the Yang-Baxter equation which are universal for quantum computation?
Let $H$ be a finite dimensional hilbert space. Let $L:H\otimes H\rightarrow H\otimes H$ be a unitary transformation. Then the equation
$$(L\otimes I)(I\otimes L)(L\otimes I)=(I\otimes L)(L\otimes I)(I\...
4
votes
0answers
94 views
Do the normal forms for braid groups really conceal information about better than randomly applying the braid relations?
In braid based cryptography, one typically wants to conceal the way a certain braid $b$ has been obtained. One therefore puts $b$ into some normal form. Since every braid has a unique normal form, the ...
4
votes
2answers
349 views
Breaking the RSA encryption based on a $(e,N)$ given an integer $w \neq 0$ such that $e^w = 1 \mod(N)$?
In his book 'Forcing with Random Variables and Proof Complexity' Jan Krajíček claims (p.154) that it is possible to break the RSA encryption with public key $(e,N)$ if one has has an integer $w \neq ...
10
votes
5answers
1k views
Zero knowledge proof of equality
Alice and Bob each secretly chooses an integer between 1 and 10, a and b. They want to know (with high probability) whether or ...
1
vote
1answer
62 views
Dual lattices up to a q scaling factor
In this paper : https://eprint.iacr.org/2011/501.pdf
There is an equality page 10, in the second paragraph considered by the authors as "easy to check". If someone could explain to me why the set at ...
22
votes
1answer
808 views
Is hyperelliptic cryptography “practical”?
Previosly my impression on this subject was that hyperelliptic cryptography systems (as well as other possible cryptosystems based on abelian varieties of dimension $>1$) have no advantages over ...
1
vote
1answer
405 views
Finding cyclic subgroups of points on elliptic curves for isogeny based cryptography
Isogeny based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is a theorem:
Elliptic curves ...
0
votes
0answers
47 views
lower bound for solve ECDLP
Let $P$ and $Q$ are two points of NIST elliptic curve $E$ (defined over $F_{2^m}$ with prime $m$) and $k$ is a private key such that $k.P=Q$. Suppose $\ell$ be the number of bits in $k$, and let $k_i$ ...
1
vote
1answer
85 views
Reduced echelon form of sparce matrices and constructing hash function
Let $G$ be a $d$-regular graph, and $A$ be the incidence matrix of $G$. Also suppose $B$ is a reduced echelon form of $A$ such that computations are in $\mathbb F_2$. Given matrix $B$, can we find ...
2
votes
1answer
180 views
Does this modification of the General Number Field Sieve factor integers?
The General Number Field Sieve
factors composite $n$ basically this way.
Select homogeneous polynomials with integer coefficients $f(x,y),g(x,y)$
s.t. $f(x,1),g(x,1)$ have common root modulo $n$ but ...
3
votes
1answer
191 views
Equivalence between Diffie Hellman and Discrete Log
For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?
Is there any group for which we suspect them to be different?
Could there be a finite ...
6
votes
1answer
240 views
Shortest vector problem over polynomials
In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult.
Answer in Evidence for integer factorization ...
2
votes
1answer
123 views
Mestre-type algorithm for higher-genus curves?
Is there an analogous algorithm for genus $g>2$ curves that, given a complete set of invariants, outputs a curve with those invariants?
(I'm interested in particular in $g=3$.)
Any references ...
9
votes
3answers
440 views
“Most Similar Vector Problem” on an Integer Lattice?
I am currently working on problem that I think could be expressed as an integer lattice problem.
Given $u \in \mathbb{R}^n$ and a bounded integer lattice $L = \mathbb{Z}^n \cap [-M,M]^n$ I would like ...
1
vote
1answer
94 views
Optimal covering and CSPNG
Consider a function $f: \{0,1\}^n \to \{0,1\}^{cn}$, where $c>1$.
A random $f$ with high probability generates optimal covering of $\{0,1\}^{cn}$,
i. e.:
$\forall x \in \{0,1\}^{cn}$ $\exists y \...
-4
votes
1answer
165 views
Elliptic Curve Multiplication [closed]
What would happen if I performed Elliptic Curve multiplication on some random point within the FiniteField that wasn't actually on the curve? I assume that I would get a point in return but would that ...
11
votes
2answers
573 views
“The Two Sheriffs” puzzle -2: threshold for security
I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects.
...
