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.

Während mathematischen Beweise ein wesentliches Konzept in der Mathematik und der gesamten Wissenschaft sind, ist es eine Kunst für sich andere mit einem prägnanten Argument zu überzeugen. Aus Sicht der Kryptographie ist die Minimierung der Kommunikationskosten für Argumentsysteme sowohl von theoretischem als auch praktischem Interesse. In der Tat ist der Beweis der Korrektheit von mathematischen Aussagen häufig eine zentrale Aufgabe in vielen komplexen kryptographischen Protokollen. Diese Dissertation vertieft das Verständnis von kurzen Argumenten, indem neue Konstruktionen und Anwendungen vorgeschlagen werden.

Konstruktionen. Die erste Frage beschäftigt sich damit, wie kurz Argumente konkret werden können. Dazu wird als Grundlage die Konstruktion von kurzen Argumenten von Kilian [STOC'92] herangezogen, welche probabilistisch überprüfbare Beweise (PCP) mit Hilfe eines Vektorcommitments (VC) erzeugen. Dabei dominiert die Größe von λ vielen Elementen zum Aufdecken von VCs die Größe des Beweises. Um den Faktor λ entfernen zu können werden in dieser Arbeit Subvektorcommitments (SVC) definiert und konstruiert -- eine Verallgemeinerung von VC, welche den Beweis von für viele Elemente zum Aufdecken zu den Kosten eines einzigen erlauben. Das Ersetzen der VCs in Kilians Konstruktion mit SVC erlaubt ein Argumentsystem mit öffentlichem Setup, 0.7 KB Beweisgröße und 2^{-80} Soundness Fehler bei den besten Angriffen. Auf Grund der Kostenintensivität traditioneller PCP bei der Berechnung besteht die Motivation Compiler zu entwerfen, welche auch lineare PCPs akzeptieren, bei welchen der Verifizierer Zugriff auf ein Orakel erhält, welches gegebene lineare Funktionen auf dem PCP-String auswertet. Dazu werden Linear Map Commitments (LMC) definiert und konstruiert, welche es dem Beweisenden erlauben, das Bild des festgelegten und versteckten Vektors bezüglich einer beliebigen linearen Abbildung mit einer Beweisgröße, welche unabhängig von der Dimension der linearen Abbildung ist, anzugeben.

Für die Verwendung von allgemeinen Beweissystem wie den oben erwähnten ist es häufig notwendig, die zu beweisenden Aussagen in solche umzuwandeln, welche durch die Systeme unterstützt werden. Diese Konvertierung führt oft zu signifikanten Mehrkosten, weshalb eine Konstruktion von Argumentsystemen mit direkter Unterstützung der zu beweisenden Aussagen wünschenswert ist. Unter anderem von besonderem Interesse sind dabei kryptographische Beziehungen die Elemente aus (bilinearen) Gruppen mit Primzahlordnung erhalten, welche naturgemäß in kryptographischen Protokollen aufbauend auf diesen Gruppen auftreten. Für die Konstruktion solcher Argumentsysteme wird in dieser Arbeit das Bulletproof Protokoll [EUROCRYPT'16, S&P'18] als Grundlage herangezogen, welches über zyklischen Gruppen mit Primzahlordnung q arithmetische Beziehungen in Z_q beweist. Dabei zeigt sich, dass dieselbe Technik, mit welcher Kürze erreicht wird, nicht nur für Z_q sondern für allgemeine Z_q-Module verwendet werden kann. (Bilineare) Gruppen mit Primzahlordnung q als Z_q-Module zu betrachten erlaubt eine Verallgemeinerung des Bulletproof Protokolls um arithmetische Relationen in diesen Gruppen zu beweisen.

Anwendungen. Eine klassische theoretische Anwendung von kurzen Argumenten ist die Konstruktion von homomorphen Signaturen (mit mehreren Schlüsseln) (MHS). Unfälschbarkeitsgarantien von existierenden MHS Schemata sind schwach -- eine einzelne korrupte Partei kann die Signatur eines eingeforderten Outputs einer gemeinsamen Berechnung fälschen, selbst wenn der Output mit den gegebenen Inputs der ehrlichen Parteien unmöglich ist. Deshalb führt diese Arbeit den Begriff der Insider Unfälschbarkeit für (M)HS ein und beweist, dass die Existenz eines insider unfälschbaren MHS' fast äquivalent zu der von kurzen nicht-interaktiven Argumenten ist. Da letzteres nicht durch black-box Reduktionen basierend auf falsifizierbaren Annahmen bewiesen werden kann, ergibt sich ein analoges Unmöglichkeitsresultat für insider unfälschbare (M)HS.

Abschließend wird als praktische Anwendung von kurzen Argumenten eine Konstruktion von Ring Confidential Transactions (RingCT) vorgestellt. Ein üblicher Teil solcher Konstruktionen ist die Darstellung von Transaktionsanweisungen als Relation zwischen kryptographischen Basiskomponenten und der Beweis dieser mit Hilfe von kurzen Argumentsystemen. Die größte Herausforderung für tatsächliche Effizienz liegt dabei in der Auswahl von ohne Anpassungen kompatiblen Argumentsystemen und Basiskomponenten. Dazu wird eine allgemeine Konstruktion von RingCT mit Argumentsystemen und anderen Basiskomponenten sowie deren Instanziierung mit gruppenbasieren Basiswerkzeugen in einer Form angegeben die es erlaubt, die benötigten Relationen mit Hilfe des hier vorgestellten, verallgemeinerten Bullteproof Protokolls zu beweisen. Im Zuge dessen wird eine formale Definition von RingCT angegeben, welche als eigenständiger definitorischer Beitrag zu sehen ist.