access icon free Adaptive proofs of knowledge in the random oracle model

© The Institution of Engineering and Technology
Received 09/11/2015, Accepted 31/08/2016, Revised 31/08/2016, Published 31/08/2016

The authors define a notion of adaptive proofs of knowledge (PoKs) in the random oracle model (ROM). These are proofs where the malicious prover can adaptively issue multiple statements and proofs, and where the extractor is supposed to extract a witness for each statement. They begin by studying the traditional notion of zero-knowledge PoKs in the ROM and then show how to extend it to the case of adaptive adversaries and to simulation soundness, where the adversary can also learn simulated proofs. The authors’ first main result is negative. Under common assumptions, they can show that the well-known Fiat–Shamir–Schnorr proof system is not adaptively secure. As for the second result, they prove that an existing construction due to Fischlin (Crypto 2005) yields adaptively secure simulation-sound PoKs in the ROM. Since the purpose of this work is to motivate and introduce adaptive proofs, they only briefly discuss some applications to other areas, for example that adaptive proofs seem to be exactly what one requires to construct chosen-ciphertext attack-secure public-key encryption from indistinguishability under chosen plaintext attack secure schemes.

Inspec keywords: public key cryptography

Other keywords: malicious prover; adaptively secure simulation-sound PoK; zero-knowledge PoK; random oracle model; adaptive proof-of-knowledge; chosen-plaintext attack secure schemes; ROM; chosen-ciphertext attack-secure public-key encryption

Subjects: Data security

References

    1. 1)
      • 2. Feige, U., Shamir, A.: ‘Zero-knowledge proofs of identity’, J. Cryptol., 1988, 1, (2), pp. 77–94.
    2. 2)
      • 21. Bernhard, D., Pereira, O., Warinschi, B.: ‘How not to prove yourself: pitfalls of Fiat-Shamir and applications to Helios’. Advances in Cryptology – Asiacrypt'12, 2012 (LNCS, 7658), pp. 626–643.
    3. 3)
      • 16. Chase, M., Lysyanskaya, A.: ‘On defining signatures of knowledge’. Advances in Cryptology (Crypto'06)’, 2006 (LNCS, 4117), pp. 78–96.
    4. 4)
      • 8. Fiat, A., Shamir, A.: ‘How to prove yourself: Practical solutions to identification and signature problems’. Proc. on Advances in Cryptology (CRYPTO'86), 1986, pp. 186–194.
    5. 5)
      • 18. Bellare, M., Rogaway, P.: ‘Random oracles are practical: a paradigm for designing efficient protocols’. ACM Conf. on Computer and Communications Security, 1993, pp. 62–73.
    6. 6)
      • 4. Bellare, M., Goldreich, O.: ‘On defining proofs of knowledge’. Advances in Cryptology (CRYPTO'92), 1992 (LNCS, 740) pp. 390–420.
    7. 7)
      • 12. Sahai, A.: ‘Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security’. Proc. of the 40th Annual Symp. on Foundations of Computer Science (FOCS'99), 1999, pp. 543–553.
    8. 8)
      • 19. Wee, H.: ‘Zero knowledge in the random oracle model, revisited’. ASIACRYPT, 2009 (LNCS, 5912), pp. 417–434.
    9. 9)
      • 1. Goldwasser, S., Micali, S., Rackoff, C.: ‘The knowledge complexity of interactive proof systems’, SIAM J. Comput., 1989, 18, (1), pp. 186–208.
    10. 10)
      • 24. Bellare, M., Rogaway, P.: ‘Code-based game-playing proofs and the security of triple encryption’. Advances in Cryptology (Eurocrypt'06).2006 (LNCS, 4004), pp. 409–426, Full version of 27 November 2008 (Draft 3.0) eprint.iacr.org/2004/331.
    11. 11)
      • 3. Tompa, M., Woll, H.: ‘Random self-reducibility and zero knowledge interactive proofs of possession of information’. FOCS, 1987, pp. 472–482.
    12. 12)
      • 22. Faust, S., Kohlweiss, M., Marson, G., et al: ‘On the non-malleability of the Fiat-Shamir transform’. Indocrypt, 2012 (LNCS).
    13. 13)
      • 11. Bernhard, D., Fischlin, M., Warinschi, B.: ‘On the hardness of proving CCA security of Signed ElGamal’. PKC 2016, 2016 (LNCS, 9614), pp. 47–69, eprint.iacr.org/2015/649.
    14. 14)
      • 17. Dodis, Y., Haralambiev, K., López-Alt, A., et al: Efficient public-key cryptography in the presence of key leakage’, ASIACRYPT, 2010 (LNCS, 6477), pp. 613–631.
    15. 15)
      • 5. Shoup, V., Gennaro, R.: ‘Securing threshold cryptosystems against chosen ciphertext attack’, J. Cryptol., 2002, 15, (2), pp. 75–96.
    16. 16)
      • 14. De Santis, A., Persiano, G.: ‘Zero-knowledge proofs of knowledge without interaction (extended abstract)’. FOCS, 1992, pp. 427–436.
    17. 17)
      • 13. Naor, M., Yung, M.: ‘Public-key cryptosystems provably secure against chosen ciphertext attacks’. Proc. of the Twenty-Second Annual ACM Symp. on Theory of Computing (STOC'90), 1990, pp. 42–437.
    18. 18)
      • 10. Bernhard, D., Fischlin, M., Warinschi, B.: ‘Adaptive proofs of knowledge in the random oracle model’. PKC 2015, 2015 (LNCS, 9020), pp. 629–649.
    19. 19)
      • 6. Bellare, M., Sahai, A.: ‘Non-malleable encryption: equivalence between two notions, and an indistinguishability-based characterization’. Advances in Cryptology (Crypto'99), 1999 (LNCS, 1666) pp. 519–536.
    20. 20)
      • 25. Coretti, S., Dodis, Y., Tackman, B., et al: ‘Non-malleable encryption: simpler, shorter, stronger’. Theory of Cryptography (TCC'16), 2016 (LNCS, 9012), pp. 306–335.
    21. 21)
      • 23. Bagherzandi, A., Cheaon, J.H., Jarecki, S.: ‘Multisignatures secure under the discrete logarithm assumption and a generalized Forking lemma’. CCS'08, 2008, pp. 449–458.
    22. 22)
      • 20. Fouque, P., Pointcheval, D.: ‘Threshold cryptosystems secure against chosen-ciphertext attacks’. Advances in Cryptology (Asiacrypt'01), 2001 (LNCS, 2248), pp. 351–368.
    23. 23)
      • 15. Groth, J.: ‘Simulation-sound NIZK proofs for a practical language and constant size group signatures’. ASIACRYPT, 2006 (LNCS, 4284), pp. 444–459.
    24. 24)
      • 7. Fischlin, M.: ‘Communication-efficient non-interactive proofs of knowledge with online extractors’. Proc. of the 25th Annual Int. Cryptology Conf. on Advances in Cryptology (CRYPTO'05), 2005, pp. 152–168.
    25. 25)
      • 9. Canetti, R., Goldreich, O., Goldwasser, S., et al: ‘Resettable zero-knowledgej’. STOC, 2000, pp. 235–244.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0506
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0506
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading