Privacy Pass is a cryptographic scheme for issuing one-time anonymous authorization tokens, first designed as an anti-DDoS tool and an alternative to CAPTCHAs. It has attracted a lot of attention from the industry and is currently used and supported by the technological giants such as Cloudflare, Google and Apple. At the same time, Privacy Enhancing Technologies became the focus of European and non-European lawmakers (for example in the eIDAS 2.0 regulation and GDPR). Security and privacy by-design is now quite frequently a formal requirement. Privacy Pass could be used in that context as well as a lightweight solution for many application areas, e.g., for age verification. It is therefore imperative that Privacy Pass is analyzed in all possible aspects and adversarial models that are realistic, yet have not been considered during the design process. In this work, we first prove that the three most prominent variants of Privacy Pass are anamorphic. Then, we show that anamorphism of Privacy Pass makes it insecure in a model where user's device or client application is working against them (as it can be supplied by a malicious third party, the OS might be subverted or the device could be subverted). Due to anamorphism, the attacks on unlinkability remain undetectable even if an auditor is given all private keys used in the protocol, including the signer/issuer's private key. On the positive side, anamorphism can also be used to achieve a private metadata-like functionality and utilized, for example, for lawful deanonymization of malicious users, without reshaping Privacy Pass.

The paper concerns sampling from a data stream {$S_{i}$}: at a moment t the sampler should hold a value $S_{t-j}$, where j$\in${0,$\ldots$,n-1} should be chosen according to an a priori specified probability distribution D on {0,$\ldots$,n-1}, where D as well as the window size n are fixed and do not depend on t. We assume that the sampler has a constant size memory, while n might be large, so the sampler cannot remember the last n values of the stream except for a few. The problem is that the window of the last n elements changes at each step and when we have to resample, then almost all values from which we have to choose are already forgotten. The case of uniform distribution D has been considered by Braverman, Ostrovsky, and Zaniolo in 2013. We present an alternative generic approach based on specific Markov chains called devil’s staircases. Unlike the previous solution, it is not limited to the uniform distribution: it generates a sample according to any admissible distribution in the window of size n and uses memory of size $\mathrm{O}(1)$. We provide sufficient conditions for the distribution D to be admissible. Although the class of such distributions is quite wide from the point of view of practical applications, we show some natural limitations for this class.

As part of the responses to the ongoing crypto wars, the notion of Anamorphic Encryption was put forth. The notion allows private communication in spite of a dictator who is engaged in an extreme form of surveillance and or censorship, where it asks for all private keys and knows and may even dictate all messages. The original work pointed out efficient ways to use two known schemes in the anamorphic mode, bypassing the draconian censorship and hiding information from the all-powerful dictator. A question left open was whether these examples are outlier results or whether anamorphic mode is pervasive in existing systems. Here we answer the above question: we develop new techniques, expand the notion, and show that the notion of Anamorphic Cryptography is, in fact, very much prevalent. We first refine the notion of Anamorphic Encryption with respect to the nature of covert communication. Specifically, we distinguish Single-Receiver Encryption for many to one communication, and Multiple-Receiver Encryption for many to many communication within the group of conspiring users. We then show that Anamorphic Encryption can be embedded in the randomness used in the encryption, and we give families of constructions that can be applied to numerous ciphers. In total the families cover classical encryption schemes, some of which in actual use. Among our examples is an anamorphic channel with much higher capacity than the regular channel. In sum, the work shows the very large extent of the potential futility of control and censorship over the use of strong encryption by the dictator (typical for and even stronger than governments engaging in the ongoing crypto-wars): While such limitations obviously hurt utility which encryption typically brings to safety in computing systems, they essentially, are not helping the dictator. While the actual implications of what we show here and what it means in practice require further policy and legal analyses and perspectives, the technical aspects regarding the issues are clearly showing the futility of the war against Cryptography.

