Selecting and boolean masking in nada_numpy

[vishakh]

Hello, I am trying to write a Nada program using nada_numpy and running into some issues.

Here is the plain Python code I am trying to run:

target_snp_1 = 1815739
target_genotype_1 = 9

rows_of_interest = gene_data[gene_data[:, 0] == target_snp_1]
is_successful = rows_of_interest[0, 3] == target_genotype_1

When I try to replicate this within a Nada program..

from nada_dsl import *
import nada_numpy as na

# Checks based on SNP rs1815739 whether someone is a sprinter or an endurance athelete
# Genotype TT indicates endurance athlete
# We arbitrarily assume sprinter otherwise
# This program returns 0 if sprinter, 1 if endurance athlete
# This is a counterpart to muscle-perform.py which operates on tabular data rather than atomic secrets.
def nada_main():

    target_snp_1 = Integer(1815739)
    target_genotype_1 = Integer(9)

    party1 = Party(name="Party1")

    gene_data = na.array((1, 4), party1, "gene_data", SecretInteger)
    rows_of_interest = gene_data[gene_data[:, 0] == target_snp_1]
    is_successful = rows_of_interest[0, 3] == target_genotype_1

    result = is_successful.reveal()

    return [Output(result, "Result", party1)]

..I get this error during compilation:

Compiling muscle-perform-array.py
Error: compilation failed

Caused by:
    Traceback (most recent call last):
      File "/home/vishakh/dev/cryptonomic/MonadicDNA/services/nillion-interactor/venv/lib/python3.10/site-packages/nada_dsl/compile.py", line 97, in <module>
        output = compile(sys.argv[1])
      File "/home/vishakh/dev/cryptonomic/MonadicDNA/services/nillion-interactor/venv/lib/python3.10/site-packages/nada_dsl/timer.py", line 116, in wrapper
        value = func(*args, **kwargs)
      File "/home/vishakh/dev/cryptonomic/MonadicDNA/services/nillion-interactor/venv/lib/python3.10/site-packages/nada_dsl/compile.py", line 48, in compile
        outputs = main()
      File "/home/vishakh/dev/cryptonomic/MonadicDNA/services/nillion-interactor/programs/muscle-perform-array.py", line 17, in nada_main
        rows_of_interest = gene_data[gene_data[:, 0] == target_snp_1]
      File "/home/vishakh/dev/cryptonomic/MonadicDNA/services/nillion-interactor/venv/lib/python3.10/site-packages/nada_dsl/nada_types/types.py", line 186, in __eq__
        raise TypeError(f"Invalid operation: {self} == {other}")
    TypeError: Invalid operation: Integer(inner=Literal(inner=None), value=1815739) == 
    NadaArray((1,)):
    [(SI)]

Am I doing anything not supported by nada_numpy? If so, is there a way I can still accomplish my goal with nada-numpy?

In addition, the Nada code is supposed to operate on much larger arrays, e.g. (631955, 4). When I use the line gene_data = na.array((631955, 4), party1, "gene_data", SecretInteger) in the Nada program, the compile time seems to blow up. Is this expected behavior? Is there a current and future target upper bound on the size of arrays pynadac can handle?

Thanks!

[jcabrero]

Hey @vishakh, the application seems super cool. Unfortunately, your application won't be able to be carried out in the exact way you had planned it because of how privacy-preserving applications work. Also, to put the blame on our side, we have not yet integrated the support for comparison operations on Nada Numpy as our focus was our application to Machine Learning.

That said, your use case seems very interesting, so I will personally work to include support for comparison operations in Nada arrays in the next few days. We will get back to you with a tentative solution as soon as the new version is released.

Thanks again for building with Nillion! Cheers!

[vishakh]

Many thanks, @jcabrero, I appreciate it! We will wait for you.

[manel1874]

Hi @vishakh! Just adding some more bits to @jcabrero answer.

So, you are trying to select a secret element based on a secret filter (list of secret bools). This is currently not supported but it should be possible to achieve something similar as @jcabrero was mentioning.

I mean similar because dealing with secret vectors is tricky and we cannot exactly do what you are trying to do under blind computation (i.e., under MPC). Coding under the blind computation framework has its caveats. For example, observe that the size of rows_of_interested already reveals some information about the gene_data: it reveals the number of gene_data rows where the first element is equal to target_snp_1. This is somewhat related to the security guarantees of oblivious RAM (i.e. indexing vectors by a secret index).

