3
$\begingroup$

Recall that the Toffoli gate is the mapping $T(x,y,z)=(x,y,(x\wedge y)\oplus z)$. We shall say that a function $T$ is Toffoli-like if $T(x,y,z)=(x,y,((a\oplus x)\wedge(b\oplus y))\oplus z\oplus c)$ for some $a,b,c\in\{0,1\}$.

Suppose that our key is $m$ bits and the message we want to encrypt $\mathbf{x}$ is $n$ bits. Let $C$ be a circuit on the $m+n$ bits consisting of Toffoli-like gates which are selected at random where either the target is always in the $n$ message input bits or both the control and the target are in the $m$ key bits. Then for each key $\mathbf{b}$ there is some $\mathbf{c}$ along with functions $D_{\mathbf{b}},E_{\mathbf{b}}$ (the encryption and decryption functions) such that $(\mathbf{c},E_{\mathbf{b}}(\mathbf{x}))=C(\mathbf{b},\mathbf{x})$ and $(\mathbf{b},D_{\mathbf{b}}(\mathbf{x}))=C^{-1}(\mathbf{c},\mathbf{x})$.

Is there any symmetric encryption system similar to the above cryptosystem which has been deeply studied or is already in use?

If so, then how does such a cryptosystem compare against the AES or another symmetric cryptosystem?

If there is no such cryptosystem available, then what weaknesses do such cryptosystems have and why are they not in use?

Will such a randomly generated symmetric encryption system be practical once super efficient reversible computers or partially reversible computers hit the market?

In this paper, it takes 109664 reversible gates to implement the 128 bit key AES. By comparison 100,000 Toffoli gates seems to be more than sufficient when one randomly applies Toffoli and Fredkin gate, so I am wondering why this randomly generated symmetric cryptosystem is not in use.

|improve this question
$\endgroup$
  • $\begingroup$ I am still relatively new to crypto.stackexchange, so let me know if this question is a good fit for this site. $\endgroup$ – Joseph Van Name May 12 '17 at 22:05
  • $\begingroup$ Shouldn't your second function have $c$ as an input as well? $\endgroup$ – kodlu May 12 '17 at 22:31
  • 1
    $\begingroup$ This is fascinating to me, I hope someone will do research on this class of ciphers. It is worth noting that you do not need to extend the you do not need the more powerful version of Toffoli gates: you can toggle x or y with a gate with a True control bit, apply the gate that changes z, then toggle x and y back. $\endgroup$ – yberman Dec 29 '17 at 20:20
1
$\begingroup$

It seems plausible that one builds a symmetric encryption system competitive with AES by randomly applying Toffoli(-like) gates as restricted in the question. I do not know that it has been studied.

Paraphrasing the question, it constructs a block cipher with 128-bit block and 128-bit key similar in function to AES-128 as follows:

  • number inputs as $b_i$ with $0\le i<128$ for block bits and $128\le i<256$ for key bits
  • repeat $r$ times
    • pick random distinct indices $i,j,k$ with $(k\ge128)\implies(i\ge128)\wedge(j\ge128)$
    • apply a random Toffoli-like gate to $(b_i,b_j,b_k)$

In the end, the result is the 128-bit $x_i$ with $0\le i<128$. The rule $(k\ge128)\implies(i\ge128)\wedge(j\ge128)$ insures that for any fixed key, the block cipher is reversible.

Seen from far away with blurry vision, there are similarities between this construction and AES-128: both are iterated permutation-substitution ciphers with reversible key transformation along the rounds, and 256 variables. If we chose $i$, $j$, $k$ randomly until acceptable, a key bit is chosen as $z$ (the potentially changed bit) with odds about $1/5$, which grossly mimics AES spending significantly less computational effort on key scheduling than on data encryption.

I do not know the number of rounds $r$ making the block cipher secure; nor a technique to derive this. But I would not be astonished if it was markedly lower than $100000$.

|improve this answer
$\endgroup$
0
$\begingroup$

I am not aware of any such cipher. To begin with you seem to be asking two questions which are kind of at cross-purposes.

One, the linked paper has shown that AES can be implemented this way by reversible gates. This would be a case of using classical implementation of a quantum gate to build a classical cipher, AES. The authors of that paper are not clear what the purpose of this is, since it is very inefficient in gate count.

What if you built AES out of actual quantum gates? This would be, I guess, even less efficient.

The second question is if it is possible to select such gates randomly and generate some symmetric cryptosystem with properties hopefully comparable to AES. But, in the worst case, you may randomly get a very weak cipher, and there may be no way to provably guard against this.

As for your last paragraph:

it takes 109664 reversible gates to implement the 128 bit key AES which appears to be much more than sufficient when one randomly applies Toffoli and Fredkin gate, so I am wondering why this randomly generated symmetric cryptosystem is not in use.

A quick skim of the paper left me with the impression that this system was not randomly generated.

|improve this answer
$\endgroup$
  • $\begingroup$ It is of course dependent on speed but the data sheet below suggests counts as low as 16,000 gates are possible and commercially available. heliontech.com/downloads/aes_asic_helioncore.pdf $\endgroup$ – kodlu May 12 '17 at 22:57
  • $\begingroup$ 16,000 seems more reasonable, but even when I tried randomly applying 10000 or so Toffoli gates to compute $\mathbf{E}$ there does not seem to be any correlation between the key and the ciphertext nor does there seem to be any correlation between the plaintext and the ciphertext (of course, I don't know if any random Toffoli gate cryptosystem has been thoroughly investigated though). $\endgroup$ – Joseph Van Name May 12 '17 at 23:03
  • 1
    $\begingroup$ And Toffoli gates are not necessarily quantum gates since the bits that Toffoli gates act on do not necessarily have to be in a superposition of each other (and hence do not require "quantumness"). Toffoli gates are simply universal reversible gates so that a reversible computer can be constructed using Toffoli gates. I bring up reversible computation since reversible computers have the potential to be much more efficient than classical computers since they are not subject to Landaeur's limit and because symmetric encryption is a reversible process. $\endgroup$ – Joseph Van Name May 12 '17 at 23:07
  • 1
    $\begingroup$ @JosephVanName When you say "does not seem to be any correlation between the key and cipher text" are you looking at this mathematically, and conducting cryptanalysis? $\endgroup$ – nonce May 13 '17 at 17:47
  • $\begingroup$ I have looked at it mathematically in the sense that I tested when a bit of the key switches from 0 to 1 or vice-versa, I counted about half of the bits of the ciphertext change (as long as the reversible circuit had enough gates), and if I switch a bit in the plain-text, then I counted about half of the bits in the ciphertext change. I have not done any other cryptanalysis other than these initial observations. $\endgroup$ – Joseph Van Name May 13 '17 at 18:20

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.