the other node (twin-node) it is sharing a twin-
key with. Second, for each aggregation phase, we
use an anonymous liveness announcement proto-
col t o declare the liveness of each twin-key—each
node becomes aware of whether a twin-key it pos-
sesses will be used by the anonymous twin-node.
Finally, during the aggregation phase, each node
encrypts its own value by adding shadow values
computed from the alive twin-keys it holds. As a
result, the contribution of the shadow values for
each twin-key will cancel out each other.
Our protocol consists of three major steps as
follows:
1. Local cluster formation: In this step, we re-
quire the network nodes t o group themselves
into clusters. In literature, there are different
solutions for the cluster formation. The de-
scription of a detailed cluster formation al-
gorithm is out of the scope of this paper. In
the following, we assume that a cluster al-
gorithm such as the one proposed in [4] is
used. For ease of exposition, from now on
we also assume that each cluster has a fixed
number of nodes, C. In the following steps of
the protocol, we further require each cluster
to form different logical Hamiltonian circuits.
Note that an extension of the cluster forma-
tion in [4] can be used fo r the Hamiltonian cir-
cuit formation: e.g. the hash function, H, de-
scribed in the previous Section returns a value
for each node; the order of these values define
an order of the corresponding nodes that can
be used to determine the next and previous
neighbour of each node. As another example,
a node, say n
i
, can start setting a new circuit
by randomly choosing one cluster node, say
n
j
, as its next (right) neighbor in a circuit.
Node n
i
communicates its choice to node n
j
.
The selected node, n
j
, will choose its own next
(right) neighbor within the nodes in the same
cluster, t hat are not yet selected. Eventually,
the last node will select node n
i
as its next
(right) neighbor, t o complete the Hamiltonian
circuit. We observe that, we require to build
just a logical circuit that it is not based on any
physical information (as for example a right
nodes b eing actually on the right of a node)
but on the fact tha t the considered nodes are
in the same neighbourhood (i.e. they are in
the communication range of each other). As
a result, no GPS equipments of any triangu-
lation task is required. Finally, we require for
each pair of nodes that are neighbors in the
circuit to share a pair-wise key.
2. Twin-key establishment: This step is per-
formed independently within each local clus-
ter. We recall that we assume that each node
contains a pre-deployed key-ring of K sym-
metric keys, randomly chosen from a larger
common key-pool of size P . In this step, each
node n
i
anonymously checks which ones of its
K keys are also shared with other nodes in
the same cluster. In particular, a node is re-
quired to have at least A out if its K keys
shared within its local cluster. This step will
be further discussed in Section 5.
3. Data aggregation: This is the actual aggre-
gation step of our protocol. Note that, other
than this step, all the previous steps are per-
formed only once during the set-up phase.
The data agg r ega tio n step can be further di-
vided into two main parts:
3.1. First, each cluster computes the aggre-
gated value of its nodes, together with
a twin-key liveness announcement proce-
dure. During this phase an a ggregate is
routed twice along the Hamiltonian cir-
cuit. Each node adds to the aggregate its
own sensed value. At the same time, for
each alive twin-key it adds (or removes,
in accordance with the liveness announce-
ment) a corresponding shadow value. As a
result, the cluster head obtains the correct
aggregate for the cluster.
The liveness announcement guarantees
that any shadow value, computed f r om a
twin-key, that is added in the aggregation
by one node, will be removed by another
node that shares the same twin-key.
3.2. At the end of step 3.1, there will be several
nodes in the network that acted as cluster
heads. These nodes own the correspond-
ing cluster aggregates. Now, we want to
further ag gregate all of these values and
5