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
4
votes
1
answer
288
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 ...
- 218
2
votes
1
answer
170
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 ...
- 63.9k
4
votes
1
answer
448
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 ...
1
vote
1
answer
142
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 ...
- 10.4k
76
votes
13
answers
9k
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,185
0
votes
0
answers
92
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 ...
- 1
4
votes
1
answer
425
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 ...
CommunityBot
- 1
2
votes
1
answer
152
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 ...
- 188k
1
vote
1
answer
138
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_{...
- 5,407
6
votes
1
answer
441
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:...
- 4,991
5
votes
0
answers
317
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}...
- 12.3k
5
votes
1
answer
148
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 ...
- 71
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 ...
- 188k
1
vote
1
answer
119
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" ...
- 34.4k
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 ...
- 25.4k
3
votes
1
answer
293
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 ...
- 215
3
votes
2
answers
162
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
215
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 ...
- 17.6k
23
votes
1
answer
1k
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 ...
CommunityBot
- 1
-3
votes
1
answer
239
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 ...
- 54.2k
2
votes
0
answers
88
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. ...
- 1,583
6
votes
1
answer
304
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 ...
- 13.9k
2
votes
0
answers
275
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 ...
5
votes
1
answer
453
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 ...
CommunityBot
- 1
4
votes
3
answers
5k
views
modular exponentation for RSA, why is 2^16 + 1 commonly chosen?
I know that the number 216 + 1 is commonly used for RSA, since 0b 1 0000 0000 0000 0001 only contains two 1 bits. Many sites explain that this makes modular exponentiation faster, but I haven't come ...
0
votes
1
answer
204
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 ...
CommunityBot
- 1
3
votes
1
answer
344
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 ...
- 10.4k
6
votes
5
answers
6k
views
Analog to the Chinese Remainder Theorem in groups other than Z_n.
The idea hit me when I was in my Elliptic Curve Cryptography class. $Z_n \leftrightarrow Z_{f_1} \times Z_{f_2} \times ...$ where $f_1 \times f_2 \times ... = n$ and $\{f_1, f_2, ...\}$ are pairwise ...
CommunityBot
- 1
15
votes
2
answers
1k
views
Factorization when a factor is partially known
Let's say that I have a very large number of the order ($10^{250+}$) which is composite. I have been given one of its factor partially to a significant amount of digits (say 75+). Then, how can I ...
- 9,114
2
votes
0
answers
60
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 ...
CommunityBot
- 1
1
vote
0
answers
459
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 ...
- 575
8
votes
1
answer
406
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\...
- 188k
4
votes
0
answers
107
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
501
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 ...
- 47.8k
1
vote
1
answer
799
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 ...
CommunityBot
- 1
1
vote
1
answer
92
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 ...
- 125
11
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 ...
- 101
13
votes
2
answers
9k
views
Encrypting a message for multiple recipients
Let $m$ be a secret message that needs to be sent to $n >1$ recipients. Let each recipient $r_i$ have a public key $p_i$ and private key $s_i$. Is there a scheme such that we can encrypt the ...
CommunityBot
- 1
2
votes
1
answer
148
views
Combinations Question about the construction of some special sets [closed]
Let $n$ and $k$ be two given numbers. The goal is to choose $n$ subsets from $\{1,2,...,n\}$ such that the union of any $k$ of these subsets is the set $\{1,2,...,n\}$ and the union of any $m < k$ ...
0
votes
0
answers
57
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
133
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 ...
- 20.2k
1
vote
1
answer
154
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 \...
CommunityBot
- 1
2
votes
1
answer
258
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 ...
CommunityBot
- 1
3
votes
1
answer
383
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 ...
- 25.4k
3
votes
1
answer
164
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 ...
CommunityBot
- 1
9
votes
3
answers
576
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 ...
- 131
-4
votes
1
answer
224
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 ...
- 47.4k
12
votes
2
answers
621
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.
...
CommunityBot
- 1
7
votes
3
answers
896
views
A balls and urns model for a hashing problem
Fix $N \in \mathbb{N}$. Suppose we throw $N$ numbered balls into $N$ numbered urns, so that for each $b \in \{1,\ldots,N\}$, ball $b$ lands in urn $j$ with equal probability $1/N$. Choose a number $c \...
- 3,255
2
votes
1
answer
127
views
Future-Proof Encrypt for Multiple Independent Parties
I have a secret message which I want to encrypt such that any of several different keys can open it independently. The keys can't know about each other and it has to be able to work completely ...
- 54.2k