31

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 Q)$ or to the $p$-adics $E(\mathbb Q_p)$ in order to devise algorithms to solve the discrete log problem in $E(\mathbb F_p)$ (although, unsuccessfully so far). ...

answered May 9 '19 at 11:45

Joe Silverman

39.3k22 gold badges114114 silver badges202202 bronze badges

27

Bitcoin mining is based on hash functions. Specifically the SHA-256 hash function, which maps arbitrary bit strings to 256-bit outputs in such a way that nobody knows how to find a collision (two inputs with the same output), although the pigeonhole principle implies collisions exist. Bitcoin mining doesn't involve finding collisions, which would be way too ...

22

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, but most random graphs are known to be unknotted under certain knotting algorithms: http://iopscience.iop.org/article/10.1088/1751-8113/49/40/405001/meta
...

20

Here is an example of the type you appear to be seeking. The story -- like many good stories -- involves a million dollar prize offered by a billion dollar corporation, sought by armies of computer wizards. There's even a courtroom scene at the climax.
In 2007, Netflix released a dataset consisting of roughly a hundred million movie ratings (from 1 through ...

18

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, hyperelliptic provide comparatively few (if any!) advantages over elliptic curves but have the huge disadvantage that virtually nobody has well-tested, battle-hardened ...

17

Let us assume that everybody uses the same asymmetric encryption system (such as PGP), with keys that are so large that Big Brother cannot crack them.
If Alice wants to send a message to Bob, she encrypts it with Bob's public key and broadcasts it to everybody. All of Alice's friends will use their own private keys to decrypt the message, but only Bob will ...

16

This question seems a bit vague, but one answer is that there are cryptosystems such as NTRU that are based on (special cases) of the closest vector problem (CVP). At present, quantum computers would not significantly speed up the solution of the CVP. If I understand correctly, they would require doubling the length of the keys.
Disclaimer: Jeff Hoffstein, ...

answered Apr 20 '13 at 17:00

Joe Silverman

39.3k22 gold badges114114 silver badges202202 bronze badges

15

Let's assume that the secret service can view all transmitted messages and how they are routed, but has no access to anyone's private computer, since otherwise privacy clearly cannot be guaranteed.
There's still no way to mathematically guarantee privacy in any realistic way. One big problem is traffic analysis: the secret service can try to correlate when ...

15

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 calculation of $\text{perm}(A)$ using the definition may require $|S_n|=n!$ multiplications. One of the best known algorithms is Ryser’s formula [Rys63], based on ...

14

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 documentation
http://pari.math.u-bordeaux.fr/dochtml/html-stable/Arithmetic_functions.html#zncoppersmith
has an explicit example. Coron, Faugère, Renault, & Zeitoun [...

14

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 well as bounties for improving the currently best implementations.
Of course, the specific pseudo-random graphs generated in Cuckoo Cycle have no practical use ...

13

There is a very good book that you can find your answer there completely. This book's name is:
"Post-Quantum Cryptography" by "Daniel J. Bernstein, Johannes Buchmann and Erik Dahmen".
As a part of this book, today we know that these cryptosystems can be broken by quantum computers:
$1)$ RSA public key encryption
$2)$ Diffie-Hellman key-exchange
$3)$ ...

13

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 value? Would factoring large integers have any intrinsic value?
One example that I can think of is chess endgames. There is a growing database of which positions ...

13

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 with some planning, some expertise and access to computational
assistance, but not to a group of friends without access to computers.
Here we present an ...

answered Dec 18 '17 at 21:04

Carlo Beenakker

128k1212 gold badges314314 silver badges445445 bronze badges

12

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 useful proof-of-work problems, if one replaces the hash function for the proof-of-work with a randomizing function specifically designed to be computed by ...

answered May 29 '17 at 17:59

Joseph Van Name

19.8k33 gold badges5454 silver badges8585 bronze badges