Driven by various legal obligations and service requirements, the redactable blockchain was introduced to balance the modifiability and immutability of blockchain technology. However, such a blockchain inevitably generates one or even more acceptable versions for the same block data, enabling malicious full nodes to deceive light/new nodes with old data, and even disrupt the consistency of the blockchain ledger. In this paper, we introduce the concept of verifiable redactable blockchain (VRBC) to provide efficient validity verification for on-chain data. To this end, we design a novel authentication data structure, called blockchain authentication tree (BAT), which employs a chameleon hash function and aggregatable vector commitment to bind continuously-appended blocks. Based on this, we propose an efficient VRBC scheme supporting integrity auditing, which not only allows the light nodes to query and validate on-chain data, but also enables new nodes to check the integrity of the blockchain ledger before synchronizing it, effectively avoiding resource waste and security risks caused by invalid queries and ledger synchronization. Furthermore, we introduce some optimized strategies to improve the performance of our scheme and extend it to transaction-level and permissionless VRBC. Finally, we demonstrate the practicability of our scheme through detailed security analysis and visual performance evaluation.

A EU Regulation from 2019 aims to achieve a minimal degree of interoperability of personal identity documents in Europe (eID). In particular, eID document verification should be performed according to ICAO protocols, including biometric verification. At the same time, additional functionalities implemented by the Member States must not interfere with the obligatory ICAO part. As presenting personal data from an eID requires an explicit consent of the eID owner, PACE - a password authenticated key exchange (PAKE) protocol, the core part of the ICAO specification - must be used. A side effect of the EU Regulation are problems regarding already deployed additional functionalities, such as digital signatures. In this paper we present a pragmatic approach for solving this problem. Instead of installing these functionalities independently - e.g. at a cost of extra code on the eID chip and potential compatibility problems - we may reuse the basic ICAO protocols. As an example of this approach we show a proof-of-presence protocol derived from PACE.

A recent CSCML'2020 paper by Dolev and Liber presents a low cost blockchain based on cryptographic mechanism. Its main feature is a mechanism discouraging a user to fork a blockchain - if this happens, then a user's secret is leaked and thereby a proof of his misbehavior emerges. This approach is very attractive as long as we can guarantee that breaking the underlying cryptographic problem is infeasible for all parties. The situation changes dramatically in case of a partial compromise of a cryptographic scheme: when a powerful adversary can break the underlying scheme, while for the regular users the scheme is still resistant to attacks. In this case the blockchain techniques proposed becomes a dangerous trap allowing discrediting the users by powerful parties hiding own cryptanalytic power. To address this problem we introduce a David and Goliath adversary model, where a powerful adversary (Goliath) can break the underlying cryptographic assumption, but for a regular user (David) this is infeasible. For almost all cryptographic schemes, the situation of David is hopeless in this model: e.g., Goliath can forge standard signatures of David. Such an advantage of Goliath in case of a blockchain would be disastrous. We show that one can create a blockchain such that the advantage of Goliath is limited: if he creates a fork in a blockchain mimicking a double-spending attempt by David, then David can prove to be innocent.

Security of many cryptographic protocols is conditioned by the quality of the random elements generated in the course of the protocol execution. On the other hand, cryptographic devices implementing these protocols are designed given technical limitations, usability requirements and cost constraint s. This frequently results in a black box solution. Unfortunately, black box random number generators may enable creating backdoors for stealing signing keys, breaking authentication protocols and encrypted communication. In this paper we deal with this problem and extend our approach proposed during MYCRYPT’2016. The solution discussed is generating random parameters so that: (a) the protocols are backwards compatible (a user gets additional data that can be simply ignored), (b) verification of randomness might be executed any time without notice, so a device is forced to behave honestly, (c) the solution makes almost no intrusion in the existing protocols and is easy to implement, (d) the owner of a cryptographic device becomes secured against its designer and manufacturer that may even predict the output of the generator. In this paper we focus on a case when Diffie-Hellman protocol is executed for a generator that itself is a secret – this case has not been solved in our paper from MYCRYPT’2016. On the other hand, exactly this case occurs for the PACE protocol from the ICAO standard specifying electronic travel documents. For the sake of the proof we develop a framework of nested security games that aims to enable security proofs of modified protocols without redoing the proofs designed for their original versions.

Abstract This special issue contains 28 full papers selected from the Computer Animation

This special issue collates a selection of representative research articles that were primarily presented at the 9th International Conference on Network and System Security. This annual conference brings together researchers and practitioners from both academia and industry who are working on security and privacy in computer systems and social networks, in order to promote an exchange of ideas, discuss future collaborations, and develop new research directions.

