10
$\begingroup$

Reversible computing refers to the type of computing where one minimizes the the amount of data to be deleted usually to save energy (Reversible computing could also thwart side-channel attacks). Energy efficient reversible computers do not exist yet in the free market although some have constructed prototypes and they should become the computers of the future. In reversible computing, the AND and OR gates are forbidden since they delete data (the AND gate has 2 inputs but 1 output so one bit is necessarily deleted).

With purely reversible computing, only the bijective logic gates are allowed for computation since non-bijective gates delete information. For example, the CNOT $(x,y)\mapsto(x,x\oplus y)$, Toffoli $(x,y,z)\mapsto(x,y,(x\wedge y)\oplus z)$, and Fredkin $(0,y,z)\mapsto(0,y,z),(1,y,z)\mapsto(1,z,y)$ gates are all reversible gates.

While reversible computing theoretically should save energy, it typically takes more steps to compute something reversibly than it does to perform the same computation irreversibly. However, in symmetric cryptography, one could potentially design cryptosystems such as encryption systems, hash functions, (cryptographic and non-cryptographic) pseudorandom number generators which do not contain any such algorithmic overhead (the only irreversibility that is required in a cryptographic hash function is that unless one wants to keep the hash around forever, one must eventually delete the hash).

1) Are there any symmetric cryptosystems which are specifically designed to be used by reversible computers?

2) Are there any symmetric cryptosystems which were not necessarily designed to be used by reversible computers but which just-so-happen to be reversible?

3) Are there any symmetric cryptosystems which are nearly reversible and which can potentially be modified slightly to become reversible?

Here are some characteristics that one would like in reversible cryptosystem.

-The cryptosystem should ideally be computed using solely reversible gates without any garbage bits, ancilla bits, uncomputation, or irreversible gates.

-The inverses of all parts included in the cryptosystem should be computed in exactly the same way as the forward direction (for example, the inverse $\chi$ in Keccak is computed differently than the forward direction; $\chi$ has algebraic degree 2 while the inverse of $\chi$ has algebraic degree 3 (see page 16 of these slides)).

-The cryptosystem must not require any uncomputing. Uncomputing is an overhead that arises in reversible computing even though irreversible computing does not require any uncomputing.

-The cryptosystem should not use any lookup tables.

-The cryptosystem should not use modular multiplication, finite field multiplication, or finite field inversion at all these operations require uncomputing.

$\endgroup$
  • $\begingroup$ You might want to clarify reversible computing, I can't tell if it's a method or some physical device. Also you say that AND/OR can't be used, but according to Wikipedia those gates are used to define the Fredkin gate. Also $\chi$ is a S-Box which to my knowledge don't have algebraic degrees. $\endgroup$ – Q-Club Feb 14 '18 at 22:57
  • 1
    $\begingroup$ I think they are referring to the algebraic degree of the individual output bits in $\chi$ whose corresponding polynomials over $F_{2}$ are of the form $(1\oplus x)\cdot y\oplus z$. $\endgroup$ – Joseph Van Name Feb 15 '18 at 1:46
  • $\begingroup$ I'll take your word for it. But you should elaborate on "uncomputing", and link to where someone could find a function that will reverse $\chi$ $\endgroup$ – Q-Club Feb 15 '18 at 2:04
  • $\begingroup$ A symmetric cryptosystem where the inverses of all parts are computed in exactly the same way as the forward direction (i.e., all parts are involutions) is ICEBERG. But I don't know whether there exists a reversible circuit that implements this, nor am I aware of a symmetric cryptosystem that is specifically designed to have one. $\endgroup$ – Bla Blaat Feb 15 '18 at 10:42
  • $\begingroup$ Linear (and some non-linear) feedback shift registers which are used in to generate pseudorandom bit streams are reversible since the can be computed solely using shifts and CNOT gates without any deletions. $\endgroup$ – Joseph Van Name Feb 24 '18 at 20:25
5
$\begingroup$

We can think of encryption as a deterministic function producing ciphertext $C$ from key $K$, plaintext $P$, and for other than deterministic encryption an extra input $R$ for randomness/Initialization Vector. That function $(K,R,P)\mapsto C$ can't be both secure and reversible. Proof: it would be possible to obtain $(K,R,P)$ from $C$ because of reversibility, and from that extract $P$, which goes straight against the security goal.

The same reasoning shows that a fully reversible TRNG can't be secure, or a fully reversible hash function first-preimage resistant.


However, we can implement all steps reversibly, except discarding some of the final result. In particular, for any size-preserving symmetric cipher, in principle we can reversibly implement $(K,R,P)\mapsto(G,C)$, with garbage $G$ the same width as $K$ (and $C$ the same width as $R$ and $P$ combined), and discard $G$ from the output. For a block cipher, that is $(K,P)\mapsto(G,C)$ (proof and/or straightening welcome; Scott Aaronson, Daniel Grier, Luke Schaeffer's The Classification of Reversible Bit Operations would be a useful reference).

With that conception of reversible cipher allowing to discard garbage the width of the key, I tentatively answer:

  1. Yes, if your AES-128 replacement with easy implementation as Toffoli-like gates qualifies.
  2. Yes. The AES block cipher is a well-studied example, and all its standard modes qualify. For the reversible construction of AES-128, see

  3. Rather no. Making things easily reversible when they are not would be a huge design change, likely to compromise security. That applies in particular to Feistel block ciphers using large non-reversible round functions, which I guess are quite hard to re-express as reversible.

I asked how costly DES would be.

$\endgroup$
1
$\begingroup$

It seems like most symmetric cryptosystems could be modified to make completely reversible cryptosystems without the need for garbage or ancilla bits in such a way that the security level is likely to increase rather than decrease.

Reversible computing takes in clean bits of data and returns garbage data which must be cleaned up through the process of uncomputing. However, for the purpose of encryption, it does not make much sense to clean up any garbage data generated since that garbage data provides confusion and diffusion. It also does not make too much sense to insist on using clean 0 bits on the inputs of the ancilla bits because using dirty ancilla bits could also provide confusion and diffusion. Of course, these modifications will change the design of the block cipher, so they will need to be investigated and optimized, but these modifications may increase the security of the block cipher.

Suppose that $S:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is an $S$-box or other bijective function used in a symmetric encryption-decryption algorithm.

Suppose now that one has an efficient reversible circuit $C:\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}$ such that $C(\mathbf{x},\mathbf{0})=(S(\mathbf{x}),G(\mathbf{x}))$ (here $G(\mathbf{x})$ is the garbage data that has been produced from computing $S(\mathbf{x})$). Then to make the block cipher reversible, one would replace the $S$-box $\mathbf{x}\mapsto S(\mathbf{x})$ with the function $(\mathbf{x},\mathbf{y})\mapsto C(\mathbf{x},\mathbf{y})$.

Similarly, if $D$ is a reversible circuit such that $D(\mathbf{x},\mathbf{0})=(S^{-1}(\mathbf{x}),H(\mathbf{x}))$, then one could replace the $S$-box $\mathbf{x}\mapsto S(\mathbf{x})$ with the reversible mapping $(\mathbf{x},\mathbf{y})\mapsto D^{-1}(\mathbf{x},\mathbf{y})$.

$\endgroup$

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.