We study a game-theoretic model for pool formation in Proof of Stake blockchain protocols. In such systems, stakeholders can form pools as a means of obtaining regular rewards from participation in ledger maintenance, with the power of each pool being dependent on its collective stake. The question we are interested in is the design of mechanisms, i.e., "reward sharing schemes," that suitably split rewards among pool members and achieve favorable properties in the resulting pool configuration. With this in mind, we initiate a non-cooperative game-theoretic analysis of the well known Shapley value scheme from cooperative game theory into the context of blockchains. In particular, we focus on the oceanic model of games, proposed by Milnor and Shapley (1978), which is suitable for populations where a small set of large players coexists with a big mass of rather small, negligible players. This provides an appropriate level of abstraction for pool formation processes that occur among the stakeholders of a blockchain. We provide comparisons between the Shapley mechanism and the more standard proportional scheme, in terms of attained decentralization, via a Price of Stability analysis and in terms of susceptibility to Sybil attacks, i.e., the strategic splitting of a players' stake with the intention of participating in multiple pools for increased profit. Interestingly, while the widely deployed proportional scheme appears to have certain advantages, the Shapley value scheme, which rewards higher the most pivotal players, emerges as a competitive alternative, by being able to bypass some of the downsides of proportional sharing in terms of Sybil attack susceptibility, while also not being far from optimal guarantees w.r.t. decentralization. Finally, we also complement our study with some variations of proportional sharing, where the profit is split in proportion to a superadditive or a subadditive function of the stake, showing that our results for the Shapley value scheme are maintained in comparison to these functions as well.

We study long-term equilibria that arise in the token monetary policy, or tokenomics, design of proof-of-stake (PoS) blockchain systems that engage utility maximizing users and validators. Validators are system maintainers who get rewarded with tokens for performing the work necessary for the system to function properly, while users compete and pay with such tokens for getting a desired portion of the system service. We study how the system service provision and suitable rewards schemes together can lead to equilibria with the following desirable characteristics (1) viability: the system keeps parties engaged, (2) decentralization and skin-in-the-game: multiple sufficiently invested validators are participating, (3) stability: the price path of the underlying token used to transact with the system does not change widely over time, and (4) feasibility: the mechanism is easy to implement as a smart contract, e.g., it does not require a fiat reserve on-chain to perform token buybacks or to perform bookkeeping of exponentially growing token holdings. Our analysis enables us to put forward a novel generic mechanism for blockchain monetary policy that we call quantitative rewarding (QR). We investigate how to implement QR in single-token and two-token proof of stake (PoS) blockchain systems. The latter are systems that utilize one token for the users to pay the transaction fees and a different token for the validators to participate in the PoS protocol and get rewarded. Our approach demonstrates a concrete advantage of the two-token setting in terms of the ability of the QR mechanism to be realized effectively and provide good equilibria. Our analysis also reveals an inherent limitation of the single token setting in terms of implementing an effective blockchain monetary policy - a distinction that is, to the best of our knowledge, highlighted for the first time.licy - a distinction that is, to the best of our knowledge, highlighted for the first time.

We study Sybil-Resilient Anonymous (SyRA) signatures, a cryptographic primitive that enables credentialed users to generate, on demand, unlinkable pseudonyms tied to any given context, and issue signatures on behalf of these pseudonyms. Concretely, SyRA allows a distributed issuer to turn any legacy identity or personhood identifier, possibly of low entropy, into a unique associated cryptographic key of high pseudoentropy, for use in generating signatures for any given context. Sybil-resilient anonymous signatures achieve three main objectives: 1) Sybil resilience: every user is entitled to at most one digital identity, 2) anonymity: no information about the user's real identity is leaked, and 3) non-interactive context switching: users can create on their own at most one credential for any given context in a manner that is unlinkable across contexts.

Launching a new blockchain system or application is frequently facilitated by a so called airdrop, where the system designer chooses a pre-existing set of potentially interested parties and allocates newly minted tokens to them with the expectation that they will participate in the system — such engagement, especially if it is of significant level — facilitates the system and raises its value and also the value of its newly minted token, hence benefiting the airdrop recipients. A number of challenging questions befuddle designers in this setting, such as how to choose the set of interested parties and how to allocate tokens to them. To address these considerations we put forward a game theoretic model for such airdrop games. Our model can be used to guide the designer’s choices based on the way the system’s value depends on participation (modeled by a “technology function” in our framework) and the costs that participations incurs. We identify both bad and good equilibria and identify the settings and the choices that can be made where the designer can influence the players towards good equilibria in an expedient manner.

Handling congestion in blockchain systems is a fundamental problem given that the security and decentralization objectives of such systems lead to designs that compromise on (horizontal) scalability (what sometimes is referred to as the “blockchain trilemma”). Motivated by this, we focus on the question whether it is possible to design a transaction inclusion policy for block producers that facilitates fee and delay predictability while being incentive compatible at the same time. Reconciling these three properties is seemingly paradoxical given that the dominant approach to transaction processing is based on first-price auctions (e.g., as in Bitcoin) or dynamic adjustment of the minimum admissible fee (e.g. as in Ethereum EIP-1559) something that breaks fee predictability. At the same time, in fixed fee mechanisms (e.g., as in Cardano), fees are trivially predictable but are subject to relatively inexpensive bribing or denial of service attacks where transactions may be delayed indefinitely by a well funded attacker, hence breaking delay predictability. In this work, we set out to address this problem by putting forward blockchain space tokenization (BST), namely a new capability of a blockchain system to tokenize its capacity for transactions and allocate it to interested users who are willing to pay ahead of time for the ability to post transactions regularly for a period of time. We analyze our system in the face of worst-case transaction-processing attacks by introducing a security game played between the mempool mechanism and an adversary. Leveraging this framework, we prove that BST offers predictable and asymptotically optimal delays, predictable fees, and is incentive compatible, thus answering the question posed in the affirmative.

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.

Permissionless distributed ledgers, such as those arising from blockchain protocols, have been touted as the centerpiece of an upcoming security-critical information technology infrastructure. Their basic properties-consistency and liveness-can be guaranteed under specific constraints on the resources available to an adversary relative to the resources of the participants that follow the protocol. Given their permissionless participation convention and their intended long-livedness, a critical open security question is their behavior-and potential resilience-to temporary spikes in adversarial resources. In this work we give the first thorough treatment of the self-healing properties of Nakamoto ledgers, addressing both proof-of-work (PoW) and proof-of-stake (PoS) protocols. First, we present a unified model that allows us to define self-healing for both of these protocol classes. Then we provide a formal analysis establishing self-healing with respect to both consistency and liveness in both classes, quantifying the resulting vulnerability period as a function of the magnitude of the spike. Finally, we provide numerical simulations giving explicit quantitative bounds relevant for practice.

Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone , and prove three of its fundamental properties which we call Common Prefix , Chain Quality, and Chain Growth in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the “hashing power” of the protocol participants and their interplay with the protocol parameters and the time needed for reliable message passing between honest parties in terms of computational steps. A takeaway from our analysis is that, all else being equal, the protocol’s provable tolerance in terms of the number of adversarial parties (or, equivalently, their “hashing power” in our model) decreases as the duration of a message passing round increases. Next, we propose and analyze applications that can be built “on top” of the backbone protocol, specifically focusing on Byzantine agreement (BA) and on the notion of a public transaction ledger. Regarding BA, we observe that a proposal due to Nakamoto falls short of solving it, and present a simple alternative which works assuming that the adversary’s hashing power is bounded by 1/3. The public transaction ledger captures the essence of Bitcoin’s operation as a cryptocurrency, in the sense that it guarantees the liveness and persistence of committed transactions. Based on this notion, we describe and analyze the Bitcoin system as well as a more elaborate BA protocol and we prove them secure assuming the adversary’s hashing power is strictly less than 1/2. Instrumental to this latter result is a technique we call 2-for-1 proof-of-work (PoW) that has proven to be useful in the design of other PoW-based protocols.