The goal of this special issue is to collate a selection of representative research articles that were primarily presented at the 8th International Conference on Network and System Security (NSS 2014). This annual conference brings together researchers and practitioners in the world from both academia and industry who are working on network and system security, in order to foster interaction between researchers and developers, promote an exchange of ideas, discuss future collaborations, and develop new research directions.

The recent advances in cutting-edge electronic and computer technologies and wireless communications have paved the way for the proliferation of wireless networks, encompassing cellular, vehicular, body area, underwater, mobile ad hoc, and sensor networks. Wireless networks, allowing communications from any device, anywhere and anytime, bring a wide range of emerging and disruptive applications in manufacturing, healthcare, military, personal entertainment, safety, and rescue. However, the increasing sophistication and scale of cyber security and crimes in wireless networks have challenged traditional techniques of securing devices, applications, and traffic of wireless networks. Particularly, as the threats and vulnerabilities continue to grow in ubiquitous wireless networks, devices, and applications, it is crucial and imperative for researchers and practitioners of wireless networks to understand the entire cyber-attack and crime spectrum on wireless networks and applications and explore new technologies to mitigate and thwart these attacks, as well as to monitor, capture, and analyze security attacks via forensics analysis. The editorial committees have accepted 12 submissions in this special issue and all the papers have gone through a regular reviewing process. Among these accepted papers, four of them are related to Cloud Computing security. In the paper titled ‘PIMRS: achieving privacy and integrity-preserving multi-owner ranked-keyword search over encrypted cloud data’, Li et al. propose a privacy and integrity-preserving multi-owner ranked-keyword search scheme named PIMRS, where an asymmetric scalar-product encryption function is adopted to preserve data privacy and to obtain more precise search results. In the paper titled ‘MEDAPs: Secure Multi-Entities Delegated Authentication Protocols for Mobile Cloud Computing’, three secure multi-entities delegated authentication protocols are proposed for mobile cloud computing. In these protocols, multiple mobile data owners can authorize a group-designated cloud server with signing rights. Irfan et al. present a framework based on security information and event management to efficiently collect evidence for crime investigation, which can benefit cloud forensics in their paper ‘A framework for cloud forensics evidence collection and analysis using security information and event management’. In the paper ‘Efficient Keyword Search over Encrypted Data in Multi-cloud Setting’, Miao et al. propose two keyword search schemes over encrypted data in multi-cloud setting scenarios. The proposed schemes can guarantee data privacy and reliability. Furthermore, the experimental results indicate that the proposed schemes are feasible and efficient in practical applications. Besides cloud computing security, this special issue also involves another 8 papers covering a wide variety of topics. In the paper titled ‘Secure the Internet, one home at a time’, Xu et al. propose a Bloom-filter based analytics framework to capture persistent threats towards the same home routers and to identify correlated attacks towards distributed home networks. This work is the first one to characterize cyber threats towards home networks. In the paper titled ‘Secure multi-unit sealed first-price auction mechanisms’, Li et al. propose three secure, multi-unit, sealed-bid, and first-price auction schemes. An auctioneer is able to verify that the winners have paid the correct amounts in these three schemes. Theoretical analysis is provided to evaluate the security properties, computational complexity, and communication complexity of the auctions. Zhang et al. propose a data aggregation approach where an untrustful aggregator in mobile sensing can collect statistic data from mobile users in their paper titled ‘An Efficient Privacy Preserving Data Aggregation Approach for Mobile Sensing’. This approach preserves user privacy and can perform data integrity verification. Lai et al. propose a secure and privacy-preserving group setup framework, SPGS, for platoon-based VCPS in their paper titled ‘SPGS: A Secure and Privacy-Preserving Group Setup Framework for Platoon-Based Vehicular Cyber-Physical Systems’. Two authentication protocols are also provided accordingly. The security feature and efficiency of SPGS are verified by the thorough analysis. In the paper titled ‘Multi-proxy multi-signature binding positioning protocol’, Xue et al. propose a multi-proxy multi-signature binding positioning protocol, based on which a multi-proxy multi-signature binding positioning protocol is designed. The correctness and security features of the proposed protocols are analyzed. Qi et al. propose an effective steganography attacking method which is not limited by the types of the steganography method in their paper titled ‘Generic attack against robust steganography based on spring transform and geometrization’. The experiment results indicate that the peak signal-to-noise ratio of images can be above 32 dB Q4 while the stego data are destroyed. In the paper titled ‘Active jamming for multi-user information security improvement with the access statuses of users’, Xu et al. propose a novel physical layer scheme for improving multiple users' information security in the next-generation communication systems. The proposed scheme is linear without iteration and it is feasible for multi-user security enhancement. In the paper titled ‘Secured measurement fusion scheme against deceptive ECM attack in radar network’, in order to prevent electronic countermeasure attacks in radar networks, Yang et al. propose a new measurement fusion scheme, which shows better security performance when a DECM attack happens. The authors also perform simulations to demonstrate the superior of their novel scheme. On behalf of the editorial committee, we would like to thank all the authors for contributing their high quality papers to this special issue. We also want to thank all the reviewers for volunteering their time to review the papers and providing valuable comments, which help with improving the quality of the papers. We are also grateful to Prof. Hsiao-Hwa Chen and Prof. Hamid R. Sharif, who are the Editor-in-Chiefs of Security and Communication Networks, for providing us the opportunity to organize this special issue and for their support during the whole publication process.

