The entire argument is based on the definition of an “Incoherent cryptosystem”, which is too restrictive to be useful for cases that you want eg. Tor is also developed and distributed by Tor people and it is supposed to protect you against everyone, including the Tor people.
FHE is simply the wrong tool here. FHE is for a central server operating on data held/known by another. They want MPC -multiple parties jointly computing on distributed data- and that’s fairly more efficient.
Gauss 2.0; He’s very prolific, very famous in the math community. In this context, he is noteworthy because he’s taking automated theorem proving seriously which destigmatizes it for other pure mathematicians.
Not sure simplicity of spec translates into simplicity of user code. This change is backward compatible and will allow things that previously were disallowed.
People [sadly] put a lot of "exotic" cryptography/distributed systems under the term "blockchain" eg. If you want to do byzantine agreement with sub quadratic message complexity, where do you look it up? If you want to do high throughput threshold signing, where do you look it up?
An allergic reaction to the term "blockchain" is to miss the forrest for the trees... and I would imagine the authors share the same point of view.
It’s all just bytes and hashes and alike at the bottom. Absolutely nothing magical. It is the abstractions over them that makes them esoteric, not the fundamental building blocks.
As to why your example isn’t zero-knowledge proof of knowledge of a password, it’s because hash of the same password is always the same thing. So what if someone copies the hashed password and passes it as their own? You say, sign something? But I can reuse the signature. You say, sign a random challenge? Okay, but what if, on the other side, the verifier (ie. the app) adaptively picks a challenge instead of randomly sampling it? … Continue this line of thought, and once you have the correct solution, simplify it and remove the unnecessary parts (eg. Signing something is too strong of a requirement) and you get something called Zero-Knowledge proof of knowledge out of an honest-verifier sigma protocol.
As for ZK proofs that are not proofs of knowledge, then the easiest way to think of it is an encrypted data structure like a database. Imagine the client wants to check whether an element is in some set on a server, where the server has an “encrypted” form of a set and can’t see what’s in it. How can the server check membership of an element and convince the client? That’s done with a ZK proof. You say what about Fully Homomorphic encryption? That’s also technically ZK… what’s not a ZK? For anything that you can’t write a simulator. What’s a simulator? Pick a cryptography textbook.
> zk signature schemes exist and are implied by the existence of one way functions and publicly verifiable nizk.
Almost. The result is from CRYPTO89 paper of Bellare and Goldwasser. They derive a signature scheme from a nizk. It is not known whether you can get a nizk from a signature scheme. Moreover, no signature scheme can be a ZK: https://crypto.stackexchange.com/questions/35177/is-using-di...
Sybil attacks [1] came out about a decade before the Red Balloons paper [2] or the DARPA Challenge itself [3]. It is proven in [1] that CA is necessary for a Sybil-proof system, which made people to talk about Sybil resistance eg [4] - all before Bitcoin or the DARPA challenge.
Unless I’m categorically missing something, Claims like network centralization is much less likely in a Sybil-proof system, is just plain wrong and confusing, to say the least, if discussed “formally” and “mathematically”.
EdDSA signatures are not Schnorr signatures. A Schnorr signature is dlog proof made non interactive with fiat Shamir binded with the message, and that is equivalent/verifiable as an EdDSA signature, up to one time signing per message (as Schnorr is not deterministic)
EdDSA being deterministic, means it’s not Schnorr by definition.
The other difference of EdDSA is having a different keygen process: SHA512 then clamp the first 32 bytes (and this process breaks down all additive key derivation that’s nice to have) clamping is not the problem and you have to clear cofactors for Schnorr over that curve anyway, but it’s the hashing at the beginning that’s different and has nothing to do with cofactor clearing.
The other difference of EdDSA is not having a standardized verifier (keywords are “cofactored” and “cofactorless” verifier) and this breaks down another nice property of Schnorr signatures which is signature aggregation.
Overall the standards for EdDSA -unfortunately- still leave a lot to be desired.
I was a long time keepass user but moved to Bitwarden. My problem with keepass is the low quality and often poorly supported closed source clients that you get on mobile.
Thanks! I’ll definitely take a look. These works are valuable but my problem is just with that particular claim about CAs.
1. This impossibility theorem is proved in a really broad setting (assuming a “broadcast communication cloud” and a P2P channel). If he wants to circumvent the impossibility theorem he should clearly specify the system model and say how it differs from Doceur’s. There are other instances where by playing with the model you go around an impossibility theorem, but you have to specify the differences. Especially since this theorem is so well known/cited.
2. Some claims in the old paper are just plain wrong. Like, you can’t say it’s Sybil resistant just because it tolerates arbitrary number of Byzantine nodes. Dolev-Strong also needs just one honest party, but it requires a CA.
I’m not saying his paper is wrong or not up to the workshop quality. But he’s saying something against an easy-to-prove impossibility theorem in a seriously sloppy/hand-wavy way. I trust Doceur and the entire early 2000s literature more than his paper. But who knows, I might be wrong.
The only way to provably prevent Sybil attacks are CAs (https://www.freehaven.net/anonbib/cache/sybil.pdf)
This is why almost all P2P and DHT papers assumed existence of a CA in their system model eg. Castro’s secure routing etc.
P.S. PoS protocols are also Sybil resistance mechanisms. Look into Tendermint and compare it with, say, PBFT.
The paper is simple and readable enough for me to not have to comment. Anyway, The abstract itself says:
> This paper shows that, without a logically centralized authority, Sybil attacks are always possible except under extreme and unrealistic assumptions of resource parity and coordination among entities.
And the proof is a few pages later in a few Lemmas.
Note that this paper is where Sybil attacks actually come from, and you can see almost all DHT security papers (eg. Castro’s secure routing paper [1]) assume a CA.