Abstract Non-malleable codes were introduced by Dziembowski et al. (in: Yao (ed) ICS2010, Tsinghua University Press, 2010), and its main application is the protection of cryptographic devices against tampering attacks on memory. In this work, we initiate a comprehensive study on non-malleable codes for the class of partial functions, that read/write on an arbitrary subset of codeword bits with specific cardinality. We present two constructions: the first one is in the CRS model and allows the adversary to selectively choose the subset of codeword bits, while the latter is in the standard model and adaptively secure. Our constructions are efficient in terms of information rate, while allowing the attacker to access asymptotically almost the entire codeword. In addition, they satisfy a notion which is stronger than non-malleability, that we call non-malleability with manipulation detection, guaranteeing that any modified codeword decodes to either the original message or to $$\bot $$ ⊥ . We show that our primitive implies All-Or-Nothing Transforms (AONTs), and as a result our constructions yield efficient AONTs under standard assumptions (only one-way functions), which, to the best of our knowledge, was an open question until now. Furthermore, we construct a notion of continuous non-malleable codes (CNMC), namely CNMC with light updates, that avoids the full re-encoding process and only uses shuffling and refreshing operations. Finally, we present a number of additional applications of our primitive in tamper resilience.

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.

We study the problem of committee selection in the context of proof-of-stake consensus mechanisms or distributed ledgers. These settings determine a family of participating parties---each of which has been assigned a non-negative ''stake''---and are subject to an adversary that may corrupt a subset of the parties. The challenge is to select a committee of participants that accurately reflects the proportion of corrupt and honest parties, as measured by stake, in the full population. The trade-off between committee size and the probability of selecting a committee that over-represents the corrupt parties is a fundamental factor in both security and efficiency of proof-of-stake consensus, as well as committee-run layer-two protocols.

We describe and analyze a simple protocol for$n$parties that implements a randomness beacon: a sequence of high entropy values, continuously emitted at regular intervals, with sub-linear communication per value. The algorithm can tolerate a$(1-\epsilon)/2$fraction of the$n$players to be controlled by an adaptive adversary that may deviate arbitrarily from the protocol. The randomness mechanism relies on verifiable random functions (VRF), modeled as random functions, and effectively stretches an initial$\lambda$-bit seed to an arbitrarily long public sequence so that (i) with overwhelming probability in k-the security parameter-each beacon value has high min-entropy conditioned on the full history of the algorithm, and (ii) the total work and communication required per value is$O(k)$cryptographic operations. The protocol can be directly applied to provide a qualitative improvement in the security of several proof-of-stake blockchain algorithms, rendering them safe from “grinding” attacks.

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.

Blockchain systems come with a promise of decentralization that, more often than not, stumbles on a roadblock when key decisions about modifying the software codebase need to be made. In a setting where "code-is-law," modifying the code can be a controversial process, frustrating to system stakeholders, and, most crucially, highly disruptive for the underlying systems. This is attested by the fact that both of the two major cryptocurrencies, Bitcoin and Ethereum, have undergone "hard forks" that resulted in the creation of alternative systems which divided engineering teams, computational resources, and duplicated digital assets creating confusion for the wider community and opportunities for fraudulent activities. The above events, and numerous other similar ones, underscore the importance of Blockchain governance, namely the set of processes that blockchain platforms utilize in order to perform decision-making and converge to a widely accepted direction for the system to evolve. While a rich topic of study in other areas, including social choice theory and electronic voting for public office elections, governance of blockchain platforms is lacking a well established set of methods and practices that are adopted industry wide. Instead, different systems adopt approaches of a variable level of sophistication and degree of integration within the platform and its functionality. This makes the topic of blockchain governance a fertile domain for a thorough systematization that we undertake in this work.

One of the most successful applications of peer-to-peer communication networks is in the context of blockchain protocols, which-in Satoshi Nakamoto's own words-rely on the "nature of information being easy to spread and hard to stifle." Significant efforts were invested in the last decade into analyzing the security of these protocols, and invariably the security arguments known for longest-chain Nakamoto-style consensus use an idealization of this tenet. Unfortunately, the real-world implementations of peer-topeer gossip-style networks used by blockchain protocols rely on a number of ad-hoc attack mitigation strategies that leave a glaring gap between the idealized communication layer assumed in formal security arguments for blockchains and the real world, where a wide array of attacks have been showcased.

Resource-based consensus is the backbone of permissionless distributed ledger systems. The security of such protocols relies fundamentally on the level of resources actively engaged in the system. The variety of different resources (and related proof protocols, some times referred to as PoX in the literature) raises the fundamental question whether it is possible to utilize many of them in tandem and build multi-resource consensus protocols. The challenge in combining different resources is to achieve fungibility between them, in the sense that security would hold as long as the cumulative adversarial power across all resources is bounded.

Central Bank Digital Currencies (CBDCs) aspire to offer a digital replacement for physical cash and as such need to tackle two fundamental requirements that are in conflict. On the one hand, it is desired they are private so that a financial "panopticon'' is avoided, while on the other, they should be regulation friendly in the sense of facilitating any threshold-limiting, tracing, and counterparty auditing functionality that is necessary to comply with regulations such as Know Your Customer (KYC), Anti Money Laundering (AML) and Combating Financing of Terrorism (CFT) as well as financial stability considerations. In this work, we put forth a new model for CBDCs and an efficient construction that, for the first time, fully addresses these issues simultaneously. Moreover, recognizing the importance of avoiding a single point of failure, our construction is distributed so that all its properties can withstand a suitably bounded minority of participating entities getting corrupted by an adversary. Achieving all the above properties efficiently is technically involved; among others, our construction uses suitable cryptographic tools to thwart man-in-the-middle attacks, it showcases a novel traceability mechanism with significant performance gains compared to previously known techniques and, perhaps surprisingly, shows how to obviate Byzantine agreement or broadcast from the optimistic execution path of a payment, something that results in an essentially optimal communication pattern and communication overhead when the sender and receiver are honest. Going beyond "simple'' payments, we also discuss how our scheme can facilitate one-off large transfers complying with Know Your Transaction (KYT) disclosure requirements. Our CBDC concept is expressed and realized in the Universal Composition (UC) framework providing in this way a modular and secure way to embed it within a larger financial ecosystem.

Proof of Work (PoW) blockchains are susceptible to adversarial majority mining attacks in the early stages due to incipient participation and corresponding low net hash power. Bootstrapping ensures safety and liveness during the transient stage by protecting against a majority mining attack, allowing a PoW chain to grow the participation base and corresponding mining hash power. Liveness is especially important since a loss of liveness will lead to loss of honest mining rewards, decreasing honest participation, hence creating an undesired spiral; indeed existing bootstrapping mechanisms offer especially weak liveness guarantees.

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.

