Come dimostrare ad un amico che ho una soluzione per risolvere un puzzle (senza rivelarlo)? [chiuso]

Puoi utilizzare una prova a conoscenza zero per dimostrare che hai una soluzione per una classe generale di problemi . (Ad esempio: "Riesco a trovare in modo efficiente la fattorizzazione primaria di qualsiasi numero. Non ti dirò come lo faccio, ma proverò a dimostrare la mia capacità realizzando rapidamente qualsiasi numero che mi passi addosso.") Tuttavia, qui, la soluzione è come hai risolto il problema; è tautologico dire che non puoi mostrare come hai risolto il problema senza rivelare come hai risolto il problema.

Potresti dichiarare segretamente, ma in modo dimostrabile, la tua soluzione tramite impegno crittografico . Ad esempio, pubblichi un hash della tua soluzione e successivamente pubblichi la tua soluzione. Ciò ti consente di dimostrare che avevi la soluzione almeno finchè l'hash è stato pubblico. Tuttavia, diventa solo chiaro che il segreto che hai commesso è una soluzione valida dopo aver reso pubblico il segreto. (Questo approccio permetterà a Paul di confrontare la sua (non) risposta con la tua - semplicemente confrontare gli hash, usando un formato standard - ma non dimostrerà nulla a Ollie.)

Per Ollie, hai bisogno di un modo per dimostrare una soluzione a un problema diverso che si rapporta al problema reale in qualche modo dimostrabile. Ho brevemente considerato una specie di crittografia completamente omomorfica , ma non vedo come potresti dimostrare il problema in modo omomorfico in un modo che 1) non consente al tuo amico di decrittografarlo e 2) consente comunque al tuo amico di verificare il risultato. Ad esempio, considera un tentativo di prova iterativa a conoscenza zero con uno schema omomorfico che può crittografare ( Enc ) con una chiave pubblica e decifrare ( Dec ) con una chiave privata:

1. Mostra il tuo amico Enc(1) , Enc(5) , Enc(6) e Enc(7) in un ordine casuale e mostra separatamente Enc(21) . A questo punto, il tuo amico potrebbe interrompere questi passaggi, richiedere la chiave privata e verificare che non stai mentendo sui valori dei numeri. (Questo ti impedisce di usare valori sbagliati, dato che probabilmente verrai catturato se hai giocato abbastanza volte.)

2. Esegui le operazioni matematiche necessarie sui primi quattro valori codificati per produrre 21. (Questo passaggio mostra le operazioni necessarie, che non sono ottimali, ma non rivela quali valori vanno con le operazioni.) A questo punto non possiamo più fornire la chiave di decrittazione al tuo amico, altrimenti sarà in grado di visualizzare l'intera soluzione.

3. Esegui un test di uguaglianza omomorfica del risultato del passaggio 2 rispetto al Enc(21) del passaggio 1. Questo produce un valore booleano crittografato.

Non c'è modo di permettere al tuo amico di decifrare il valore booleano senza permettergli anche di decifrare ogni altro valore, il che rivelerebbe la tua soluzione interamente. Pertanto, non c'è modo di verificare al tuo amico la correttezza della soluzione.

Esistono solo 7680 espressioni possibili che utilizzano esattamente una volta ciascuno dei quattro valori e operatori binari in un elenco di quattro possibili operatori binari. Un certo numero di queste espressioni sono di fatto duplicate l'una dall'altra, dal momento che due operatori (addizione e moltiplicazione) sono commutativi. Puoi dire a Ollie e a Paul che sono pigri bastardi.

Questo breve numero di candidati invalida la maggior parte degli sforzi crittografici, poiché una prova a conoscenza zero è sempre relativa a un problema fondamentale: una prova ZK è una prova in cui si dimostra di conoscere una soluzione senza fornire al verificatore alcuna informazione < em> che non poteva ottenere da solo . Qui, provare tutte le possibili soluzioni è semplicemente troppo facile, quindi Ollie e Paul possono già ottenere da soli tutte le informazioni che devono essere ottenute.

(Inoltre, secondo i miei calcoli, non c'è una soluzione, quindi la soluzione al puzzle deve essere una sorta di gioco di parole o di scappatoie, che per sua natura sfugge all'analisi matematica.)

Modifica: c'era un bug nel mio programma (dannata conversione silenziosa double in int ; nessun avviso da GCC nemmeno con -W -Wall ). In effetti c'è una soluzione, quella trovata da @Gudradain (ed è unica). Per chi è interessato a queste cose, ecco il mio orribile programma .

Una soluzione alternativa che potrei pensare sarebbe scrivere un sito Web open source. Il sito è configurato per accettare un tipo di formula, ad es. uno che contiene uno o più ()/*+= (in qualsiasi quantità e qualsiasi ordine) e 1 , 5 , 6 e 7 devono verificarsi solo una volta. La formula di input verrà archiviata in un file o database, la formula valutata e il risultato mostrato. Quindi l'amico può vedere che hai una soluzione che risulta in 21.

Quindi c'è il problema di ospitare il sito web. Se lo si ospita, è possibile modificare il codice. Se il tuo amico lo ospita, potrebbe dare un'occhiata alla formula memorizzata. Sarebbe comunque certo che non lo stai prendendo in giro. Non è molto vantaggioso semplicemente dirgli che c'è davvero, è davvero una soluzione, ma ora può essere sicuro al 100%. Solo ora devi fidarti di lui senza dare una sbirciatina alla soluzione.

Non sono sicuro che ci siano soluzioni migliori, questo è il massimo che riesco a trovare.

Penso che questo sia oltre alla domanda, ma per completezza: se vuoi verificare se hai la stessa risposta senza rivelare la risposta l'una all'altra, puoi usare una funzione di hash. Se esegui sha-256 su entrambe le tue risposte, l'hash risultante dovrebbe essere identico. Assicurati di utilizzare lo stesso formato (spaziatura, ordine delle cose, ecc.), Forse puoi dare qualche hash da confrontare.

Puoi condividere l'hash della risposta.

1. memorizza la risposta in un file statico. cat >answer.txt

2. hash questo file sha1sum answer.txt .

3. condividi l'hash risultante con il tuo amico.

Una volta raggiunto il timeout del puzzle, puoi mostrare il tuo file e ri calcolo dell'hash. Devono corrispondere!