# 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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**13**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**5**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**3**answers

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

**1**answer

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

**1**answer

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

**2**answers

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