Android Protected Confirmation (APC) is an authentication protocol designed by Google. It leverages the extra security of the Trusted Execution Environment (TEE) to secure transactions even in the presence of a compromised OS. The intended security guarantee for APC is that if a transaction has been signed under APC, then the user must have previously given its explicit consent, even if an attacker has gained root access to the victim’s Android OS. In this paper, we present a security analysis of APC in the Universal Composability (UC) framework. We uncover two attacks on the design of the protocol which allow a root adversary to issue transactions without the user consenting to them. We provide an attack implementation on a Google Pixel phone, and propose light-weight fixes. Finally, we specify the ideal UC functionality capturing the intended security guarantees for APC, and prove that the fixed protocol UC-realizes it.

We analyze bribing attacks in Proof-of-Stake distributed ledgers from a game theoretic perspective. In bribing attacks, an adversary offers participants a reward in exchange for instructing them how to behave, with the goal of attacking the protocol's properties. Specifically, our work focuses on adversaries that target blockchain safety. We consider two types of bribing, depending on how the bribes are awarded: i) guided bribing, where the bribe is given as long as the bribed party behaves as instructed; ii) effective bribing, where bribes are conditional on the attack's success, w.r.t. well-defined metrics. We analyze each type of attack in a game theoretic setting and identify relevant equilibria. In guided bribing, we show that the protocol is not an equilibrium and then describe good equilibria, where the attack is unsuccessful, and a negative one, where all parties are bribed such that the attack succeeds. In effective bribing, we show that both the protocol and the "all bribed" setting are equilibria. Using the identified equilibria, we then compute bounds on the Prices of Stability and Anarchy. Our results indicate that additional mitigations are needed for guided bribing, so our analysis concludes with incentive-based mitigation techniques, namely slashing and dilution. Here, we present two positive results, that both render the protocol an equilibrium and achieve maximal welfare for all parties, and a negative result, wherein an attack becomes more plausible if it severely affects the ledger's token's market price.

This work formally analyzes the anonymity guarantees of continuous stop-and-go mixnets and attempts to answer the titular question. Existing mixnet based anonymous communication protocols that aim to provide provable anonymity guarantees rely on round-based communication models, which requires synchronization among all the nodes and clients that is difficult to achieve in practice. Continuous stop-and-go mixnets (e.g., Loopix and Nym) provide a nice alternative by adding a random delay for each message on every hop independent of all other hops and all other messages. The core anonymization technique of continuous mixnets combined with the fact that the messages are sent by the clients to the mixnet at different times makes it a difficult problem to formally prove security for such mixnet protocols; existing end-to-end analyses for such designs provide only experimental evaluations for anonymity and were lacking a comprehensive formal treatment. We are the first to close that gap and provide a formal analysis. We provide two indistinguishability based definitions (of sender anonymity), namely pairwise unlinkability and user unlinkability, tuned specifically for continuous stop-and-go mixnets. We derive the adversarial advantage as a function of the protocol parameters for the two definitions. We show that there is a fundamental lower bound on the adversarial advantage $\delta$ for pairwise unlinkability; however, strong user unlinkability (negligible adversarial advantage) can be achieved if the users message rate ($\lambda_u$) is proportional to message processing rate ($\lambda$) on the nodes.

One of the most important features of blockchain protocols is decentralization, as their main contribution is that they formulate a distributed ledger that will be maintained and extended without the need of a trusted party. Bitcoin has been criticized for its tendency to centralization, as very few pools control the majority of the hashing power. Pass et al. proposed FruitChain [PODC 17] and claimed that this blockchain protocol mitigates the formation of pools by reducing the variance of the rewards in the same way as mining pools, but in a fully decentralized fashion. Many follow up papers consider that the problem of centralization in Proof-of- Work (PoW) blockchain systems can be solved via lower rewards' variance, and that in FruitChain the formation of pools is unnecessary. Contrary to the common perception, in this work, we prove that lower variance of the rewards does not eliminate the tendency of the PoW blockchain protocols to centralization; miners have also other incentives to create large pools, and specifically to share the cost of creating the instance they need to solve the PoW puzzle. We abstract the procedures of FruitChain as oracles and assign to each of them a cost. Then, we provide a formal definition of a pool in a blockchain system, and by utilizing the notion of equilibrium with virtual payoffs (EVP) [AFT 21], we prove that there is a completely centralized EVP, where all the parties form a single pool controlled by one party called the pool leader. The pool leader is responsible for creating the instance used for the PoW procedure. To the best of our knowledge, this is the first work that examines the construction of mining pools in the FruitChain system.

