Every computing paradigm involving communication requires new security protocols employing cryptography. For example, the Internet gave rise to TLS/SSL, and Mobile Computing gave rise to End-to-End Encryption protocols. In this paper, we address an emerging IoT paradigm involving beacons attached to things and security protocols associated with this new configuration. Specifically, we address the “Beacon Notification Problem,” a critical IoT paradigm aimed at providing secure and efficient real-time notifications from beacons to their owners. Since the beacon notification problem has not yet been formally defined, we begin by inspecting natural requirements based on the operational setting and establishing correctness, security, and privacy definitions through the use of cryptographic games. To resolve the beacon notification problem, we propose a novel cryptographic tool we call XDHIES, which is a considerable extension of available Diffie-Hellman encryption schemes. We then show a new notification protocol built upon XDHIES and we prove that this cryptographic protocol is secure and private and successfully meets all the above problem's requirements.

The notion of traitor tracing was introduced by Chor, Fiat, and Naor [Tracing Traitors, Lecture Notes in Comput. Sci. 839, 1994, pp. 257--270] in order to combat piracy scenarios. Recently, Fiat and Tassa [ Tracing Traitors, Lecture Notes in Comput. Sci. 1666, 1999, pp. 354--371] proposed a dynamic traitor tracing scenario, in which the algorithm adapts dynamically according to the responses of the pirate. Let n be the number of users and p the number of traitors. Our main result is an algorithm which locates p traitors, even if p is unknown, using a watermarking alphabet of size p+1 and an optimal number of $\Theta(p^2 + p\log n)$ rounds. This improves the exponential number of rounds achieved by Fiat and Tassa in this case. We also present two algorithms that use a larger alphabet: for an alphabet of size p+c+1, $c\geq1$, an algorithm that uses O(p 2 /c+ p log n) rounds; for an alphabet of size pc+1, an algorithm that uses O(p log c n ) rounds. Our final result is a lower bound of $\Omega(p^2/c+p\log_{c+1}n)$ rounds for any algorithm that uses an alphabet of size p+c, assuming that p is not known in advance.

A new parallel algorithm for the prefix minima problem is presented for inputs drawn from the range of integers $[1..s]$. For an input of size n, it runs in $O(\log \log \log s)$ time and $O(n)$ work (which is optimal). A faster algorithm is presented for the special case $s = n$; it runs in $O(\log ^ * n)$ time with optimal work. Both algorithms are for the Priority concurrent-read concurrent-write parallel random access machine (CROW PRAM). A possibly surprising outcome of this work is that, whenever the range of the input is restricted, the prefix minima problem can be solved significantly faster than the $\Omega (\log \log n)$ time lower bound in a decision model of parallel computation, as described by Valiant [SIAM J. Comput., 4 (1975), pp. 348–355]. The top-bottom routing problem, which is an important subproblem of routing wires around a rectangle in two layers, is also considered. It is established that, for parallel (and hence for serial) computation, the problem of top-bottom routing is no harder than the prefix minima problem with $s = n$, thus giving an $O(\log ^ * n)$ time optimal parallel algorithm for the top-bottom routing problem. This is one of the first nontrivial problems to be given an optimal parallel algorithm that runs in sublogarithmic time.

This paper introduces a novel parallel data structure called the recursive star-tree (denoted “${}^ * $-tree”). For its definition a generalization of the $ * $ functional is used (where for a function $f * f(n) = \min \{ {i|f^{(i)} (n) \leqslant 1} \}$ and $f^{(i)} $ is the ith iterate of f). Recursive ${}^ * $-trees are derived by using recursion in the spirit of the inverse Ackermann function. The recursive ${}^ * $-tree data structure leads to a new design paradigm for parallel algorithms. This paradigm allows for extremely fast parallel computations, specifically, $O(\alpha (n))$ time (where $\alpha (n)$ is the inverse of the Ackermann function), using an optimal number of processors on the (weakest) concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM). These computations need only constant time, and use an optimal number of processors if the following nonstandard assumption about the model of parallel computation is added to the CRCW PRAM: an extremely small number of processors each can write simultaneously into different bits of the same word. Applications include finding lowest common ancestors in trees by a new algorithm that is considerably simpler than the known algorithms for the problem, restricted domain merging, parentheses matching, and a new parallel reducibility.

It is established that several natural problems have triply logarithmic, or even faster, optimal parallel algorithms. These problems include: merging two sorted lists, where the values are drawn from a large, but restricted, domain on a CREW PRAM; finding all prefix minima, where the values are drawn from a restricted domain; and top-bottom global routing around a rectangle, a well-investigated problem in VLSI routing for which only highly involved serial algorithms were known.>

The authors introduce a fundamentally novel parallel data structure, called recursive *-tree (star tree). For its definition, they use a generalization of this * functional and apply it to functions other than log. Using recursion in the spirit of the inverse-Akermann function, they derive recursive *-trees. The recursive *-tree data structure leads to a new design paradigm for parallel algorithms. The paradigm allows for unusually fast parallel computations that need only constant time, using an optimal number of processors under the assumption that a very small number of processors can write simultaneously, each into different bits of the same word.>

of Results.We establish that several problems are highly parallelizable.For each of these problems, we design an optimal 0 (loglogn ) time parallel algorithm on the Common CRCW PRAM model which is the weakest among the CRCW PRAM models.These problems include: 0 all nearest smaller values, l preprocessing for answering range maxima queries, l several problems in Computational Geometry, l string matching.