Quantum Resistant Error Correcting Code Based Blind Signatures Can Enhance Voter Privacy On Steemit
The state of the art of blind signature schemes
In my research, so far I've found that most blind signature schemes are not quantum resistant. This means a quantum computer can crack the scheme using an advanced algorithm to invalidate the security premises the blind signatures are based on. This is similar to how Shor's algorithm can run on a quantum computer or other forms of cryptography can be broken on a quantum computer.
In my previous post I offered an idea for a privacy preserving reputation system to be built on top of Steemit. This system I described here, utilizes a blind signature technique from Okamoto which is very much like a mechanism to allow anonymous voting. This is basically a mechanism which would decouple the reviews from the reviewers in an e-commerce use case and this is necessary for e-commerce but also have benefits for other possible features.
The problem? Quantum resistant blind signatures may not work using the Okamoto scheme.
Enter the State of the Art Error Correcting Code based Blind signature scheme
The security of this coding scheme is equivalent to the security of Niederreiter PKC. What is Niederreiter PKC? Niederreiter PKC is a public key encryption scheme based on error correcting codes. It's an alternative to the RSA or typical public key cryptography schemes we see.
The blind signature scheme is based on Niederreiter PKC,
so the security of the proposed signature scheme is up to
the security of Niederreiter PKC
What you can take away from this security analysis in the research papers is that Niederreiter PKC is resistant to quantum crypt-analysis attacks. In fact, by all currently known methods it is unbreakable. So for Steemit, this particular alternative crypto scheme may be of great value for enhancing privacy without the long term risk of a well financed quantum super computer trying to attack it.
Conclusion
Any sort of voting, reviewing, or rating scheme on Steemit ultimately will have to rely on a blind signature scheme. If a blind signature scheme must be chosen then the state of the art is going to provide quantum resistance. This post is to reveal the research on the state of the art and show that a quantum resistant blind signature scheme is possible.
References
Repka, M. (2014). McEliece PKC calculator. Journal of Electrical Engineering, 65(6), 342-348.
Ye, J., Ren, F., Zheng, D., & Chen, K. (2015). an Efficient Blind Signature Scheme based on Error Correcting Codes.
I just reviewed many of dana-edwards' articles:
The best of @dana-edwards: Summary and Analysis of Swarm AI
Great post, a lot to think about; thank you for sharing.
Indeed, using Blind Signatures using quantum technology offer us a very high security level. However, nothing is safe for eternity. As soon as the first quantum computers are available, quantum encryption will be breakable
Did you read and understand the paper? Quantum resistant crypto schemes using error correcting codes cannot ever be broken by any kind of quantum computer.
@dana-edwards All due respect, but that's false.
When we say quantum resistant, we mean that it uses methods which are not susceptible to Shor's algorithm. However there are encryption methods which are not susceptible to Shors algorithm but can still be broken without a brute force search even now. For example any form of lattice based encryption. Also Shor's is probably not the only attack vector that quantum computing will bring us.
Also we don't quite yet know what is meant by "any" in the context of a quantum computer because at the moment all known quantum computers are extremely "special purpose". The field is too young to be making any sort of claims on yet.
My personal preference for quantum resistance is NTRU, but like all known Quantum Algos it leaks a little bit of the private key with each signature and so you have to change keys frequently. It may be that this is some fundamental thing with nature. Or it may be we just don't yet have the math to do encryption that deals in realms of physics we barely have any understanding in at all.
You should make a post on this and edify us on the benefits of NTRU.
@dana-edwards First off allow me to apologize, the comment you were responding to was hidden on my tiny little phone screen. So all I saw was you saying Did you read and understand the paper? Quantum resistant crypto schemes using error correcting codes cannot ever be broken by any kind of quantum computer.
I didn't realize until I logged in at home you were replying to someone.
So please forgive me, I responded because it looked like you were just coming out of the blue and saying that, which seemed totally out of character.
As for NTRU I know enough about it to know that there is a fairly high risk key leakage issue on signing operations and also that things encrypted with NTRU don't always decrypt.
The best way not to leak keys is to change them every hundred or so operations (current best attack is 1,000 signing operations, so 10% of that should give a good margin for safety). But it doesn't look like there is any way to ensure that what is encrypted with this method always decrypts properly.
Once I read that, I sort of stopped following it for a bit. I'm a bit of a standards monkey. Right now there is no NIST or other standard quantum crypto scheme.
Frankly we are in a pretty scary place, in that there are lots of ways to break existing crypto schemes and not much in the pipeline that could replace it yet.
Glad to see this paper, I'm going to read it thoroughly tonite and give you my thoughts in the morning.
@dana-edwards Have you read about the encryption method called "A new hope"? Looks like google is testing it in chrome right now.
I read it and might not understand it fully. Am sorry for that. It's just people find always a way. There nothing more I wish than to be fully secure
Theoretically secure would be 100% true. Practical implementation on the other hand is much more difficult. So I would never say any encryption is 100% secure in practice even if it's unbreakable theoretically.
Great. Thanks for the post
👍nice post @dana-edwards
Very interesting! Thank you for sharing. Happy Steeming.
What's the drawback in terms of "bloat" - if there is any?
Cost benefit analysis, is the feature it can provide in terms of enhanced privacy worth the code complexity? I would say yes but someone else might say no. Considering private voting typically relies on blind signature schemes, and a lot of people will ask to have the ability to obfuscate their votes for political or commercial reasons, I can understand that at least in my opinion the benefit outweighs the cost.
For e-commerce I would say it's a critical feature. People wont want to rate a service if they think it could negatively effect their reputation or somehow cost them votes from whales.
I'm asking because in blockchain use, the extra bloat might be critical in terms of scaling.
I had asked on bitcointalk about QC-resistant algorithms for Bitcoin and the signatures (lamport, not a Niederreiter PKC scheme) where several kbytes which would make the network process a small fraction of its current transactions (which are currently 250-300 bytes on average). In other words it would hurt scaling so much that it could render Bitcoin useless.
@alexgr Most lattice based schemes are faster and lighter weight than what we use now.
https://en.wikipedia.org/wiki/NTRU#Performance
This is very promising, hmmm... hopefully patents don't limit its use in cryptocurrencies....
@alexgr The patents are a non-issue, they seem to be defensive only. They have released a GPL reference implementation and it's also part of bouncy castle crypto libs.
From my current knowledge of Graphene which I admit is limited, this particular chunk of code wouldn't have an effect on scaling. Graphene is easily able to scale from what I've seen and this part of the code would be on a layer above all that and could be just a smart contract or I forget what they call their plugin method but I do know they have some sort of operation for extending Steemit.
As far as size of transactions, I am not entirely sure on that and there would have to be some tests before I can tell you anything. The data would have to show if it will work but from the literature it's very efficient. We can't compare the architecture of Graphene to Bitcoin at all as they aren't the same species.
Because I'm not an official Graphene developer I am not intimate with the code base. I cannot tell you with certainty how best to do it. But I am familiar enough with the design (LMAX) and Bitshares, to believe that you can easily scale, but again the gold standard is to try it out on test net and analyze the results.
I'm quite unfamiliar with graphene too...so I don't know the specifics. In any case, Williams answer above indicate it's quite promising in terms of performance. Size remains a bit of a mystery, but we'll see when the time comes I guess...
Even though not knowing anything about the deep world of cryptography I can appreciate your valuable updates ;-)
I don't see how this can help voter privacy, though. Votes are stake-weighted, and I'm not aware of any way of hiding who voted how in a stake-weighted voting system -- if you don't know who cast the vote, you don't know how much weight it has in the count.
@modprobe Here is how you protect voter privacy...
Voters vote into a witness they trust. The witness keeps a tally.
When voting ends the witness reports a summary of results.
The voter knows which witness they used, and can ask the witness which portion of the total that their vote comprised.
The witness still knows how they voted, though. And the witness could lie about the results.
This wouldn't be for stake weighted votes. This would be for votes to review or rate products and services. For example you buy a product from someone on Steemit and you want to rate your experience, but this can't be stake weighted because you're rating an experience as a unique customer. You want to be able to report your experience without anyone being able to link you back to your review. But you want the blockchain to admit it's a verified user experience.
For e-commerce, blind signatures may be necessary. You can't rate products without voting, and if votes are linked to customers then no one can honestly rate any product or service. As a shopper, I cannot know what to buy if I can't get any ratings or reviews on the quality.
Ahh, OK, I assumed you meant chain-managed votes, like upvotes or witness elections.
You might be able to do chian-managed votes but it would have to be a different operation from stake-weighted voting. Blind voting for example using blind signatures, and other schemes, can be done on chain, can use witnesses, and witnesses wouldn't be able to link the votes to any particular person because of blind signatures.