DocumentCode
2817522
Title
Efficient recovery of secrets
Author
Fernandez, Marcel ; Soriano, Miguel
Author_Institution
Dept. of Telematics Eng., Univ. Politecnica de Catalunya, Barcelona, Spain
Volume
2
fYear
2004
fDate
5-7 April 2004
Firstpage
763
Abstract
In the guessing secrets game defined by Chung, Graham and Leighton [(2001)], player B has to unveil a set of c > 1 secrets that player A has chosen from a pool of N values. To discover the secrets, player B is allowed to ask a series of boolean questions. For each question asked, A can adversarially choose one of the secrets but once he has made his choice he must answer truthfully. Here we present a solution to the c = 2 guessing secrets game consisting in an error correcting code equipped with a tracing algorithm that, using the Viterbi algorithm as its underlying routine, efficiently recovers the secrets.
Keywords
Boolean functions; Viterbi decoding; block codes; error correction codes; game theory; graph theory; maximum likelihood decoding; trellis codes; Viterbi algorithm; boolean question; error correction code; guessing secrets game; tracing algorithm; Algorithm design and analysis; Block codes; Chromium; Computer errors; Councils; Decoding; Error correction codes; TV; Telematics; Viterbi algorithm;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Technology: Coding and Computing, 2004. Proceedings. ITCC 2004. International Conference on
Print_ISBN
0-7695-2108-8
Type
conf
DOI
10.1109/ITCC.2004.1286749
Filename
1286749
Link To Document