International Association
for Cryptologic Research

We present Orbweaver, the first plausibly post-quantum functional commitment to achieve quasilinear prover time together with O(log(n)) proof size and O(log(n)loglog(n)) verifier time. Orbweaver enables evaluation of linear maps on committed vectors over cyclotomic rings or the integers. It is extractable, preprocessing, non-interactive, structure-preserving, amenable to recursive composition, and supports logarithmic public proof aggregation. The security of our scheme is based on the k-R-ISIS assumption (and its knowledge counterpart), whereby we require a trusted setup to generate a universal structured reference string. We additionally use Orbweaver to construct a succinct polynomial commitment for integer polynomials.

Amortized bootstrapping offers a way to refresh multiple ciphertexts of a fully homomorphic encryption scheme in parallel more efficiently than refreshing a single ciphertext at a time. Micciancio and Sorrell (ICALP 2018) first proposed this technique to bootstrap n LWE ciphertexts at a time, reducing the total cost from \tilde{O}(n^2) to \tilde{O}(3^\epsilon n^{1+1/\epsilon}) for arbitrary \epsilon > 0. Several recent follow-up works have further improved the asymptotic cost. Despite these amazing progresses in theoretical efficiency, none of these works have demonstrated the practicality of batched LWE ciphertext bootstrapping. Moreover, most of these works only support limited functional bootstrapping, i.e., they only allow evaluating a specific type of function when bootstrapping. In this work, we propose a construction that is not only asymptotically efficient (requiring only \tilde{O}(n) polynomial multiplications for bootstrapping of n LWE ciphertexts) but also concretely efficient. We have our scheme implemented as a C++ library and show that it takes <5ms per LWE ciphertext to bootstrap for a binary gate, which is an order of magnitude faster than the state-of-the-art C++ implementation on LWE ciphertext bootstrapping in OpenFHE. Furthermore, our construction supports batched arbitrary functional bootstrapping. For a 9-bit messages space, our scheme takes ~6.7ms per LWE ciphertext to evaluate an arbitrary function with bootstrapping, which is about two to three magnitudes faster than all the existing schemes that achieve a similar functionality and message space.

Anonymous message delivery systems, such as private messaging services and privacy-preserving payment systems, need a mechanism for recipients to retrieve the messages addressed to them, without leaking metadata or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale. We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. These servers operate obliviously and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding (unlike in prior schemes). Our starting point is an asymptotically-efficient approach, using Fully Homomorphic Encryption and homomorphically-encoded Sparse Random Linear Codes. We then address the concrete performance using bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations. This reduces the digest size to a few bits per message scanned. Concretely, the servers' cost is ~$1 per million messages scanned, and the resulting digests can be decoded by recipients in ~20ms. Our schemes can thus practically attain the strongest form of receiver privacy for current applications such as privacy-preserving cryptocurrencies.