Slow right shift (table lookups)

Zama Concrete
1

Hello,

I read that “TFHE also has a fast primitive for right bit-shift”. Is that supported in concrete or are bit shifts always a table lookup? Since fast removal of LSBs is supported, support for fast right-shifts would feel natural.
When I test left and right shifts they are translated to table lookups:

My circuit:

  1         @fhe.compiler({"query": "encrypted"})
  2         def lookup(query):
  3             index = query >> 1
  4             return index

My Computation Graph:

----------------------------------------------------------------------------------------------------------------------------
%0 = query                      # EncryptedTensor<uint2, shape=(378,)>        ∈ [0, 2]
%1 = 1                          # ClearScalar<uint1>                          ∈ [1, 1]
%2 = right_shift(%0, %1)        # EncryptedTensor<uint1, shape=(378,)>        ∈ [0, 1]
return %2
----------------------------------------------------------------------------------------------------------------------------

My MLIR:

module {
  func.func @main(%arg0: tensor<378x!FHE.eint<2>>) -> tensor<378x!FHE.eint<1>> {
    %c1_i2 = arith.constant 1 : i2
    %cst = arith.constant dense<[0, 0, 1, 1]> : tensor<4xi64>
    %0 = "FHELinalg.apply_lookup_table"(%arg0, %cst) : (tensor<378x!FHE.eint<2>>, tensor<4xi64>) -> tensor<378x!FHE.eint<1>>
    return %0 : tensor<378x!FHE.eint<1>>
  }
}
2

Hi @lulu,

At the moment, it works but it’s not optimal. In the near future, it might be :slightly_smiling_face:

Hope this answers your question!

3

Ok, thank you for your answer.