Superlight blockchain clients learn facts about the blockchain state while requiring merely polylogarithmic communication in the total number of blocks. For proof-of-work blockchains, two known constructions exist: Superblock and FlyClient. Unfortunately, none of them can be easily deployed to existing blockchains, as they require consensus changes and at least a soft fork to implement.

Consider a set of participants invited to execute a protocol Π. The protocol will incur some cost to run while in the end (or at regular intervals), it will populate and update local bookkeeping tables that assign virtual rewards to participants. Each participant aspires to offset the costs of participation by these virtual payoffs that are provided in the course of the protocol and are assumed to be accepted as forms of payment. In this setting, we introduce and study a notion of coalition-safe equilibria. In particular, we consider a strategic coalition of participants that is centrally coordinated and potentially deviates from Π with the objective to increase its utility with respect to the view of at least one of the other participants. The protocol Π is called a coalition-safe equilibrium with virtual payoffs (EVP) if no such protocol deviation exists. We apply our notion to study incentives in blockchain protocols.

Blockchains maintain two types of data: Application data and consensus data. Towards long-term blockchain scalability, both of these must be pruned. While a large body of literature has explored the pruning of application data (UTXOs, account balances, and contract state), little has been said about the permanent pruning of consensus data (block headers). We present a protocol which allows pruning the blockchain by garbage collecting old blocks as they become unnecessary. These blocks can simply be discarded and are no longer stored by any miner. We show that all miners can be light miners with no harm to security. Our protocol is based on the notion of superblocks, blocks that have achieved an unusually high difficulty. We leverage them to represent underlying proof-of-work without ever illustrating it, storing it, or transmitting it. After our pruning is applied, the storage and communication requirements for consensus data are reduced exponentially. We develop new probabilistic mathematical methods to analyze our protocol in the random oracle model. We prove our protocol is both secure and succinct under an uninterrupted honest majority assumption for 1/3 adversaries. Our protocol is the first to achieve always secure, always succinct, and online Non-Interactive Proofs of Proof-of-Work, all necessary components for a logarithmic space mining scheme. Our work has applications beyond mining and also constitutes an improvement in state-of-the-art superlight clients and cross-chain bridges.

In functional encryption (FE) a sender, Alice, encrypts plaintexts for which a receiver, Bob, can obtain functional evaluations, while Charlie is responsible for initializing the encryption keys and issuing the decryption keys. Standard notions of security for FE deal with a malicious Bob and guarantee the confidentiality of Alice's messages despite the leakage that occurs due to the functional keys that are revealed to the adversary via various forms of indistinguishability experiments that correspond to IND-CPA, IND-CCA and simulation-based security.In this work we provide a complete and systematic investigation of Consistency, a natural security property for FE, that deals with attacks that can be mounted by Alice, Charlie or a collusion of the two against Bob. We develop three main types of consistency notions according to which set of parties is corrupted and investigate their relation to the standard security properties of FE. To validate our different consistency types, we extend the universally composable framework for FE by Matt and Maurer (CSF 2015) and we show that our consistency notions naturally complement FE security by proving how they imply (and are implied by) UC security depending on which set of parties is corrupted; in this way we demonstrate a complete characterization of consistency for FE. Finally, we provide explicit constructions that achieve consistency efficiently either directly via a construction based on MDDH for specific function classes of inner products over a modulo group or generically for all the consistency types via compilers using standard cryptographic tools.

Smart contracts present a uniform approach for deploying distributed computation and have become a popular means to develop security critical applications. A major barrier to adoption for many applications is the public nature of existing systems, such as Ethereum. Several systems satisfying various definitions of privacy and requiring various trust assumptions have been proposed; however, none achieved the universality and uniformity that Ethereum achieved for non-private contracts: One unified method to construct most contracts. We provide a unified security model for private smart contracts which is based on the Universal Composition (UC) model and propose a novel core protocol, KACHINA, for deploying privacy-preserving smart contracts, which encompasses previous systems. We demonstrate the KACHINA method of smart contract development, using it to construct a contract that implements privacy-preserving payments, along the lines of Zerocash, which is provably secure in the UC setting and facilitates concurrency.

Abstract A watermarking scheme for a public‐key cryptographic functionality enables the embedding of a mark in the instance of the secret‐key algorithm such that the functionality of the original scheme is maintained, while it is infeasible for an adversary to remove the mark (unremovability) or mark a fresh object without the marking key (unforgeability). A number of works have appeared in the literature proposing different definitional frameworks and schemes secure under a wide range of assumptions. In the previous work [1, 2], the authors proposed a meaningful relaxation of the watermarking model and gave constructions that allow direct watermarking of popular cryptographic schemes (e.g. ElGamal Encryption). A definitional framework for watermarking public‐key cryptographic functionalities and implementations which covers both deterministic (e.g. decryption) and probabilistic (e.g. signing) secret‐key algorithms is provided. The authors’ work unifies the previous results of [1, 2] where deterministic and probabilistic circuits to be watermarked as separate cases are considered. The constructions of [1, 2] were previously presented as extended abstracts missing rigorous security proofs. The authors prove those constructions secure under their new, unified framework. In the authors’ schemes secret detection of the watermark is provided, and security under minimal hardness assumptions assuming only the existence of one‐way functions, is proved.

Superlight clients enable the verification of proof-of-work-based blockchains by checking only a small representative number of block headers instead of all the block headers as done in simplified payment verification (SPV). Such clients can be embedded within other blockchains by implementing them as smart contracts, allowing for cross-chain verification. One such interesting instance is the consumption of Bitcoin data within Ethereum by implementing a Bitcoin superlight client in Solidity. While such theoretical constructions have demonstrated security and efficiency in theory, no practical implementation exists. In this work, we put forth the first practical Solidity implementation of a superlight client which implements the NIPoPoW superblocks protocol. Contrary to previous work, our Solidity smart contract achieves sufficient gas-efficiency to allow a proof and counter-proof to fit within the gas limit of a block, making it practical. We provide extensive experimental measurements for gas consumption. The optimizations that enable gas-efficiency heavily leverage a novel technique which we term hash-and-resubmit, which almost completely eliminates persistent storage requirements, the most expensive operation of smart contracts in terms of gas. Instead, the contract asks contesters to resubmit data and checks their veracity by hashing it. Other optimizations include off-chain manipulation of proofs in order to remove expensive look-up structures, and the usage of an optimistic schema. We show that such techniques can be used to bring down gas costs significantly and may be of independent interest. Lastly, our implementation allows us to calculate concrete cryptoeconomic parameters for the superblocks NIPoPoWs protocol and in particular to make recommendations about the monetary value of the collateral parameters. We provide such parameter recommendations over a variety of liveness settings.

We establish the optimal security threshold for the Bitcoin protocol in terms of adversarial hashing power, honest hashing power, and network delays. Specifically, we prove that the protocol is secure if [ra < 1/Δ0 + 1/rh,,] where rh is the expected number of honest proof-of-work successes in unit time, ra is the expected number of adversarial successes, and no message is delayed by more than Δ0 time units. In this regime, the protocol guarantees consistency and liveness with exponentially decaying failure probabilities. Outside this region, the simple private chain attack prevents consensus. Our analysis immediately applies to any Nakamoto-style proof-of-work protocol; in the full version of this paper we also present the adaptations needed to apply it in the proof-of-stake setting, establishing a similar threshold there.

