7
$\begingroup$

I am looking for a references for post-quantum threshold secret sharing schemes.

I am especially interested in knowing whether any one based on one-way compressor functions or cryptographic hashes exist.

The trivial secret sharing systems with $t=1$ and $t=n$ give information-theoretic security.

Here are some other alternatives that I don't know the security of:

  • Shamir's secret sharing - I don't know [Update: gives information-theoretic security]
  • Blakley's scheme - I don't know
  • The Chinese Remainder Theorem - It seems like it is a problem a quantum computer would easily solve.
$\endgroup$
5
  • $\begingroup$ What research have you already done? I personally am not a fan of existance questions though I don't think the site as completely resolved the issue. That said we do expect you to do some of your own research, etc. Tell us what you have found so far and why it doesn't meet your needs, etc. $\endgroup$
    – mikeazo
    Oct 9, 2013 at 13:49
  • 2
    $\begingroup$ If by threshold secret sharing, you mean something like Shamir's secret sharing, you can continue to use it. It's secure against computationally unbounded attackers i.e. it offers information theoretic security. It's essentially a system with less equations than variables, so there are many equally likely solutions. $\endgroup$ Oct 9, 2013 at 13:57
  • $\begingroup$ Hashes/one-way-functions are a completely different issue. As far as we can tell they still exist, you just need to use twice the size. A 512 bit hash will offer 256 bits of security against QCs, far from any realistic attack. $\endgroup$ Oct 9, 2013 at 13:58
  • $\begingroup$ @mikeazo I have updated the question with a few schemes. It would be interesting to know the facts about the other schemes mentioned as well. $\endgroup$
    – user239558
    Oct 10, 2013 at 2:19
  • $\begingroup$ Are you operating under Shannon Entropy/information theory? You can't do that so much with quantum computing $\endgroup$ Apr 2, 2018 at 3:17

2 Answers 2

7
$\begingroup$

I am not quite sure why you are looking for the kind you have mentioned in your question.

But good old Shamir's polynomial secret sharing over finite fields, look here, provides information theoretic secrecy, i.e., even a quantum computer will not help you to break the secrecy.

$\endgroup$
1
  • $\begingroup$ Ah, I didn't see the information theoretic security property in the article. Thanks! $\endgroup$
    – user239558
    Oct 9, 2013 at 14:02
5
$\begingroup$

It would appear that (for example) Shamir's original threshold secret sharing scheme would meet the requirements of 'post-quantum' (that is, remain secure even if that attacker has access to a Quantum computer).

Let us assume that the shares were generated using a truly random stream; in that case, someone with $N-1$ shares (where $N$ is the threshold) does not have enough information to derive any information about the secret, even if we assumed that the attacker had unbounded computational resources.

Giving him a Quantum computer does not change this; hence Shamir's scheme already meets your criteria.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.