2

I have mobile devices (low power, low bandwidth) need to act as a proxy for certain types of P2P encrypted data, such as voting, bitcoin payment, or other specific-purpose usage, and I want to make sure that each phone's data service isn't abused.

To that end I need to verify

  • The general contents of the data going through my service
  • Not know what the data is exactly (a range-check is sufficient)

Question

  1. Is Verifiable Encryption the correct thing to learn to solve this issue?

  2. What is it, and how does it work?

  3. What roadmap should I follow when learning it?

Encrypted Data

The data will be a ZKP (like Bitcoin) and any of the following

  • A vote for a candidate
  • A bid for a product (eBay)
  • A bitcoin-style purchase (where the Tor part anonymizes the buyer and the merchant) with a .onion equivalent
makerofthings7
  • 50,488
  • 54
  • 253
  • 542
  • 1
    You need to verify the contents or just that the content integrity is unchanged since it was created? Are data segments going to be split and remixed? – this.josh Apr 09 '15 at 00:39
  • @this.josh I need to verify that the contents is data an encrypted vote for a person (a single value of a set for first past the post FPTP, or ranked 1st place 2nd place, etc for alternative vote). The data segments should be small, product ID + bid. – makerofthings7 Apr 09 '15 at 05:03
  • Also, in all cases, the data sets (product IDs for eBay, and users on a ballot) are common knowledge. The users selection of a product or candidate are private, along with the paring of a bid or a ranked preference, is also private – makerofthings7 Apr 09 '15 at 05:05
  • Read http://security.stackexchange.com/questions/5769/secure-internet-polling/5796 and http://security.stackexchange.com/questions/67819/e-voting-receipt-free-verifiable-and-anonymous for reference. Are you mixing content type for plausable deniability? – this.josh Apr 09 '15 at 17:19
  • I would suggest using I2P. Any reason for keeping the network private? You CAN restrict the set of interconnected nodes to your own whitelisted nodes only, if you wish. And FYI, you can prove what something IS, but rarely can you prove what it ISN'T. – Natanael May 05 '15 at 23:32

2 Answers2

2

It sounds like what you really are looking for is a zero knowledge proof (or several zkps).

You want to prove that (1) data belongs to a given class (general contents) and (2) that the data is within some limits (upper/lower bounds).

Since you also want to transmit the data through the system, you'll need to bind the proof to the data in such a way that the proof is valid only for the ciphertext being transmitted through the system.

One possible way to do this is to have both the sender and the recipient conduct zero knowledge proofs.

In general this is a very hard problem, but if you can limit the scope of the problem it should be solvable.

I'd recommend starting with learning about zero knowledge proofs, and then looking at some real world examples. One particular example that comes to mind is the use of zero knowledge proofs in the context of nuclear weapon verification.

COL Wotohice
  • 503
  • 2
  • 10
  • Thank you, I'd be interested in learning what constraints are possible.. – makerofthings7 Apr 09 '15 at 01:03
  • 1
    There are no restriction on what can be proved, a la the Church-Turing thesis. However, formalizing what you want to prove can be difficult. – COL Wotohice Apr 09 '15 at 11:30
  • Does my edit to the post clarify / constrain what's to be proven sufficiently? – makerofthings7 Apr 09 '15 at 11:39
  • Yes, your edit does clarify this. The basic outline I would suggest is to have the initiator perform some interactive computation with the verifier, and then have the receiver also perform an interactive computation with the verifier where the both computations depend upon the hidden information. You could use something similar to DHKE where the "individual secret" is used as salt in the computation of a hash, and the "common secret" is used to bind it to the encrypted data. I'd need to think this through more, but that is where I would start. – COL Wotohice Apr 09 '15 at 11:56
  • I made an assumption that receiver can be trusted and therefor can help in the verification. If the verification can't involve the receiver, then you'll need to do something different. – COL Wotohice Apr 09 '15 at 12:06
2

Another approach or approaches that you can take to try to solve this problem is the idea of a semi-fragile signature. A semi-fragile signature is a digital signature which can be verified even when the data undergoes a limited set of transformations. I developed the concept originally (I called it a robust signature) in context of limiting the set of transforms that could be applied to an image yet still be able to be authenticated as "effectively" unmodified.

For example, with regard to images I wanted to allow lossy compression such as JPEG, but not allow "photoshopping" of the image. In this case, you could filter the image and then sign a (potentially quantized) FFT. See "Marc Schneider and Shih-Fu Chang, A Robust Content Based Digital Signature for Image Authentication, IEEE International Conf. on Image Processing, Laussane, Switzerland, October 1996."

A related concept is the idea of algebraic coding, where each additional unit of data (bit, byte, etc...) is a refinement of the preceding data just as 3.141 is a refinement of .14 and both are refinements of pi.

Taking the example of a bid on ebay, the price is naturally an algebraic coding. Let say Alice bid $267.32 for a three handled family credenza, you could have the hundreds digit signed (i.e. sign $200.00) then also combine this signature with a signature of the exact price and sign the combination. Given the two signatures, you can verify that the price is between $200.00 and $299.99 inclusive without knowing the exact price. You can also verify that Alice bid $267.32 at a later date due to the second signature.

COL Wotohice
  • 503
  • 2
  • 10