Refine
Year of publication
- 2022 (1)
Document Type
- Doctoral Thesis (1)
Language
- English (1)
Has Fulltext
- yes (1)
Institute
While the concept of a mathematical proof is fundamental in mathematics and science, to convince others with a concise argument is an art in itself. From a cryptographic point of view, minimising the communication costs of argument systems is of both theoretical and practical interests. Indeed, proving the validity of mathematical statements is often a central task in many complex cryptographic protocols. Improvements of argument systems therefore have far-reaching consequences. In this dissertation, we further our understanding of succinct arguments by proposing new constructions and applications.
Constructions. Our first question is how short an argument can concretely be. Towards answering, we revisit a classic construction of succinct arguments by Kilian [STOC'92] who compiles a probabilistically checkable proof (PCP) using a vector commitment (VC). In Kilian's scheme, the size of λ many VC openings dominates the proof size. To remove this λ factor, we define and construct subvector commitment (SVC), a generalisation of VC which allows to prove many openings at the cost of one. Replacing the VC in Kilian's construction with an SVC yields an argument system with a public-coin setup, 0.7 KB proof size, and 2^{-80} soundness error under best known attacks. Since traditional PCPs are computationally expensive, we are motivated to design compilers which also accept linear PCPs, where the verifier is given an oracle which evaluates given linear functions on the PCP string. For this we define and construct linear map commitments (LMC) which allow the prover to reveal the image of the committed vector under any given linear map, with proof size independent of the dimensions of the map.
When applying general purpose argument systems such as the above, it is often needed to convert the statements to be proven to those supported by the systems. This conversion process often introduces significant overheads. It is therefore desirable to construct argument systems native for the statements to be proven. Of particular interest are cryptographic relations involving elements of prime-order (bilinear-)groups, which arise naturally in (bilinear-)group-based cryptographic protocols. To build a native argument system for these relations, our starting point is the Bulletproof protocol [EUROCRYPT'16, S&P'18] constructed over a cyclic group of prime order q for proving arithmetic relations over Z_q. We observe that their technique of achieving succinctness can in fact be applied not only to Z_q, but any Z_q-modules in general. By viewing (bilinear-)groups of prime order q as Z_q-modules, we successfully generalise the Bulletproof protocol to prove arithmetic relations over these groups.
Applications. A classic theoretical application of succinct arguments is the construction of (multi-key) homomorphic signatures (MHS). We observe that the unforgeability guarantees of existing MHS schemes are weak -- a single corrupt party could forge a signature of a claimed output of a joint computation, even if the output is impossible given the inputs of the honest parties. We therefore introduce the notion of insider unforgeability for (M)HS and prove that the existence of insider unforgeable (M)HS is almost equivalent to that of succinct non-interactive arguments. Since the latter cannot be proven under falsifiable assumptions with black-box reductions, we obtain an analogous impossibility result for insider unforgeable (M)HS.
We conclude with a practical application of succinct arguments in constructing ring confidential transaction (RingCT) schemes. RingCT constructions typically involve expressing transaction instructions as relations among the cryptographic building blocks, and then proving these relations using succinct argument systems. The main challenge for concrete efficiency lies in finding an argument system and other building blocks which are natively compatible. To this end, we present a generic construction of RingCT from argument systems and other basic tools, and show how to instantiate it with group-based building blocks, such that the relations among them can be natively proven by our generalised Bulletproof protocol. During the process, we also present a formal model of RingCT which we view as an independent definitional contribution.