Adding a dash of encryption to key algorithms used in artificial intelligence models could 鈥� surprisingly 鈥� make them more efficient, thanks to a trick of mathematics.
Cryptography normally involves scrambling messages to make them appear random to malicious onlookers while preserving their information by hiding a pattern in the randomness. This randomness can then be unlocked with the correct key.
Now, at Tel Aviv University in Israel and at the Massachusetts Institute of Technology have found that a similar use of cryptography can also improve certain algorithms鈥� efficiency by exploiting this 鈥減seudorandomness鈥�. 鈥淚nstead of trying to make this malicious player think that what he鈥檚 seeing is randomness, we are going to try [to] trick an algorithm,鈥� says Zamir.
Advertisement
Many algorithms already use randomness in the form of random matrices, grids of randomly selected numbers that can make problems easier to solve by reducing their size. Zamir and Vaikuntanathan have found that replacing these random matrices with interlopers that only appeared random, called trapdoored matrices, allowed them to be multiplied together more quickly, speeding up algorithms that involve this process without changing the results.
Key to this trick is that, like encrypted messages, the trapdoored matrices can be unlocked with a password, which reveals a pattern to the seemingly random numbers. This pattern serves as a shortcut: the matrices can be multiplied in one go, rather than having to multiply every number by every other number, as would normally be required. 鈥淭his is the difference between a line and a square of the same size,鈥� says Zamir.
These trapdoored matrices could have numerous applications. Machine learning algorithms often use random matrices when they are being trained as part of a tool called a classifier, which is used to distinguish between different data points, such as cats or dogs in images. This involves looking at very large datasets, but the random matrices can help make them smaller.
The pair also found that this trick could help in other areas, such as data compression, which uses random matrices to preserve important features of a dataset while discarding irrelevant data, or searches for similar items, like those used by music recommendation services.
at King鈥檚 College London says using cryptography in this way is a clever trick, but it is likely to only work well in cases where algorithms rely on very large random matrices, because of the way these matrices are designed. 鈥淭hey are solid speed-ups, but you probably need quite big systems to really see it,鈥� says Albrecht. 鈥淭here will be some cool applications, but it鈥檚 not like it will be slotted in everywhere and everything is magically faster.鈥�
arXiv
