Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Rational Censorship Attack: Breaking Blockchain with a Blackboard
Get PDFCensorship resilience is a fundamental assumption underlying the security of blockchain protocols. Additionally, the analysis of blockchain security from an economic and game theoretic perspective has been growing in popularity in recent years.
In this work, we present a surprising rational censorship attack on blockchain censorship resilience when we adopt the analysis of blockchain security from a game theoretic lens and assume all users are rational.
In our attack, a colluding group with sufficient voting power censors the remainder nodes such that the group alone can gain all the rewards from maintaining the blockchain.
We show that if nodes are rational, coordinating this attack just requires a public read and write blackboard and we formally model the attack using a game theoretic framework.
Furthermore, we note that to ensure the success of the attack, nodes need to know the total true voting power held by the colluding group.
We prove that the strategy to join the rational censorship attack and also for nodes to honestly declare their power is a subgame perfect equilibrium in the corresponding extensive form game induced by our attack.
Finally, we discuss the implications of the attack on blockchain users and protocol designers as well as some potential countermeasures
An Update to ``Polynomial Hashing over Prime Order Fields\u27\u27
No full textNew state-of-the-art assembly implementations show that BRWHash is consistently faster than polyHash and both t-BRWHash and d-2LHash for all message lengths and for both the primes and
Hobbit: Space-Efficient zkSNARK with Optimal Prover Time
Get PDFZero-knowledge succinct non-interactive arguments (zkSNARKs) are notorious for their large prover space requirements, which almost prohibits their use for really large instances. Space-efficient zkSNARKs aim to address this by limiting the prover space usage, without critical sacrifices to its runtime. In this work, we introduce Hobbit, the only existing space-efficient zkSNARK that achieves optimal prover time for an arithmetic circuit . At the same time, Hobbit is the first transparent and plausibly post-quantum secure construction of its kind. Moreover, our experimental evaluation shows that Hobbit outperforms all prior general-purpose space-efficient zkSNARKs in the literature across four different applications (arbitrary arithmetic circuits, inference of pruned Multi-Layer Perceptron, batch AES128 evaluation, and select-and-aggregate SQL query) by 8- in terms or prover time while requiring up to 23 less total space.
At a technical level, we introduce two new building blocks that may be of independent interest: (i) the first sumcheck protocol for products of polynomials with optimal prover time in the streaming setting, and (ii) a novel multi-linear plausibly post-quantum polynomial commitment that outperforms all prior works in prover time (and can be tuned to work in a space-efficient manner). We build Hobbit by combining the above with a modified version of HyperPlonk, providing an explicit routine to stream access to the circuit evaluation
May the Force Be with you: Brute-Force Resistant Biometric Authentication and Key Reconstruction
No full textThe use of biometric-based security protocols is on the steep rise. As
biometrics become more popular, we witness more attacks. For example, recent
BrutePrint/InfinityGauntlet attacks showed how to brute-force fingerprints
stored on an Android phone in about 40 minutes. The attacks are possible because biometrics, like passwords, do not have high entropy. But unlike passwords, brute-force attacks are much more damaging for biometrics, because one cannot easily change biometrics in case of compromise. In this work, we propose a novel provably secure Brute-Force Resistant Biometrics (BFRB) protocol for biometric-based authentication and key reconstruction that protects against brute-force attacks even when the server storing biometric-related data is compromised. Our protocol utilizes a verifiable partially oblivious pseudorandom function, an authenticated encryption scheme, a pseudorandom function, and a hash. We formally define security for a BFRB protocol and reduce the security of our protocol to the security of the building blocks. We implement the protocol and study its performance for the ND-0405 iris dataset
Simple VESS
Get PDFWe present a scheme for verifiably encrypting a Shamir secret sharing to a committee of shareholders. Such a scheme can be used to easily implement distributed key generation (DKG) and resharing protocols used in threshold signing and decryption protocols. Our scheme is a minor variation on known techniques, and is not the most efficient in terms of communication and computational complexity. However, it is extremely simple and easy to implement. Moreover, for moderately sized shareholder committees of up to, say, 13 parties or so, and for applications where a DKG/resharing only needs to be performed occasionally, its performance should be acceptable in practice
The Effectiveness of Differential Privacy in Real-world Settings: A Metrics-based Framework to help Practitioners Visualise and Evaluate
Get PDFDifferential privacy (DP) has emerged as a preferred solution for privacy-preserving data analysis, having been adopted by several leading Internet companies. DP is a privacy-preserving mechanism that protects against re-identification of individuals within aggregated datasets. It is known that the privacy budget determines the trade-off between privacy and utility. In this paper, we propose the use of novel set of metrics and an easy-to-implement, step-by-step framework to facilitate the implementation of the DP mechanism on real-world datasets and guide the selection of based on desired accuracy vs utility trade-off. Currently, for a given query there is no widely accepted methodology on how to select and choose the best DP mechanism that offers an optimal trade-off between privacy and utility. In order to address this gap, we perform experiments by considering three real-world datasets, aiming to identify optimal and suitable mechanisms (Laplace or Gaussian) based on privacy utility trade-off as per use case for the commonly used count, sum and average queries for each dataset. Based on our experiment results, we observe that using our metric and framework, one can analyse noise distribution charts of multiple queries, and choose the suitable and the DP mechanism for achieving a balance between privacy and utility. Additionally, we show that the optimal depends on the particular query, desired accuracy and context in which DP is implemented, which suggests that an arbitrary, a-prior selection of cannot provide adequate results. Our framework prioritises the plotting and visualisation of values and results in the DP analysis, making its adoption easy for a wider audience
Lightweight Sorting in Approximate Homomorphic Encryption
Get PDFSorting encrypted values is an open research problem that plays a crucial role in the broader objective of providing efficient and practical privacy-preserving online services.
The current state of the art work by Mazzone, Everts, Hahn and Peter (USENIX Security \u2725) proposes efficient algorithms for ranking, indexing and sorting based on the CKKS scheme, which deviates from the compare-and-swap paradigm, typically used by sorting networks, using a permutation-based approach. This allows to build shallow sorting circuits in a very simple way.
In this work, we follow up their work and explore different approaches to approximate the nonlinear functions required by the encrypted circuit (where only additions and multiplications can be evaluated), and we propose simpler solutions that allow for faster computations and smaller memory requirements.
In particular, we drastically reduce the upper bound on the depth of the circuits from 65 to 20, making our circuits usable in relatively small rings such as , even for sorting values while preserving up to three decimal places. As an example, our circuit sorts 128 values with duplicates in roughly 20 seconds on a laptop, using roughly 1 GB of memory, maintaining a precision of 0.01.
Furthermore, we propose an implementation of a swap-based bitonic network that is not based on approximations of the sgn function, which scales linearly with the number of values, useful when the number of available slots is small
Jigsaw: Doubly Private Smart Contracts
Get PDFPrivacy is a growing concern for smart contracts on public ledgers.
In recent years, we have seen several practical systems for privacy-preserving smart contracts, but they only target privacy of on-chain data, and rely on trusted off-chain parties with user data -- for instance, a decentralized finance application (e.g. exchange) relies on an off-chain matching engine to process client orders that get settled on-chain, where privacy only applies to the on-chain data.
Privacy conscious users demand stronger notions of privacy, for their identity and their data, from all other parties in the ecosystem.
We propose a novel framework for smart contracts that ensures {\em doubly private}
execution, addressing {both on-chain and off-chain privacy} requirements.
In our framework, clients submit their requests in a privacy-preserving manner to a group of (potentially mutually untrusting) servers. These servers collaboratively match client requests without learning any information about the data or identities of the clients.
We then present {\em Jigsaw}, an efficient cryptographic realization of our proposed framework. {\em Jigsaw} builds on the ZEXE architecture (Bowe et al., S\&P 2020), which leverages zkSNARKs, and extends Collaborative zkSNARKs (Ozdemir and Boneh, USENIX 2022) to enable proof generation by a group of servers.
In Jigsaw, we introduce a novel collaborative zkSNARK construction that achieves low latency and reduced proving time, and showcase these advantages over sample applications ranging from trading in a decentralized exchange to auctions and voting.
Our experiments demonstrate that {\em Jigsaw} is roughly x faster in proof generation and uses orders-of-magnitude less bandwidth than the naive approach of using off-the-shelf Collaborative zkSNARKs
QV-net: Decentralized Self-Tallying Quadratic Voting with Maximal Ballot Secrecy
Get PDFDecentralized e-voting enables secure and transparent elections without relying on trusted authorities, with blockchain emerging as a popular platform. It has compelling applications in Decentralized Autonomous Organizations (DAOs), where governance relies on voting with blockchain-issued tokens. Quadratic voting (QV), a mechanism that mitigates the dominance of large token holders, has been adopted by many DAO elections to enhance fairness. However, current QV systems deployed in practice publish voters\u27 choices in plaintext with digital signatures. The open nature of all ballots comprises voter privacy, potentially affecting voters\u27 honest participation. Prior research proposes using cryptographic techniques to encrypt QV ballots, but they work in a centralized setting, relying on a trusted group of tallying authorities to administrate an election. However, in DAO voting, there is no trusted third party.
In this paper, we propose QV Network (QV-net), the first decentralized quadratic voting scheme, in which voters do not need to trust any third party other than themselves for ballot secrecy. QV-net is self-tallying with maximal ballot secrecy. Self-tallying allows anyone to compute election results once all ballots are cast. Maximal ballot secrecy ensures that what each voter learns from QV-net is nothing more than the tally and their own ballot. We provide an open-source implementation of QV-net to demonstrate its practicality based on real-world DAO voting settings, reporting only a few milliseconds for voting and a maximum of 255 milliseconds for tallying.
The exceptional efficiency of QV-net is attributed to the design of two new Zero-Knowledge Argument of Knowledge (ZKAoK) protocols for QV ballot secrecy and integrity. Previous works generally rely on pairing-friendly curves to prove the well-formedness of an encrypted QV ballot. But they incur heavy computation and large data sizes. We tackle the challenges of appropriately formalizing and proving ZKAoK relations for QV without using these curves. Specifically, we develop a succinct ZKAoK to prove a new relation: the sum of squares of a private vector\u27s components equals a private scalar. We also introduce the first aggregated range proof to prove that values committed under different keys fall within their respective ranges. Together, these two new zero-knowledge protocols enable us to build an efficient decentralized QV scheme and are of independent interest
Dynamic Group Signatures with Verifier-Local Revocation
Get PDFGroup Signatures are fundamental cryptographic primitives that allow users to sign a message on behalf of a predefined set of users, curated by the group manager. The security properties ensure that members of the group can sign anonymously and without fear of being framed. In dynamic group signatures, the group manager has finer-grained control over group updates while ensuring membership privacy (i.e., hiding when users join and leave). The only known scheme that achieves standard security properties and membership privacy has been proposed by Backes et al. CCS 2019. However, they rely on an inefficient revocation mechanism that re-issues credentials to all active members during every group update, and users have to rely on a secure and private channel to join the group.
In this paper, we introduce a dynamic group signature that supports verifier-local revocation, while achieving strong security properties, including membership privacy for users joining over a public channel. Moreover, when our scheme is paired with structure-preserving signatures over equivalence class it enjoys a smaller signature size compared to Backes et al. Finally, as a stand-alone contribution we extend the primitive Asynchronous Remote Key Generation (Frymann et al. CCS 2020) with trapdoors and introduce new security properties to capture this new functionality, which is fundamental to the design of our revocation mechanis