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

129
questions

**1**

vote

**1**answer

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

**3**

votes

**1**answer

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

**1**

vote

**0**answers

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

**-1**

votes

**2**answers

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

**0**

votes

**1**answer

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

**3**

votes

**0**answers

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

**1**

vote

**0**answers

79 views

### On relationship between cryptography and operator algebras [closed]

Does quantum cryptography connect two different areas of math operator algebras and Cryptography?

**1**

vote

**0**answers

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

**18**

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?

**2**

votes

**0**answers

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

**4**

votes

**0**answers

391 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

63 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

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

**1**

vote

**0**answers

106 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

236 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

116 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

363 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

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

**4**

votes

**1**answer

404 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

95 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

117 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

396 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

242 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

107 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

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

**1**

vote

**1**answer

100 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

17k 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

144 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

139 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

180 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

242 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

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

**72**

votes

**13**answers

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

**2**

votes

**0**answers

86 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

232 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

278 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

165 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

215 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

137 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

244 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

256 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

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

**7**

votes

**1**answer

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

**4**

votes

**2**answers

361 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

2k 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

67 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

965 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

538 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

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