I am working on Bent functions that are of interest in cryptography. I developed an algorithm that construct such functions. However, I need some tools to calculate boolean expression from the truth table. Is there such a application or applet available? (Actually I am interested in expressions without any NOTs).

  • $\begingroup$ How many boolean inputs/outputs are we talking about? sontrak.com can handle up to 16 if I'm not mistaken. $\endgroup$ – orlp Oct 28 '13 at 8:59
  • 2
    $\begingroup$ For relatively small number of variables it might be simpler just to construct your own? A naive method would be to iterate based on the fact $f(x,y,z)=z*f(x,y,1)+(1-z)f(x,y,0)$ $\endgroup$ – Cryptographeur Oct 28 '13 at 10:43
  • $\begingroup$ @nightcracker That was nice, thanks. But I need one that return an expression without any NOTs. $\endgroup$ – Mahdi Khosravi Oct 28 '13 at 11:00
  • $\begingroup$ karnaugh maps will help $\endgroup$ – ratchet freak Oct 28 '13 at 11:34
  • 6
    $\begingroup$ This question appears to be off-topic because it is about Boolean circuits/formal logic in general, not cryptography, and because it is a reference recommendation/request, which is off-topic here. $\endgroup$ – Reid Oct 28 '13 at 19:47

It depends on what you are interested in, when building your expression. If you want to optimize for speed and/or expression size, then the problem is hard, and no good solution is known. You can either try to enumerate all expressions, looking for a match with your table (this is exponential in the size of the expression, so it becomes prohibitive real fast); or you can start with a generic expression as a tree of multiplexers then try to find local shortcuts.

You can often work with the "fake multiplexer": for inputs $a$ and $b$, and control $c$, output $a \oplus (b \wedge c)$: in this way, the bit $c$ selects between values $a$ (if $c = 0$) and $a \oplus b$ (if $c = 1$). For a function $f : n \rightarrow 1$ ($n$ input bits, $1$ output bit), you work recursively:

  • An expression with no input is either $0$ or $1$ (it is a constant).
  • You define $f_0 : n - 1 \rightarrow 1$ such that $f_0(x_1, x_2,... x_{n-1}) = f(x_1, x_2,... x_{n-1}, 0)$ (that's the function $f$ when the last bit is $0$).
  • You define $f_1 : n - 1 \rightarrow 1$ such that $f_1(x_1, x_2,... x_{n-1}) = f(x_1, x_2,... x_{n-1}, 1)$ (that's the function $f$ when the last bit is $1$).
  • You compute the boolean expression $e_0$ for $f_0$, and the boolean expression $e_1$ for $f_0 \oplus f_1$.
  • The expression for $f$ is now $e_0 \oplus (x_n \wedge e_1)$.

There has been such efforts for some table-based operators used in cryptographic algorithms, e.g. DES S-boxes. See also this article.

(Note: if you have only bitwise AND, OR and XOR, and not access to constants, then you cannot build all functions; in particular, you won't be able to make a $1$ out of an all-$0$ input. If you really don't want a NOT or the equivalent "$\oplus 1$", and the output of your function for an all-zero input is $1$, then there is no solution. On the other hand, if the function output for an all-zero input is $0$, then you can make a serviceable $1$ by ORing all input bits together.)

(Note 2: if you want to optimize for speed on software platforms, be aware that not all processor architectures offer the same set of operations. On some processors you have elementary XORNOT or NOTXOR. This can change the achievable speed quite a lot.)


Not the answer you're looking for? Browse other questions tagged or ask your own question.