The high latency and low throughput of blockchain protocols constitute one of the fundamental barriers for their wider adoption. Overlay protocols, notably the lightning network, have been touted as the most viable direction for rectifying this in practice. In this work we present for the first time a full formalisation and security analysis of the lightning network in the (global) universal composition setting that leverages a global ledger functionality, for which realisability by the Bitcoin blockchain protocol has been demonstrated in previous work [Badertscher et al., Crypto’17]. As a result, our treatment delineates exactly how the security guarantees of the protocol depend on the properties of the underlying ledger and the frequent availability of the protocol participants. Moreover, we provide a complete and modular description of the core of the lightning protocol that highlights precisely its dependency to underlying basic cryptographic primitives such as igital signatures, pseudorandom functions, identity-based signatures and a less common two-party primitive, which we term a combined digital signature, that were originally hidden within the lightning protocol’s implementation.

We introduce and study reward sharing schemes (RSS) that promote the fair formation of stake pools in collaborative projects that involve a large number of stakeholders such as the maintenance of a proof-of-stake (PoS) blockchain. Our mechanisms are parameterized by a target value for the desired number of pools. We show that by properly incentivizing participants, the desired number of stake pools is a Nash equilibrium arising from rational play. Our equilibria also exhibit an efficiency / security tradeoff via a parameter that calibrates between including pools with the smallest cost and providing protection against Sybil attacks, the setting where a single stakeholder creates a large number of pools in the hopes to dominate the collaborative project. We then describe how RSS can be deployed in the PoS setting, mitigating a number of potential deployment attacks and protocol deviations that include censoring transactions, performing Sybil attacks with the objective to control the majority of stake, lying about the actual cost and others. Finally, we experimentally demonstrate fast convergence to equilibria in dynamic environments where players react to each other's strategic moves over an indefinite period of interactive play. We also show how simple reward sharing schemes that are seemingly more “fair”, perhaps counterin-tuitively, converge to centralized equilibria.

We improve the fundamental security threshold of eventual consensus Proof-of-Stake (PoS) blockchain protocols under the longest-chain rule by showing, for the first time, the positive effect of rounds with concurrent honest leaders. Current security analyses reduce consistency to the dynamics of an abstract, round-based block creation process that is determined by three events associated with a round: (i) event A: at least one adversarial leader, (ii) event S: a single honest leader, and (iii) event M: multiple, but honest, leaders. We present an asymptotically optimal consistency analysis assuming that an honest round is more likely than an adversarial round (i.e., Pr[S]+Pr[M] > Pr[A]); this threshold is optimal. This is a first in the literature and can be applied to both the simple synchronous communication as well as communication with bounded delays.In all existing consistency analyses, event M is either penalized or treated neutrally. Specifically, the consistency analyses in Ouroboros Praos (Eurocrypt 2018) and Genesis (CCS 2018) assume that Pr[S] - Pr[M] > Pr[A]; the analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto 2019) assume that Pr[S] > Pr[A]. Moreover, all existing analyses completely break down when Pr[S] <; Pr[A]. These thresholds determine the critical trade-off between the honest majority, network delays, and consistency error.Our new results can be directly applied to improve the security guarantees of the existing protocols. We also complement these results by analyzing the setting where S is rare, even allowing Pr[S] = 0, under the added assumption that honest players adopt a consistent chain selection rule.

The blockchain data structure maintained via the longest-chain rule—popularized by Bitcoin—is a powerful algorithmic tool for consensus algorithms. Such algorithms achieve consistency for blocks in the chain as a function of their depth from the end of the chain. While the analysis of Bitcoin guarantees consistency with error 2−k for blocks of depth O(k), the state-of-the-art of proof-of-stake (PoS) blockchains suffers from a quadratic dependence on k: these protocols, exemplified by Ouroboros (Crypto 2017), Ouroboros Praos (Eurocrypt 2018) and Sleepy Consensus (Asiacrypt 2017), can only establish that depth Θ(k2) is sufficient. Whether this quadratic gap is an intrinsic limitation of PoS—due to issues such as the nothing-at-stake problem—has been an urgent open question, as deployed PoS blockchains further rely on consistency for protocol correctnes. We give an axiomatic theory of blockchain dynamics that permits rigorous reasoning about the longest-chain rule and achieve, in broad generality, Θ(k) dependence on depth in order to achieve consistency error 2−k In particular, for the first time we show that PoS protocols can match proof-of-work protocols for linear consistency. We analyze the associated stochastic process, give a recursive relation for the critical functionals of this process, and derive tail bounds in both i.i.d. and martingale settings via associated generating functions.

We define the notion of one-shot signatures, which are signatures where any secret key can be used to sign only a single message, and then self-destructs. While such signatures are of course impossible classically, we construct one-shot signatures using quantum no-cloning. In particular, we show that such signatures exist relative to a classical oracle, which we can then heuristically obfuscate using known indistinguishability obfuscation schemes.

Sidechains have long been heralded as the key enabler of blockchain scalability and interoperability. However, no modeling of the concept or a provably secure construction has so far been attempted. We provide the first formal definition of what a sidechain system is and how assets can be moved between sidechains securely. We put forth a security definition that augments the known transaction ledger properties of liveness and safety to hold across multiple ledgers and enhance them with a new “firewall” security property which safeguards each blockchain from its sidechains, limiting the impact of an otherwise catastrophic sidechain failure. We then provide a sidechain construction that is suitable for proof-of-stake (PoS) sidechain systems. As an exemplary concrete instantiation we present our construction for an epoch- based PoS system consistent with Ouroboros (Crypto 2017), the PoS blockchain protocol used in Cardano which is one of the largest pure PoS systems by market capitalisation, and we also comment how the construction can be adapted for other protocols such as Ouroboros Praos (Eurocrypt 2018), Ouroboros Genesis (CCS 2018), Snow White and Algorand. An important feature of our construction is merged-staking that prevents “goldfinger” attacks against a sidechain that is only carrying a small amount of stake. An important technique for pegging chains that we use in our construction is cross-chain certification which is facilitated by a novel cryptographic primitive we introduce called ad-hoc threshold multisignatures (ATMS) which may be of independent interest. We show how ATMS can be securely instantiated by regular and aggregate digital signatures as well as succinct arguments of knowledge such as STARKs and bulletproofs with varying degrees of storage efficiency.

We present Ouroboros Crypsinous, the first formally analyzed privacy-preserving proof-of-stake blockchain protocol. To model its security we give a thorough treatment of private ledgers in the (G)UC setting that might be of independent interest. To prove our protocol secure against adaptive attacks, we introduce a new coin evolution technique relying on SNARKs and key-private forward secure encryption. The latter primitive-and the associated construction-can be of independent interest. We stress that existing approaches to private blockchain, such as the proof-of-work-based Zerocash are analyzed only against static corruptions.

We present a novel Proof-of-Stake (PoS) protocol, Ouroboros Genesis, that enables parties to safely join (or rejoin) the protocol execution using only the genesis block information. Prior to our work, PoS protocols either required parties to obtain a trusted "checkpoint" block upon joining and, furthermore, to be frequently online or required an accurate estimate of the number of online parties to be hardcoded into the protocol logic. This ability of new parties to "bootstrap from genesis" was a hallmark property of the Bitcoin blockchain and was considered an important advantage of PoW-based blockchains over PoS-based blockchains since it facilitates robust operation in a setting with dynamic availability, i.e., the natural setting---without external trusted objects such as checkpoint blocks---where parties come and go arbitrarily, may join at any moment, or remain offline for prolonged periods of time. We prove the security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake in a partially synchronous network with unknown message delay and unknown, varying levels of party availability. Our security proof is in the Universally Composable setting assuming the most natural abstraction of a hash function, known as the strict Global Random Oracle (ACM-CCS 2014); this highlights an important advantage of PoS blockchains over their PoW counterparts in terms of composability with respect to the hash function formalisation: rather than a strict GRO, PoW-based protocol security requires a "local" random oracle. Finally, proving the security of our construction against an adaptive adversary requires a novel martingale technique that may be of independent interest in the analysis of blockchain protocols.

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.

