Bilinear Accumulators for Cryptocurrency Enthusiasts
tl;dr: We give on overview of bilinear accumulators, a more communication-efficient alternative to Merkle Hash Trees (MHTs) that comes at an increase in computation.
Put simply, bilinear accumulators are commitments to sets with constant-sized (non)membership proofs.
For more details, see this full post on Decentralized Thoughts.
Multiplying a Toeplitz matrix by a vector
These are some notes on how to efficiently multiply a Toeplitz matrix by a vector.
I was writing these for myself while implementing the new amortized KZG proofs by Feist and Khovratovich, but I thought they might be useful for you too.
Basics of Polynomials for Cryptography
A polynomial $\phi$ of degree $d$ is a vector of $d+1$ coefficients:
\begin{align}
\phi &= [\phi_0, \phi_1, \phi_2, \dots, \phi_d]
\end{align}
For example, $\phi = [1, 10, 9]$ is a degree 2 polynomial.
Also, $\phi’ = [1, 10, 9, 0, 0, 0]$ is also a degree 2 polynomial, since the zero coefficients at the end do not count.
But $\phi’’ = [...
Towards Scalable Verifiable Secret Sharing and Distributed Key Generation
tl;dr: We “authenticate” a polynomial multipoint evaluation using Kate-Zaverucha-Goldberg (KZG) commitments.
This gives a new way to precompute $n$ proofs on a degree $t$ polynomial in $\Theta(n\log{t})$ time, rather than $\Theta(nt)$.
The key trade-off is that our proofs are logarithmic-sized, rather than constant-sized.
Nonetheless, we use ou...
How to do threshold BLS the right way
tl;dr:
Most people implement threshold BLS naively, using a $O(t^2)$ algorithm to compute Lagrange coefficients.
We show how to use a faster $O(t\log^2{t})$-time algorithm for this.
This makes aggregating $(t,n)$ BLS threshold signatures much faster, both at small and large scales.
The question of scaling threshold signatures came to us at VMw...
Range Proofs from Polynomial Commitments, Re-explained
This is a re-exposition of a post by Dan Boneh, Ben Fisch, Ariel Gabizon on how to obtain a constant-sized range proof from constant-sized polynomial commitments.
This post was moved to Decentralized Thoughts.
"Ego is the enemy", by Ryan Holiday
This is Ryan Holiday’s “Ego is the enemy” in bullet-point form.
These are the ideas I found interesting from the book, without the excellent stories used to back them.
For those, you’ll have to buy the book.
I changed some of the excerpts from 2nd person to 1st person, so they resonate more.
I kept the same table of contents as in the book, exc...
How to give (and make) a presentation
These are my notes from a quick workshop at Stony Brook University given by Professor
Michael Bender and Professor Rob Johnson in May 2012.
How to make the presentation
Prefix competitive
If you had one slide, make your presentation.
If you had two slides, extend your 1 slide presentation.
1 slide -> 2 slides -> 3 slides.
Quick...
43 post articles, 6 pages.