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
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
2
votes
2
answers
235
views
On fixed point probability in discrete logarithm
Fix an integer $n>2$.
Question. 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$?
- 13.9k
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, \...
- 11.2k
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 ...
- 149
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 ...
- 39
-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 ...
- 1
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
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. ...
- 21
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 ...
- 560
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 ...
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 ...
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 ...
user91523
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 ...
- 129
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\...
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 ...
8
votes
1
answer
579
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 ...
user6671
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 ...
- 43
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 ...
- 2,967
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 ...
- 215
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 ...
- 16.9k
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 ...
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 ...
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 ...
- 25.4k
3
votes
1
answer
382
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 ...
user76479
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
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 ...
- 61
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 ...
- 379
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 \...
- 2,576
-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 ...
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.
...
- 12.3k
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 ...
- 153
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 \...
- 11.2k
3
votes
1
answer
286
views
PRNG and coding theory
Let $k, n \in \mathbb{N}$, $k = (1 - \epsilon)n$ where $1 >\epsilon > 0$.
I want to find $f: \{0,1\}^k \to \{0, 1\}^n$
such that:
1) $f(a) \not= f(b)$ if $a \not=b $
2) for any $x \in \{0,1\}...
- 2,576
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 ...
- 123
2
votes
0
answers
145
views
Showing that a crypto hash function is not permutation, possibly conditionally?
Let $f$ be some crypto hash function, say MD5 with output $n$ bits. Restrict the input to $n$ bits.
Cryptographer told me it is open problem if such restricted collision
exists, i.e. $f(x)=f(y),x \ne ...
- 25.4k
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$ ...
- 313
2
votes
1
answer
162
views
DL-problem on abelian variety
Let $A$ be an abelian variety over $\mathbb{F_q}$ with dimension $n$. Let $q$ be a constant.
Is there polynomial algorithm of finding discrete logarithm in $A$?
UPD: really I don't undestend: can we ...
- 2,576
7
votes
1
answer
1k
views
Modular polynomials for elliptic curves point counting
The Schoof-Elkies-Atkin (SEA) algorithm (for counting points on elliptic curves over a finite field) performs computations over polynomials modulo some modular polynomials. Originally the "classical" ...
- 647
1
vote
1
answer
204
views
Functional Encryption for Inner Product Predicates
I want to try to implement a functional encryption scheme proposed in http://eprint.iacr.org/2011/410. The first problem I faced with is a TrapGen algorithm. In the paper theorem 3.1 states that:
...
- 113
4
votes
0
answers
264
views
Polynomial dynamical systems
The question is somewhat related to the theory of permutation polynomials. Let $\mathbb{F}_p$ be a finite field of $p$ elements ($p$ is prime) and $\mathcal{V} = \mathbb{F}_p^2 = \{ (t_1,t_2)\::\: t_1,...
- 411
2
votes
1
answer
801
views
Canonical lifts from $\mathbb F_q$ and CM-theory
One knows that (ordinary) Jacobians of hyperelliptic curves over a finite field $\mathbb F_q$ (mostly of genus 1 (elliptic curves) and 2) are extensively studied by cryptographers, as a platform for ...
- 647
2
votes
0
answers
132
views
Genus 2 hyperelliptic cryptography : typical discriminant and class number
As far as I know, there is no standard yet for cryptography based on the DLP over Jacobians of genus 2 curves. Yet, what can we say about the class number, and the discriminant of the complex ...
- 647
0
votes
0
answers
81
views
Encrypting the same message using different schemes
$E_1$ and $E_2$ are IND-CPA secure encryption schemes.
$E$ is defined as:
$k_1,k_2 \leftarrow K_1 \times K_2$ .
$E_{k_1,k_2}(m) \leftarrow E_{1,k_1}(m)||E_{2,k_2}(m)$.
Hope the notations are in an ...
- 1
1
vote
1
answer
205
views
Connection between inf-entropy rate and min-entropy
I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...
- 1,109
2
votes
2
answers
1k
views
Anomalous elliptic curves over finite rings
I was wondering if it is possible to solve the discrete logarithm on an Elliptic Curve E(Z/nZ) (defined over the ring of integers modulo a composite n) with #E(Z/nZ)=n by applying a method analogous ...
- 21
2
votes
0
answers
44
views
largest size for a randomness extractor
I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature.
Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...
- 1,109
2
votes
0
answers
63
views
Private Randomness extractor
Suppose we are given two random variables $X$ and $Y$ with fixed marginal and joint distribution. What is the maximum randomness that we can extract from $Y$ that is independent from $X$, that is, if $...
- 1,109