Expanding Table Lookups Size Beyond 16-Bit in Concrete Cryptography Library

Zama Concrete
1

Hello everyone,

I’ve been working with the Concrete cryptography library and noticed that the table lookups in Concrete currently have a maximum support for 16-bit. I’m interested in exploring ways to expand the size of table lookups beyond this limit.

Has anyone encountered a similar requirement or found a workaround to handle larger table lookups in Concrete? I’d appreciate any insights or suggestions on how to achieve this. Are there specific extensions, configurations, or alternative approaches that can be considered to overcome the 16-bit limitation?

Looking forward to your expertise and experiences on this matter. Thanks in advance for your assistance!

2

Hi @Holly_Liang,

We’d love to help you! Could you describe your use case a bit?

Thanks!

3

Thank you for your assistance. I’ve encountered a challenge in performing multiplication on ciphertexts using table lookups. The limitation is that table lookups can only be done with up to 16-bit integers, and my requirement involves 32-bit integers. I attempted to address this issue by employing binary encoding, but unfortunately, I couldn’t achieve the desired outcome.

My question is whether there is a way to modify the properties of table lookups to support 32-bit integers. Any guidance on this matter would be greatly appreciated.

Thank you again for your help.

4

Of course :slightly_smiling_face:

I attempted to address this issue by employing binary encoding, but unfortunately, I couldn’t achieve the desired outcome.

Could you share what you tried? It should be doable like this, even with slightly bigger integers (e.g., 8 integers of 4-bits to represent a 32-bit number).

My question is whether there is a way to modify the properties of table lookups to support 32-bit integers.

Unfortunately, no. 16-bit limit comes from the underlying cryptography, and it’s not easy to overcome. We might be able to support more precision in the future, but not at this time. Also, it’s not a good idea in terms of binary size, as a table lookup on a 32-bit number would require a table with 2^32 elements, which is 16gb if table values are also 32-bit integers.

Waiting for your response!

5

Thank you for your timely reply😃

This is my implementation of 8-bit binary multiplication using plaintext.

#Convert the input to a binary array.
import numpy as np

input1 = 200
input2 = 222

binary_input1 = np.unpackbits(np.array([input1], dtype=np.uint8))
binary_input2 = np.unpackbits(np.array([input2], dtype=np.uint8))

binary_input1=binary_input1[::-1]
binary_input2=binary_input2[::-1]

print(binary_input1)
print(binary_input2)

[0 0 0 1 0 0 1 1]
[0 1 1 1 1 0 1 1]

#Create an n * 2n matrix to store the result of the multiplication.
n = 8
matrix = np.zeros((n, 2*n), dtype=np.uint8)
print(matrix)

[[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

#Perform the multiplication.
for i in range(n):
    for j in range(n):
        matrix[i,i+j] = binary_input1[j] & binary_input2[i]
print(matrix)

[[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0]
 [0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0]
 [0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0]]

#reduce_add
def reduce_add(a, b, size):
    sum = [0] * size
    sum[0]=np.bitwise_xor(a[0],b[0])
    carry = np.bitwise_and(a[0],b[0])
    for i in range(1,size):
       tmp_s=np.bitwise_xor(a[i],b[i])
       tmp_c=np.bitwise_and(a[i],b[i])
       sum[i]=np.bitwise_xor(tmp_s,carry)
       carry=np.bitwise_or(np.bitwise_and(tmp_s,carry),tmp_c)
    return sum

result=[0]*2*n
for i in range(n):
    result=reduce_add(result,matrix[i],2*n)

result=result[::-1]
print(result)

[1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0]

Below is the encryption circuit implemented using the Concrete library for the same method.

from concrete import fhe
@fhe.circuit({"binary_input1": "encrypted","binary_input2": "encrypted"})
def circuit2(binary_input1: fhe.tensor[fhe.uint2, 8, ],binary_input2: fhe.tensor[fhe.uint2, 8, ]):
    n = 8
    matrix = np.zeros((n, 2*n), dtype=np.object)
    result=[0]*2*n
    for i in range(n):
        for j in range(n):
            matrix[i,i+j] = np.bitwise_and(binary_input1[j],binary_input2[i])
    for i in range(n):
        result=reduce_add(result,matrix[i],2*n)
    return matrix
enc=circuit2.encrypt(result,binary_input1,binary_input2)
res_enc=circuit2.run(enc)
result=circuit2.decrypt(res_enc)
print(result)

I will encounter the following error due to issues with the return value😢

 ValueError: Function 'circuit2' returned '[[<concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac1ed910>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29abfa2fd0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bce15e0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bcdbb20>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bcdb100>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac1b98e0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac1b92e0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac1df790> 0 0 0 0 0
  0 0 0]
 [0 <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac1eab50>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bcdc340>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac22f9a0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac22f220>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac2993d0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac1fd3d0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bc3d1f0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac1db640> 0 0 0 0 0
  0 0]
<concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac1e02e0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f29ac1dea30>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bc3f310>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bc3f070>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bc38970>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bc5dfd0>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bc2a550>
  <concrete.fhe.tracing.tracer.Tracer object at 0x7f292bc2af40> 0]]', which is not supported

I feel that my binary encoding method may not be well-suited for concrete. I would greatly appreciate it if you could provide a detailed description of your approach.

6

Let’s start by fixing your implementation :slightly_smiling_face:

Could you try again after replacing:

np.zeros((n, 2*n), dtype=np.object)

to

fhe.zeros((n, 2*n))

and

return matrix

to

return fhe.array(matrix)

Let me know how it goes!

1 Like
7

I have modified part of the code based on your advice, and my issue has been resolved. Thank you very much for your assistance.

from concrete import fhe
@fhe.circuit({"binary_input1": "encrypted","binary_input2": "encrypted"})
def circuit2(binary_input1: fhe.tensor[fhe.uint2, 8, ],binary_input2: fhe.tensor[fhe.uint2, 8, ]):
    n = 8
    matrix =fhe.zeros((n, 2*n))
    result=[0]*2*n
    for i in range(n):
        for j in range(n):
            matrix[i,i+j] = np.bitwise_and(binary_input1[j],binary_input2[i])
    for i in range(n):
        result=reduce_add(result,matrix[i],2*n)
    return fhe.array(result)
enc=circuit2.encrypt(binary_input1,binary_input2)
res_enc=circuit2.run(enc)
result=circuit2.decrypt(res_enc)
result=result[::-1]
print(result)

[1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0]
8

Glad to help :slightly_smiling_face:

I’d also recommend using tensorized operations (e.g., np.bitwise_and(binary_input1, binary_input2[i]) instead of for j in range(n): np.bitwise_and(binary_input1[j],binary_input2[i])). It’ll enable parallelization and make your code run much faster.

1 Like