Fair exchange protocols let two mutually distrustful parties exchange digital data in a way that neither party can cheat. They have various applications such as the exchange of digital items, or the exchange of digital coins and digital services between a buyer/client and seller/server.In this work, we formally define and propose a generic blockchain-based construction called "Recurring Contingent Service Payment" (RC-S-P). It (i) lets a fair exchange of digital coins and verifiable service reoccur securely between clients and a server while ensuring that the server is paid if and only if it delivers a valid service, and (ii) ensures the parties’ privacy is preserved. RC-S-P supports arbitrary verifiable services, such as "Proofs of Retrievability" (PoR) or verifiable computation and imposes low on-chain over-heads. Our formal treatment and construction, for the first time, consider the setting where either client or server is malicious.We also present a concrete efficient instantiation of RC-S-P when the verifiable service is PoR. We implemented the concrete instantiation and analysed its cost. When it deals with a 4-GB outsourced file, a verifier can check a proof in only 90 milliseconds, and a dispute between a prover and verifier is resolved in 0.1 milliseconds.At CCS 2017, two blockchain-based protocols were proposed to support the fair exchange of digital coins and a certain verifiable service; namely, PoR. In this work, we show that these protocols (i) are susceptible to a free-riding attack which enables a client to receive the service without paying the server, and (ii) are not suitable for cases where parties’ privacy matters, e.g., when the server’s proof status or buyer’s file size must remain private from the public. RC-S-P simultaneously mitigates the above attack and preserves the parties’ privacy.

Simultaneous broadcast (SBC) protocols, introduced in [Chor et al., FOCS 1985], constitute a special class of broadcast channels which, besides consistency, guarantee that all senders broadcast their messages independently of the messages broadcast by other parties. SBC has proved extremely useful in the design of various distributed computing constructions (e.g., multiparty computation, coin flipping, electronic voting, fair bidding). As with any communication channel, it is crucial that SBC security is composable, i.e., it is preserved under concurrent protocol executions. The work of [Hevia, SCN 2006] proposes a formal treatment of SBC in the state-of-the-art Universal Composability (UC) framework [Canetti, FOCS 2001] and a construction secure assuming an honest majority.

We study "Nash dynamics" in the context of adversarial deviations in blockchain protocols. We introduce a formal model, within which one can assess whether the Nash dynamics can lead utility-maximizing participants to defect from the "honest" protocol operation, towards variations that exhibit one or more undesirable infractions that affect protocol security, like abstaining from participation and producing conflicting protocol histories. Blockchain protocols that lead to no such infraction states are deemed compliant. Armed with this model, we evaluate the compliance of various Proof-of-Work (PoW) and Proof-of-Stake (PoS) protocol families, under different utility functions and reward schemes, leading to the following results: i) PoW and PoS protocols exhibit different compliance behavior, depending on the lossiness of the network; ii) PoS ledgers can be compliant w.r.t. one realistic infraction (producing conflicting messages) but non-compliant (hence non-equilibria) w.r.t. others (abstaining or an attack we call selfish signing); iii) considering externalities, like exchange rate fluctuations, we quantify the benefit of economic penalties in the context of PoS protocols as mitigation for particular infractions that affect protocol security.

Electronic voting (e-voting), compared with article voting, has advantages in several aspects. Among those benefits, the ability to audit the electoral process at every stage is one of the most desired features of an e-voting system. In Eurocrypt 2015, Kiayias, Zacharias, and Zhang proposed a new E2E verifiable e-voting system that for the first time provides E2E verifiability without relying on external sources of randomness or the random oracle model; the main advantage of such system is in the fact that election auditors need only the election transcript and the feedback from the voters to pronounce the election process unequivocally valid. Unfortunately, their system comes with a huge performance and storage penalty for the election authority (EA) compared to other e-voting systems such as Helios. The main reason is that due to the way the EA forms the proof of the tally result, it is required toprecomputea number of ciphertexts for each voter and each possible choice of the voter. The performance penalty on the EA appears to be intrinsic to the approach: voters cannot compute an enciphered ballot themselves because there seems to be no way for them to prove that it is a valid ciphertext. In this work, we construct a new e-voting system that retains similar strong E2E characteristics (but against computational adversaries) while completely eliminating the performance and storage penalty of the EA. Our construction has similar performance to Helios and is practical. The privacy of our construction relies on the SXDH assumption over bilinear groups via complexity leveraging.