11

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 & \text{if $x=0$.}\end{cases} $$
It is a nice exercise to show that $p$ is as strong as possible against the difference attack. That is, given any non-zero $\...

11

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 generator is a classic example. Let $N = pq$ be the product of two large safe primes, and consider the sequence defined by $x_{i+1} = x_i^2 \pmod{N}$, where $x_0$ is ...

10

Another interesting topic is on performing computation on encrypted data. For example, you can have your data encrypted and yet use cloud services on them. There are mathematicians and computer scientists working on this, however the current constructions are not efficient enough for practical purposes yet (AFAIK).
The keyword to search for is Homomorphic ...

10

The mathematics of privacy is a HUGE area of research. It started in the statistics community way back when, with issues of disclosure along the lines of what Vidit Nanda mentioned. In the 90s, things exploded in the CS community when a researcher at CMU first showed that using only publicly disclosed information she could retrieve private information about ...

10

there is a nice preprint server, widely used by cryptographic researchers: http://eprint.iacr.org
If you do a search, there are some papers talking more or less about bitcoin. I guess "Decentralized anonymous credentials" is a good begin for your student. This is indeed a well known area of research, and is the main point of bitcoins (with mining).
You may ...

10

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 Small solutions to polynomial equations, and low exponent RSA vulnerabilities
by Coppersmith. All it requires is that the number of digits you know of a factor is ...

9

"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, similar flavor):
Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13
Zeroizing Attacks on Indistinguishability Obfuscation over CLT13
...

9

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 to enable a cryptocurrency to be built upon it:
Given a string $S$, find some string $T$ such that the $16 \times 16$ pseudorandom pattern $f(S+T)$ yields ...

answered Jul 31 '17 at 19:20

Adam P. Goucher

11.3k22 gold badges4545 silver badges8787 bronze badges

9

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 $n$, and decryption is inverting this function. In that case, such a problem will always be in NP.
Indeed, we must have $m \leq n$, since we require that ...

answered Sep 21 '20 at 12:23

David E Speyer

130k1010 gold badges339339 silver badges644644 bronze badges

8

Most of the examples given above are nice textbook examples of ZK proofs meant for students. Here's something I'd call more a "real life" example. Assume that Alice has a secret key $x$ and public key $y = g^x$. (Here we assume that $g$ generates a group $G$ of size $p$, for large prime $p$.) She wants to convince Bob that she knows $x$ without revealing $x$....

7

There is a web site and conference series on post-quantum cryptography, leading up to Bernstein et al's book mentioned by Shahrooz. See:
http://pqcrypto.org/

7

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 lets consider the solution space for your problem as I start and when I have progressed in an arbitrary algorithm that searches the solution space.
when I ...

7

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 from a source that is sufficiently random and then we have to do some computation on it to get some data. (If you prefer groundhogs to E.T., the weather ...

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 algorithm is presented, which finds a prime factor $p$ of an integer $n$ in time $(D \log{n})^{O(1)}$, if $4p - 1 = Db^2$
If $p=27a^2+27a+7$ we have $4p-1=3\...

6

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 of first collecting the boxes, try the following zig-zag algorithm: start from the origin and poll the up and right nearest lattice points. One of them is closer ...

nt.number-theory diophantine-approximation global-optimization cryptography combinatorial-optimization

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

#### Related Tags

cryptography × 148nt.number-theory × 47

algorithms × 17

elliptic-curves × 17

computational-complexity × 16

co.combinatorics × 12

computer-science × 11

factorization × 11

ag.algebraic-geometry × 9

finite-fields × 9

gr.group-theory × 8

coding-theory × 8

reference-request × 7

pr.probability × 7

polynomials × 7

linear-algebra × 6

lattices × 6

analytic-number-theory × 5

computational-number-theory × 5

lo.logic × 4

bitcoins × 4

soft-question × 3

algebraic-number-theory × 3

prime-numbers × 3

arithmetic-geometry × 3