Anonymous credential systems have to provide strong privacy protection: a user may prove his (chosen) attributes without leaking neither his identity nor other attributes. In this paper we consider U-Prove - one of the major commercial anonymous credential systems.

A key distribution scheme for wireless sensor networks based on a system of dynamic, pairwise keys is considered. In the scheme, each pair of communicating nodes shares pairwise symmetric keys and changes them at every transmission using a set of hashing functions. This article examines security aspects of the protocol. The most important issue is to ensure that it is infeasible for an adversary to restrict exhaustive key search to a subset of the keyspace. This desirable property holds if, after a small number of random key transitions, the distribution of keys among the nodes is close to uniform. The article provides a rigorous mathematical analysis of the distribution of keys and supplements it with experimental results. The problem is reduced to the question of determining mixing time and the stationary distribution of a random walk on a random digraph. It is shown that with probability close to 1, the mixing time is of small order and the fluctuations of the distribution are limited. This ensures the ongoing security of the protocol by making the communications forward secure and protecting against node compromise.

We present two protocols for data aggregation in networks consisting of many subsystems run by different and potentially adversarial parties. In such a case the messages from the nodes of a subnetwork are aggregated and transmitted to the sink over intermediate nodes which are not controlled by the subnetwork, and which potentially are influenced by an adversary. The adversary aims at changing the result of computations and/or learning the data processed by the stations of the subnetwork.

We present a variant of the protocol stack for anonymous authentication implemented in German personal identity documents. We strengthen the system by eliminating group keys - a potential target of attack for a powerful adversary aiming to undermine Restricted Identification mechanisms. We provide a mechanism of authentication that merges Chip Authentication protocol with Restricted Identification.

We propose a solution for electronic identity cards that makes it possible to create multiple identities for a person creating digital signatures with just one private key stored on his personal electronic identity card. The public keys corresponding to this secret key belong to different sectors, devoted to different applications or activity areas (like private use and signing in behalf of a company or an authority). We provide strong privacy guarantees called unlinkability. It means that given two public keys from different sectors and some signatures corresponding to these keys, it is unfeasible to say if these keys (and signatures) come from the same person. The proof is performed in the random oracle model and reduces linkability to the Decisional Diffie-Hellman Problem. Our proposal extends the idea of Restricted Identification introduced in German personal identity cards from unlinkable sector identification to unlinkable sector signatures.

We consider a scenario in which Alice entitles Bob to serve as her proxy with the right to sign one out of two possible documents, say m1 and m2. The protocol guarantees that the data given to Bob cannot be recognized as signatures of m1 and m2, unless Bob transforms them with his private key. The most important feature is, however, then if Bob finalizes both signatures (of m1 and of m2) - violating the delegated rights, then Bob's private key will be revealed to Alice. So we propose an undeniable proof of misbehavior instead of other means that turn out to be less effective and more difficult to implement.

