Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Cryptanalysis of Morillo–Obrador polynomial delegation schemes

  • Author(s): Shuaijianni Xu 1, 2  and  Liang Feng Zhang 2
    • View affiliations
  • Source: Volume 12, Issue 2, March 2018, p. 127 – 132
    DOI:  10.1049/iet-ifs.2017.0259 , Print ISSN 1751-8709, Online ISSN 1751-8717
© The Institution of Engineering and Technology
Received 22/05/2017, Accepted 16/11/2017, Revised 07/11/2017, Published 17/11/2017

Verifiable computation (VC) allows a client to outsource (delegate) the computation of a function f on an input x to a server and then verify the server's results with substantially less time than computing f(x) from scratch. The security of VC requires no efficient adversary can persuade the client to accept any wrong results. Morillo and Obrador (PST 2013) proposed three VC schemes for outsourcing the computation of polynomial functions and claimed that all schemes are secure under the decisional subgroup membership assumption. The authors show a simple attack against the security of their first scheme and then extend the attack to the other two schemes. Morillo and Obrador (PST 2013) also claimed that their third scheme keeps the client's input private under the square root assumption. The authors show that this is not true under the standard definition of input privacy. In particular, a curious server can extract the client's input x, if the x is not too large. The authors’ results show that Morillo–Obrador schemes cannot be used in the polynomial delegation.

Inspec keywords: polynomial approximation; least squares approximations; cryptography; decision theory

Other keywords: cryptanalysis; Morillo-Obrador polynomial delegation schemes; verifiable computation; square root assumption; polynomial functions; decisional subgroup membership assumption; input privacy

Subjects: Interpolation and function approximation (numerical analysis); Interpolation and function approximation (numerical analysis); Game theory; Data security; Cryptography; Game theory