Finding differences between programs with similar functionality is an important security problem as such differences can be used for fingerprinting or creating evasion attacks against security software like Web Application Firewalls (WAFs) which are designed to detect malicious inputs to web applications. In this paper, we present SFADIFF, a black-box differential testing framework based on Symbolic Finite Automata (SFA) learning. SFADIFF can automatically find differences between a set of programs with comparable functionality. Unlike existing differential testing techniques, instead of searching for each difference individually, SFADIFF infers SFA models of the target programs using black-box queries and systematically enumerates the differences between the inferred SFA models. All differences between the inferred models are checked against the corresponding programs. Any difference between the models, that does not result in a difference between the corresponding programs, is used as a counterexample for further refinement of the inferred models. SFADIFF's model-based approach, unlike existing differential testing tools, also support fully automated root cause analysis in a domain-independent manner.

In this work, we significantly improve the efficiency of non-malleable codes in the split state model, by constructing a code with codeword length (roughly), where |s| is the length of the message, and k is the security parameter. This is a substantial improvement over previous constructions, both asymptotically and concretely.

PPSS is a central primitive introduced by Bagherzandi et al. [2] which allows a user to store a secret among n servers such that the user can later reconstruct the secret with the sole possession of a single password by contacting t + 1 (t <; n) servers. At the same time, an attacker breaking into t of these servers - and controlling all communication channels - learns nothing about the secret (or the password). Thus, PPSS schemes are ideal for on-line storing of valuable secrets when retrieval solely relies on a memorizable password. We show the most efficient Password-Protected Secret Sharing (PPSS) to date (and its implied Threshold-PAKE scheme), which is optimal in round communication as in Jarecki et al. [10] but which improves computation and communication complexity over that scheme requiring a single per-server exponentiation for the client and a single exponentiation for the server. As with the schemes from [10] and Camenisch et al. [4] we do not require secure channels or PKI other than in the initialization stage. We prove the security of our PPSS scheme in the Universally Composable (UC) model. For this we present a UC definition of PPSS that relaxes the UC formalism of [4] in a way that enables more efficient PPSS schemes (by dispensing with the need to extract the user's password in the simulation) and present a UC-based definition of Oblivious PRF (OPRF) that is more general than the (Verifiable) OPRF definition from [10] and is also crucial for enabling our performance optimization.

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.

We study the strategic considerations of miners participating in the bitcoin's protocol. We formulate and study the stochastic game that underlies these strategic considerations. The miners collectively build a tree of blocks, and they are paid when they create a node (mine a block) which will end up in the path of the tree that is adopted by all. Since the miners can hide newly mined nodes, they play a game with incomplete information. Here we consider two simplified forms of this game in which the miners have complete information. In the simplest game the miners release every mined block immediately, but are strategic on which blocks to mine. In the second more complicated game, when a block is mined it is announced immediately, but it may not be released so that other miners cannot continue mining from it. A miner not only decides which blocks to mine, but also when to release blocks to other miners. In both games, we show that when the computational power of each miner is relatively small, their best response matches the expected behavior of the bitcoin designer. However, when the computational power of a miner is large, he deviates from the expected behavior, and other Nash equilibria arise.

We tackle the problem of analyzing filter and sanitizer programs remotely, i.e. given only the ability to query the targeted program and observe the output. We focus on two important and widely used program classes: regular expression (RE) filters and string sanitizers. We demonstrate that existing tools from machine learning that are available for analyzing RE filters, namely automata learning algorithms, require a very large number of queries in order to infer real life RE filters. Motivated by this, we develop the first algorithm that infers symbolic representations of automata in the standard membership/equivalence query model. We show that our algorithm provides an improvement of x15 times in the number of queries required to learn real life XSS and SQL filters of popular web application firewall systems such as mod-security and PHPIDS. % Active learning algorithms require the usage of an equivalence oracle, i.e. an oracle that tests the equivalence of a hypothesis with the target machine. We show that when the goal is to audit a target filter with respect to a set of attack strings from a context free grammar, i.e. find an attack or infer that none exists, we can use the attack grammar to implement the equivalence oracle with a single query to the filter. Our construction finds on average 90% of the target filter states when no attack exists and is very effective in finding attacks when they are present. For the case of string sanitizers, we show that existing algorithms for inferring sanitizers modelled as Mealy Machines are not only inefficient, but lack the expressive power to be able to infer real life sanitizers. We design two novel extensions to existing algorithms that allow one to infer sanitizers represented as single-valued transducers. Our algorithms are able to infer many common sanitizer functions such as HTML encoders and decoders. Furthermore, we design an algorithm to convert the inferred models into BEK programs, which allows for further applications such as cross checking different sanitizer implementations and cross compiling sanitizers into different languages supported by the BEK backend. We showcase the power of our techniques by utilizing our black-box inference algorithms to perform an equivalence checking between different HTML encoders including the encoders from Twitter, Facebook and Microsoft Outlook email, for which no implementation is publicly available.

Many smartphone applications are web based and rely on cookies to maintain the status of a web session. Cookies, however, may lead to security threats since they may contain sensitive information. In addition, an attacker having access to a cookie can easily impersonate the legitimate user. In this paper, we propose and implement a system that securely outsources browser cookies to the cloud and ensures user privacy using Private Information Retrieval. Experimental evaluation using traces collected from operational cellular and WiFi networks demonstrates that our system achieves satisfactory performance for most real-life web browsing scenarios: the average latency is within 1.0 to 1.2 seconds (well within users' tolerance) even when retrieving tens of cookies over an LTE or WiFi network, and the amount of generated traffic is significantly lower than that when downloading the entire cookie database.

Wireless network traces have been widely used to understand human behaviors and provide value-added services. Sanitization based techniques have been shown to be severely lacking in protecting sensitive user information embedded in such traces. In this paper, we take an encryption based approach that provides much stronger protection of user privacy. One challenge in encrypting wireless network traces is how to encrypt time range while maintaining the utility of the traces. We propose two practical encryption techniques to support queries that involve time range. These two techniques provide much stronger security guarantee than existing order preserving encryption schemes, and present different tradeoffs in complexity, as well as storage and network bandwidth requirement. Last, we quantify the performance of the proposed approach using a smart campus prototype. The results show that our approach only leads to moderate increase in storage, network bandwidth and computation overhead, demonstrating the practicality of our approach.

Key extraction via measuring a physical quantity is a class of information theoretic key exchange protocols that rely on the physical characteristics of the communication channel, to enable the computation of a shared key by two parties that share no prior secret information. The key is supposed to be information theoretically hidden to an eavesdropper. Despite the recent surge of research activity in the area, concrete claims about the security of the protocols typically rely on channel abstractions that are not fully experimentally substantiated. In this paper, we propose a novel methodology for the experimental security analysis of these protocols. The crux of our methodology is a falsifiable channel abstraction that is accompanied by an efficient experimental approximation algorithm of the conditional min-entropy available to the parties given the view of the eavesdropper. We focus on the signal strength between two wirelessly communicating transceivers as the measured quantity, and we use an experimental setup to compute the conditional min-entropy of the channel given the view of the attacker which we find to be linearly increasing. Armed with this understanding of the channel, we showcase the methodology by providing a general protocol for key extraction in this setting that is shown to be secure for a concrete parameter selection. In this way, we provide a comprehensively analyzed wireless key extraction protocol that is demonstrably secure against passive adversaries assuming our falsifiable channel abstraction. Our use of hidden Markov models as the channel model and a dynamic programming approach to approximate conditional min-entropy might be of independent interest, while other possible instantiations of our methodology can be feasible and may be motivated by this paper.

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 a new cryptographic primitive called a Traitor Deterring Scheme (TDS). A TDS is a multi-recipient public-key encryption scheme where an authority issues decryption keys to a set of users. The distinguishing feature of a TDS is that secret-keys are issued only after the users provide some private information as a form of collateral. The traitor deterring property ensures that if a malicious coalition of users (aka "traitors") produces an unauthorized (aka "pirate") decryption device, any recipient of the device will be able to recover at least one of the traitors' collaterals with only black-box access to the device. On the other hand, honest users' collaterals are guaranteed to remain hidden. In this fashion a TDS deincentivizes malicious behavior among users.

Identity-Based Encryption (IBE) provides a compelling solution to the PKI management problem, however it comes with the serious privacy consideration that a trusted party (called the PKG) is required to generate (and hence also know) the secret keys of all users. This inherent key escrow problem is considered to be one of the major reasons hindering the wider utilization of IBE systems. In order to address this problem, Goyal [ 20 ] introduced the notion of accountable authority IBE (A-IBE), in which a judge can differentiate the PKG from the user as the source of a decryption software. Via this “tracing” mechanism, A-IBE deters the PKG from leaking the user’s secret key and hence offers a defense mechanism for IBE users against a malicious PKG. All previous works on A-IBE focused on specialized constructions trying to achieve different properties and efficiency enhancements. In this paper for the first time we show how to add accountability to any IBE scheme using oblivious transfer (OT), with almost the same ciphertext efficiency as the underlying IBE. Furthermore, we extend our generic construction to support identity reuse without losing efficiency. This property is desirable in practice as users may accidentally lose their secret keys and they -naturally- prefer not to abandon their identities. How to achieve this property was open until our work. Along the way, we first modify the generic construction and develop a new technique to provide public traceability generically. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We present a randomized algorithm for asynchronous task allocation, also known as the write-all or do-all problem. Our algorithm has work complexity O(n+k2log3k) with high probability, where n the number of tasks and k the number of processes that participate in the computation. Our solution uses O(n) shared memory space that supports atomic test-and-set operations and with high probability each participating process uses O(k) internal memory space. This is the first adaptive solution for the write-all problem that has work n plus some additive term which depends only on the number of participating processes k and not the size of the problem n.

Abstract We consider the problem of minimizing the communication in single-database private information retrieval protocols in the case where the length of the data to be transmitted is large. We present first rate-optimal protocols for 1-out-of-n computationallyprivate information retrieval (CPIR), oblivious transfer (OT), and strong conditional oblivious transfer (SCOT). These protocols are based on a new optimalrate leveled homomorphic encryption scheme for large-output polynomial-size branching programs, that might be of independent interest. The analysis of the new scheme is intricate: the optimal rate is achieved if a certain parameter s is set equal to the only positive root of a degree-(m + 1) polynomial, where m is the length of the branching program. We show, by using Galois theory, that even when m = 4, this polynomial cannot be solved in radicals. We employ the Newton-Puiseux algorithm to find a Puiseux series for s, and based on this, propose a Θ (logm)-time algorithm to find an integer approximation to s.

Malware is one of the biggest security threats on the Internet today and deploying effective defensive solutions requires the rapid analysis of a continuously increasing number of malware samples. With the proliferation of metamorphic malware the analysis is further complicated as the efficacy of signature-based static analysis systems is greatly reduced. While dynamic malware analysis is an effective alternative, the approach faces significant challenges as the ever increasing number of samples requiring analysis places a burden on hardware resources. At the same time modern malware can both detect the monitoring environment and hide in unmonitored corners of the system.

Universally composable (UC) protocols retain their security properties even when run concurrently alongside arbitrary other protocols. Unfortunately, it is known that UC multiparty computation (for general functionalities, and without assuming honest majority) is impossible without some form of setup. To circumvent this impossibility, various complete setup assumptions have been proposed. With only a few exceptions, past work has viewed these setup assumptions as being implemented by some ideal, incorruptible entity. Any such entity is thus a single point of failure, and security fails catastrophically in case the setup entity is subverted by an adversary. We propose here a clean, general, and generic approach for distributing trust among m arbitrary setups, by modeling potential corruption of setups within the UC framework, where such corruption might be fail-stop, passive, or arbitrary and is in addition to possible corruption of the parties themselves. We show several feasibility and impossibility results in this model, for different specifications of the corruptible sets. For example, we show that given m complete setups, up to t of which might be actively corrupted in an adaptive manner, general multiparty computation with no honest majority is possible if and only if t < m/2.

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.

How is it possible to prevent the sharing of cryptographic functions? This question appears to be fundamentally hard to address since in this setting the owner of the key is the adversary: she wishes to share a program or device that (potentially only partly) implements her main cryptographic functionality. Given that she possesses the cryptographic key, it is impossible for her to be prevented from writing code or building a device that uses that key. She may though be deterred from doing so. We introduce leakage-deterring public-key cryptosystems to address this problem. Such primitives have the feature of enabling the embedding of owner-specific private data into the owner's public-key so that given access to any (even partially functional) implementation of the primitive, the recovery of the data can be facilitated. We formalize the notion of leakage-deterring in the context of encryption, signature, and identification and we provide efficient generic constructions that facilitate the recoverability of the hidden data while retaining privacy as long as no sharing takes place.

In the setting of cryptographic protocols, the corruption of a party has traditionally been viewed as a simple, uniform and atomic operation, where the adversary decides to get control over a party and this party immediately gets corrupted. In this paper, motivated by the fact that different players may require different resources to get corrupted, we put forth the notion of resource-based corruptions, where the adversary must invest some resources in order to corrupt a player.

In-network aggregation reduces the energy cost of processing aggregate queries (such as SUM, MAX, etc.) in wireless sensor networks. Recently, research has focused on secure in-network aggregation, motivated by the following two scenarios: 1) the sensors are deployed in open and unsafe environments, and 2) the aggregation process is outsourced to an untrustworthy service. Despite the bulk of work on the topic, there is currently no solution providing both integrity and confidentiality in the above scenarios. Moreover, existing solutions either return approximate results, or have limited applicability to certain types of aggregate queries. Our paper is the first work that provides both integrity and confidentiality in the aforementioned scenarios, while covering a wide range of aggregates and returning exact results. We initially present SIES, a scheme that solves exact SUM queries through a combination of homomorphic encryption and secret sharing. Subsequently, we show how to adapt SIES in order to support many other exact aggregate queries (such as MAX, MEDIAN, etc.). Finally, we augment our schemes with a functionality that identifies malicious sensors, preventing denial-of-service (DoS) attacks and attributing robustness to the system. Our techniques are lightweight and induce very small bandwidth consumption. Therefore, they constitute ideal solutions for resource-constrained sensors.

