Search

Participatory sensing is often used in environmental or personal data monitoring, wherein a number of participants collect data using their mobile intelligent devices for earning the incentives. However, a lot of additional information is submitted along with the data, such as the participant’s location, IP and incentives. This multimodal information implicitly links to the participant’s identity and exposes the participant’s privacy. In order to solve the issue of these multimodal information associating with participants’ identities, this paper proposes a protocol to ensure anonymous data reporting while providing a dynamic incentive mechanism simultaneously. The proposed protocol first establishes a submission schedule by anonymously selecting a slot in a vector by each member where every member and system entities are oblivious of other members’ slots and then uses this schedule to submit the all members’ data in an encoded vector through bulk transfer and multiplayer dining cryptographers networks (DC-nets) . Hence, the link between the data and the member’s identity is broken. The incentive mechanism uses blind signature to anonymously mark the price and complete the micropayments transfer. Finally, the theoretical analysis of the protocol proves the anonymity, integrity, and efficiency of this protocol. We implemented and tested the protocol on Android phones. The experiment results show that the protocol is efficient for low latency tolerable applications, which is the cases with most participatory sensing applications, and they also show the advantage of our optimization over similar anonymous data reporting protocols.

A k-anonymous broadcast can be implemented using a small group of dining cryptographers to first share the message, followed by a flooding phase started by group members. Members have little incentive to forward the message in a timely manner, as forwarding incurs costs, or they may even profit from keeping the message. In worst case, this leaves the true originator as the only sender, rendering the dining-cryptographers phase useless and compromising their privacy. We present a novel approach using a modified dining-cryptographers protocol to distributed shares of an (n,k)-Shamir's secret sharing scheme. Finally, all group members broadcast their received share through the network, allowing any recipient of k shares to reconstruct the message, enforcing anonymity. If less than k group members broadcast their shares, the message cannot be decoded thus preventing privacy breaches for the originator. Our system provides (n-|attackers|)-anonymity for up to k-1 attackers and has little performance impact on dissemination. We show these results in a security analysis and performance evaluation based on a proof-of-concept prototype. Throughput rates between 10 and 100 kB/s are enough for many real applications with high privacy requirements, e.g., financial blockchain system., 16 pages, 5 figures

Opacity is a property of a system that captures whether certain event sequences (or certain states) are indistinguishable from other event sequences (or states) in the system. Opacity is used in analyzing privacy, secrecy, and other aspects of systems modeled by discrete-event systems. In this paper, we introduce the concept of minimal information release policies for non-opacity and the concept of mixed opacity. Mixed opacity policies are introduced as a holistic approach for solving problems that involve a combination of releasing information to make some objectives of the system opaque while making some other objectives non-opaque. We present a set of algorithms for information release under a mixed opacity policy. These algorithms compute policies in a system such that two given sublanguages are opaque, and at the same time, two other sublanguages in the same system are non-opaque. The application of mixed opacity is demonstrated on the Dining Cryptographers Problem. Note to Practitioners —Many organizations and companies must deal with maintaining privacy and secrecy and the protection of their intellectual property while at the same time revealing information to their employees so that they can properly do their jobs. In addition, to maintain transparency, companies and organizations must also reveal information to the public. In this paper, discrete-event system’s modeling is used to produce policies that capture the balance between privacy and transparency.

A Dining Cryptographers network (DCnet for short) allows anonymous communication with sender and receiver untraceability even if an adversary has unlimited access to the connection metadata of the network. Originally introduced by David Chaum in the 1980s, DCnets were for a long time considered not practical for real-world applications because of the tremendous communication and computation overhead they introduce. However, technological innovations such as 5G networks and extremely powerful 64-bit processors make a good case to reassess the practicality of DCnets. In addition, recent advances in elliptic-curve based commitment schemes and Zero-Knowledge Proofs (ZKPs) provide a great opportunity to reduce the computational cost of modern DCnets that are able to detect malicious behavior of communicating parties. In this paper we introduce X64ECC, a self-contained library for Elliptic Curve Cryptography (ECC) developed from scratch to support all the public-key operations needed by modern DCnets: key exchange, digital signatures, Pedersen commitments, and ZKPs. X64ECC is written in C and uses compiler intrinsics to speed up performance-critical arithmetic operations. It is highly scalable and works with Montgomery curves and twisted Edwards curves of different cryptographic strength. Despite its high scalability and portability, X64ECC is able to compute a fixed-base scalar multiplication on a twisted Edwards curve over a 255-bit prime field in about 145,000 clock cycles on a modern Intel X64 processor. All cryptosystems can be adapted on-the-fly (i.e. without recompilation) to implement DCnets with arbitrary message sizes, and tradeoffs between the cryptographic strength and throughput of a DCnet are possible.

