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:
- m_i-k with k>=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.