Implementing Comparison Strategies

Zama Concrete
1

Hello,

I’ve implemented a bitonic sort algorithm using concrete. I’m trying different comparison strategies to see which one would be the most efficient. However, all of the strategies return the same complexity. Following is my code:


# Helper function to compare and swap two elements
def compare_and_swap(a, b, direction):
    c = (a > b) if direction == 1 else (a < b)
    a_new = c * b + (1 - c) * a
    b_new = c * a + (1 - c) * b
    return a_new, b_new


# Helper function to perform the bitonic merge
def bitonic_merge(arr, low, cnt, direction):
    if cnt > 1:
        k = cnt // 2
        for i in range(low, low + k):
            arr[i], arr[i + k] = compare_and_swap(arr[i], arr[i + k], direction)
        bitonic_merge(arr, low, k, direction)
        bitonic_merge(arr, low + k, k, direction)


# Helper function to perform bitonic sort recursively
def bitonic_sort(arr, low, cnt, direction):
    if cnt > 1:
        k = cnt // 2
        bitonic_sort(arr, low, k, 1)  # Sort first half in ascending order
        bitonic_sort(arr, low + k, k, 0)  # Sort second half in descending order
        bitonic_merge(arr, low, cnt, direction)  # Merge both halves

    return arr


@fhe.compiler({"array": "encrypted"})
def sort_array_bitonic(array):
    array = bitonic_sort(array, 0, array.size, 1)
    return array

strategies = [
    None,
    fhe.ComparisonStrategy.ONE_TLU_PROMOTED,
    fhe.ComparisonStrategy.THREE_TLU_CASTED,
    fhe.ComparisonStrategy.TWO_TLU_BIGGER_PROMOTED_SMALLER_CASTED,
    fhe.ComparisonStrategy.TWO_TLU_BIGGER_CASTED_SMALLER_PROMOTED,
    fhe.ComparisonStrategy.THREE_TLU_BIGGER_CLIPPED_SMALLER_CASTED,
    fhe.ComparisonStrategy.TWO_TLU_BIGGER_CLIPPED_SMALLER_PROMOTED,
    fhe.ComparisonStrategy.CHUNKED,
]


for strategy in strategies:
    print("Runnig with strategy ", strategy)
    bitonic_circuit = sort_array_bitonic.compile(inputset, comparison_strategy_preference=strategy)

        enc_array = bitonic_circuit.encrypt(input_array)
        enc_result = bitonic_circuit.run(enc_array)
        dec_array = bitonic_circuit.decrypt(enc_result)
        print("output ", dec_array)
        print("complexity ", bitonic_circuit.complexity)

Could you please confirm if I’m implementing the strategies correctly? If so, am I missing something that would explain why there’s no difference in execution time or complexity? If not, then what would be the correct way to approach this?

2

The strategy you gives is not forced, it’s only pick when they could improve something over the default strategy. And it depends a lot on the input set here.

All strategy with BIGGER/SMALLERr only helps in systematic non symetric comparison (eg comparing a 2bits number with a 5bits number), ie when one operand (left or right) is a lot bigger and smaller than the other one.
So in your case only ONE_TLU_PROMOTED THREE_TLU_CASTED and CHUNKED are relevant.

Then depending on the bitwidth of operands some strategy are not taken because they are never interesting, (so back to the default strategy).
You can try with different bitwidths via the input set to see the effect if any w.r.t. strategy.

What’s your input set here ?

3

Hey

Also, to make your code more efficient, you might want to look at the fhe.if_then_else (Extensions | Concrete) operator, which would make your

a_new = c * b + (1 - c) * a
b_new = c * a + (1 - c) * b

much more efficient.

4

Hi @Rudy_Sicard

Thank you for your response,

My inputset is:
inputset = [np.random.randint(1, lrange, size=lsize) for _ in range(5)]

basically I’m working with a range of 1 to 15 or 1 to 25 etc. array length varies between 4, 8 and 16.

I did try creating a configuration object and tweaking my code a bit and was able to vary the complexity but only when I don’t use a strategy and when I do.

The complexity remains same regardless of what strategy I use, I’m assuming it should change with each relevant strategy?

Here’s my updated code:


for strategy in strategies:
    configuration = fhe.Configuration(
        comparison_strategy_preference=strategy,
    )
    bitonic_circuit = None
    if strategy is None:
        bitonic_circuit = sort_array_bitonic.compile(inputset)
    else:
        bitonic_circuit = None
        bitonic_circuit = sort_array_bitonic.compile(inputset, configuration)

Also, does the default strategy have to be one of the strategies listed or could it be multiple or none at all? When I run the code without specifying a strategy, I get a better result as compared to running it with a specific one.

Thanks.

5

Hi @benoit

Thank you for your suggestion. I tried using if_then_else

    c = (a > b) if direction == 1 else (a < b)
    a_new = fhe.if_then_else(c, b, a)
    b_new = fhe.if_then_else(c, a, b)
    return a_new, b_new

but I’m getting a runtime error:

raise RuntimeError(

RuntimeError: A subgraph within the function you are trying to compile cannot be fused because of a node, which is marked explicitly as non-fusable

6

Arg! For this, I would recommend opening another thread, still on community.zama.ai, to split the issues. Someone from the team will help you (they’ll certainly want to see the MLIR). I don’t know myself. In such a situation, I would try to simplify the code first, to see what’s the issue on a small piece of code.

7

And at least, you can factorize this into

a_new = c * (b - a) + a
b_new = a + b - a_new

to have less multiplications between encrypted values.