Is there a cryptographic algorithm that can 'pack' a bunch of strings/numbers and "confirm" if a string/numbers exists (later in the code) while keeping the output hidden?

For example, I have algorithm X, to which I can run something like:

// From Alice's side
algo1 = new X(key);


print(algo1.output) // Prints a bunch of random bytes

//Later, somewhere in Bob's code
algo2 = new X(key, algo1.output);

algo2.has(111) // false
algo2.has(222) // false
algo2.has(100) // true
algo2.has(200) // true

I do realize this can be done with an encrypted database, but I am searching for a solution in an algorithm.

The purpose is data hiding: in case algo1.output as well as key are revealed to an attacker, they would still have to know the values in the set to get a truthful answer (100, 200 and 300 in the case above), which would protect the integrity of those values, even if the key and algo1.output are revealed

They would then have to rely on brute-force methods to extract those values, which could make it expensive for the attacker.

  • $\begingroup$ See Socialist millionaire problem. Also the Accumulators. Note that = doesn't hide the output from Bob. It leaks the existence and inequality leaks the non-existence. $\endgroup$ – kelalaka Jun 16 '20 at 9:49
  • $\begingroup$ @kelalaka Maybe OP's issue can be solved with a one-way accumulator function, but I don't know if it is possible to initialize it with a 'key'... $\endgroup$ – jimmytann Jun 16 '20 at 9:55
  • $\begingroup$ In that code example, there does not appear to be any connection between the object called "algo" in the first half and the one called "algo" in the second half. Therefore what you seem to be asking for is trivially impossible, because there's no communication whatsoever. $\endgroup$ – Maeher Jun 16 '20 at 10:12
  • $\begingroup$ @Maeher Apologies. algo.output from Alice's code is sent to Bob's code. I clarified it above $\endgroup$ – JohnnyP Jun 16 '20 at 11:48
  • $\begingroup$ Thanks for the clarification. So what are the security properties you want? As it stands, a list of elements seems to serve the purpose. $\endgroup$ – Maeher Jun 16 '20 at 12:53

It seems we can use commitment schemes with homomorphic hiding and binding properties here. Often these commitment schemes are used for secure multiparty computation, and zero knowledge proof generation purposes.

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding.

Commitment schemes are a way for one counterparty to commit to a value such that the value committed remains private, but can be revealed at a later time when the committing party divulges a necessary parameter of the commitment process. Strong commitment schemes must be both information hiding and computationally binding.

There are different types of commitment schemes.Pedersen commitment scheme is a popular one. There are other approaches such as Polynomial commitment schemes as well.

EDIT based on Comments

The purpose of commitment scheme here would be to commit on the existence of a number ( a packed number ) and then keeping the output hidden until there is a requirement for revealing it. An algorithm for packing the numbers can be implemented using arithmetic circuits, functional encryption etc. The advantage of secure multi-party computation will be to delegate the packing operation to multiple parties and aggregating the result of the operations. This is the perspective on recommending commitment schemes and multi-party computation.

  • $\begingroup$ I don't understand how (homomorphic) commitments allow "packing". Could you elaborate? $\endgroup$ – Occams_Trimmer Jun 16 '20 at 22:05
  • $\begingroup$ I agree: it also does not allow for "multiple values", as described? Is there any counter-argument here against using accumulators? $\endgroup$ – JohnnyP Jun 17 '20 at 6:18
  • $\begingroup$ Commitment schemes are not recommended here for the packing operation. It was recommended as an efficient commit on the existence on a particular number and to reveal it later as per the requirement. $\endgroup$ – Gokul Alex Jun 19 '20 at 12:22
  • $\begingroup$ Dear @Johnny, Accumulators would be a nice idea for the specific operation. However if you would like to more operations on the numbers in the encrypted setting it would be nice to do secure multi-party computation. $\endgroup$ – Gokul Alex Jun 19 '20 at 12:24

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.