In-network aggregation is a popular methodology adopted in wireless sensor networks, which reduces the energy expenditure in processing aggregate queries (such as SUM, MAX, etc.) over the sensor readings. Recently, research has focused on secure in-network aggregation, motivated (i) by the fact that the sensors are usually deployed in open and unsafe environments, and (ii) by new trends such as outsourcing, where the aggregation process is delegated to an untrustworthy service. This new paradigm necessitates the following key security properties: data confidentiality, integrity, authentication, and freshness. The majority of the existing work on the topic is either unsuitable for large-scale sensor networks, or provides only approximate answers for SUM queries (as well as their derivatives, e.g., COUNT, AVG, etc). Moreover, there is currently no approach offering both confidentiality and integrity at the same time. Towards this end, we propose a novel and efficient scheme called SIES. SIES is the first solution that supports Secure In-network processing of Exact SUM queries, satisfying all security properties. It achieves this goal through a combination of homomorphic encryption and secret sharing. Furthermore, SIES is lightweight (it relies on inexpensive hash operations and modular additions/multiplications), and features a very small bandwidth consumption (in the order of a few bytes). Consequently, SIES constitutes an ideal method for resource-constrained sensors.

We present and analyze a wait-free deterministic algorithm for solving the at-most-once problem: how m fail-prone processes perform asynchronously n tasks at most once using shared memory. Our algorithmic strategy provides for the first time nearly optimal effectiveness, which is a measure that expresses the total number of tasks completed in the worst case. Our algorithm's effectiveness equals n-2m+2. This is up to an additive factor of m close to the known effectiveness lower bound n-m+1 and improves on the previously best known deterministic solutions that have effectiveness only n-log m o(n). We also present a work and space complexity analysis for suitable ranges of the algorithm parameters and demonstrate further that (i) we can achieve work O(nm log n log m) and simultaneously effectiveness of n-3m2-m+2, which is asymptotically optimal for any m=o(√n),(ii) we can achieve optimal work up to logarithmic factors Õ(n) and asymptotically optimal effectiveness whenever m=o(3√n).

Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the “trustedparty paradigm,” where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to “emulating” the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an ideal functionality. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their “unstable” nature, does not seem to be an easy task. In this paper we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of canonical ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure. In our framework, the constituent functionalities of a task can be derived either directly or, following a translation strategy we introduce, from existing game-based definitions; such definitions have in many cases captured desired individual properties of cryptographic tasks, albeit in less adversarial settings. Our translation methodology entails a sequence of steps that systematically derive a corresponding canonical functionality given a game-based definition, effectively “lifting” the game-based definition to its composition-safe version. We showcase our methodology by applying it to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to “debug” previous definitions and pinpoint their shortcomings.