Most of the software model checkers available for code level verification can only verify safety properties since desired properties are specified by assertions. However, other temporal properties such as liveness cannot be verified with these tools. To tackle this problem, we develop a verification tool called UMC4M to verify full regular temporal properties of programs. UMC4M takes a modeling, simulation and verification language (MSVL) program M and a desired property specified by a propositional projection temporal logic (PPTL) formula P as its input. \(\lnot P\) is then translated to an MSVL program M. Thus, the property can be verified by checking whether there is an acceptable execution of “\(M~and~M'\)”, which can be solved with MSVL compiler MC. Further, UMC4M is used to verify the dining cryptographers protocol.

Hiding contents of users' messages has been successfully addressed before, while anonymization of message senders remains a challenge since users do not usually trust ISPs and messaging application providers. To resolve this challenge, several solutions have been proposed so far. Among them, the Dining Cryptographers network protocol (DC-net) provides the strongest anonymity guarantees. However, DC-net suffers from two critical issues that makes it impractical, i.e., (1) collision possibility and (2) vulnerability against disruptions. Apart from that, we noticed a third critical issue during our investigation. (3) DC-net users can be deanonymized after they publish at least three messages. We name this problem the short stability issue and prove that anonymity is provided only for a few cycles of message publishing. As far as we know, this problem has not been identified in the previous research works. In this paper, we propose Harmonized and Stable DC-net (HSDC-net), a self-organizing protocol for anonymous communications. In our protocol design, we first resolve the short stability issue and obtain SDC-net, a stable extension of DC-net. Then, we integrate the Slot Reservation and Disruption Management sub-protocols into SDC-net to overcome the collision and security issues, respectively. The obtained HSDC-net protocol can also be integrated into blockchain-based cryptocurrencies (e.g. Bitcoin) to mix multiple transactions (belonging to different users) into a single transaction in such a way that the source of each payment is unknown. This preserves privacy of blockchain users. Our prototype implementation shows that HSDC-net achieves low latencies that makes it a practical protocol.

Hyperproperties have shown to be a powerful tool for expressing and reasoning about information-flow security policies. In this paper, we investigate the problem of statistical model checking (SMC) for hyperproperties. Unlike exhaustive model checking, SMC works based on drawing samples from the system at hand and evaluate the specification with statistical confidence. The main benefit of applying SMC over exhaustive techniques is its efficiency and scalability. To reason about probabilistic hyperproperties, we first propose the temporal logic HyperPCLT* that extends PCTL* and HyperPCTL. We show that HyperPCLT* can express important probabilistic information-flow security policies that cannot be expressed with HyperPCTL. Then, we introduce SMC algorithms for verifying HyperPCLT* formulas on discrete-time Markov chains, based on sequential probability ratio tests (SPRT) with a new notion of multi-dimensional indifference region. Our SMC algorithms can handle both non-nested and nested probability operators for any desired significance level. To show the effectiveness of our technique, we evaluate our SMC algorithms on four case studies focused on information security: timing side-channel vulnerability in encryption, probabilistic anonymity in dining cryptographers, probabilistic noninterference of parallel programs, and the performance of a randomized cache replacement policy that acts as a countermeasure against cache flush attacks.

In this article, we further investigate opacity of discrete event systems. In our previous work, we defined three types of opacity: strong opacity, weak opacity, and no opacity. Strong opacity can be used to study security-related problems whereas no opacity can be used to study fault detection and diagnosis problems. In this study, we investigate the properties of strong, weak, and no opacity. We show that opacity is often closed under union, but may not be closed under the intersection. We also investigate the largest opaque sublanguages and the smallest opaque superlanguages of a language if the language is not opaque. We derive formulas for these sublanguages and superlanguages. We then extend these results from centralized opacity to decentralized opacity, when more than one observer or controller is observing the system. Finally, we apply the results to the Dining Cryptographers Problem. We show that the protocol proposed in the literature satisfies both no opacity the cryptographers know if the boss is paying and strong opacity the cryptographers do not know who is paying if the boss is not paying. We also use the formulas derived in this article to synthesize the protocol, which is much more difficult to do than verifying the protocol.

Opacity is important in investigating secrecy, privacy, and other properties in general systems that can be modeled as discrete event systems. To ensure opacity, a controller may be used to control information released to the public. For transparency and other reasons, it is often desired that the information released to the public be maximum, as long as opacity is not violated. In this paper, we investigate how to release the maximum information while ensuring opacity. We find a necessary and sufficient condition for an information release policy to ensure opacity. We also develop methods and algorithms to design a controller that releases maximum information. We consider both strong opacity and weak opacity. We apply the results to the dining cryptographers problem.

This paper presents a framework for calculating measures of data integrity for programs in a small imperative language. The authors develop a Markov chain semantics for their language which calculates Clarkson and Schneider's definitions of data contamination, data suppression, program suppression and program transmission. The authors then propose their own definition of program integrity for probabilistic specifications. These definitions are based on conditional mutual information and entropy; they present a result relating them to mutual information, which can be calculated by a number of existing tools. The authors extend a quantitative information flow tool (CH-IMP) to calculate these measures of integrity and demonstrate this tool with examples including error correcting codes, the Dining Cryptographers protocol and the attempts by a number of banks to influence the Libor rate.

We introduce a framework for the symbolic verification of epistemic properties of programs expressed in a class of general-purpose programming languages. To this end, we reduce the verification problem to that of satisfiability of first-order formulae in appropriate theories. We prove the correctness of our reduction and we validate our proposal by applying it to two examples: the dining cryptographers problem and the ThreeBallot voting protocol. We put forward an implementation using existing solvers, and report experimental results showing that the approach can perform better than state-of-the-art symbolic model checkers for temporal-epistemic logic.

The increasing adoption of the Internet of Things introduces new threats that affect the privacy of users. Current privacy enhancing technologies are not sufficient to address all these new threats. This paper explains one of the most powerful protocols, namely DC-net. The DC-net protocol, while more than 30 years old, was never used in real-life due to its overhead and sensitivity with regards to disrupters. However, many improvements have been contributed to the original protocol, which is summarised in this paper. The main contribution of this work is the implementation of a proof-of-concept DC-net suited for constrained microcontroller-based devices. The challenges faced and the optimisations done throughout the implementation are presented.

Given a description of the quantitative information flow (qif) for components, how can we determine the qif of a system composed from components? We explore this fundamental question mathematically and provide an answer based on a new composition operator. We investigate its properties and prove that it generalises existing composition operators. We illustrate the results with a fresh look on Chaum’s dining cryptographers. We show that the new operator enjoys various convenient algebraic properties and that it is well-behaved under composition refinement.

A crucial goal in computer security is to protect sensitive information from unwanted disclosure. However, some leakage is often unavoidable, be it by design of the system or by technological limitations. The field of Quantitative Information Flow (QIF) is concerned with the quantification, and limitation, of information leakage in systems.

Users often wish to communicate anonymously on the Internet, for example, in group discussion or instant messaging forums. Existing solutions are vulnerable to misbehaving users, however, who may abuse their anonymity to disrupt communication. Dining Cryptographers Networks (DC-nets) leave groups vulnerable to denial-of-service and Sybil attacks; mix networks are difficult to protect against traffic analysis; and accountable voting schemes are unsuited to general anonymous messaging. dissent is the first general protocol offering provable anonymity and accountability for moderate-size groups, while efficiently handling unbalanced communication demands among users. We present an improved and hardened dissent protocol, define its precise security properties, and offer rigorous proofs of these properties. The improved protocol systematically addresses the delicate balance between provably hiding the identities of well-behaved users, while provably revealing the identities of disruptive users, a challenging task because many forms of misbehavior are inherently undetectable. The new protocol also addresses several nontrivial attacks on the original dissent protocol stemming from subtle design flaws.

Programs are under continuous attack for disclosing secret information, and defending against these attacks is becoming increasingly vital. An attractive approach for protection is to measure the amount of secret information that might leak to attackers. A fundamental issue in computing information leakage is that given a program and attackers with various knowledge of the secret information, what is the maximum amount of leakage of the program? This is called channel capacity. In this paper, two notions of capacity are defined for concurrent probabilistic programs using information theory. These definitions consider intermediate leakage and the scheduler effect. These capacities are computed by a constrained nonlinear optimization problem. Therefore, an evolutionary algorithm is proposed to compute the capacities. Single preference voting and dining cryptographers protocols are analyzed as case studies to show how the proposed approach can automatically compute the capacities. The results demonstrate that there are attackers who can learn the whole secret of both the single preference protocol and dining cryptographers protocol. The proposed evolutionary algorithm is a general approach for computing any type of capacity in any kind of program.

In this paper, we explore the Dining Cryptographers’ protocol over a cyclic group with a one-way homomorphic image, using a boardroom voting protocol as an illustration of its desirable security properties. In particular, we address the problem of anonymous disruption, which is one of the main disadvantages of DC over more usual groups like binary vectors.

In many applications, such as e-voting, it is imperative that the privacy reaches a level of unconditional security. In this context, protocols that verify that condition reach maximum interest. Probably, the most interesting of them is Non Interactive Dining cryptographers (NIDC), which relaxes the condition of concurrency online for all participants. NIDC proposes to store the vote on a table of slots, demanding that the selection of the location of each vote is truly random. However, the probability that two votes are accommodated in the same slot (collision) is positive. And if that event occurs, both votes are lost. This paper, after reviewing records which demonstrate that it is preferable to use multiple parallel channels while maintaining the original number of slots, proposes a systematic method to get the optimum for each of the parameters involved values: number of channels, measure them and probability level required for the event "no vote is lost." Additionally, the proposed solutions are enhanced, suggesting a way to work on collisions.

Sealed bid auctions are a popular means of high-stakes bidding, as they eliminate the temporal element from the auction process, allowing participants to take less emotional, more thoughtful decisions. In this paper, we propose a digital communication protocol for conducting sealed bid auctions with high stakes, where the anonymity of bids as well as other aspects of fairness must be protected. The Dining Cryptographers’ Protocol (denoted by DC) was presented by David Chaum in 1988. The protocol allows the participants to broadcast a message anonymously. In a recent paper (Another Twist in the Dining Cryptographers’ Protocol, submitted to the Journal of Cryptology) the authors propose a variant of the original DC eliminating its main disadvantages. In this paper we present a cryptographic protocol realizing anonymous sealed bid auctions, such as first price or Vickrey auction, based on this variant. The proposed scheme allows to identify at least one dishonest participant violating the protocol without using of Trusted Third Parties. Additionally, we require that bids are binding. It is achieved by enabling all participants acting in concert (the so-called “angry mob”) to find out the identity of the winner, in case the winner fails to make the purchase.

We demonstrate an anonymous quantum communication (AQC) via the non-maximally entanglement state analysis (NESA) based on the dining cryptographer problem (DCP). The security of the present AQC is ensured due to the quantum-mechanical impossibility of local unitary transformations between non-maximally entanglement states, which provides random numbers for the secure AQC. The analysis shows that the DCP-based AQC can be performed without intractability through the NESA in the multi-photon entangled quantum system.

While many scenarios of anonymous communication can be solved by various famous classical techniques including mix nets or dining cryptographers (DC), an abundant amount of anonymous tasks remains open. In this paper, we present a solution to one such task. Our protocol serves as a private communication channel for quantum messages while ensuring that both the sender and the receiver stay anonymous in a set of all parties. Our protocol is a continuation of our previous work on anonymous transmission of quantum information. The protocol does not require trusted parties, and is secure against an active adversary. It can also withstand denial of service attacks. The protocol exhibits an advantage of quantum resources over classical because no classical solution is known (in the same security settings). Entanglement swapping technique is used to create "symmetry" in the protocol, which makes it very transparent and easier to analyze. The security analysis we present is heavily based on our previous work on quantum anonymous communication. The task we implement is also a nice illustration of a cryptographic task where two parties in a multi-party protocol can be dishonest at the same time, but are not cooperating.

We are interested in describing timed systems that exhibit probabilistic behaviour. To this purpose, we consider a model of Probabilistic Timed Automata and introduce a concept of weak bisimulation for these automata, together with an algorithm to decide it. The weak bisimulation relation is shown to be preserved when either time, or probability is abstracted away. As an application, we use weak bisimulation for Probabilistic Timed Automata to model and analyze a timing attack on the dining cryptographers protocol.

It is customary to view the scheduler as an intruder when modelling security protocols by means of process calculi that express both nondeterministic and probabilistic behavior. It has been established that traditional schedulers need to be carefully calibrated in order to more accurately reflect an intruder's real power. We propose such a class of schedulers through a variant of the Probabilistic Poly-time Calculus (PPC) of Mitchell et al. (Theoretical Computer Science 353 (2006), 118-164) called PPC νσ. We define two levels of schedulers: adversarial schedulers which schedule a class of indistinguishable actions i.e. actions that we do not want an attacker to distinguish, and internal schedulers, called task schedulers, which resolve the remaining nondeterminism within a chosen class. We also show how to apply them in order to design schedulers for the analysis of cryptographic protocols that accurately reflect an intruder's capacity for controlling communication networks, without allowing it to control the internal reactions of the protocol under attack. We give a new characterization of the asymptotic observational equivalence of Mitchell et al. (Theoretical Computer Science 353 (2006), 118-164) that is more suited for taking into account any observable trace rather than just one single action. This asymptotic observational equivalence is a congruence in accordance with these new schedulers. We illustrate the aptness of our approach by an extensive study of the Dining Cryptographers (DCP) (J. Cryptology 1 (1988), 65-75) protocol. Research partially supported by an individual NSERC research grant (Canada) of the author.

The past two decades have seen a growing interest in methods for anonymous communication on the Internet, both from the academic community and the general public. Several system designs have been proposed in the literature, of which a number have been implemented and are used by diverse groups, such as journalists, human rights workers, the military, and ordinary citizens, to protect their identities on the Internet. In this work, we survey the previous research done to design, develop, and deploy systems for enabling private and anonymous communication on the Internet. We identify and describe the major concepts and technologies in the field, including mixes and mix networks, onion routing, and Dining Cryptographers networks. We will also review powerful traffic analysis attacks that have motivated improvements and variations on many of these anonymity protocols made since their introduction. Finally, we will summarize some of the major open problems in anonymous communication research and discuss possible directions for future work in the field.

International audience; The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending emails. The protocols for ensuring anonymity often use random mechanisms which can be described probabilistically, while the agents' behavior may be totally unpredictable, irregular, and hence expressible only nondeterministically. Formal definitions of the concept of anonymity have been investigated in the past either in a totally nondeterministic framework, or in a purely probabilistic one. In this paper, we investigate a notion of anonymity which combines both probability and nondeterminism, and which is suitable for describing the most general situation in which the protocol and the users can have both probabilistic and nondeterministic behavior. We also investigate the properties of the definition for the particular cases of purely nondeterministic users and purely probabilistic users. We formulate the notions of anonymity in terms of probabilistic automata, and we describe protocols and users as processes in the probabilistic $\pi$-calculus, whose semantics is again based on probabilistic automata. Throughout the paper, we illustrate our ideas by using the example of the dining cryptographers.

Stepwise refinement is a crucial conceptual tool for system development, encouraging program construction via a number of separate correctness-preserving stages which ideally can be understood in isolation. A crucial conceptual component of security is an adversary's ignorance of concealed information. We suggest a novel method of combining these two ideas. Our suggestion is based on a mathematical definition of ''ignorance-preserving'' refinement that extends classical refinement by limiting an adversary's access to concealed information: moving from specification to implementation should never increase that access. The novelty is the way we achieve this in the context of sequential programs. Specifically we give an operational model (and detailed justification for it), a basic sequential programming language and its operational semantics in that model, a ''logic of ignorance'' interpreted over the same model, then a program-logical semantics bringing those together - and finally we use the logic to establish, via refinement, the correctness of a real (though small) protocol: Rivest's Oblivious Transfer. A previous report^@? treated Chaum's Dining Cryptographers similarly. In passing we solve the Refinement Paradox for sequential programs.

International audience; We consider a framework in which anonymity protocols are interpreted as noisy channels in the information-theoretic sense, and we explore the idea of using the notion of capacity as a measure of the loss of anonymity. Such idea was already suggested by Moskowitz, Newman and Syverson, in their analysis of the covert channel that can be created as a result of non-perfect anonymity. We consider the case in which some leak of information is intended by design, and we introduce the notion of conditional capacity to rule out this factor, thus retrieving a natural correspondence with the notion of anonymity. Furthermore, we show how to compute the capacity and the conditional capacity when the anonymity protocol satisfies certain symmetries. We also investigate how the adversary can test the system to try to infer the user's identity, and we study how his probability of success depends on the characteristics of the channel. We then illustrate how various notions of anonymity can be expressed in this framework, and show the relation with some definitions of probabilistic anonymity in literature. Finally, we show how to compute the matrix of the channel (and hence the capacity and conditional capacity) using model checking.

When modelling cryto-protocols by means of process calculi which express both nondeterministic and probabilistic behavior, it is customary to view the scheduler as an intruder. It has been established that the traditional scheduler needs to be carefully calibrated in order to more accurately reflect the intruder's capabilities for controlling communication channels. We propose such a class of schedulers through a semantic variant called PPCνσ, of the Probabilistic Poly-time Calculus (PPC) of Mitchell et al. [J.C. Mitchell, A. Ramanathan, A. Scedrov, and V. Teague. A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols. Theoretical Computer Science, 353:118–164, 2006] and we illustrate the pertinence of our approach by an extensive study of the Dining Cryptographers (DCP) [David Chaum. The dining cryptographers problem: Unconditional sender and recipient untraceability. J. Cryptology, 1(1):65–75, 1988] protocol. Along these lines, we define a new characterization of Mitchell et al.'s observational equivalence [J.C. Mitchell, A. Ramanathan, A. Scedrov, and V. Teague. A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols. Theoretical Computer Science, 353:118–164, 2006] more suited for taking into account any observable trace instead of just a single action as required in the analysis of the DCP.

International audience; Anonymity means that the identity of the user performing a certain action is maintained secret. The protocols for ensuring anonymity often use random mechanisms which can be described probabilistically. In this paper we propose a notion of weak probabilistic anonymity, where weak refers to the fact that some amount of probabilistic information may be revealed by the protocol. This information can be used by an observer to infer the likeliness that the action has been performed by a certain user. The aim of this work is to study the degree of anonymity that the protocol can still ensure, despite the leakage of information. We illustrate our ideas by using the example of the dining cryptographers with biased coins. We consider both the cases of nondeterministic and probabilistic users. Correspondingly, we propose two notions of weak anonymity and we investigate their respective dependencies on the biased factor of the coins.

Model checking is a promising approach to automatic verification, which has concentrated on specification expressed in temporal logics. Comparatively little attention has been given to temporal logics of knowledge, although such logics have been proven to be very useful in the specifications of protocols for distributed systems. In this paper, we addressed the model checking problem for a temporal logic of knowledge (Halpern and Vardi's logic of CKLn). Based on the semantics of interpreted systems with local propositions, we developed an approach to symbolic CKLn model checking via Ordered Binary decision diagrams and implemented the corresponding symbolic model checker MCTK. In our approach to model checking specifications involving agents' knowledge, the knowledge modalities are eliminated via quantifiers over agents' non-observable variables. We then modelled the Dining Cryptographers protocol and the five-hands protocol for Russian Cards problem in MCTK. Via these two examples, we compare MCTK's empirical performance with two different state-of-the-art epistemic model checkers, MCK and MCMAS.

In many applications, such as e-voting, it is imperative that the privacy scope unconditional security levels, i.e. that it is protected regardless of the resources and the time available to attack. In this context, protocols that verify that condition reach maximum interest. Probably, the most interesting of them is Non Interactive Dining cryptographers (NIDC), that relaxes the condition of concurrency online for all participants. This paper proposes a new technique, based in parallel channels, to optimize the storage of the votes in the model NIDC.

This paper presents a framework for calculating measures of data integrity for programs in a small imperative language. We develop a Markov chain semantics for our language which calculates Clarkson and Schneider’s definitions of data contamination and suppression. These definitions are based on conditional mutual information and entropy; we present a result relating them to mutual information, which can be calculated by a number of existing tools. We extend a quantitative information flow tool (CH-IMP) to calculate these measures of integrity and demonstrate this tool with examples based on error correcting codes, the Dining Cryptographers protocol and the attempts by a number of banks to influence the Libor rate.

We present a compiler that translates a multi-agent systems specification given in the formalism of Interpreted Systems into an SMV program. We show how an SMV model checker can be coupled with a Kripke model editor (Akka) to allow for the mechanical verification of epistemic properties of multi-agent systems. We apply this methodology to the verification of a communication protocol — the dining cryptographers.

In this paper we focus on sender-anonymous channels (a.k.a. Dining Cryptographers networks) and present a construction requiring a very low (constant) number of rounds of interaction while tolerating actively malicious behavior by some of the participants (up to less than half of them). Our construction is unconditionally secure (meaning that no bounds are placed on the computational power of the adversary), makes black-box use of a verifiable secret sharing (VSS) protocol, and is based on a special-purpose secure multiparty computation protocol implementing the method of "throwing darts;" its round complexity is essentially equal to that of the VSS protocol.In addition, since broadcast cannot be simulated in a point-to-point network when a third or more of the participants are corrupt, it is impossible to construct VSS (and, more generally, any other basic multiparty protocol) in this setting without using a "physical broadcast channel," and a recent line of research has sought to minimize the use of this expensive resource. Our anonymous channel protocol's reduction to VSS is broadcast-round-preserving, thus making the fewest (known to date) calls to the broadcast channel while running in an overall constant number of rounds.Finally, anonymous channels play an important role in the setup phase of an authentication technique known as pseudosignatures, which then may be used to simulate authenticated Byzantine agreement protocols in the information-theoretic setting. Plugging in our anonymous channel translates into a fast (and broadcast-efficient) pseudosignature construction.

Part 3: Security Analysis; International audience; Originally proposed for privacy protection in the context of statistical databases, differential privacy is now widely adopted in various models of computation. In this paper we investigate techniques for proving differential privacy in the context of concurrent systems. Our motivation stems from the work of Tschantz et al., who proposed a verification method based on proving the existence of a stratified family between states, that can track the privacy leakage, ensuring that it does not exceed a given leakage budget. We improve this technique by investigating a state property which is more permissive and still implies differential privacy. We consider two pseudometrics on probabilistic automata: The first one is essentially a reformulation of the notion proposed by Tschantz et al. The second one is a more liberal variant, relaxing the relation between them by integrating the notion of amortisation, which results into a more parsimonious use of the privacy budget. We show that the metrical closeness of automata guarantees the preservation of differential privacy, which makes the two metrics suitable for verification. Moreover we show that process combinators are non-expansive in this pseudometric framework. We apply the pseudometric framework to reason about the degree of differential privacy of protocols by the example of the Dining Cryptographers Protocol with biased coins.

The dining cryptographers protocol implements a multiple access channel in which senders and recipients are anonymous. A problem is that a malicious participant can disrupt communication by deliberately creating collisions. We propose a computationally secure dining cryptographers protocol with collision resolution that achieves a maximum stable throughput of 0.924 messages per round and which allows to easily detect disruptors., 11 pages, 3 figures

We describe an algorithm for fully-anonymous broadcast in large-scale networks. The protocol is similar to the dining cryptographers networks (DC-Nets) in that both are based on secure multi-party computation (MPC) techniques. However, we address the weaknesses of DC-Nets, which are poor scalability and vulnerability to jamming attacks. When compared to the state-of-the-art, our protocol reduces the total bit complexity from O(n2) to O(n) per anonymous message sent in a network of size n at the expense of an increase in total latency from O(1) to polylog(n). Our protocol can tolerate up to 1/3 dishonest parties, which are controlled by a static computationally-unbounded Byzantine adversary.

Opacity is a general language-theoretic framework in which several security properties of a system can be expressed. Its parameters are a predicate, given as a subset of runs of the system, and an observation function, from the set of runs into a set of observables. The predicate describes secret information in the system and, in the possibilistic setting, it is opaque if its membership cannot be inferred from observation. In this paper, we propose several notions of quantitative opacity for probabilistic systems, where the predicate and the observation function are seen as random variables. Our aim is to measure (i) the probability of opacity leakage relative to these random variables and (ii) the level of uncertainty about membership of the predicate inferred from observation. We show how these measures extend possibilistic opacity, we give algorithms to compute them for regular secrets and observations, and we apply these computations on several classical examples. We finally partially investigate the non-deterministic setting., To appear in Mathematical Structures in Computer Science, Cambridge University Press

We revisit the formalism of modular interpreted systems (MIS) which encourages modular and open modeling of synchronous multi-agent systems. The original formulation of MIS did not live entirely up to its promise. In this paper, we propose how to improve modularity and openness of MIS by changing the structure of interference functions. These relatively small changes allow for surprisingly high flexibility when modeling actual multi-agent systems. We demonstrate this on two well-known examples, namely the trains, tunnel and controller, and the dining cryptographers. Perhaps more importantly, we propose how the notions of multi-agency and openness, crucial for multi-agent systems, can be precisely defined based on their MIS representations., Comment: In Proceedings GandALF 2013, arXiv:1307.4162

The Dining Cryptographer network (or DC-net) is a privacy preserving communication protocol devised by David Chaum for anonymous message publication. A very attractive feature of DC-nets is the strength of its security, which is inherent in the protocol and is not dependent on other schemes, like encryption. Unfortunately the DC-net protocol has a level of complexity that causes it to suffer from exceptional communication overhead and implementation difficulty that precludes its use in many real-world use-cases. We have designed and created a DC-net implementation that uses a pure client- server model, which successfully avoids much of the complexity inherent in the DC-net protocol. We describe the theory of DC- nets and our pure client-server implementation, as well as the compromises that were made to reduce the protocol's level of complexity. Discussion centers around the details of our implementation of DC-net. Keywords—Dining Cryptographer network; Privacy; sender- untraceability I. INTRODUCTION The issue of privacy and anonymity on the Internet has become a challenging one, especially with the growing influence that the Internet has on our day-to-day social lives. With the increased use of social networking sites and mobile Internet based communication, being anonymous and maintaining privacy has becoming something that the average computer has great difficulty in achieving. Preserving the anonymity of the communicating parties is crucial in situations where knowledge of the identity of the source of communicated messages could create a conflict of interest, jeopardize the integrity of a process or endanger the participants. The concept of maintaining anonymity is simple to conceive. However, they can be rather difficult to implement. The trails left by the protocols and technologies involved in digital communication can be difficult to erase or hide to a point where the identity of the communicating parties is not exposed. The trails created in these communications are often required for the communication itself often to maintain a quality of service or integrity of the message being communicated. This paper describes a digital, computer based form of communication that preserves the anonymity of all communicating parties. The program takes heavy influence from David Chaum's Dining Cryptographers problem and the DC Net concept. A. Background

A novel electronic voting scheme is proposed which is quite suitable for small scale election settings. An outstanding characteristic of the design is its guarantee of unconditionally perfect ballot secrecy. It satisfies self-tallying, fairness and verifiability. Disruption of the result of an election equals to breaking the Discrete Logarithm Problem. Our scheme is built on top of the DC-net(dining cryptographers network) anonymous broadcast protocol. It needs no trusted authority to guarantee its security, but assumes a complete network of secure private channels between voters.

A novel quantum anonymous communication scheme is proposed on the basis of Dining Cryptographers (DC) Problem and nonmaximally entangled qubit pair. The scheme takes advantage of quantum-mechanical impossibility of local unitary transformation between certain nonmaximally entangled states to provide truly random number which can be brightly used in anonymous communication protocols based on DC-Nets. The analysis and discussions demonstrate that the proposed quantum anonymous communication scheme can be performed securely with high capacity and untraceability. The scheme can also be extended to a (2; 2) quantum secret sharing (QSS) scheme.

The paper describes an abstraction for protocols that are based on multiple rounds of Chaum's Dining Cryptographers protocol. It is proved that the abstraction preserves a rich class of specifications in the logic of knowledge. This result is applied to optimize model checking of implementations of a knowledge-based program that uses the Dining Cryptographers protocol as a primitive in an anonymous broadcast system. Performance results are given for model checking knowledge-based specifications in the concrete and abstract models of this protocol, and some new conclusions about the protocol are derived.

This paper describes an algorithm for model checking a fragment of the logic of knowledge and probability in multi-agent systems, with respect to a perfect recall interpretation of knowledge and agents' subjective probability. The algorithm has been implemented in the epistemic model checker MCK. Some experiments with the implemented algorithm are reported, in which some properties of agents' probabilistic knowledge are verified in two security protocols: Chaum's Dining Cryptographers protocol, and a protocol for Oblivious Transfer due to Rivest.

When a distributed systems protocol is used in a particular context as part of a solution to a larger problem, additional information may be generated from the context. Such information may be used for optimization of the system, and, in the case of security protocols, may be of use to the adversary for attacks. The project conducted a case study of the application of the epistemic model checker MCK to automatically detect such optimization opportunities, and to verify that the protocol remains secure in the mode of use. The particular protocol studied was Chaum's Dining Cryptographers protocol, a security protocol that allows a single agent to anonymously transmit a signal. The context of use considered was a more general 2-phase protocol for anonymous broadcast by an arbitrary number of agents, also proposed by Chaum. The aims of the 2-phase anonymous broadcast protocol were formulated as a knowledge-based program, and an iterative process of model checking and manual counter-example guided refinement was followed to converge on implementations of this knowledge-based program in which local predicates were identified that correspond precisely to the knowledge conditions in the knowledge-based program. This analysis demonstrated that the 2-phase protocol contains some quite subtle flows of information that can be used to optimize its performance, but no violation of the anonymity property was found. As an additional contribution of the research, a formal abstraction technique was developed, and proved correct, for epistemic model checking of protocols that call the Dining Cryptographers protocol as a subroutine. Experimental results show that the optimization improves epistemic model checking performance by orders of magnitude and enables problems of larger scale to be attacked.

Information hiding is a general concept which refers to the goal of preventing an adversary from inferring secret information from the observables. Anonymity and Information Flow are examples of this notion. We study the problem of information hiding in systems characterized by the coexistence of randomization and concurrency. It is well known that the presence of nondeterminism, due to the possible interleavings and interactions of the parallel components, can cause unintended information leaks. The most established approach to solve this problem is to fix the strategy of the scheduler beforehand. In this work, we propose a milder restriction on the schedulers, and we define the notion of strong (probabilistic) information hiding under various notions of observables. Furthermore, we propose a method, based on the notion of automorphism, to verify that a system satisfies the property of strong information hiding, namely strong anonymity or non-interference, depending on the context. Through the paper, we use the canonical example of the Dining Cryptographers to illustrate our ideas and techniques.