When using the Back propagation Algorithm for Machine Learning, it is often said finding the global minimum of a cost function over $\mathbb{R}^n$ is very hard, and as $n$ increases it gets even more complex. I was just wondering if there are any schemes that utilise this property.


If you look at it from the right direction, lattice-based crypto (and the Shortest Vector Problem) can be viewed as a 'global minimization' problem.

| improve this answer | |
  • $\begingroup$ I guess this is the same problem type, however do you think this is a potential problem to base a secure scheme on, as in just minimising or maximising a function globally? $\endgroup$ – John Miller Sep 20 '18 at 17:05
  • 1
    $\begingroup$ @JohnMiller: not really as stated. In crypto, we typically don't rely on things in $\mathbb{R}$ (as there are practical problems with values that cannot be expressed in a finite number of bits). And, approximations to $\mathbb{R}$ (such as floating point) often act subtlety differences (and the differences may be cryptographically important). $\endgroup$ – poncho Sep 20 '18 at 20:43
  • $\begingroup$ @JohnMiller: it's also not clear how you could make a 'trapdoor' out of a general minimization problem... $\endgroup$ – poncho Sep 20 '18 at 20:44
  • $\begingroup$ Well you can make the function public, and it's easy to find local minimum points, I'm right now trying to work on a ZKA for revealing the global minimum point such that it can be revealed without giving it away. $\endgroup$ – John Miller Sep 21 '18 at 12:55

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.