32
votes
Accepted
Cryptography and elliptic curves
Not directly, as far as I know, since explicitly computing large multiples of points in $E(\mathbb Q)$ is infeasible. However, people have considered lifting points from $E(\mathbb F_p)$ to $E(\mathbb ...
- 45.7k
22
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
Have you considered unknotting knots?
The problem would be finding a sequence of Reidemeister moves for a random link graph that reduces it to the unknot. In some cases, no such sequence would exist, ...
- 3,309
18
votes
Accepted
Is hyperelliptic cryptography "practical"?
I am not aware of anybody seriously considering hyperelliptic curves for actual real-world usage, beyond toys, and I would be rather surprised to hear differently from anyone.
As you say, ...
- 5,112
15
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
Calculating the permanent of a small matrix is a computationally challenging problem, as discussed here, here, and here. See also the Wikipedia article.
Given an $n \times n$ matrix $A$, a naïve ...
- 2,143
14
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
Finding cycles in graphs is a standard graph theory problem that lends itself well to proof-of-work. See my Cuckoo Cycle project page at
https://github.com/tromp/cuckoo which has tons of details, as ...
- 1,679
13
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
I find this to be an excellent suggestion, though not sure all requirements can be satisfied. More specifically, 3 and 5 - if we randomly generate instances, then why would they have any intrinsic ...
- 18.4k
13
votes
Cryptographic Secret Santa
Cryptographic Protocols with Everyday Objects (section 5)
Typical cryptographic Secret Santa protocols require a fully
homomorphic encryption system. These protocols are thus suitable for
those ...
- 178k
11
votes
Accepted
What computational problems would be good proof-of-work problems for cryptocurrency mining?
Here is a recent paper, which has been received positively in the cryptocurrency community. I will expand on this paper here.
While conventional hash functions do not allow one to construct very ...
- 27.8k
11
votes
Number theory in symmetric cryptography
The non-linearity in the block cipher AES comes from the pseudo-inversion function on the finite field $\mathbb{F}_{2^8}$, defined by
$$ p(x) = \begin{cases} x^{-1} & \text{if $x \not=0$} \\ 0 &...
- 10.8k
11
votes
Accepted
Number theory in symmetric cryptography
Here are a few interesting examples of symmetric primitives whose claimed security is/was based on number-theoretic problems:
From the 1980s: the famous Blum-Blum-Shub deterministic random bit ...
- 854
10
votes
Accepted
Knot Diffie–Hellman
Here I assume that by “addition” of knots you mean the usual connect sum, as defined here. With that said, I think you correctly ask the relevant question: “Is factoring knots difficult?”
In favour ...
- 26.3k
9
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
Discussion of the prospect of a cryptocurrency based on cellular automata prompted me to start developing the Catagolue project in the summer of 2014. The proof-of-work system was deliberately chosen ...
- 12.2k
9
votes
Accepted
Is this obfuscation scheme unbreakable?
"Is this obfuscation scheme unbreakable?"
"Well.. no." said people a couple of years later.
On GGHRSW13 specifically: Cryptanalyses of Candidate Branching Program Obfuscators
See also (concurrent, ...
- 238
9
votes
Is strictly harder than NP-hard cryptography possible?
I think I may not understand your model of cryptography. My model would be that encryption is a polynomial time computable, injective, function from plaintexts of length $m$ to cipher texts of length $...
- 151k
7
votes
Accepted
Zero knowledge proof of equality
In typical mathematician fashion, let me explain how to reduce your problem to a harder one ☺, namely homomorphic encryption. (Edit: I should have made it clear that the problem of constructing ...
- 30.1k
7
votes
Accepted
Inverting a function
Yes, you can use the Lehmer-Permutation to make a function that is suitable for cryptography, whose solution is just as hard as the Diffie-Helman problem. The relevant papers are:
(1) Roberto Mantaci,...
- 29.8k
7
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
Let me have another go, because I really love this question. Essentially it's like a SETI@home project - without going into details, let's just consider the theoretical model that some signals arrive ...
- 18.4k
7
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
I don't see how you will have a problem which is progress free but still in NP(requirement 7); or any kind of problem that is suitable for your purpose for that matter. To see why this seems unlikely ...
- 179
7
votes
Conjecturally unsafe RSA primes $p=27a^2+27a+7$
This appears special case of "A New Special-Purpose Factorization Algorithm":
https://pdfs.semanticscholar.org/1843/73605e846f90b0a9d7252931bab4c47a1ec7.pdf
From the abstract: a new factorization ...
- 24.2k
6
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
Has anyone considered improving a best lower bound on $\Omega_U$ by finding small programs $p_i$ that halt, where $\Omega_U$ is a Chaitin halting probability of a universal prefix-free Turing machine $...
- 2,143
6
votes
Zero knowledge proof of equality
This partial answer is from an information theoretic perspective: This cannot be done with small number of rounds of talking. Suppose the players receive a number between 1 and $n$ and they want to ...
- 505
6
votes
Extending Vigenère method using arbitrary function
Suppose that I create a list of intgers $(a_1,a_2,a_3,\dots)$, where the $0\le a_i<26$ are chosen randomly, e.g., using quantum effects or micro-temperature changes. Then I share the list with you, ...
- 45.7k
6
votes
Number theory in symmetric cryptography
The book Stream Ciphers and Number Theory by Cusick, Ding and Renvall is devoted to this topic, stream ciphers being one kind of symmetric cipher. I give some examples from there that are not that ...
- 10.1k
6
votes
Accepted
On roots of irreducible quadratics modulo composites
Ability to find all roots leads to finding factorization of $N$. For example, if $N=pq$ is a product of two odd primes, and we find a root $x'$ of $x^2-1\equiv 0\pmod N$ such that $x'\equiv 1\pmod p$ ...
- 30.6k
5
votes
Which hard mathematical problems do you have to solve to earn bitcoins ?
Another way to earn bitcoin is not to mine them, but to have them wired to you from other bitcoin accounts. The transactions are signed using ECDSA. So if you solve the discrete logarithm problem in ...
- 1,186
5
votes
Zero knowledge proof of equality
You are asking the socialist millionaire problem. There are several solutions to the problem, amongst them the one showed on the Wikipedia page, using the Diffie–Hellman-Merkle key exchange for secure ...
- 151
5
votes
Accepted
Are there any unitary matrices which satisfy the Yang-Baxter equation which are universal for quantum computation?
Braiding Operators are Universal Quantum Gates, by Louis Kauffman and Samuel Lomonaco (2004)
In this paper, we prove that certain solutions to the Yang-Baxter equation together with local unitary ...
- 178k
5
votes
Accepted
Breaking the RSA encryption based on a $(e,N)$ given an integer $w \neq 0$ such that $e^w = 1 \mod(N)$?
I think you got confused by the somewhat peculiar notation. Krajíček actually writes on p. 155 that one can break the given instance of RSA using $w\ne0$ such that
$$g^w=1\pmod N.$$
Now, what is $g$? ...
- 44.7k
5
votes
Using High Level Probability Theory (eg Markov Chain Mixing) in Cryptography/Cryptanalysis
Dr. Ben Morris from UC Davis has a research program on mixing times of Markov chains applied to cryptography, in particular the Thorp shuffle (a method of card shuffling based on "local swaps" that ...
- 178k
5
votes
Accepted
Breaking the rotate-then-substitute alphabetic cipher
As you point out, frequency analysis will yield (for cipher texts long enough, say longer than Shannon's unicity distance) a non-English text which has been transformed from English via the position ...
- 10.1k
Only top scored, non community-wiki answers of a minimum length are eligible