-3
$\begingroup$

This is a spin-off from Can Big Data attack RSA by just calculating many prime multiplications in advance? [duplicate].

Intro

I am somewhat new to cryptography.

Repeating the basics of RSA from How are the primes used to generate RSA keys?:

Textbooks say the one-way function is merely two primes (with some critical constraints) ...

may be a good base of this question, as well as What prime lengths are used for RSA?. Also, Big data and modern crypto systems already asks the same thing as the question here, but in a more abstract way. And the way primes are actually found is also astonishing. Three other links that were recommended in a comment:

The idea

Take "Big Data" and deep neural networks to get over the boundaries of weight and space.

This question brings in Big Data tricks, in contrast to Is it feasible to build an index of prime factors? which asks for an "index" and which does not take into account the chance of stochastically finding out, in a decentralized system, where the prime factors of a chosen outcome are "stored" (meaning, where the possible calculations to get these primes are stored, since storing the numbers is impossible). Quote from the top answer there:

Let's assume for an instant that you could build a large table of all primes. Then... what ? How would you use it ? What would you look up ?

With Big Data tricks, you would not need to scan one single table index in one place, but you could use a Bloom filter and / or a key coordinator (or other Big Data tricks) showing you the right storage or at least guessing the neural network that could calculate what you search for, graphical trees like Merkle trees, whatever. It may still be a huge problem, but take the mere possible links as the physical storage, and not the static particles that build the universe. When taking the links of dynamic neural networks, so that they could store not the outcome, but the mere possible calculation dependent on the input parameters, you lose that "atomic boundary of the universe".

The question

Can Big Data together with deep neural networks attack RSA by affording the vast calculation of prime multiplications in advance?

PS:

An example of how such neural networks each could become "experts for a parameter range". This does not mean that it has to be like this in the end.

Think of a neural network that is only for prime numbers that are around the square root of the outcome, with the other networks getting a growing bigger gap between the two primes. Think of taking the unknown primes as the problem of reversing a hash function that might be easier if we train neural networks for a chosen range of the outcome number only, and take the examples that we have from real life to train those networks and split them in the right ranges. These changes should also be possible in the parameters and hyperparameters, not just in the mere input or output of the network.

To my understanding, such Big Data managed dynamic neural networks, at least if the activation function is continuous, could carry up to even infinitely many links with just changes in inputs, hidden layers and gradients, so that the final primes are still just calculated in the end, but you find the neural network that can do it using Big Data.

This link about the question whether the brain has more links than the universe has atoms shows that the number of neurons and the number of links do not say the same thing. And indeed, the brain has about 10^15 links, while the universe has about 10^80 atoms, but it is hopefully clear from this that space and weight lose importance as soon as it comes to links instead of static nodes. (EDITED: This was edited after a comment.)

Taking a continuous activation function (linear activation, ReLU) instead of a discrete "yes / no", and taking the continuous "strength of a link" as a "new link" on its own, then in theory, if we could compute with continuous numbers (which we cannot), just one link would already stand for infinite possible kinds of links - and of course a huge network would have infinite links as well, then.

PS2:

If weight and space were the problem, anything smaller and lighter than atoms like light or anything physically almost weightless can build unique patterns that work "like a QR code" which then could use neural networks together with Big Data tricks, but that is not what this question is about since atoms are not believed to be the boundary anyway.

$\endgroup$
4
1
$\begingroup$

A large issue with questions like this tends to be the technical details, so apologies if I come across as particularly nit-picky --- I just do not know how to answer questions like this without pointing out the nits that need to be picked.

at least if the activation function is continuous, could carry up to even infinitely many links with just changes in inputs, hidden layers and gradients

First of all, "continuous" itself can mean many different things within math (to discuss the continuity of a generic function, you have to fix things called "topologies" on the input/output space). I will assume that you mean here that the activation function $f : \mathbb{R}\to\mathbb{R}$ is continuous with respect to the "standard" topology on $\mathbb{R}$, i.e. the topology induced by the metric. If you have taken basic math courses, this is equivalent to the standard $\epsilon/\delta$ notion of continuity.