We consider access scheduling to a shared radio channel in networks where a set of stations tries to get exclusive rights to transmit over a shared radio channel. A frequent strategy to solve this problem is that each station independently tosses an asymmetric coin and transmits in case of tails. The trials are executed some number of times and the first station that sends alone in a trial gets the right to broadcast over the shared channel. We consider here a multi-channel case: during onetime slot a station may transmit on k different channels.In this case trials can be arranged in two slightly different ways. The first method is that in each trial a station decides whether to participate in it; if it is so, then the station decides independently for each channel whether to transmit on it. According to the second method a station makes one decision whether to send and if the decision is positive it chooses a single channel for transmission. The second method guarantees a limited energy cost for each station but,as we show, turns out to be inferior regarding success probability. We consider these algorithms for a realistic number of stations. We analyze subtle differences between both algorithms regarding success probability.

We investigate a problem of maintaining a target population of mobile agents in a distributed system. The purpose of the agents is to perform certain activities, so the goal is to avoid overpopulation (leading to waste of resources) as well as underpopulation (resulting in a poor service). We assume that there must be no centralized control over the number of agents, since it might result in system's vulnerability. We analyze a simple protocol in which each node keeps at most one copy of an agent and if there is a single agent in a node, a new agent is born with a certain probability p. At each time step the agents migrate independently at random to chosen locations. We show that during a protocol execution the number of agents stabilizes around a level depending on p. We derive analytically simple formulas that determine probability p based on the target fraction of nodes holding an agent. The previous proposals of this type were based on experimental data only.

We consider an ad-hoc network consisting of devices that try to gain access for transmission through a shared radio communication channel. We consider two randomized leader election protocols the first one is due to Nakanoand Olariu (2000); the second one is due to Cai, Lu and Wang (2003) and propose combinations which give us an improvement of both of them. We show that with discrete starting points of transmission, between which a station may choose in a non-uniform way, leads to a simple algorithm that substantially outperforms the previous techniques of resolving channel access problems. We provide methods to optimize values of parameters used.

The authors presents a key management scheme for broadcast networks, which is a combination of broadcast encryption protocols of different kinds: an exclusion scheme based on Lagrangian interpolation in the exponent and a non-exclusion scheme. The authors show how to combine these techniques into one scheme in such a way that information on who is excluded and when they are excluded is hidden under certain adversary models, and communication overhead is independent of the system dynamics. Thus, the scheme is well suited for the general cases where the maximum number of excluded users is unpredictable.

A cascade of mix servers is a crucial part of e-voting protocols and other schemes which aim for user's anonymity. We present kleptographic attacks on such cascades. In order to show interesting consequences, we focus on a cascade used as a building block of a Prêt à Voter e-voting protocol. However, the attacks might be generalized to any cascade of probabilistic mix servers.

Abstract Quite often algorithms designed for no‐collision‐detection radio networks use a hidden form of collision detection: it is assumed that a station can simultaneously send and listen. If it cannot hear its own message, apparently the message has been scrambled by another station sending at the same time. Industrial standard IEEE 802.11 says that a station can either send or listen to a radio channel at a given time, but not both. In order to relate the industrial standard and theoretical algorithms we consider a weak radio network model with no collision detection in which a station cannot simultaneously send and receive signals. Otherwise we talk about a strong model. In this paper we consider a measure called energy cost (or ‘power consumption’) which is equal to the maximum over all stations of the number of steps in which the station is sending or listening. We show that computational power of weak and strong single‐hop radio networks differ substantially in the deterministic case: deterministic leader election requires $\Omega(\log n)$ energy cost in the weak model and can be solved by a practical algorithm with $O(\sqrt{\log n})$ energy cost in the strong model. By contrast, we present a very efficient randomized simulation of strong radio networks by weak ones, with preprocessing that requires $O(n)$ steps and has energy cost $O(\log \log n)$ . Copyright © 2003 John Wiley & Sons, Ltd.

We present energy efficient algorithms for leader election in single channel single-hop radio networks with no collision detection. We present a deterministic solution with sublogarithmic energy cost (the best previous result was O(logn)) and show a double logarithmic lower bound. We prove that this lower bound holds in a randomized case, in a certain sense. For the case, when the number n of active stations can be approximated in advance, we show a randomized algorithm with energy consumption O(log ∗ n) that yields a result with high probability (the best previous result was O(loglogn)). 1.

