Your function $F$ is, in an abstract way, a generic $n\rightarrow 1$ function. As I gather, the implementation you suggest is to have some sort of table or register of outputs for all possible inputs (with $n$ input bits, there are $2^n$ possible input combinations) and then somehow "select" the right one.
There are many ways to implement that, both in software and hardware, and not all of them a "constant-time". For instance, in software, you could spread the $2^n$ bits into so many array cells, and use an array access indexed by the inputs (considered as an integer). Since this would constitute a memory access at an address that depends on secret data, this is not constant-time, and may be vulnerable to cache timing attacks.
Now, on a concrete platform like a modern PC, and if $n$ is sufficiently small, then you could store the $2^n$ possible outputs in a register (this obviously works only if $2^n$ is not larger than the register length on the involved machine), and perform a right shift (>>
operator in C, shr
opcode in x86 assembly) with the inputs ($n$ bits) as shift count. In general, this should be constant-time, but it depends on the exact CPU. Most CPU include a specific piece of hardware called a "barrel shifter" that performs the shift in one clock cycle, regardless of the shift count. Historically, presence of a barrel shifter was not a given; in particular, the Pentium IV famously had not a barrel shifter, and a right shift by a variable count $x$ would take a time more or less proportional to the value of $x$. The "register shift" implementation strategy would not be constant-time in that case.
In hardware, this is a routing problem: you want to route the right bit from the $2^n$ sequence to the output; the circuit will need to "touch" all $2^n$ bits. It so happens that it can be done with a tree of multiplexers. A multiplexer mux(c,a,b)
returns a
if c
is 0, or b
if c
is 1. You can then do the following:
Combine all $2^n$ bits in pairs, with $2^{n-1}$ multiplexers, all using the first input bit as control ("c
") bit. This yields $2^{n-1}$ output.
Combine all these $2^{n-1}$ outputs by pairs, with $2^{n-2}$ multiplexers, all using the second input bit as control bit. You now have $2^{n-2}$ values.
Iterate. At the end, you have a single multiplexer, that uses the last input bit as control, and produces the result you are looking for.
This implementation as a tree of multiplexer is naturally constant-time, and it is the preferred method for making S-boxes in hardware (e.g. for DES implementations).