Researcher Dimitris Kolonelos, advised by Prof. Dario Fiore, presented yesterday to the committee his thesis defense: “Succinct Cryptographic Commitments with Fine-Grained Openings for Decentralized Environments” at the Computer Science School of the UPM in front of colleagues, family and friends.
Context
Historically, Cryptography has been the art of secure communication. For many centuries, its central purpose was hiding the content of written messages, by producing a cipher code corresponding to the actual content of the message. This way, you could only de-cipher to the message of origin knowing the method. Computers are the ones that converted Cryptography from ‘art’ to ‘science’. Now, Cryptography is all about efficiency, it follows a systematic process in order to achieve convincing results.
With the rise of blockchain technology, advancing in cryptographic techniques that provide efficient solutions is crucial. Bearing in mind that the main characteristic of a blockchain is decentralization, it is necessary that the information be as concise as possible and that verification processes must be fast. From a cryptographic perspective, this translates to a central desideratum: Succinctness. A cryptographic construction is called Succinct if its algorithm is generating outputs that are (exponentially) smaller than the inputs. This allows the cryptosystem to treat large data and produce concise outputs that, nevertheless, preserve the desired functionality of the system.
The thesis
The thesis focuses on the critical aspect of Succinct cryptographic primitives, with particular emphasis on Succinct Commitments, Vector Commitments, and Functional Commitments.
The thesis explores the concept of Succinct Commitments, cryptographic constructs that play a pivotal role in secure communication within Blockchain networks. By developing succinct zero-knowledge proofs for set (non-)membership, the research introduces efficient methods for proving statements without revealing unnecessary information. This includes protocols for membership and non-membership of single elements, as well as succinct zero-knowledge proofs for multiple elements in set commitments like RSA accumulators.
The study delves into Vector Commitments, introducing the innovative notion of Incremental Aggregation. This concept allows the aggregation of opening proofs for various positions into a single, concise proof, presenting applications in speeding up proof computation and Verifiable Decentralized Storage. The thesis also presents an efficient construction of Incrementally Aggregatable Vector Commitments from Groups of Unknown Order, showcasing versatility and applicability.
A significant portion of the thesis explores Functional Commitments, particularly for linear functions. This involves committing to a vector and subsequently opening a public function applied to that vector. The research introduces novel succinct protocols, including cardinality protocols for sets committed with RSA accumulators, demonstrating the commitment to constant-sized public parameters and proofs.
In a final result, the thesis proposes a generic method to transform any Vector Commitment into a Key-Value Map Commitment for arbitrary keys. This innovation, based on cryptographic applications of Cuckoo-Hashing, offers a generic solution with possible implications for the data structures that are widely used in major cryptocurrencies such as Ethereum.
The research, outlined in this thesis, not only pushes the boundaries of cryptographic science but also holds great promise for the future development of secure, decentralized systems. As the blockchain landscape evolves, these cryptographic advancements are poised to play a crucial role in ensuring the integrity, security, and efficiency of next-generation blockchain technologies.
