Cryptanalysis of Morillo–Obrador polynomial delegation schemes

Cryptanalysis of Morillo–Obrador polynomial delegation schemes

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.


    1. 1)
      • 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. 465482.
    2. 2)
      • 2. Babai, L.: ‘Trading group theory for randomness’. The Annual ACM Symp. on Theory of Computing, New York, NY, USA, 1985, pp. 421429.
    3. 3)
      • 3. Goldwasser, S., Micali, S., Rackoff, C.: ‘The knowledge complexity of interactive proof-systems’, SIAM J. Comput., 1989, 18, (1), pp. 186208.
    4. 4)
      • 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. 723732.
    5. 5)
      • 5. Kilian, J.: ‘Improved efficient arguments’. Advances in Cryptology-CRYPTO 1995, London, UK, pp. 311324.
    6. 6)
      • 6. Micali, S.: ‘CS proofs’. Foundations of Computer Science, 1994, pp. 436453.
    7. 7)
      • 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. 113122.
    8. 8)
      • 8. Applebaum, B., Ishai, Y., Kushilevitz, E.: ‘From secrecy to soundness: efficient verification via secure computation’. Automata, languages and Programming, 2010, pp. 152163.
    9. 9)
      • 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. 296312.
    10. 10)
      • 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. 151168.
    11. 11)
      • 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. 111131.
    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. 680699.
    13. 13)
      • 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. 501512.
    14. 14)
      • 14. Papamanthou, C., Shi, E., Tamassia, R.: ‘Signatures of correct computation’. 10th Theory of Cryptography Conf., Tokyo, Japan, March 2013, pp. 222242.
    15. 15)
      • 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. 90108.
    16. 16)
      • 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. 781796.
    17. 17)
      • 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. 341357.
    18. 18)
      • 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. 90112.
    19. 19)
      • 19. Parno, B., Howell, J., Gentry, C., et al: ‘Pinocchio: nearly practical verifiable computation’. Security and Privacy, Berkeley, CA, USA, May 2013, pp. 238252.
    20. 20)
      • 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. 7184.
    21. 21)
      • 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.
    22. 22)
      • 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. 253268.
    23. 23)
      • 23. Thaler, J.: ‘Time-optimal interactive proofs for circuit evaluation’. Advances in Cryptology (CRYPTO 2013), Santa Barbara, CA, USA, August 2013, pp. 7189.
    24. 24)
      • 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. 2228.
    25. 25)
      • 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. 223237.
    26. 26)
      • 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.
    27. 27)
      • 27. Morillo, P., Obrador, M.: ‘Efficient polynomial delegation under standard assumptions’. Privacy, Security and Trust, Tarragona, Spain, September 2013, pp. 301308.
    28. 28)
      • 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. 155165.

Related content

This is a required field
Please enter a valid email address