Fingerprinting codes, originally designed for embedding traceable fingerprints in digital content, have many applications in cryptography; most notably, they are used to construct traitor tracing systems. Recently there has been some interest in constructing robust fingerprinting codes: codes capable of tracing words even when the pirate adversarially destroys a δ fraction of the marks in the fingerprint. An early construction due to Boneh and Naor produces codewords whose length is proportional to c4/(1-δ)2 where c is the number of words at the adversary's disposal. Recently Nuida developed a scheme with codewords of length proportional to (c log c)2/(1-δ) 2. In this paper we introduce a new technique for constructing codes whose length is proportional to (c log c)2/(1-δ), which is asymptotically optimal up to logarithmic factors. These new codes lead to traitor tracing systems with constant size ciphertext and asymptotically shorter secret keys than previously possible.

Traitor tracing refers to a class of encryption schemes that can be used to deter key-leakage. They apply to a setting that involves many receivers, each one receiving a fingerprinted decryption key. If a set of malicious receivers (also known as traitors) constructs an illicit decoder then a tracing mechanism enables an authority to identify at least one of the traitors. The very first traitor tracing scheme that has sublinear ciphertext size and is capable of tracing unambiguously illicit decoders that may shut-down (or employ some sort of self-defensive mechanism that would be adverse to tracing) was proposed in AsiaCrypt 2004 by Matsushita and Imai.In this work we demonstrate that this scheme is susceptible to an attack by an illicit decoder that not only evades tracing but results with high likelihood in the incrimination of an innocent user. Our attack is based on the fact that an illicit decoder can decompose a ciphertext to a set of components that can be submitted to a statistical test which distinguishes between tracing and regular system operation. The statistical distance between the two distributions converges to 1 as the number of traitors grows with an exponential rate in the number of traitors. After demonstrating our attack we also present a way to repair the construction as long as the traitors are not spaced too far apart in the user population. In particular we devise a transmission mechanism that eliminates the discrepancies between the tracing operation and the regular operation in the system and works against illicit decoders that are correct with sufficiently high probability.

This paper investigates the feasibility of implementing at-most-once access semantics in a model where a collection of actions is to be performed by failure-prone, asynchronous shared-memory processes. We introduce the At-Most-Once problem for performing a set of n jobs using m processors, and we define the notion of efficiency for such protocols, called effectiveness, that allows the classification of algorithms solving the problem. The effectiveness for an at-most-once implementation is the number of jobs safely completed by the implementation, expressed as a function of the number of jobs n, the number of processes m, and the number of process crashes f. We prove a lower bound of n--f on the effectiveness of any algorithm. We then present two process solutions that offer a trade off between work and space complexity. Finally, we generalize a two-process solution for the multi-process setting using a hierarchical algorithm that achieves effectiveness of n--log m†o(n), coming reasonably close, asymptotically, to the corresponding lower bound.

This study introduces hidden identity-based signatures (Hidden-IBS), a type of digital signatures that provide mediated signer-anonymity on top of Shamir's identity-based signatures. The motivation of the new signature primitive is to resolve an important issue with the kind of anonymity offered by ‘group signatures’ where it is required that either the group membership list be public for opening signatures or that the opening authority be dependent on the group manager for its operation. Contrary to this, Hidden-IBS does not require the maintenance of a group membership list for opening signatures and they enable an opening authority that is totally independent of the group manager. As the authors argue this makes Hidden-IBS much more attractive than group signatures for a number of applications. In this study, the authors provide a formal model of Hidden-IBS as well as two efficient constructions that realise the new primitive. To demonstrate the power of the new primitive, the authors apply it to solve a problem of current onion-routing systems focusing on the Tor system in particular.

In recent years, two distinct electronic voting technologies have been introduced and extensively utilized in election procedures: direct recording electronic systems and optical scan (OS) systems. The latter are typically deemed safer, as they inherently provide a voter-verifiable paper trail that enables hand-counted audits and recounts that rely on direct voter input. For this reason, OS machines have been widely deployed in the United States. Despite the growing popularity of these machines, they are known to suffer from various security vulnerabilities that, if left unchecked, can compromise the integrity of elections in which the machines are used. This article studies general auditing procedures designed to enhance the integrity of elections conducted with optical scan equipment and, additionally, describes the specific auditing procedures currently in place in the State of Connecticut. We present an abstract view of a typical OS voting technology and its relationship to the general election process. With this in place, we lay down a ldquotemporal-resourcerdquo adversarial model, providing a simple language for describing the disruptive power of a potential adversary. Finally, we identify how audit procedures, injected at various critical stages before, during, and after an election, can frustrate such adversarial interference and so contribute to election integrity. We present the implementation of such auditing procedures for elections in the State of Connecticut utilizing the Premiere (Diebold) AccuVote OS; these audits were conducted by the UConn VoTeR Center, at the University of Connecticut, on request of the Office of the Secretary of the State. We discuss the effectiveness of such procedures in every stage of the process and we present results and observations gathered from the analysis of past election data.