This already runs into issues, namely that the real numbers behave much more poorly with respect to computation than you might otherwise assume. There is a lot that can be said about this (and I initially wrote out much more), but I think it is all encapsulated with the following "fact" about computation with respect to the real numbers --- namely that for certain rather natural computational models, testing whether $x = 0$ is undecidable. For this reason, while $\mathbb{R}$ is a nice heuristic model of numbers, one cannot hope to work with it computationally in general, so one has to be very careful what one means by "continuous" when discussing computation.

There is a separate issue with respect to information density, namely that in a finite region of space (and using finite energy), there is an upper bound on the amount of information that can be stored. While it is true that one can "encode infinite information" into a real number, this is an argument that they cannot be stored in the real world, rather than for their untapped use for computation.

In summary, while $\mathbb{R}$ is nice to work with mathematically, and can be a nice heuristic model for analyzing computation, it has a number of large flaws if used to encode computations, namely that one cannot:

  1. Do meaningful computation on that encoding
  2. Store that encoding in finite space with finite energy

So the answer to whether (any technique) can allow one to do infinitely many things in the real world is "not according to our understanding of physics". Of course, many techniques can allow one to do a very large number of things, and the distinction between numbers like $2^{256}$ and $\infty$ is often insignificant in real life. But when evaluating things like ideas to store all products of semi-primes in a certain range, computing these bounds becomes quite important to evaluate the feasibility of ideas, and one cannot handwave away the computed bounds via appeals to infinity.


There is a large caveat to the above with quantum computation, as our best understanding of quantum computation is that there are inherently "continuous" aspects to it. I am not an expert in this area, but I imagine the above limitations would kick in as soon as one tries to convert the "continuous" quantum information back to classical information (say via measurements or whatever). Note that quantum computers can already break RSA using Shor's algorithm, so swapping out "neural networks" with "quantum computers" in the above proposal is not a very good way to break RSA (and I would assume that would not work for the aforementioned "conversion between quantum info and classical info" reason).

$\endgroup$
4
  • $\begingroup$ The idea is that neural networks do not need to store the needed values as such within their net, they get trained to be able to calculate them quickly. That means, they only store the ability to compute, in the borders of parameters, but they do not store the values. And "storing" such large amounts of data might then be possible because of the infinite nature of a continuous activation function. Use tricks that pre-cluster the networks. Feed them with the known private / public keys of the world. Play and see what the parameters yield, start with very small test numbers, and grow. $\endgroup$ Mar 25 at 18:07
  • $\begingroup$ The continuous activation function is not the caveat of the question, even if we cannot show a real number with bits (since that would be of infinite length). Instead, we use only what can best be used as nearly continuous numbers and drop the infinite part of it, and add additional layers and even other networks to get near an infinite amount of possible numbers in the end, and that is all that is needed. I guess that this is already possible with just 100 "normal" neural networks, just to say a number. If we could work with real infinity, we would need just one neural network. $\endgroup$ Mar 25 at 18:53
  • 1
    $\begingroup$ @questionto42 For " And "storing" such large amounts of data might then be possible because of the infinite nature of a continuous activation function.", this is impossible by Bekenstein's bound, which is the point of my post. As for "we use only what can best be used as nearly continuous numbers and drop the infinite part of it, and add additional layers and even other networks to get near an infinite amount of possible numbers in the end", this is true, and why people try to quantify the "near infinite" amount, which can be used to show the infeasibility of this idea. $\endgroup$
    – Mark
    Mar 25 at 19:02
  • $\begingroup$ Not fully understanding your last sentence, and without knowing how to do all of this here, I just repeat the idea: That one can parametrize a huge Big Data network of neural networks, each with an expert parameter, and that many networks (with nearly continuous activation functions) together can be used to get enough links to cover the needed 11 x 10^612 2048-bit primes. The values do not get stored, that is why the comment puts it in inverted commas ("storing"). Storing is not possible because then you would need the space again. $\endgroup$ Mar 25 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.