http://iet.metastore.ingenta.com
1887

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
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.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 to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
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.

References

    1. 1)
      • R. Gennaro , C. Gentry , B. Parno .
        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.
        . Advances in Cryptology (CRYPTO 2010) , 465 - 482
    2. 2)
      • L. Babai .
        2. Babai, L.: ‘Trading group theory for randomness’. The Annual ACM Symp. on Theory of Computing, New York, NY, USA, 1985, pp. 421429.
        . The Annual ACM Symp. on Theory of Computing , 421 - 429
    3. 3)
      • S. Goldwasser , S. Micali , C. Rackoff .
        3. Goldwasser, S., Micali, S., Rackoff, C.: ‘The knowledge complexity of interactive proof-systems’, SIAM J. Comput., 1989, 18, (1), pp. 186208.
        . SIAM J. Comput. , 1 , 186 - 208
    4. 4)
      • J. Kilian .
        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.
        . 24th Annual ACM Symp. on Theory of Computing , 723 - 732
    5. 5)
      • J. Kilian .
        5. Kilian, J.: ‘Improved efficient arguments’. Advances in Cryptology-CRYPTO 1995, London, UK, pp. 311324.
        . Advances in Cryptology-CRYPTO 1995 , 311 - 324
    6. 6)
      • S. Micali .
        6. Micali, S.: ‘CS proofs’. Foundations of Computer Science, 1994, pp. 436453.
        . Foundations of Computer Science , 436 - 453
    7. 7)
      • S. Goldwasser , Y.T. Kalai , G.N. Rothblum .
        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.
        . 40th Annual ACM Symp. on Theory of computing , 113 - 122
    8. 8)
      • B. Applebaum , Y. Ishai , E. Kushilevitz .
        8. Applebaum, B., Ishai, Y., Kushilevitz, E.: ‘From secrecy to soundness: efficient verification via secure computation’. Automata, languages and Programming, 2010, pp. 152163.
        . Automata, languages and Programming , 152 - 163
    9. 9)
      • M. Barbosa , P. Farshim .
        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.
        . The Cryptographers’ Track at the RSA Conf. , 296 - 312
    10. 10)
      • K.-M. Chung , Y.T. Kalai , F.-H. Liu .
        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.
        . 31st Annual Cryptology Conf. , 151 - 168
    11. 11)
      • S. Benabbas , R. Gennaro , Y. Vahlis .
        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.
        . Advances in Cryptology-CRYPTO 2011 , 111 - 131
    12. 12)
      • D. Catalano , D. Fiore , R. Gennaro .
        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.
        . 10th Theory of Cryptography Conf. , 680 - 699
    13. 13)
      • D. Fiore , R. Gennaro .
        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.
        . 19th ACM Conf. on Computer and Communications Security , 501 - 512
    14. 14)
      • C. Papamanthou , E. Shi , R. Tamassia .
        14. Papamanthou, C., Shi, E., Tamassia, R.: ‘Signatures of correct computation’. 10th Theory of Cryptography Conf., Tokyo, Japan, March 2013, pp. 222242.
        . 10th Theory of Cryptography Conf. , 222 - 242
    15. 15)
      • E. Ben-Sasson , A. Chiesa , D. Genkin .
        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.
        . Advances in Cryptology (CRYPTO 2013) , 90 - 108
    16. 16)
      • E. Ben-Sasson , A. Chiesa , E. Tromer .
        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.
        . 23rd USENIX Security Symp. , 781 - 796
    17. 17)
      • B. Braun , A.J. Feldman , Z. Ren .
        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.
        . 24th ACM Symp. on Operating Systems Principles , 341 - 357
    18. 18)
      • G. Cormode , M. Mitzenmacher , J. Thaler .
        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.
        . Third Innovations in Theoretical Computer Science Conf. , 90 - 112
    19. 19)
      • B. Parno , J. Howell , C. Gentry .
        19. Parno, B., Howell, J., Gentry, C., et al: ‘Pinocchio: nearly practical verifiable computation’. Security and Privacy, Berkeley, CA, USA, May 2013, pp. 238252.
        . Security and Privacy , 238 - 252
    20. 20)
      • S. Setty , B. Braun , V. Vu .
        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.
        . 8th ACM European Conf. on Computer Systems , 71 - 84
    21. 21)
      • S. Setty , R. McPherson , A.J. Blumberg .
        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.
        . 19th Network and Distributed System Security , 17
    22. 22)
      • S. Setty , V. Vu , N. Panpalia .
        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.
        . 21st USENIX Security Symp. , 253 - 268
    23. 23)
      • J. Thaler .
        23. Thaler, J.: ‘Time-optimal interactive proofs for circuit evaluation’. Advances in Cryptology (CRYPTO 2013), Santa Barbara, CA, USA, August 2013, pp. 7189.
        . Advances in Cryptology (CRYPTO 2013) , 71 - 89
    24. 24)
      • J. Thaler , M. Roberts , M. Mitzenmacher .
        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.
        . 4th USENIX Workshop on Hot Topics in Cloud Computing , 22 - 28
    25. 25)
      • V. Vu , S. Setty , A.J. Blumberg .
        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.
        . Security and Privacy , 223 - 237
    26. 26)
      • R.S. Wahby , S. Setty , Z. Ren .
        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.
        . 22nd Network and Distributed System Security
    27. 27)
      • P. Morillo , M. Obrador .
        27. Morillo, P., Obrador, M.: ‘Efficient polynomial delegation under standard assumptions’. Privacy, Security and Trust, Tarragona, Spain, September 2013, pp. 301308.
        . Privacy, Security and Trust , 301 - 308
    28. 28)
      • D. Coppersmith .
        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.
        . EUROCRYPT'96 Proc. 15th Annual Int. Conf. on Theory and Application of Cryptographic Techniques , 155 - 165
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
This is a required field
Please enter a valid email address