Grantees: Charalampos (Babis) Papamanthou (IP), Weijie Wang

Institution: Yale University

Description: This project focuses on tree-based vector commitments.What distinguishes tree-based vector commitments from other vector commitments is the fact that all proofs can be updated/maintained in sublinear time, whenever an element of the vector changes. However, due to this convenience, other challenges arise that we plan to investigate as part of this proposal. For example, it is typically hard to provide aggregation in tree-based vector commitments (e.g., Merkle tree proofs cannot be naturally aggregated) and verification of aggregated proofs can be expensive.

Directions:

(a) tree-based commitments based on multilinear trees;

(b) tree-based commitments based on RSA groups;

(c) tree-based commitments based on lattices.

Paper: BalanceProofs: Maintainable Vector Commitments with Fast Aggregation

Grantees: Carla Rafols (IP), Alexandros Zacharakis

Institution: Universitat Pompeu Fabra

Description: This project focuses on vector commitments in the discrete logarithm setting.

While the discrete logarithm setting is limited, because it does not allow to exploit key structure, it remains quite interesting to explore the problem in this setting for the following reasons:

Directions: In this project the grantees investigate what subsets of the desired properties of vector commitments can be achieved in the discrete logarithm and with what efficiency. They will use both known techniques mainly inspired from the succinct argument literature, as well as explore new techniques to tackle the problem. Furthermore, the project will explore more restricted scenarios such as designated verifier and distributed trust that can be of practical importance for applications where fully public verifiability is not necessary.

Status: in progress

Grantees: Russell Lai, Sri Aravinda Krishnan Thyagarajan, Martin Albrecht, Giulio Malavolta

Institutions:

Description:  This project focuses on lattice-based vector commitments.

Being “lattice-based” allows for some advanced functionalities and, critically, enables potentially post-quantum secure constructions. In particular, utilising the flexibility offered by lattices, the team aims for the first direct construction of any vector commitment with functional openings for any constant-degree polynomial. Moreover, to the best of our knowledge, this would be the first example of a lattice-based vector commitment beyond positional openings (for which there are “trivial” constructions from Merkle trees).

Directions:  The proposed construction is likely to only be shown secure against a new family of lattice-based assumptions, which are natural extensions of the short integer solution (SIS) assumption. This family is called the k-Ring Inhomogenous Short Integer Solution assumptions. Such assumptions offer additional algebraic structure, which allows to transfer techniques for pairing-based cryptography to the lattice world.

Paper: Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable in Crypto 2022

Grantees: Dario Fiore, Dimitris Kolonelos, Dominique Schroder, Hien Chu

Institutions:

Description:  This project focuses on building functional commitments for a larger class of functions.

In functional commitments, an opening not only discloses single vector entries but can also be used to open a function of the committed vector, still in a concise manner. While there exist several realizations of vector commitments under different assumptions and with a variety of efficiency measures, less is known about functional commitments of which only a few schemes are known.

Directions:  This project aims at studying the foundations of functional commitments with a particular focus on the computational assumptions and the minimal efficiency measures needed to build schemes for linear functions and more.

Paper: Inner Product Functional Commitments with Constant-Size Public Parameters and Openings in SCN 2022

Grantees: Tal Moran

Institution: Reichman University

Description:  The goal of this project is to explore a new direction in constructing proofs of storage that are both useful and suitable for a permissonless consensus algorithm.

Directions: The main idea is to look at converting privately verifiable proofs of storage into publicly verifiable proofs.

Privately verifiable proofs of storage are almost trivial to construct (e.g., encrypt some useful data and send it to the storage provider; without the private key, this data is completely incompressible). Even if we want to guarantee utility of the encoded data to the holder of the data, we have constructions that can provide this. For example, the recent works on incompressible encodings (including my paper with Daniel Wichs from the previous Crypto) show how to encode arbitrary data in a way that prevents compression, but still allows it to be decoded (without requiring a secret key).

Status: end date Jan 2023

Grantees: Danilo Francati, Qiang Tang (U. Sydney), Giuseppe Ateniese (GMU), Dimitris Papadopoulos (HKUST)

Institutions: University of Sydney, GMU, HKUST

Description:  Verifiable capacity bound function (VCBF) was recently proposed as a space analog of verifiable delay function. In particular, a VCBF imposes a lower bound on the number of bits read from memory during evaluation (referred to as minimum capacity). No adversary, even unbounded, should produce an output without spending this minimum memory capacity. Moreover, a VCBF allows for an efficient public verification process: Given a proof-of-correctness, checking the validity of the output takes significantly fewer memory resources, sublinear in the target minimum capacity. Finally, it achieves soundness, i.e., no computationally bounded adversary can produce a proof that passes verification for a false output. Despite showing potentials for applications due to the strict enforcement of “energy cost” during function evaluation (and analyzed via the tool of Kolmogorov complexity), VCBF is still at its very beginning, several drawbacks remain, here we list two:

(1) Current VCBF construction is secure in a “restricted model” that the adversary reads only constant blocks. This is only a theoretical cornerstone for a construction eventually in the model that allows the adversary to “adaptively” decide which bits to read.

(2) Directly applying VCBF to proofof-space (PoS), by replacing the hash might not work, as VCBF in its current form does not support proportional capacity growth during parallel evaluations

Status: end date Oct 2022