We consider systems consisting of a constant number of finite automata communicating via messages. We assume that the automata are asynchronous, but the answers given by the system must be always correct. We examine computational power of such systems by inspecting the number of messages exchanged. This is motivated by the fact that communication volume is one of the most important complexity measures. We show that any asynchronous system of finite automata that exchanges o(n) messages is able to recognize regular languages only. This is much different than in the case of synchronous systems considered before (where already a constant number of messages suffices to recognize some non-regular languages). We show that asynchronous and synchronous systems may differ significantly in their computational power also for tasks requiring ( n) messages. We consider a language Ltrans consisting of words of the form A#A T , where A T denotes transposition of matrix A and the matrices are written row by row. While it is easy to see thatLtrans can be recognized withO(n) messages by a synchronous system of finite automata, we show thatLtrans requires ( n 3=2 = log 2 n) messages on any asynchronous system.

We consider comparator networks M that are used repeatedly: while the output produced by M is not sorted, it is fed again into M . Sorting algorithms working in this way are called periodic . The number of parallel steps performed during a single run of M is called its period , the sorting time of M is the total number of parallel steps that are necessary to sort in the worst case. Periodic sorting networks have the advantage that they need little hardware (control logic, wiring, area) and that they are adaptive. We are interested in comparator networks of a constant period, due to their potential applications in hardware design. Previously, very little was known on such networks. The fastest solutions required time O(n ε ) where the depth was roughly 1/ε. We introduce a general method called periodification scheme that converts automatically an arbitrary sorting network that sorts n items in time T(n ) and that has layout area A(n ) into a sorting network that has period 5, sorts ***( n • T ( n ) items in time O(T( )• log n ), and has layout area O(A(n) ) • T(n )). In particular, applying this scheme to Batcher's algorithms, we get practical period 5 comparator networks that sort in time O (log 3 n ). For theoretical interest, one may use the AKS netork resulting in a period 5 comparator network with runtime O (log 2 n ).

We consider the problem of sorting sequences obtained from a sorted sequence of n keys by changing the values of at most k keys at some unknown positions. Since even for k=1 a lower bound /spl Omega/(log n) on the number of parallel comparison steps applies, any comparator network solving this problem cannot be asymptotically faster than the AKS sorting network. We design a comparator network which sorts the sequences considered for a large range of k's, has a simple architecture and achieves a runtime c/spl middot/log n, for a small constant c. We present such networks of depth 4 log n+O(log/sup 2/ k log log n) with a small constant hidden behind the big "Oh". In particular, for k=o(2/spl radic/(log n/log log n)) the networks are of depth 4 log n+o(log n).

Lower and upper bounds for finding a minimum spanning tree (MST) in a weighted undirected graph on the BSP model are presented. We provide the first non-trivial lower bounds on the communication volume required to solve the MST problem. Let p denote the number of processors, n the number of nodes of the input graph, and m the number of edges of the input graph. We show that in the worst case a total of \\Omega\\Gamma \\Delta min(m;pn)) bits need to be transmitted in order to solve the MST problem, where is the number of bits required to represent a single edge weight. This implies that if each message contains bits, any BSP algorithm for finding an MST requires communication time\\Omega\\Gamma g \\Delta min(m=p; n)), where g is the gap parameter of the BSP model. In addition, we present two algorithms whose running times match the lower bounds in different situations. Both algorith...

It was shown some years ago that the computation time for many important Boolean functions of n arguments on concurrent-read exclusive-write parallel random-access machines (CREW PRAMs) of unlimited size is at least $\varphi (n) \approx 0.72\log _2 n$. On the other hand, it is known that every Boolean function of n arguments can be computed in $\varphi (n) + 1$ steps on a CREW PRAM with $n \cdot 2^{n - 1} $ processors and memory cells. In the case of the OR of n bits, n processors and cells are sufficient. In this paper, it is shown that for many important functions, there are CREW PRAM algorithms that almost meet the lower bound in that they take $\varphi (n) + o(\log n)$ steps but use only a small number of processors and memory cells (in most cases, n). In addition, the cells only have to store binary words of bounded length (in most cases, length 1). We call such algorithms “feasible.” The functions concerned include the following: the PARITY function and, more generally, all symmetric functions; a large class of Boolean formulas; some functions over non-Boolean domains $\{ 0, \ldots ,k - 1\} $ for small k, in particular, parallel-prefix sums; addition of n-bit numbers; and sorting ${n / l}$ binary numbers of length l. Further, it is shown that Boolean circuits with fan-in 2, depth d, and size s can be evaluated by CREW PRAMs with fewer than s processors in ,$\varphi (2^d ) + o(d) \approx 0.72d + o(d)$ steps. For the exclusive-read exclusive-write (EREW) PRAM model, a feasible algorithm is described that computes PARITY of n bits in $0.86\log _2 n$ steps.

