Abstract
Proof-of-sequential-work (PoSW) is a protocol which ensures that a prover must spend a specified number of sequential steps to evaluate a proof against some given statement, but can be efficiently verified. A crucial criterion for PoSW, known as soundness, is that a prover even with reasonable parallelism should not be able to compute the proof in steps much less than the specified amount. In particular, if a malicious prover skips \(\alpha \) (known as soundness gap) fraction of computations to produce a proof, then the verifier should accept this proof with the probability \(\le (1-\alpha )^t\) using t number of random challenges. While all the existing PoSWs [1, 4, 5] achieve soundness of \((1-\alpha )^t\), our proposed scheme gives a quadratic improvement of \((1-\alpha )^{2t}\). Our construction is based on linear hybrid cellular automata (LHCA), a widely used primitive in symmetric-key cryptography. Additionally, we show that our scheme is proven to be secure in the random oracle model.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abusalah, H., Kamath, C., Klein, K., Pietrzak, K., Walter, M.: Reversible proofs of sequential work. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology—EUROCRYPT 2019—38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, 19–23 May 2019, Proceedings, Part II. Lecture Notes in Computer Science, vol. 11477, pp. 277–291. Springer (2019). https://doi.org/10.1007/978-3-030-17656-3_10
Cattell, K., Muzio, J.: Synthesis of one-dimensional linear hybrid cellular automata. IEEE Trans. CAD Integr. Circuits Syst. 15, 325–335 (1996). https://doi.org/10.1109/43.489103
Chaudhuri, P.P., Chowdhury, D.R., Nandi, S., Chattopadhyay, S.: Additive Cellular Automata: Theory and Applications, vol. 1. Wiley (1997)
Cohen, B., Pietrzak, K.: Simple proofs of sequential work. In: Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology—EUROCRYPT 2018—37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 29 Apr.–3 May 2018 Proceedings, Part II. Lecture Notes in Computer Science, vol. 10821, pp. 451–467. Springer (2018). https://doi.org/10.1007/978-3-319-78375-8_15
Mahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable proofs of sequential work. In: Kleinberg, R.D. (ed.) Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, 9–12 Jan. 2013, pp. 373–388. ACM (2013). https://doi.org/10.1145/2422436.2422479
Menezes, A., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press (1996). https://doi.org/10.1201/9781439821916
Sur, S., Das, A., Chowdhury, D.R.: Carrency: an energy-efficient proof-of-work scheme for crypto-currencies. In: Proceedings of the Seventh International Conference on Mathematics and Computing—ICMC 2021, Shibpur, India, pp. 23–38 (2021). https://doi.org/10.1007/978-981-16-6890-6_3
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Sur, S., Roychowdhury, D. (2022). Quadratically Sound Proof-of-Sequential-Work. In: Rushi Kumar, B., Ponnusamy, S., Giri, D., Thuraisingham, B., Clifton, C.W., Carminati, B. (eds) Mathematics and Computing. ICMC 2022. Springer Proceedings in Mathematics & Statistics, vol 415. Springer, Singapore. https://doi.org/10.1007/978-981-19-9307-7_11
Download citation
DOI: https://doi.org/10.1007/978-981-19-9307-7_11
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-9306-0
Online ISBN: 978-981-19-9307-7
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)