31 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 ...
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, ...
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, ...
  • 4,273
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 ...
  • 1,605
14 votes
Accepted

Factorization when a factor is partially known

You can use Coppersmith's algorithm [1] (or Howgrave-Graham's [2] simplification) to find the factor, which will be efficient if the number of remaining bits is not too large. The PARI/GP ...
  • 8,446
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,509
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 ...
  • 17.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 ...
12 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 ...
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.4k
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 ...
  • 652
10 votes

Factorization when a factor is partially known

I assume you mean you know the leading 75 digits of a roughly 125-digit factor. Then you can reconstruct the factorization using lattice basis reduction. For an explicit algorithm, see the paper ...
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, ...
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 ...
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 $...
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,...
  • 22.6k
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

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 ...
  • 17.4k
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 ...
  • 23.5k
6 votes
Accepted

"Most Similar Vector Problem" on an Integer Lattice?

Writing up the comment: You just need to "pixelate" the line by finding all lattice boxes that it crosses: Then the answer vector $v$ must connect to one of the corners of the shaded boxes. Instead ...
  • 4,822
6 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 ...
  • 23.1k
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 $...
  • 1,605
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, ...
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 ...
  • 8,851
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$ ...
5 votes
Accepted

Future-Proof Encrypt for Multiple Independent Parties

Using a standard encryption method, let code(i) = encrypt([key(i), message], key(i)) (where [A,B] is concatenation of A and B, with a publicly-known separator), and code = [code(1), code(2), ..., ...
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 ...
5 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 ...
  • 495
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

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$? ...

Only top scored, non community-wiki answers of a minimum length are eligible