I have been studying multi-party computation and want to start implementing it. I think it would be interesting to do this where one of the inputs (say party 1) is some source code, say a .py file.

If for example I wanted to securely compute the number of lines of code this file had, how would I go about it? The functionality would look something like $$f(code.py, \_) = (\_, \text{number of lines in code.py})$$ where $\_$ represents the empty string.

I think MPC is up to this task but are there any better ways this functionality could be realised?

Also, any pointers to packages that would be good to implement this in would be nice also.

  • $\begingroup$ When you say "number of lines of code" you mean excluding blank lines and comments or you just mean the number of lines the file has? And is $f$ known only by the client? I mean, the server, which holds the file, is supposed to known that the client just want to count lines or it must run the protocol as if $f$ could be something else? $\endgroup$ – Hilder Vitor Lima Pereira Jul 25 '19 at 7:41
  • $\begingroup$ Yes excluding blank lines and comments. The functionality is publicly known. Essentially want to count the lines that are not blank and not comments without leaking information other information about code.py (which is a private input). $\endgroup$ – LDG Jul 25 '19 at 8:01
  • $\begingroup$ That is not really a good scenario for multi-party computation, since the server can just count the lines, encrypt, and send it to the client. Interesting examples use functions $f$ that have two inputs, $c$, known by the client and $s$, known by the server. Then they want to compute $f(c, s)$ without disclosing their values (so, each party cannot compute $f(c, s)$ alone)... $\endgroup$ – Hilder Vitor Lima Pereira Jul 25 '19 at 11:24

I'd like to divide the problem into semi-honest and malicious adversaries with corrupt the party inputting the source code.

In the semi-honest setting, you assume an adversary which follows the protocol correctly, but tries to learn information from the messages the party corrupted by the adversary. As a result, if you assume the adversary is semi-honest, the problem will be trivial to compute since that party can simply compute the lines of code himself and send the other party the result.

It will be very hard to securely construct a secure multiparty computation protocol in the malicious setting where an adversary may also vary the protocol specification, if there are not additional properties about the code known to both parties, like the length of the code. That is for two reasons:

  1. Some data like the length of the code has to get leaked. As to my knowledge, there is no MPC protocol known which permits inputs of variable length.
  2. Adversaries in the malicious setting may input another input like anothercode.py. You can assume that the input is not changed by the adversary, but then you can just use the semi-honest setting.

My best idea of designing the MPC procotol you desire would be to define and reveal properties about the code and then prove them using zero knowledge protocols such that these properties are fulfilled. The best candidates which come to my mind are Zero-Knowledge Using Garbled Circuits or ZKBoo: Faster Zero-Knowledge for Boolean Circuits (the authors even provided an impmenentation of ZKBoo on Github). These protocols are zero-knowledge protocols which prove generic statements (generic as described using AND/XOR gates) using MPC techniques.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.