4 ms·

> It just seems like this is bound to be useful. If (a) it's hard to find cycles in a graph, and (b) it's not hard to construct a graph with a cycle, that soun

> It just seems like this is bound to be useful. If (a) it's hard to find cycles in a graph, and (b) it's not hard to construct a graph with a cycle, that sounds to me like the makings of a trapdoor function that could be useful in cryptography. [I'm neither a mathematician nor a cryptographer]

foota 2y ago
Nit: It's only hard to find _hamiltonian_ cycles, finding general cycles is trivial. More generally, it's hard to find long simple cycles (a simple cycle is one with no overlapping vertices visited twice). I don't know how hard it is to generate graphs that are hard to find simple cycles in though. For example, previous work showed that random graphs are likely to contain hamiltonian cycles (and with this algorithm they can now be found).
- klyrs 2y ago
  Take your favorite hash function, and view it as inducing a directed graph on the set of its possible outputs. Finding a cycle is hard! (except, most hash functions map 0->0 for "nothing up my sleeves" appeal) But also, it's ridiculously hard to answer simple questions about such graphs, such as listing its nodes.
  - adzm 2y ago
    I can't even think of a hash function that maps 0 to 0
    - adrianN 2y ago
      Since there are uncountably many functions, the functions we can think of have measure zero in the set of all functions.
  - deleted 2y ago
    [deleted]
  - foota 2y ago
    Interestingly, CRC32C is a bijective function over 4 byte integers. More generally, any perfect minimal hashing function could be used to map a set of N integers to the numbers 1 through N.
  - ithinkso 2y ago
    > Finding a cycle is hard! I mean, it is easy in the size of the graph, you constructed implicitly an exponentially large graph, I don't think it's in the spirit of GP point where the hamiltonian cycle is exponentially (in the size of the graph) hard to find
dustfinger 2y ago
> that could be useful in cryptography. See related Neural Cryptography https://en.wikipedia.org/wiki/Neural_cryptography https://en.wikipedia.org/wiki/Neural_cryptography
- denton-scratch 2y ago
  Thanks; interesting. Sounds like it's mainly to do with cryptanalysis and key-exchange.
  - dustfinger 2y ago
    See https://en.wikipedia.org/wiki/Neural_cryptography#Applications https://en.wikipedia.org/wiki/Neural_cryptography#Applicatio... > One example of a public-key protocol is given by Khalil Shihab. He describes the decryption scheme and the public key creation that are based on a backpropagation neural network. Which leads to this paper by Khalil Shihab (2006) https://web.archive.org/web/20070712012959/http://www.scipub.org/fulltext/jcs/jcs29710-715.pdf https://web.archive.org/web/20070712012959/http://www.scipub... > Abstract: In this paper, an efficient and scalable technique for computer network security is presented. On one hand, the decryption scheme and the public key creation used in this work are based on a multi-layer neural network that is trained by backpropagation learning algorithm. On the other hand, the encryption scheme and the private key creation process are based on Boolean algebra. This is a new potential source for public key cryptographic schemes which are not based on number theoretic functions and have small time and memory complexities. This paper along with test results show that the possibility of guessing keys is extremely weaker than using the Data Encryption Standard method (DES), which is a widely-used method of data encryption. The presented results are obtained through the use of MATLAB 6.5.1 software.
    - marvel_boy 2y ago
      > ing the Data Encryption Standard method (DES), which is a widely-used method of data encryption. No, it is not. Today AES is preferred.

foota 2y ago

Nit: It's only hard to find _hamiltonian_ cycles, finding general cycles is trivial. More generally, it's hard to find long simple cycles (a simple cycle is one with no overlapping vertices visited twice). I don't know how hard it is to generate graphs that are hard to find simple cycles in though. For example, previous work showed that random graphs are likely to contain hamiltonian cycles (and with this algorithm they can now be found).

klyrs 2y ago
Take your favorite hash function, and view it as inducing a directed graph on the set of its possible outputs. Finding a cycle is hard! (except, most hash functions map 0->0 for "nothing up my sleeves" appeal) But also, it's ridiculously hard to answer simple questions about such graphs, such as listing its nodes.
- adzm 2y ago
  I can't even think of a hash function that maps 0 to 0
  - adrianN 2y ago
    Since there are uncountably many functions, the functions we can think of have measure zero in the set of all functions.
- deleted 2y ago
  [deleted]
- foota 2y ago
  Interestingly, CRC32C is a bijective function over 4 byte integers. More generally, any perfect minimal hashing function could be used to map a set of N integers to the numbers 1 through N.
- ithinkso 2y ago
  > Finding a cycle is hard! I mean, it is easy in the size of the graph, you constructed implicitly an exponentially large graph, I don't think it's in the spirit of GP point where the hamiltonian cycle is exponentially (in the size of the graph) hard to find

dustfinger 2y ago

> that could be useful in cryptography. See related Neural Cryptography https://en.wikipedia.org/wiki/Neural_cryptography https://en.wikipedia.org/wiki/Neural_cryptography

denton-scratch 2y ago
Thanks; interesting. Sounds like it's mainly to do with cryptanalysis and key-exchange.
- dustfinger 2y ago
  See https://en.wikipedia.org/wiki/Neural_cryptography#Applications https://en.wikipedia.org/wiki/Neural_cryptography#Applicatio... > One example of a public-key protocol is given by Khalil Shihab. He describes the decryption scheme and the public key creation that are based on a backpropagation neural network. Which leads to this paper by Khalil Shihab (2006) https://web.archive.org/web/20070712012959/http://www.scipub.org/fulltext/jcs/jcs29710-715.pdf https://web.archive.org/web/20070712012959/http://www.scipub... > Abstract: In this paper, an efficient and scalable technique for computer network security is presented. On one hand, the decryption scheme and the public key creation used in this work are based on a multi-layer neural network that is trained by backpropagation learning algorithm. On the other hand, the encryption scheme and the private key creation process are based on Boolean algebra. This is a new potential source for public key cryptographic schemes which are not based on number theoretic functions and have small time and memory complexities. This paper along with test results show that the possibility of guessing keys is extremely weaker than using the Data Encryption Standard method (DES), which is a widely-used method of data encryption. The presented results are obtained through the use of MATLAB 6.5.1 software.
  - marvel_boy 2y ago
    > ing the Data Encryption Standard method (DES), which is a widely-used method of data encryption. No, it is not. Today AES is preferred.