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

Filter by
Sorted by
Tagged with
1
vote
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
1answer
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
13answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
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
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
5answers
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
1answer
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
1answer
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
1answer
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
0answers
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$ ...