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 ...
- 47.4k
25
votes
Accepted
A cipher proposed by Littlewood
Littlewood's cypher is a one-time-pad, which would be unbreakable if fed by a true random number generator, but Littlewood's pseudo-random number generator is broken. See Breaking Littlewood's cypher ...
- 188k
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,359
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,185
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,734
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 ...
- 188k
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.7k
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 &...
- 11.2k
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 ...
- 879
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 ...
- 28.1k
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.4k
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 $...
- 156k
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 ...
- 25.4k
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,...
- 30.3k
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.7k
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
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,185
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, ...
- 47.4k
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.4k
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$ ...
- 34.3k
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,196
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 ...
- 188k
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.4k
5
votes
Accepted
How to compute the Müller modular polynomials?
The definition of the coefficients $a_{r,k}$ is given by theorem III.17 on page 53 of "Elliptic curves in cryptography" by I.F. Blake, G. Seroussi, N.P. Smart (Cambridge University Press, 1999) (also ...
- 5,407
5
votes
A p-adic logarithm as a limit of discrete logs
For $p\ge 3$ if $g$ is a generator of $(\Bbb{Z}/(p^2))^\times$ then it is a generator of all $(\Bbb{Z}/(p^k))^\times$. For $a\in \Bbb{Z}_p^\times$ there is a unique $l_{g,k}(a)\in \Bbb{Z}/(p-1)p^{k-1}...
- 3,403
5
votes
Are there trapdoor functions breakable by moderate polynomial degree complexity algorithm?
Q1 goes right back to the dawn of public-key cryptography, with Merkle's Secure communications over insecure channels (see also Merkle's historical note on this). Merkle showed that running this ...
- 879
5
votes
Accepted
Proving that a function is a trapdoor function
First, there is a site crypto.stackexchange.com that is typically better for questions like this.
Second,
Coming from a CS background, if I wanted to prove a problem was NP-hard, I would try to prove ...
- 2,183
5
votes
Knot Diffie–Hellman
Edit: Thanks to @SamNead, for pointing out that the conjugacy problem is polynomial time, albeit with horrible constants. See video here
There is some literature on Braid group cryptography.
Here is ...
- 10.4k
Only top scored, non community-wiki answers of a minimum length are eligible