Purpose This paper aims to investigate the importance of auditing for election privacy via issues that appear in the state-of-the-art implementations of e-voting systems that apply threshold public key encryption (TPKE) in the client such as Helios and use a bulletin board (BB). Design/methodology/approach Argumentation builds upon a formal description of a typical TPKE-based e-voting system where the election authority (EA) is the central node in a star network topology. The paper points out the weaknesses of the said topology with respect to privacy and analyzes how these weaknesses affect the security of several instances of TPKE-based e-voting systems. Overall, it studies the importance of auditing from a privacy aspect. Findings The paper shows that without public key infrastructure (PKI) support or – more generally – authenticated BB “append” operations, TPKE-based e-voting systems are vulnerable to attacks where the malicious EA can act as a man-in-the-middle between the election trustees and the voters; hence, it can learn how the voters have voted. As a countermeasure for such attacks, this work suggests compulsory trustee auditing. Furthermore, it analyzes how lack of cryptographic proof verification affects the level of privacy that can be provably guaranteed in a typical TPKE e-voting system. Originality/value As opposed to the extensively studied importance of auditing to ensure election integrity, the necessity of auditing to protect privacy in an e-voting system has been mostly overlooked. This paper reveals design weaknesses present in noticeable TPKE-based e-voting systems that can lead to a total breach of voters’ privacy and shows how auditing can be applied for providing strong provable privacy guarantees.

E-voting systems have emerged as a powerful technology for improving democracy by reducing election cost, increasing voter participation, and even allowing voters to directly verify the entire election procedure. Prior internet voting systems have single points of failure, which may result in the compromise of availability, voter secrecy, or integrity of the election results. In this paper, we present the design, implementation, security analysis, and evaluation of D-DEMOS, a complete e-voting system that is distributed, privacy-preserving and end-to-end verifiable. Our system includes a fully asynchronous vote collection subsystem that provides immediate assurance to the voter her vote was recorded as cast, without requiring cryptographic operations on behalf of the voter. We also include a distributed, replicated and fault-tolerant Bulletin Board component, that stores all necessary election-related information, and allows any party to read and verify the complete election process. Finally, we also incorporate trustees, i.e., individuals who control election result production while guaranteeing privacy and end-to-end-verifiability as long as their strong majority is honest. Our system is the first e-voting system whose voting operation is human verifiable, i.e., a voter can vote over the web, even when her web client stack is potentially unsafe, without sacrificing her privacy, and still be assured her vote was recorded as cast. Additionally, a voter can outsource election auditing to third parties, still without sacrificing privacy. Finally, as the number of auditors increases, the probability of election fraud going undetected is diminished exponentially. We provide a model and security analysis of the system. We implement a prototype of the complete system, we measure its performance experimentally, and we demonstrate its ability to handle large-scale elections.

Recently, Kiayias, Zacharias and Zhang-proposed a new E2E verifiable e-voting system called 'DEMOS' that for the first time provides E2E verifiability without relying on external sources of randomness or the random oracle model; the main advantage of such system is in the fact that election auditors need only the election transcript and the feedback from the voters to pronounce the election process unequivocally valid. Unfortunately, DEMOS comes with a huge performance and storage penalty for the election authority (EA) compared to other e-voting systems such as Helios. The main reason is that due to the way the EA forms the proof of the tally result, it is required to {\em precompute} a number of ciphertexts for each voter and each possible choice of the voter. This approach clearly does not scale to elections that have a complex ballot and voters have an exponential number of ways to vote in the number of candidates. The performance penalty on the EA appears to be intrinsic to the approach: voters cannot compute an enciphered ballot themselves because there seems to be no way for them to prove that it is a valid ciphertext.

We put forth the problem of delegating the evaluation of a pseudorandom function (PRF) to an untrusted proxy and introduce a novel cryptographic primitive called delegatable pseudorandom functions, or DPRFs for short: A DPRF enables a proxy to evaluate a pseudorandom function on a strict subset of its domain using a trapdoor derived from the DPRF secret key. The trapdoor is constructed with respect to a certain policy predicate that determines the subset of input values which the proxy is allowed to compute. The main challenge in constructing DPRFs is to achieve bandwidth efficiency (which mandates that the trapdoor is smaller than the precomputed sequence of the PRF values conforming to the predicate), while maintaining the pseudorandomness of unknown values against an attacker that adaptively controls the proxy. A DPRF may be optionally equipped with an additional property we call policy privacy, where any two delegation predicates remain indistinguishable in the view of a DPRF-querying proxy: achieving this raises new design challenges as policy privacy and bandwidth efficiency are seemingly conflicting goals.