Good morning,

I state that I am not an expert in cryptography.

I'm studying the feasibility of a project which looks like requires a kind of cryptographic counter that behave similarly to the one in Katz-Myers-Ostrovsky2001 https://link.springer.com/chapter/10.1007/3-540-44987-6_6 but with a fundamental difference that I'm going to explain.

A brief contextualization.

The counter is embedded in a message m_0 generated at sender s_0 moving along a sequence of edges of a graph and it effectively contains the distance d from the sender (but this can alternatively be a TTL decrementing to zero).

At each node, d less than d_max is checked to let the node s_i decide if further propagate the message. If true, d is incremented by 1 and something not important for the question is computed on the payload, then the message m_i forwarded to s_i+1.

If d=d_max (or alternatively if TTL=0) a reply message is sent back to the original sender s_0.

The message is the first message going around the graph, imagine it like a proximity flooding/exploration. No information (keys or shared secrets) is shared between any node before nor using any means other than this message, except between two adjacent nodes but strictly limited to information about nodes involved in that the specific edge.

I noticed an approach based on timing like in Bojja-Fanti-Viswanath2017 https://arxiv.org/pdf/1701.04439.pdf but this cannot work in my case.

The fundamental difference.

A requisite of the project is bitwise unlinkability between message m_i and any messages:

  1. m_i-k with k>=2
  2. m_i+k with k>=2

the consequence is that I can not transmit the same pk0 along the message to be used in the transition algorithm, nor I can send sk0 to the end node and this invalidates the approach of the first paper.

How to count distance in a hidden but verifiable way?

I haven't found anything googling so I'm trying asking as last resort, at least to find a direction to move forward. Can be likely that I have missed a different common approach to solve the issue.

  • $\begingroup$ You can use an additive homomorphic scheme (e.g., Paillier) to increment an encrypted tally $x$, represented as ciphertext $C_x$, in a private way: $C_x \leftarrow C_x \odot C_1 \odot C_0 \odot C_0 \dots$ where $\odot$ is the additive operator (integer multiplication for Paillier) and we include several encryptions of zero to mask which node did the increment. However, unless the nodes are trusted with the private key, how will they know if the count exceeded the desired hopcount? They can't both know, and not know, the value of the counter at the same time. $\endgroup$ – Russ May 28 '19 at 19:09

Your Answer

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

Browse other questions tagged or ask your own question.