Another comment on the program: there is no need to reveal the value of is_successful as it is passed as output of the nada program. All outputs are revealed to the output party.

[vishakh]

Hello, @manel1874. Please forgive my ignorance but only the result is being outputted and all it reveals is where there is a single row with a given value. Is the concern that the executing host might be able to intercept the value of gene_data and reveal information about it? If so, am I conflating MPC with TEE by assuming that the computation is somehow completely segregated or completely obscured on the host machine?

Another way I could write the Nada program is by following the dot product example on the nada-numpy repo. I could provide a second vector with all zeros except for a single one at a particular index and then perform a dot product to derive the final answer. Is this a better approach or shall I just wait for changes in nada-numpy?

[manel1874]

Is the concern that the executing host might be able to intercept the value of gene_data and reveal information about it? If so, am I conflating MPC with TEE by assuming that the computation is somehow completely segregated or completely obscured on the host machine?

That is not the concern, no. The executing host is a cluster of computing parties with only shares of the computing elements. So, within MPC, the underlying values of single elements are completely obscured on the cluster. However, in MPC, when it comes to data structures, the size of these data structures are known by the cluster computing nodes. More specifically, the size of the vectors are always known and we cannot tie together the size with secret values. In Nada this is prevented by enforcing the vector size to be known at compilation-time. This ensures that the size does not depend on any secret. I hope this clarifies what I was trying to say in my previous message.

Another way I could write the Nada program is by following the dot product example on the nada-numpy repo. I could provide a second vector with all zeros except for a single one at a particular index and then perform a dot product to derive the final answer. Is this a better approach or shall I just wait for changes in nada-numpy?

Yes, that is a way to go and probably the built-in implementation will be based on that. So, you can create a new vector with secret booleans, then you need to use if_else to transform the vector of secret bools into a vector of secret integers (0 or 1) and then you apply the inner product approach. You need the transformation because you cannot multiply boolean and integer types together.

[vishakh]

Thanks, @manel1874.

We'll wait for @jcabrero's update before proceeding.

[jcabrero]

Hi @vishakh, we have just dropped Nada Numpy 0.4.2 to support array comparison operations. So now, you will be able to do a == b (but also !=, <, <=, > and >=) where a is a NadaArray and b is either a NadaValue (SecretInteger, SecretRational...) or another NadaArray of the same dimensions. You can take the advice from @manel1874 to continue your implementation. You can let us know how it works and if you find any issues making you're idea work.

[vishakh]

Thanks, @jcabrero. Could you please link me to a Nada program which uses array comparisons? I want to understand how to do this correctly in my program.

[jcabrero]

This is a test that we use in Nada Numpy which uses all the comparison operations: Array Comparison Test. Let me know if this clarifies your question.

[vishakh]

I was looking for something which solves an actual problem, even if it's a toy problem, to see how it ties in to the rest of the stack, e.g. how the secrets and external logic are set up. I'd appreciate a link if something like it becomes available.

[manel1874]

@vishakh one question related to the program above that may help increase its efficiency: what exactly has to be kept private in the gene sequence?

1. Is the existence of the target_snp in the first column of gene_data sensitive information?
2. Is the place where target_snp is in gene_data sensitive information?
3. Is the target_genotype value sensitive information?

I believe 3 is answered positively. But, if 1 and 2 are not sensitive information, then you would only need to do comparisons over public values (which will be faster).

[vishakh]

You are correct, only (1) and (2) are not sensitive. Also, (3) is not sensitive by itself as target_genotype is just a little DNA pair.

The only things that are truly sensitive are the gene data itself, i.e. gene_data, and whether it has a row matching target_snp_1 and
target_genotype_1, i.e. is_successful.

[manel1874]

Thanks for clarifying. It seems there's no way to avoid performing all comparisons between gene_data and target_snp_1 under MPC. I guess the only approach is the one we talked about during the call. Even if we used a specialized Private Information Retrieval (PIR) protocol, the communication would still scale linearly with the size of gene_data, so it wouldn’t offer a speed advantage in this case.

However, if the presence and position of target_snp_1 in gene_data weren't sensitive, we could compare them directly with public values.