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).
188
questions
76
votes
13
answers
8k
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 ...
- 27.4k
63
votes
8
answers
42k
views
Example of a good Zero Knowledge Proof
I am working on my zero knowledge proofs and I am looking for a good example of a real world proof of this type. An even better answer would be a Zero Knowledge Proof that shows the statement isn't ...
- 649
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 ...
- 24.1k
25
votes
4
answers
6k
views
Discrete logs vs. factoring
One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction ...
- 12.5k
23
votes
5
answers
1k
views
Securing privacy of "who communicates with whom" under Orwell-like conditions
Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...
- 19.3k
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.3k
20
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?
- 281
19
votes
2
answers
2k
views
Bitcoin Research
I have recently been assigned to advise a student on a senior thesis. She has taken linear algebra, introductory real analysis, and abstract algebra. Her interest is in cryptography. And she has a ...
- 812
17
votes
5
answers
952
views
Mathematics of privacy?
I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...
- 10.7k
17
votes
3
answers
23k
views
Which hard mathematical problems do you have to solve to earn bitcoins ?
A virtual currency called bitcoins has been in the news recently. It is said that in order to "mine" bitcoins, you have to solve hard mathematical problems.
Now, there are two kinds of mathematical ...
- 18.4k
16
votes
4
answers
3k
views
Zero-knowledge proof of positivity
If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?
My bounty is ending ...
15
votes
2
answers
921
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
14
votes
3
answers
3k
views
Will quantum computing kill cryptography ? [closed]
I apologize as this question is not really mathematical, and therefore perhaps not
well-suited for this site. Please feel free to close it if you think it is not. My reason
for asking it here is that ...
- 25.6k
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 ...
- 179
12
votes
2
answers
616
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.
...
- 11.5k
12
votes
1
answer
555
views
Are there very strongly pseudorandom permutations?
A pseudorandom permutation can be defined formally as a function $\phi$ from $\{0,1\}^k\times\{0,1\}^n$ to $\{0,1\}^n$ such that for every $x\in\{0,1\}^k$ the function $\phi_x:y\mapsto\phi(x,y)$ is a ...
- 28.5k
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,909
11
votes
5
answers
2k
views
Introducing Cryptology to Undergraduates
This summer I am going to give some lectures to some REU students. I am still tossing around ideas for what I am going to talk about, but one thing I would at least like to give one or two lectures on,...
- 4,762
10
votes
4
answers
1k
views
Number theory in symmetric cryptography
One of the most famous application of number theory is the RSA cryptosystem, which essentially initiated asymmetric cryptography.
I wonder if there are applications of number theory also in symmetric ...
- 111
10
votes
1
answer
736
views
What can I say about the permutation $\alpha\beta$ if I know the permutation $\beta\alpha$?
I'm looking into a secret sharing scheme that has a secret permutation $\theta$ which has the cycle structure (n/2)+(n/2) (i.e. two (n/2)-cycles).
The permutation $\theta$ is decomposed into two ...
- 4,189
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 ...
- 101
10
votes
1
answer
2k
views
Attack on CRT-RSA
The survey paper of Prof. Dan Boneh entitled
"Twenty years of attacks on the RSA cryptosystem" mentioned that (Page 5)
one can attack CRT-RSA in square root of decryption exponent. However no
...
- 125
10
votes
1
answer
539
views
Discrete logarithm for polynomials
Let $p$ be a fixed small prime (I'm particularly interested in $p = 2$), and let $Q, R \in \mathbb{F}_p[X]$ be polynomials.
Consider the problem of determining the set of $n \in \mathbb{N}$ such that $...
- 12.1k
9
votes
3
answers
546
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
9
votes
1
answer
745
views
Any nice examples of small cancellation theory appearing in applied mathematics?
Are there any nice discussions of applications of small cancellation theory, or other cases of the word problem, in applied mathematics or algorithms for seemingly non-group theoretic problems?
I ...
- 555
9
votes
3
answers
3k
views
Reduction from factoring to solving Pell equation
The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims
There are reductions from factoring to solving Pell’s equation, and from solving Pell’s
...
- 24.1k
8
votes
4
answers
1k
views
The "interplay" between additive and multiplicative structure in a field
A field is an ordered triple $(F, +,\cdot)$ of a set $F$ and binary operations $+,\times$ on $F$ such that $(F,+)$ and $(F\backslash 0,\times)$ are abelian groups satisfying the distributive laws
$\...
- 1,933
8
votes
3
answers
709
views
Predicting if something is a code
I'm trying to help a non-mathematical friend by posting a question of his here. He studies literature and has come across a book which is written in a made-up language. The book is hundreds of pages,...
- 265
8
votes
2
answers
378
views
Knot Diffie–Hellman
Here's an idea for a knot-based Diffie–Hellman exchange:
Public: random (oriented) knot $P$.
Private: random (oriented) knots $A$ and $B$.
Exchange: Alice sends (randomized or canonical ...
- 487
8
votes
1
answer
716
views
Is this obfuscation scheme unbreakable?
I've just come across this popular article about a breakthrough (which can be purchased here), published in Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium by a team of ...
- 18.4k
8
votes
1
answer
571
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
8
votes
4
answers
3k
views
Is there a two-party multiplicative and additive secret sharing scheme ?
A secret sharing scheme such as Shamir's secret sharing allow to perform addition and multiplication for secret values so far as there is at least 3 participants. Addition of two secret values is done ...
- 193
8
votes
1
answer
373
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\...
- 27.4k
8
votes
0
answers
1k
views
Question on randomness extractors
Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.
The adversary doesn't ...
- 81
7
votes
3
answers
855
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 \...
- 10.7k
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" ...
- 617
7
votes
0
answers
446
views
Zero-knowledge proofs for answers to the $P=NP$ question
Are there zero-knowledge proofs for every answer to the $P=NP$ question?
For instance, if you have a polynomial-time algorithm of moderate complexity for the graph-coloring problem, then it is easy to ...
- 12.5k
7
votes
0
answers
175
views
Polynomial representation of modular arithmetic in finite fields
Let $n \in \mathbb{N}$ be a predefined integer. Consider the following bijection (between the ring of integers modulo $2^n$ and finite field with $2^n$ elements:
$$ \phi: \mathbb{Z}_{2^n} \to \mathbb{...
- 81
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 ...
- 359
6
votes
1
answer
447
views
Computing the correlation between two vectors without divulging them
Alice and Bob respectively know a vector of $N$ real numbers $u$ and $v$. They would both like to know $\rho = \langle u,v \rangle/N$ but Alice does not want Bob to gain anymore information about $u$ ...
- 1,862
6
votes
1
answer
434
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:...
- 2,879
6
votes
1
answer
291
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.5k
6
votes
1
answer
328
views
Groups in which Computational Diffie Hellman is in $P$ but Discrete Logarithm is not known to be in $P$
The Computational Diffie Hellman (CDH) problem is to compute $g^{XY}$ given $g^X$ and $g^Y$ where $g$ generates the group. The Discrete Logarithm (DLOG) problem is to compute $X$ given $g^X$. The ...
- 13.5k
5
votes
3
answers
926
views
Torus based cryptography
In cryptography one needs finite groups $G$ in which the discrete logarithm problem is infeasible. Often they use the multiplicative group $\mathbb{G}_m(\mathbb{F}_p)$ where $p$ is a prime number of ...
- 1,653
5
votes
1
answer
633
views
A silly question: is the number of points on a Jacobian (of a curve, over a finite field) known?
In a cryptography book I read that people does not known how to compute the number of points on a Jacobian of a hyperelliptic curve $C$ over a finite field $F_q$? Is this true? It seems easy to ...
- 16.3k
5
votes
2
answers
3k
views
Whitening a random bit sequence
Given an (infinite) stream of uncorrelated random bit with a known "reasonable" bias (say 15-85% 1's) I want to whiten it, e.i. produce a shorter stream of bits that has no bias. The restriction is ...
- 151
5
votes
2
answers
470
views
Diffie Hellman cryptography based on graph isomorphism?
We got a cryptographic algorithm and computer implementation
based on graph isomorphism.
An isomorphism between two graphs is a bijection between their vertices that pre
serves the edges.
For a graph $...
- 24.1k
5
votes
2
answers
390
views
Maximum number of vectors with upper bound on pairwise inner products
I have a collection $\{v_1,...,v_k\}$ of vectors in $\{\pm 1\}^n$ with the property that for all $i\neq j$ we have $\langle v_i, v_j \rangle \le c\log_2(n)$. I am looking for an upper bound on $k$ in ...
- 63
5
votes
1
answer
422
views
Fastest algorithm to compute (a^(2^N))%m?
Hi.
There are well-known algorithms for cryptography to compute modular exponentiation $a^b\%c$ (like Right-to-left binary method here : http://en.wikipedia.org/wiki/Modular_exponentiation).
But do ...
- 151
5
votes
1
answer
139
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