0
$\begingroup$

I want to discuss a simplistic scheme that comes to my mind, after I read about zero-knowledge proof and some fermentation time. I should mention that this is not born out of a business need or academic studies / research. So please bear my level in security in general.

Assumptions:

With n participants and m < n communities to be formed. With m > 2

  1. Participants form a community if they have the same secret key set in the beginning and also know their peers.
  2. Participants form a community secretly if no one knows no participant’s community besides his peers (We assume they do not know about each other at the beginning).

A Counter (shared memory with initial value) or a Timer approach are considered.

Counter approach:

Procedure:

All participants hash their secret keys based on some salt. The goal is that when they broadcast the hashes, participants within a single community must broadcast no same hash values (no equal two hashes), otherwise they will be discovered by all participants (as participants within a single community). The salt is defined as number between the current counter’s value and the next, Randomly chosen with a relatively small granularity, so that collisions of two participants within the same community is very less probable, for example if Counter is the natural numbers, the first value is 0 and if it is the current, then the next value is 1, salts for one round are derived from [0, 0.0001, 0.0002, …, 1]. After a broadcast for round j:

  1. Participants of C(i) (Community i) hash their keys, considering all possible salts between [0, 0.0001, 0.0002, …, 1], hence they calculate 1000 hash value for their key and store results in a secure internal memory.

(a random salt chosen from between the “current counter” and “current counter + 1” with a probability 0.0001 of collisions)

  1. Each participant of C(i) picks up randomly one value from the secret table of 1000 hashes.
  2. Each participant in the network broadcast his calculated hash to all participants.

In this case, other participants receive hashes when broadcasted with 0.0001 probability of discovery of a couple (same two hash values) belonging to a same community.

  1. Participants of C(j) compare the received hashes (n-1) each hash with other 1/0.0001 salted hashes stored in the secret cache table, they all definitely discover their peers after some time.

Maximum Time of Discovery for all participants to their communities is: (n) * 1000. This calculation can be done parallelly.

This way, all communities {C0, …, Cm} are formed secretly.

NB: I mentioned this in the context of IOT, but obviously it is very abstract.

The question now is: What are flaws ? and How is this problem addressed otherwise ?

Edit1:

I guess I should read about the socialist millionaire problem as I just knew about.

Edit2:

This can be perfectly achieved in a secure way using: Diffie-Hellman exchanges

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

How big is the secret key that defines a community?

If it is trivial, say a number between 1-100, then an attacker can easily calculate 100.000 hashes to know in which community each user is.

If the secret s is long, say 64 bytes, then I don't see the usefulness to generate 1000 hashes for each option. Then it would be best to just send your hash H(s+n), with a random nonce n you used (as knowing the nonce and the hash would not help anyone else to know the secret).

Improve this answer
$\endgroup$
5
  • $\begingroup$ The nonce n here, if the same for all members in a community, or for all participants at all, results to collisions for the same key. So a community will definitely be discovered. The solution would be to choose a nonce from a large pool (to lessen probability of discovery) OR (I referred to it as Timer option but did not describe in the post) to derive a nonce from the key (like the key + 1) but key broadcasting would be sequentially, one participant after the other. One participant broadcast after the other. randomly chosen. $\endgroup$
    – Curcuma_
    Commented Jan 28, 2020 at 11:01
  • $\begingroup$ The secret s, would be a long value like any other encryption algorithm, 128 bits for example, no reason to have a key between 1-100 ? $\endgroup$
    – Curcuma_
    Commented Jan 28, 2020 at 12:02
  • $\begingroup$ The generation of 1000 hashes, is to be cached for each participant, not to be sent. One randomly picked hash is sent. $\endgroup$
    – Curcuma_
    Commented Jan 28, 2020 at 12:42
  • 1
    $\begingroup$ Well in that case, you can pick a nonce of 128 bits (can be more or less, but big enough to not be guessed), add it to the key of 128 bits and provide the hash of that key + nonce, and also provide the nonce. That way, others with the same key can simply add the key to the nonce they received and check if the hashes are the same. If so, the people have the same secret. This ensures nobody has to generate 1000 hashes and also ensures people in the same communities cannot be identified as being from the same community. $\endgroup$
    – vrwim
    Commented Jan 28, 2020 at 12:48
  • $\begingroup$ Oh yes, my bad, I did not figure it out myself, ty! $\endgroup$
    – Curcuma_
    Commented Jan 28, 2020 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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