4
$\begingroup$

I have a service that allows multiple parties to share domain-specific textual data. This data is also end-to-end encrypted. How can I be sure the sharing parties don't send non-domain-specific data, considering I receive it encrypted?

For example, assuming I require a specific algorithm to be used for the encryption, is there either:

  • a zero-knowledge proof that would verify that the original data matches a given regular expression

or

  • a homomorphic identity operation that, applied to valid domain-specific encrypted data, would result in no change to the data, but applied to anything else, would result in undecryptable garbage
Improve this question
$\endgroup$
  • $\begingroup$ Interesting question. (: By "domain-specific textual data", do you mean strings with some specific format or from some particular set of words? $\endgroup$ – Hilder Vitor Lima Pereira May 19 '17 at 10:57
  • 1
    $\begingroup$ @Vitor. Thank you. Yes, it would be a string with a specific fixed-length format, one that could be matched by a basic regular expression. For [a short] example: /[a-z]{2}[0-9]{8}/ $\endgroup$ – Eliott May 19 '17 at 12:13
4
$\begingroup$

One (very generalized) solution would be to use a general ZKP solution like libsnark.

In libsnark (and other tools like it), you would write a function that accepts both public and private inputs, and outputs a proof that the inputs satisfy the logic of the function. This proof can then be verified, at a much lower cost than it took to generate it.

E.g., you might have:

public_inputs = { encrypted_string, regex, length }
private_inputs = { plaintext_string }

function(public_inputs, private_inputs)
  s = encrypt(plaintext_string)
  check1 = (encrypted_string == s)
  check2 = (length(plaintext_string) == length)
  check3 = string_fits_regex(plaintext_string, regex
  return (check1 and check2 and check3)

Libsnark gives you one algorithm for "prove" and one for "verify".

The sender would then call "prove", which would generate the proof, and then send the proof along with the encrypted string.

Then you (or the receiver), could call "verify" with the same public inputs and it would say "yes" or "no".

There's a lot more details, check the references at the end of that repo's README page. Here's a good illustration from a (somewhat related) blog post.

I bet there are other, even better (less computationally intensive) solutions as well.

Improve this answer
$\endgroup$
  • $\begingroup$ A very warm welcome to crypto, Elliot and ads. Elliot, don't forget to accept this answer if this fully answers your question. Please indicate in comments below or below your question if anything is missing. $\endgroup$ – Maarten Bodewes♦ May 31 '17 at 8:44
  • $\begingroup$ @MaartenBodewes Thank you. I've been trying to confirm whether this answers my question, but after failing to compile libsnark on Windows and Linux, failing to build a solution from reading papers on LIBSNARK, Pinocchio NIZK, QSPs, etc', and not getting much support from one of the authors of the original paper, I'm still no closer to knowing whether this will work for me... $\endgroup$ – Eliott May 31 '17 at 22:42
  • $\begingroup$ @Eliott there's a docker container at (github.com/stratumn/pequin) that runs, and i've gotten lots of help from the people at pepper at this email: pepper@pepper-project.org $\endgroup$ – ads Jun 1 '17 at 2:49
  • $\begingroup$ @ads ...still working on this. When you say "s = encrypt(plaintext_string)", are you saying that I need to implement the encrypt function as a QSP? Thank you. $\endgroup$ – Eliott Jul 4 '17 at 15:52
  • $\begingroup$ @eliott not sure what you mean by QSP. when i played with this, i implemented a basic version of RSA decryption in (a subset of) C, which was then compiled to constraints by libsnark. see here $\endgroup$ – ads Jul 5 '17 at 16:36

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.