References

    1. 1)
      • 7. Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: ‘Delegating computation: interactive proofs for muggles’. 40th Annual ACM Symp. on Theory of computing, Victoria, British Columbia, Canada, May 2008, pp. 113–122.
    2. 2)
      • 3. Goldwasser, S., Micali, S., Rackoff, C.: ‘The knowledge complexity of interactive proof-systems’, SIAM J. Comput., 1989, 18, (1), pp. 186–208.
    3. 3)
      • 27. Morillo, P., Obrador, M.: ‘Efficient polynomial delegation under standard assumptions’. Privacy, Security and Trust, Tarragona, Spain, September 2013, pp. 301–308.
    4. 4)
      • 13. Fiore, D., Gennaro, R.: ‘Publicly verifiable delegation of large polynomials and matrix computations, with applications’. 19th ACM Conf. on Computer and Communications Security, Raleigh, NC, USA, October 2012, pp. 501–512.
    5. 5)
      • 28. Coppersmith, D.: ‘Finding a small root of a univariate modular equation’. EUROCRYPT'96 Proc. 15th Annual Int. Conf. on Theory and Application of Cryptographic Techniques, Saragossa, Spain, 12–16 May 1996, pp. 155–165.
    6. 6)
      • 22. Setty, S., Vu, V., Panpalia, N., et al: ‘Taking proof-Based verified computation a Few steps closer to practicality’. 21st USENIX Security Symp., Bellevue, WA, USA, August 2012, pp. 253–268.
    7. 7)
      • 14. Papamanthou, C., Shi, E., Tamassia, R.: ‘Signatures of correct computation’. 10th Theory of Cryptography Conf., Tokyo, Japan, March 2013, pp. 222–242.
    8. 8)
      • 21. Setty, S., McPherson, R., Blumberg, A.J., et al: ‘Making argument systems for outsourced computation practical (sometimes)’. 19th Network and Distributed System Security, San Diego, CA, USA, February 2012, p. 17.
    9. 9)
      • 19. Parno, B., Howell, J., Gentry, C., et al: ‘Pinocchio: nearly practical verifiable computation’. Security and Privacy, Berkeley, CA, USA, May 2013, pp. 238–252.
    10. 10)
      • 18. Cormode, G., Mitzenmacher, M., Thaler, J.: ‘Practical verified computation with streaming interactive proofs’. Third Innovations in Theoretical Computer Science Conf., Cambridge, MA, USA, January 2012, pp. 90–112.
    11. 11)
      • 2. Babai, L.: ‘Trading group theory for randomness’. The Annual ACM Symp. on Theory of Computing, New York, NY, USA, 1985, pp. 421–429.
    12. 12)
      • 12. Catalano, D., Fiore, D., Gennaro, R., et al: ‘Algebraic (trapdoor) one way functions and their applications’. 10th Theory of Cryptography Conf., Tokyo, Japan, March 2013, pp. 680–699.
    13. 13)
      • 15. Ben-Sasson, E., Chiesa, A., Genkin, D., et al: ‘SNARKs for C: verifying program executions succinctly and in zero knowledge’. Advances in Cryptology (CRYPTO 2013), Santa Barbara, CA, USA, August 2013, pp. 90–108.
    14. 14)
      • 17. Braun, B., Feldman, A.J., Ren, Z., et al: ‘Verifying computations with state’. 24th ACM Symp. on Operating Systems Principles, Farminton, PA, USA, November 2013, pp. 341–357.
    15. 15)
      • 23. Thaler, J.: ‘Time-optimal interactive proofs for circuit evaluation’. Advances in Cryptology (CRYPTO 2013), Santa Barbara, CA, USA, August 2013, pp. 71–89.
    16. 16)
      • 10. Chung, K.-M., Kalai, Y.T., Liu, F.-H., et al: ‘Memory delegation’. 31st Annual Cryptology Conf., Santa Barbara, CA, USA, August 2011, pp. 151–168.
    17. 17)
      • 25. Vu, V., Setty, S., Blumberg, A.J., et al: ‘A hybrid architecture for interactive verifiable computation’. Security and Privacy, San Francisco, CA, USA, February 2013, pp. 223–237.
    18. 18)
      • 16. Ben-Sasson, E., Chiesa, A., Tromer, E., et al: ‘Succinct non-interactive zero knowledge for a von Neumann architecture’. 23rd USENIX Security Symp., San Diego, CA, USA, August 2014, pp. 781–796.
    19. 19)
      • 26. Wahby, R.S., Setty, S., Ren, Z., et al: ‘Efficient RAM and control flow in verifiable outsourced computation’. 22nd Network and Distributed System Security, San Diego, CA, USA, February 2015.
    20. 20)
      • 4. Kilian, J.: ‘A note on efficient zero-knowledge proofs and arguments’. 24th Annual ACM Symp. on Theory of Computing, Victoria, British Columbia, Canada, May 1992, pp. 723–732.
    21. 21)
      • 5. Kilian, J.: ‘Improved efficient arguments’. Advances in Cryptology-CRYPTO 1995, London, UK, pp. 311–324.
    22. 22)
      • 6. Micali, S.: ‘CS proofs’. Foundations of Computer Science, 1994, pp. 436–453.
    23. 23)
      • 11. Benabbas, S., Gennaro, R., Vahlis, Y.: ‘Verifiable delegation of computation over large datasets’. Advances in Cryptology-CRYPTO 2011, Santa Barbara, CA, USA, August 2011, pp. 111–131.
    24. 24)
      • 1. Gennaro, R., Gentry, C., Parno, B.: ‘Non-interactive verifiable computing: outsourcing computation to untrusted workers’. Advances in Cryptology (CRYPTO 2010), Santa Barbara, CA, USA, August 2010, pp. 465–482.
    25. 25)
      • 20. Setty, S., Braun, B., Vu, V., et al: ‘Resolving the conflict between generality and plausibility in verified computation’. 8th ACM European Conf. on Computer Systems, Prague, Czech Republic, April 2013, pp. 71–84.
    26. 26)
      • 9. Barbosa, M., Farshim, P.: ‘Delegatable homomorphic encryption with applications to secure outsourcing of computation’. The Cryptographers’ Track at the RSA Conf., San Francisco, CA, USA, February 2012, pp. 296–312.
    27. 27)
      • 24. Thaler, J., Roberts, M., Mitzenmacher, M., et al: ‘Verifiable computation with massively parallel interactive proofs’. 4th USENIX Workshop on Hot Topics in Cloud Computing, Boston, MA, USA, June 2012, pp. 22–28.
    28. 28)
      • 8. Applebaum, B., Ishai, Y., Kushilevitz, E.: ‘From secrecy to soundness: efficient verification via secure computation’. Automata, languages and Programming, 2010, pp. 152–163.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2017.0259
Loading

Related content

content/journals/10.1049/iet-ifs.2017.0259
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address