Emad Heydari Beni

We present the first horizontally scalable polynomial commitment scheme (PCS) that is both transparent and plausibly post-quantum (PQ) secure. This PCS can be combined with the distributed polynomial interactive oracle proof (PIOP) introduced in Pianist (IEEE S& P 2024), which achieves linear scalability by encoding witnesses using bivariate polynomials. While Pianist and other scalable SNARK systems offer strong performance profiles, they rely on trusted setup ceremonies and cryptographic assumptions that are not PQ secure, e.g., pairing-based primitives. In contrast, we present a bivariate PCS based on FRI, which, when used to compile the Pianist PIOP, achieves a transparent and plausibly PQ alternative. Distributed FRI has a high communication cost. Therefore, we introduce Fold-and-Batch, a customizable technique that applies partial folding locally before performing batched FRI centrally. We formally prove the security of our constructions and provide an implementation for three variants of distributed FRI, accompanied by thorough performance evaluations. Our results show that Fold-and-Batch reduces communication overhead compared to existing distributed FRI approaches, while preserving scalability and maintaining moderate proof sizes. To our knowledge, this is the first horizontally scalable PCS that simultaneously achieves transparency, plausible PQ security, and a tunable tradeoff between efficiency, verifier cost, and communication.

An anonymous credential (AC) system with partial disclosure allows users to prove possession of a credential issued by an issuer while selectively disclosing a subset of their attributes to a verifier in a privacy-preserving manner. In keyed-verification AC (KVAC) systems, the issuer and verifier share a secret key. Existing KVAC schemes rely on computationally expensive zero-knowledge proofs during credential presentation, with the presentation size growing linearly with the number of attributes. In this work, we propose two highly efficient KVAC constructions that eliminate the need for zero-knowledge proofs during the credential presentation and achieve constant-size presentations. Our first construction adapts the approach of Fuchsbauer, Hanser and Slamanig (JoC'19), which achieved constant-size credential presentation in a publicly verifiable setting using their proposed structure-preserving signatures on equivalence classes (SPS-EQ) and set commitment schemes, to the KVAC setting. We introduce structure-preserving message authentication codes on equivalence classes (SP-MAC-EQ) and designated-verifier set commitments (DVSC), resulting in a KVAC system with constant-size credentials (2 group elements) and presentations (5 group elements). To avoid the bilinear groups and pairing operations required by SP-MAC-EQ, our second construction uses a homomorphic MAC with a simplified DVSC. While this sacrifices constant-size credentials (n+2 group elements, where n is the number of attributes), it retains constant-size presentations (2 group elements) in a pairingless setting. We formally prove the security of both constructions and provide open-source implementation results demonstrating their practicality. We extensively benchmarked our KVAC protocols and, additionally, bechmarked the efficiency of our SP-MAC-EQ scheme against the original SPS-EQ scheme, showcasing significant performance improvements.

In this paper, we show for the first time it is practical to privately delegate proof generation of zkSNARKs to a single server for computations of up to 2^20 R1CS constraints. We achieve this by computing zkSNARK proof generation over homomorphic ciphertexts, an approach we call blind zkSNARKs. We formalize the concept of blind proofs, analyze their cryptographic properties and show that the resulting blind zkSNARKs remain sound when compiled using BCS compilation. Our work follows the framework proposed by Garg et al. (Crypto'24) and improves the instantiation presented by Aranha et al. (Asiacrypt'24), which implements only the FRI subprotocol. By delegating proof generation, we are able to reduce client computation time from 10 minutes to mere seconds, while server computation time remains limited to 20 minutes. We also propose a practical construction for vCOED supporting constraint sizes four orders of magnitude larger than the current state-of-the-art verifiable FHE-based approaches. These results are achieved by optimizing Fractal for the GBFV homomorphic encryption scheme, including a novel method for making homomorphic NTT evaluation packing-friendly by computing it in two dimensions. Furthermore, we make the proofs publicly verifiable by appending a zero-knowledge Proof of Decryption (PoD). We propose a new construction for PoDs optimized for low proof generation time, exploiting modulus and ring switching in GBFV and using the Schwartz-Zippel lemma for proof batching; these techniques might be of independent interest. Finally, we implement the latter protocol in C and report on execution time and proof sizes.

In stream processing, managing sensitive information in a timely manner while ensuring trust remains a significant challenge. When parties without a priori trust cooperate to execute a streaming application, it is difficult to ensure that sensitive data is kept confidential while guaranteeing that every party executes their code honestly. This paper presents zkStream: a framework that leverages signatures and zero-knowledge proofs (ZKP) to add trust to streaming applications that run in the edge cloud, guaranteeing data confidentiality, provenance, and computational integrity. We introduce two optimizations to minimize the computational overhead associated with ZKPs, making our framework suitable for real-world applications. We validated our solution with existing benchmarks for streaming applications. Our method achieves an end-to-end latency that is between 6.5 and 15× faster than a naive implementation, demonstrating its potential for industrial adoption where trust is critical.

In recent years, part of the web is shifting to a client-centric, decentralized model where web clients become the leading execution environment for application logic and data storage. However, current solutions to build decentralized web applications with multiple distrusting parties often involve a decentralized backend of servers running a BFT protocol between them. Existing consensus protocols using either all-to-all communication, or leader-based gossip suffer from performance degradation in unstable network conditions. In this paper, we present BeauForT, a purely browser-based platform for decentralized BFT consensus in client-centric, community-driven applications. We propose a novel, optimistic, leaderless, gossip-based consensus protocol, tolerating Byzantine replicas, combined with a robust and efficient state-based synchronization protocol. This protocol makes BeauForT well suited for the decentralized client-centric web and its dynamic nature with many network disruptions or node failures.

Business application owners want to outsource data storage, including sensitive data, to the public cloud for economical reasons. This is often challenging since these businesses are and remain responsible for regulatory compliance and data protection, even though cloud providers may do their best to offer (data) protection. Meanwhile, data protection techniques evolve and get better because of continuous research and improvement of advanced encryption. Numerous cryptographic tactics have been proposed, e.g., searchable symmetric encryption (SSE) and homomorphic encryption (HE), that support search and aggregation functions on encrypted data. Each of these tactics has a trade-off between security, performance and functionality, but there is no one-size-fits-all solution. For the application developer, the underpinning concepts of these tactics are complex to comprehend, complex to integrate in a distributed application, and prone to implementation mistakes. In this paper we present DataBlinder, a distributed data access middleware that provides crypto agility by means of configurable fine-grained data protection at the application level. DataBlinder supports adaptive runtime selection of data protection tactics, and offers a plugin architecture for such tactics based on a key abstraction model for protection level, performance and supported query functionality. We have developed this middleware in close collaboration with businesses that face these challenges and offer cloud-based applications in e-finance, and e-health, by implementing and integrating state-of-the-art cryptographic schemes to Dat-aBlinder. This paper illustrates the case of medical data protection with FHIR-compliant [30] medical data. CCS Concepts • Security and privacy → Management and querying of encrypted data; • Information systems → Middleware for databases.