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

- 42.6k

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,271

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

- 152k

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

- 23.6k

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

- 16k

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

### 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 ...

- 11.8k

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

- 141k

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, ...

- 42.6k

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

- 26.7k

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), ..., ...

- 51.7k

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,166

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

- 40.1k

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

#### Related Tags

cryptography × 163nt.number-theory × 52

algorithms × 21

computational-complexity × 21

elliptic-curves × 17

reference-request × 12

co.combinatorics × 12

computer-science × 12

ag.algebraic-geometry × 11

finite-fields × 11

factorization × 11

gr.group-theory × 9

polynomials × 9

computational-number-theory × 8

coding-theory × 8

pr.probability × 7

linear-algebra × 6

lattices × 6

lo.logic × 5

analytic-number-theory × 5

entropy × 4

bitcoins × 4

matrices × 3

soft-question × 3

algebraic-number-theory × 3