Approximate lower bound arguments

OpenBU (Boston University) · 2024-05-26

Accepted manuscript

Verifiable Random Functions (VRFs)

2023-08-01 · 29 citations

A Verifiable Random Function (VRF) is the public-key version of a
\n keyed cryptographic hash. Only the holder of the private key can
\n compute the hash, but anyone with public key can verify the
\n correctness of the hash. VRFs are useful for preventing enumeration
\n of hash-based data structures. This document specifies several VRF
\n constructions that are secure in the cryptographic random oracle
\n model. One VRF uses RSA and the other VRF uses Eliptic Curves (EC).

Turning HATE into LOVE: Compact Homomorphic Ad Hoc Threshold Encryption for Scalable MPC

Lecture notes in computer science · 2021-01-01 · 11 citations

Compact Certificates of Collective Knowledge

2021-05-01 · 19 citations

We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message M, by many signers of different weights, and compress them to a much shorter certificate. This certificate convinces the verifiers that signers with sufficient total weight signed M, even though the verifier will not see—let alone verify—all of the signatures. Thus, for example, a compact certificate can be used to prove that parties who jointly have a sufficient total account balance have attested to a given block in a blockchain.After defining compact certificates, we demonstrate an effi-cient compact certificate scheme. We then show how to implement such a scheme in a decentralized setting over an unreliable network and in the presence of adversarial parties who wish to disrupt certificate creation. Our evaluation shows that compact certificates are 50–280× smaller and 300–4000 cheaper to verify than a natural baseline approach.

Can a Blockchain Keep a Secret

IACR Cryptology ePrint Archive · 2020-01-01 · 5 citations

Compact Certificates of Collective Knowledge.

DSpace@MIT (Massachusetts Institute of Technology) · 2020-01-01

We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message M, by many signers of different weights, and compress them to a much shorter certificate. This certificate convinces the verifiers that signers with sufficient total weight signed M, even though the verifier will not see—let alone verify—all of the signatures. Thus, for example, a compact certificate can be used to prove that parties who jointly have a sufficient total account balance have attested to a given block in a blockchain.After defining compact certificates, we demonstrate an effi-cient compact certificate scheme. We then show how to implement such a scheme in a decentralized setting over an unreliable network and in the presence of adversarial parties who wish to disrupt certificate creation. Our evaluation shows that compact certificates are 50–280× smaller and 300–4000 cheaper to verify than a natural baseline approach.

Can a Public Blockchain Keep a Secret?

Lecture notes in computer science · 2020 · 87 citations

• Computer Science
• Computer Science
• Computer Security

Pointproofs: Aggregating Proofs for Multiple Vector Commitments

2020-10-30 · 5 citations

Vector commitments enable a user to commit to a sequence of values and provably reveal one or many values at specific posi- tions at a later time. In this work, we construct Pointproofs? a new vector commitment scheme that supports non-interactive aggregation of proofs across multiple commitments. Our construction enables any third party to aggregate a collection of proofs with respect to different, independently computed commitments into a single proof represented by an elliptic curve point of 48-bytes. In addition, our scheme is hiding: a commitment and proofs for some values reveal no information about the remaining values. We build Pointproofs and demonstrate how to apply them to blockchain smart contracts. In our example application, Pointproofs reduce bandwidth overheads for propagating a block of transactions by at least 60% compared to prior state- of-art vector commitments. Pointproofs are also efficient: on a single-thread, it takes 0.08 seconds to generate a proof for 8 values with respect to one commitment, 0.25 seconds to aggregate 4000 such proofs across multiple commitments into one proof, and 23 seconds (0.7 ms per value proven) to verify the aggregated proof.