We introduce Zero-Knowledge Location Privacy (ZKLP), enabling users to prove to third parties that they are within a specified geographical region while not disclosing their exact location. ZKLP supports varying levels of granularity, allowing for customization depending on the use case. To realize ZKLP, we introduce the first set of Zero-Knowledge Proof (ZKP) circuits that are fully compliant to the IEEE 754 standard for floating-point arithmetic. Our results demonstrate that our floating point circuits amortize efficiently, requiring only 64 constraints per operation for 215single-precision floating-point multiplications. We utilize our floating point implementation to realize the ZKLP paradigm. In comparison to a baseline, we find that our optimized implementation has 15.9× less constraints utilizing single precision floating-point values, and 12.2× less constraints when utilizing double precision floating-point values. We demonstrate the practicability of ZKLP by building a protocol for privacy preserving peer-to-peer proximity testing - Alice can test if she is close to Bob by receiving a single message, without either party revealing any other information about their location. In such a setting, Bob can create a proof of (non-)proximity in 0.26 s, whereas Alice can verify her distance to about 470 peers per second.

With the increasing usage of fake videos in misinformation campaigns, proving the provenance of an edited video becomes critical, in particular, without revealing the original footage. We formalize the notion and security model of proofs of video authenticity and give the first cryptographic video authentication protocol Eva, which supports lossy codecs and arbitrary edits and is proven secure under well-established cryptographic assumptions. Compared to previous cryptographic methods for image authentication, Eva is not only capable of handling significantly larger amounts of data originating from the complex lossy video encoding but also achieves linear prover time, constant RAM usage, and constant proof size with respect to video size. These improvements have optimal theoretic complexity and are enabled by our two new theoretical advancements of integrating lookup arguments with folding-based incrementally verifiable computation (IVC) and compressing IVC proof efficiently, which may be of independent interest. For our implementation of Eva, we then integrate them with the Nova folding scheme, which we call Loua. As for concrete performance, we additionally utilize various optimizations such as tailored circuit design and GPU acceleration to make Eva highly practical: for a 2-minute HD (1280 × 720) video encoded in H.264 at 30 frames per second, Eva generates a 448 B proof in about 2.4 hours on consumer-grade hardware at 2.6 µs per pixel, surpassing state-of-the-art cryptographic image authentication schemes by more than an order of magnitude in terms of prover time and proof size.

A Verifiably Encrypted Signature (VES) scheme encrypts a digital signature in a way that allows the public to verify the validity of the encrypted signature. Recently, several practical VES schemes for ECDSA have been proposed to enable escrowed transactions with cryptocurrencies. However, these schemes are inefficient in terms of both communication and computation, or require a large lookup table. In this paper, we present two efficient VES schemes for ECDSA that improve upon previous work. The first scheme is based on Castagnos-Laguillaumie (CL) encryption, while the second is based on modified Joye-Libert (JL) encryption. Our benchmark shows that our schemes outperform existing constructions by a factor of at least 2 in both computation and communication. Additionally, our solution does not rely on any lookup table. We demonstrate that these schemes can also be generalized to design VES for Schnorr signature scheme and EdDSA. The main technical contribution of this paper, which is of independent interest, is a zero-knowledge proof for the equality of the discrete log of an elliptic-curve point and that of a JL ciphertext. Importantly, the security of our proof does not rely on any non-standard assumptions.

Threshold ECDSA receives interest lately due to its widespread adoption in blockchain applications. A common building block of all leading constructions involves a secure conversion of multiplicative shares into additive ones, which is called the multiplicative-to-additive (MtA) function. MtA dominates the overall complexity of all existing threshold ECDSA constructions. Specifically, O(n2) invocations of MtA are required in the case of n active signers. Hence, improvement of MtA leads directly to significant improvements for all state-of-the-art threshold ECDSA schemes.

Data availability is the major concern of outsourced data storage services. While reliability is promoted by many storage providers, it is infeasible for users to verify these claims. Proofs of Storage-Time are proposed to address this issue: they allow a prover to convince a verifier that the prover indeed stores the outsourced data continuously during the whole storage period. These protocols, however, either fail to guarantee the actual duration of data possession, or require the client to perform a computationally expensive storing process for each file, marking them far from being practical. We present$\mathsf {ePoSt}$, the first secure, stateless and efficient Proof of Storage-Time protocol with public verifiability. Not only does it ensure continuous data availability, but it also minimizes the cost of the client, which is crucial for real-world deployment. Specifically, processing a 1GB file for outsourcing, in anticipation for 3 proof/verify interactions, each attesting a period of 1 year at 25 minutes intervals requires only 66.34 minutes. In contrast, state-of-the-art solution requires 51 hours of processing to prepare a file for outsourcing. Proof size and verification remains at a reasonable cost: a proof is of size 48.82KB, and can be verified in 36.05 ms. Furthermore, our solution enjoys public verifiability and remains stateless. The former allows the data owner to outsource the verification process, and the latter allows unlimited number of proofs and verification to be conducted after the file has been stored. These properties make$\mathsf {ePoSt}$particularly suitable for new business models such as decentralised storage networks (e.g., Filecoin).