Question about automaton evaluation

[hilder-vitor]

Hello,

In the paper Homomorphic Encryption for Finite Automata, an automaton with n states over some alphabet, let's say {a, b}, is represented by nxn transition matrices, M_a and M_b, and a n-dimensional state vector, v.

If the automaton is deterministic, then all the entries of the transitions matrices and of the state vector are always binary.

To evaluate the automaton on any given string, we just need to traverse the string updating the state vector as the product of the current state vector and the transition matrix corresponding to the current char.

For example, for the string s = "aab", we would compute homomorphically

v_1 = v * M_a,
then
v_2 = v_1 * M_a,
then
v_3 = v_2 * M_b.

Notice that the string is in clear and the state vectors and transition matrices are encrypted.

If we try to do the same with TFHE, then we have to encrypt all the entries of M_a and M_b separately and, since everything is binary, we can use the AND gate as the multiplication.
But then, each vector-matrix product would cost at least n^2 AND gates and bootstrappings. For a string of length k, we would them need at least k * n^2 AND gates and bootstrappings.

Therefore, if the automaton had n=1000 states, the string had k=1024 chars, and each AND plus bootstrapping took 0.01 second, we would need at least 1000^2 * 1024 * 0.01 seconds, or equivalently, 118 days, to evaluate it.

So, first of all, is my estimate correct?
Additionally, is there another way of doing this automaton evaluation using TFHE?
And if you are kind enough to answer this as well: would this other way of performing the evaluation apply also to nondeterministic automata, since in this case, the transition matrices and the state vectors are no longer binary?

I am sorry for the long post and I would like to thank you already for the attention!

[nindanaoto]

Hello, @hilder-vitor.

I'm the writer of another TFHE implementation, TFHEpp.

I think your way to estimate gate size is wrong. Interpreting the automaton as the transitions matrices and the state vector is not suitable for TFHE since it implements logic gate, not matrix multiplication.
As far as I know,the best way to estimate the size of TFHE implementation of automaton is writing automaton by Verilog or Chisel and synthesizing it by Yosys.
Our project may helpful for you.
https://github.com/virtualsecureplatform/Iyokan

By the way, there is completely different way to evaluate the deterministic weighted finite automata described in original paper. This uses TFHE's LHE function, CMUX.
https://eprint.iacr.org/2018/421

I'm not sure about how to evaluate non deterministic automata in TFHE, but modifying LHE way could be enable that.

[hilder-vitor]

Hello @nindanaoto

I know that TFHE implements logic gates, but since all the entries of the operands and of the resulting vector are binaries, we could perform vector-matrix multiplication using AND gate to multiply and XOR to add the values. For example, let
v = (v1, v2)
and
M = ( m11, m12)
. . . . ( m21, m22)
then, because we know that v * M is also a binary vector, we could compute v * M in this case as
((v1 AND m11) XOR (v2 AND m21) , (v1 AND m12) XOR (v2 AND m22))
This is what I mean in my question.

Thank you very much for your answer. I will check the links you provided.

[nindanaoto]

@hilder-vitor
I see.

From that view, your estimation is correct and it may work.