Public-key traitor-tracing schemes is a supporting technology for content distribution that discourages abuse and resale of cryptographic keys used for the distribution. These schemes enable a system manager to maintain a set of subscribers so that any external content provider can use the public key nature of the method and transmit data to the subscribers, while assuring that if a coalition of users generate a pirate deciphering device, they can be identified via a procedure called "traitor tracing."

In this paper, we investigate the decoding problem of Reed–Solomon (RS) codes, also known as the polynomial reconstruction problem (PR), from a cryptographic hardness perspective. Namely, we deal with samplable PR instances over parameter choices for which decoding is not known to be feasibly solvable and where part of the solution polynomial is the hidden input. We put forth a natural decisional intractability assumption that relates to this decoding problem: distinguishing between a single randomly chosen error location and a single randomly chosen nonerror location for a given corrupted RS codeword with random noise. We prove that under this assumption, PR instances are entirely pseudorandom, i.e., they are indistinguishable from random vectors over the underlying finite field. Moreover, under the same assumption, we show that it is hard to extract any partial information related to the hidden input encoded by the corrupted PR instance, i.e., PR instances hide their message polynomial solution in the semantic security sense. The above results lay a framework for the exploitation of PR as an intractability assumption for provable security of cryptographic primitives. Based on this framework, we present provably secure cryptographic constructions for 1) a pseudorandom number generator, 2) a semantically secure version of the oblivious polynomial evaluation (OPE) protocol, and 3) a stateful cipher with a set of interesting properties that include: semantic security, forward secrecy, error-correcting decryption and an array of random self-reducibility properties with respect to the plaintext choice, key choice, and partial domain choice.

Special purpose trusted computing devices are currently being deployed to offer many services for which the general purpose computing paradigm is unsuitable. The nature of the services offered by many of these devices demand high security and reliability, as well as low cost and low power consumption. Electronic Voting machines is a canonical example of this phenomenon. With electronic voting machines currently being used in much of the United States and several other countries, there is a strong need for thorough security evaluation of these devices and the procedures in place for their use. In this work, we first put forth a general framework for special purpose trusted computing devices. We then focus on Optical Scan (OS) electronic voting technology as a specific instance of this framework. OS terminals are a popular e-voting technology with the decided advantage of a user-verified paper trail: the ballot sheets themselves. Still election results are based on machine- generated totals as well as machine-generated audit reports to validate the voting process. In this paper we present a security assessment of the Diebold AccuVote Optical Scan voting terminal (AV-OS), a popular OS terminal currently in wide deployment anticipating the 2008 Presidential elections. The assessment is developed using exclusively reverse-engineering, without any technical specifications provided by the machine suppliers. We demonstrate a number of security issues that relate to the machine's proprietary language, called AccuBasic, that is used for reporting election results. While this language is thought to be benign, especially given that it is essentially sandboxed by the firmware to have only read access, we demonstrate that it is powerful enough to (i) strengthen known attacks against the AV-OS so that they become undetectable prior to elections (and thus significantly increasing their magnitude) or, (ii) to conditionally bias the election results to reach a desired outcome. Given the discovered vulnerabilities and attacks we proceed to discuss how random audits can be used to validate with high confidence that a procedure carried out by special purpose devices such as the AV-OS has not been manipulated. We end with a set of recommendations for the design and safe-use of OS voting systems.

The broadcast nature of a wireless link provides a natural eavesdropping and intervention capability to an adversary. Thus, securing a wireless link is essential to the security of a wireless network, and key generation algorithms are necessary for securing wireless links. However, traditional key agreement algorithms can be very costly in many settings, e.g. in wireless ad-hoc networks, since they consume scarce resources such as bandwidth and battery power.

This work introduces the Adder system , an Internet-based, free and open source electronic voting system which employs strong cryptography. Our system is a fully functional e-voting platform and enjoys a number of security properties, such as robustness, trust distribution, ballot privacy, auditability and verifiability. It can readily implement and carry out various voting procedures in parallel and can be used for small scale boardroom/department-wide voting as well as large-scale elections. In addition, Adder employs a flexible voting scheme which allows the system to carry out procedures such as surveys or other data collection activities. Adder offers a unique opportunity to study cryptographic voting protocols from a systems perspective and to explore the security and usability of electronic voting systems

The IEEE 802.11 Wireless Local Area Network (WLAN) specifications have been the subject of increased attention due to their rapid commercial adaptation and the introduction of new security and privacy concerns. The IEEE 802.1x standard was introduced in order to overcome the initial security shortcomings of the Wired Equivalent Privacy (WEP) protocol. The IEEE 802.1x standard is an extensible standard that couples 802.11 networks with various authentication services through the incorporation of an Extensible Authentication Protocol (EAP) authentication dialog. The existing implementations of EAP dialogs are based on standard cryptographic solutions for authentication and session key generation but do not, however, provide any form of user anonymity or privacy. Anonymity and privacy are currently of pressing interest, especially in the context of WLANs, which are simultaneously the best medium to provide privacy (there is no physical phone number or connection end-point with a predetermined owner) as well as the most threatening medium to user privacy, as they have the potential of disclosing not only the identity of the user, but also their physical location. At the same time, the potential "perfect hiding" capabilities of WLAN users also highlights the need to control anonymity by introducing more flexible authentication mechanisms. Moreover, payment for wireless services is completely decoupled from the above procedures, raising additional efficiency and privacy concerns. In this work we propose a new EAP authentication dialog based on anonymous electronic cash that provides for privacy, anonymity control, payment acceptance and billing, and authentication. Our solution is based on the notion of "public-key embedding e-cash," an e-cash variant we present and formalize in this paper. We present a concrete description of the new EAP authentication dialog in the context of IEEE 802.1x. We also present an effi- cient implementation of a public-key embedding e-cash scheme based on RSA blind signatures and prove its security.

Traitor Tracing Schemes constitute a very useful tool against piracy in the context of digital content broadcast. In such multi-recipient encryption schemes, each decryption key is fingerprinted and when a pirate decoder is discovered, the authorities can trace the identities of the users that contributed in its construction (called traitors). Public-key traitor tracing schemes allow for a multitude of non trusted content providers using the same set of keys, which makes the scheme "server-side scalable." To make such schemes also "client-side scalable," i.e. long lived and usable for a large population of subscribers that changes dynamically over time, it is crucial to implement efficient Add-user and Remove-user operations. Previous work on public-key traitor tracing did not address this dynamic scenario thoroughly, and there is no efficient scalable public key traitor tracing scheme that allows an increasing number of Add-user and Remove-user operations.To address these issues, we introduce the model of Scalable Public-Key Traitor Tracing, and present the first construction of such a scheme. Our model mandates for deterministic traitor tracing and an unlimited number of efficient Add-user operations and Remove-user operations. A scalable system achieves an unlimited number of revocations while retaining high level of efficiency by dividing the run-time of the system into periods. Each period has a saturation level for the number of revocations. When a period becomes saturated, an efficient new-period operation is issued by the system server that resets the saturation level. We present a formal adversarial model for our system taking into account its periodic structure, and we prove our construction secure, both against adversaries that attempt to cheat the revocation mechanism as well as against adversaries that attempt to cheat the traitor tracing mechanism.