A periodic comparator network has depth (or period) k, if for every t>k, the compare-exchange operations performed at step t are executed between exactly the same registers as at step t-k. We introduce a general method that converts an arbitrary comparator network that sorts n items in time T(n) and that has layout area A into a periodic sorting network of depth 5 that sorts /spl Theta/(n/spl middot/T(n)) items in time O(T(n)/spl middot/log n) and has layout area O(A/spl middot/T(n)). This scheme applied to the AKS network yields a depth 5 periodic comparator network that sorts in time O(log/sup 2/ n). More practical networks with runtime O(log/sup 3/ n) can be obtained from Batcher's networks. Developing the techniques for the main result, we improve some previous results: Let us fix a d/spl isin/N. Then we can construct a network of depth 3 based on a d-dimensional mesh sorting n items in time O(n/sup 1/d//spl middot/log/sup O(d/) n).>

This paper is concerned with parallel random access machines (PRAMS), where each processor can read from and write into a common random access memory. Different processors may read the same memory location at a time, but only one processor is allowed to write into it (the CREW model). Suppose f is a Boolean function of n variables. Let ${\operatorname{CREW}}(f)$ be the number of steps required by CREW PRAMS to compute function f It has been proved that ${\operatorname{CREW}}(f) \geqq \log _b {\operatorname{crit}}(f)$, where $b \approx 4.79$ and $crit(f)$ is the critical complexity of and f (see [S. Cook, C. Dwork, and R. Reischuk, SIAM J. Comput.,15 (1986), pp. 87–97]). It was proved by Parberry and Pei Yuan Yan [SIAM J. Comput., 20 (1991), pp. 88–99] that the same holds for $b = 4$. It follows that the time required by the logical *#8220;or” of n variables is at least $\log _4 n$. This paper presents an essentially different method of estimating PRAM complexity of Boolean functions. Let and $n_f$ be the number of inputs $x \in \{ 0,1 \}^n $ for which $f(x) = 1$. Let $i_f = \max \{ {j:2^j |n_f } \}$. Then ${\operatorname{CREW}}(f) \geqq \log _c (n - i_f )$, where $c \approx 2.618$. Thanks to this result, the time complexity of the logical “or” of n variables is determined exactly. This in turn allows better estimations of time complexity of the threshold functions to be obtained. Another corollary is that for sorting n arbitrary keys, PRAMS require time, which can be determined up to five steps.

Article Free Access Share on Exact time bounds for computing boolean functions on PRAMs without simultaneous writes Authors: M. Dietzfelbinger Universität-GH-Paderborn, F.R.G. Universität-GH-Paderborn, F.R.G.View Profile , M. Kutylowski University of Wroclaw, Poland University of Wroclaw, PolandView Profile , R. Reischuk Technische Hochschule Darmstadt, F.R.G. Technische Hochschule Darmstadt, F.R.G.View Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 125–135https://doi.org/10.1145/97444.97678Published:01 May 1990Publication History 14citation271DownloadsMetricsTotal Citations14Total Downloads271Last 12 Months10Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Alternating Turing machines (ATMs) with bounded number of reversals are considered. It is proved that the machines making fewer than $\log ^{*} n$ reversals can recognize only regular languages. On the other hand, the class of languages that can be recognized by ATMs using $\log ^{*} n$ reversals is very wide. The authors prove that above this limit even a slight increase of the number of reversals leads to a considerably larger class of languages. It is also proved that every $T(n)$-time bounded ATM may be replaced by an equivalent machine working in the same time and making no more than $\log ^{*} (T(n))$ reversals.

Abstract In this paper we present a negative solution of counting problems for some classes slightly different from bounded arithmetic (Δ0sets). To get the results we study properties of chains of finite automata.