2
$\begingroup$

The problem I'm trying to solve: Identifying the cheater in (3,5)-Shamir's secret sharing when we can see only the 3 shares that were given to the system in the secret reconstruction process, and we can inquire the 3 people who inserted the shares into the system(they don't know what the other people inserted). Also, we have no knowledge about the correct secret, but we do know the wrong secret.

Is there a way to identify the cheater(we know there is only one)? cause me and my friends are stuck at this problem for 2 weeks and we don't seem to have a solution(the question claims that it should be possible).

For those who are interested, this is the full question, we are in section (c), and we succeed in all the other sections

For those who are interested, this is the full question, we are in (c)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

If he can inquire any of the colonels, he can asks the secret keys of the two other colonels $S_4, S_5$. Then he reads on the log's the three secret keys written $S_1, S_2, S_3$.

And he will compute $a_i := \texttt{Reconstruct}(S_i, S_4, S_5)$, for each $1\leq i\leq 3$. The $a_i$ which is different of the two others told you that $i$ is guilty.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! I will ask the teacher if the meaning is that he can inquire all of the colonels, cause me and my friends interpreted it as he can inquire only Alice, Bob and Carol $\endgroup$
    – Irad Nuriel
    Jun 18, 2021 at 11:57
  • $\begingroup$ I think, you can prove that only with three or four colonels, the traitor can't be distinguish from another colonel. $\endgroup$
    – Ievgeni
    Jun 18, 2021 at 12:01
  • $\begingroup$ Yes, I think so to, but I better check with the teacher to be sure. $\endgroup$
    – Irad Nuriel
    Jun 18, 2021 at 12:06
1
$\begingroup$

If I could join (c) & (d), or what I think the book writer had in mind(what is the book, and who are the authors by the way?)

-A cryptographic hash function or a public key signature could be used by the machine (stored in it) to verify the correctness of the key share without knowing it.

-Similarly the police investigator can use the same Cryptographic hash/signature if he doesn't have the right to know the military secret

Improve this answer
$\endgroup$
4
  • $\begingroup$ We solved d, by using certificates signed by the system that distributing the shares. The question is from our homework(given us by the teacher in the form of a pdf). Unfortunately, you cannot combine c and d. We asked the teacher and @levgeni’s answer is the correct one, we just misinterpreted the question. $\endgroup$
    – Irad Nuriel
    Jun 18, 2021 at 14:08
  • $\begingroup$ I guess that's what I mean, the signed certificate is a hash of the key part given by the system ( a value that the machine will recompute & compare to the stored). You didn't say what is the text book? $\endgroup$
    – ShAr
    Jun 18, 2021 at 14:12
  • $\begingroup$ & there's nothing unfortunate about it, u said a constrain is imposed (can't call the other 2), then it turned out it is not $\endgroup$
    – ShAr
    Jun 18, 2021 at 14:21
  • $\begingroup$ I haven’t said the name of the textbook because there is no textbook, it is from our homework, which are given to us in a pdf via the website of the class. $\endgroup$
    – Irad Nuriel
    Jun 18, 2021 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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