mirror of
https://github.com/lux-apps/papers.git
synced 2026-11-02 11:39:52 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
55 lines
1.7 KiB
TeX
55 lines
1.7 KiB
TeX
\section{Comparison with Alternatives}
|
||
|
||
|
||
\subsection{Proof System Comparison}
|
||
|
||
\begin{table}[H]
|
||
\centering
|
||
\begin{tabular}{@{}lrrrr@{}}
|
||
\toprule
|
||
\textbf{Scheme} & \textbf{Proof Size} & \textbf{Verify Time} & \textbf{Setup} & \textbf{PQ-Secure} \\
|
||
\midrule
|
||
Merkle & $O(\log n)$ & $O(\log n)$ & None & Yes \\
|
||
Verkle (KZG) & $O(1)$ & $O(1)$ & Trusted & No \\
|
||
STARK & $O(\log^2 n)$ & $O(\log^2 n)$ & None & Yes \\
|
||
Bulletproofs & $O(\log n)$ & $O(n)$ & None & No \\
|
||
RSA Accumulator & $O(1)$ & $O(1)$ & Trusted & No \\
|
||
\bottomrule
|
||
\end{tabular}
|
||
\caption{Comparison of cryptographic proof systems}
|
||
\label{tab:proof-comparison}
|
||
\end{table}
|
||
|
||
\subsection{Trade-off Analysis}
|
||
|
||
\subsubsection{STARKs}
|
||
\begin{itemize}
|
||
\item \textbf{Advantages}: No trusted setup, post-quantum secure
|
||
\item \textbf{Disadvantages}: 100× larger proofs (50-200 KB)
|
||
\item \textbf{Use case}: High-security applications tolerating bandwidth overhead
|
||
\end{itemize}
|
||
|
||
\subsubsection{Bulletproofs}
|
||
\begin{itemize}
|
||
\item \textbf{Advantages}: No trusted setup, reasonable proof size
|
||
\item \textbf{Disadvantages}: Linear verification time
|
||
\item \textbf{Use case}: Private transactions with few verifiers
|
||
\end{itemize}
|
||
|
||
\subsubsection{RSA Accumulators}
|
||
\begin{itemize}
|
||
\item \textbf{Advantages}: Simple construction, constant proofs
|
||
\item \textbf{Disadvantages}: RSA assumption, slower operations
|
||
\item \textbf{Use case}: Systems with existing RSA infrastructure
|
||
\end{itemize}
|
||
|
||
\subsection{Hybrid Approaches}
|
||
|
||
Combining multiple schemes for optimal trade-offs:
|
||
\begin{equation}
|
||
\pi_{hybrid} = (\pi_{verkle}, \pi_{stark})
|
||
\end{equation}
|
||
|
||
Provides both efficiency (Verkle) and quantum-resistance fallback (STARK).
|
||
|