
-
Previous Article
The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes
- AMC Home
- This Issue
-
Next Article
Complete weight enumerators of a class of linear codes over finite fields
A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions
Instituto Superior Técnico - University of Lisbon, SQIG - IT, Lisbon, Portugal |
In this work, we propose a post-quantum UC-commitment scheme in the Global Random Oracle Model, where only one non-programmable random oracle is available. The security of our proposal is based on two well-established post-quantum hardness assumptions from coding theory: The Syndrome Decoding and the Goppa Distinguisher. We prove that our proposal is perfectly hiding and computationally binding.
References:
[1] |
P. S. L. M. Barreto, B. David, R. Dowsley, K. Morozov and A. C. A. Nascimento, A Framework for Efficient Adaptively Secure Composable Oblivious Transfer in the ROM, Cryptology ePrint Archive, Report 2017/993, 2017, https://eprint.iacr.org/2017/993. |
[2] |
A. Becker, A. Joux, A. May and A. Meurer,
Decoding random binary linear codes in $2^{n/20}$: How $1+1 = 0$ improves information set decoding, Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7237 (2012), 520-536.
doi: 10.1007/978-3-642-29011-4_31. |
[3] |
M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, CCS '93 Proceedings of the 1st ACM Conference on Computer and Communications Security, (1993), 62–73.
doi: 10.1145/168588.168596. |
[4] |
E. R. Berlekamp, R. J. McEliece and H. C. A. van Tilborg,
On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory, 24 (1978), 384-386.
doi: 10.1109/tit.1978.1055873. |
[5] |
P. Branco, J. T. Ding, M. Goulão and P. Mateus, Universally Composable Oblivious Transfer Protocol Based on the RLWE Assumption, Cryptology ePrint Archive, Report 2018/1155, 2018, https://eprint.iacr.org/2018/1155. |
[6] |
Megha Byali, Arpita Patra, Divya Ravi and Pratik Sarkar., Fast and Universally-Composable Oblivious Transfer and Commitment Scheme with Adaptive Security, Cryptology ePrint Archive, Report 2017/1165, 2017, https://eprint.iacr.org/2017/1165. |
[7] |
J. Camenisch, M. Drijvers, T. Gagliardoni, A. Lehmann and G. Neven,
The wonderful world of global random oracles, Advances in cryptology—EUROCRYPT 2018. Part I, Lecture Notes in Comput. Sci., Springer, Cham, 10820 (2018), 280-312.
|
[8] |
R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, (2001), 136–145. |
[9] |
R. Canetti and M. Fischlin, Universally composable commitments, Advances in Cryptology—CRYPTO 2001, Berlin, Heidelberg, Springer Berlin Heidelberg, (2001), 19–40.
doi: 10.1007/3-540-44647-8_2. |
[10] |
R. Canetti, A. Jain and A. Scafuro, Practical UC security with a global random oracle, Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS '14, New York, NY, USA, ACM, (2014), 597–608.
doi: 10.1145/2660267.2660374. |
[11] |
R. Canetti, Y. Lindell, R. Ostrovsky and A. Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, (2002), 494–503.
doi: 10.1145/509907.509980. |
[12] |
I. Cascudo, I. Damgård, B. David, I. Giacomelli, J. B. Nielse and R. Trifiletti,
Additively homomorphic uc commitments with optimal amortized overhead, Public-Key Cryptography—PKC 2015, Berlin, Heidelberg, Springer Berlin Heidelberg, 9020 (2015), 495-515.
doi: 10.1007/978-3-662-46447-2_22. |
[13] |
I. Cascudo, I. Damgård, B. David, N. Döttling and J. B.Nielsen, Rate-1, linear time and additively homomorphic uc commitments, Advances in Cryptology—CRYPTO 2016, Berlin, Heidelberg, Springer Berlin Heidelberg, (2016), 179–207. |
[14] |
N. T. Courtois, M. Finiasz and N. Sendrier, How to achieve a McEliece-based digital signature scheme, Advances in Cryptology—ASIACRYPT 2001, Berlin, Heidelberg, Springer Berlin Heidelberg, 2248 (2001), 157–174.
doi: 10.1007/3-540-45682-1_10. |
[15] |
I. Damgård and J. B. Nielsen,
Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor, Advances in Cryptology—CRYPTO 2002, Berlin, Heidelberg, Springer Berlin Heidelberg, 2442 (2002), 581-596.
doi: 10.1007/3-540-45708-9_37. |
[16] |
T. Debris-Alazard, N. Sendrier and J.-P. Tillich, Wave: A New Code-Based Signature Scheme, Cryptology ePrint Archive, Report 2018/996, 2018, https://eprint.iacr.org/2018/996. |
[17] |
A. Esser, R. Kübler and A. May,
LPN decoded, Advances in cryptology—CRYPTO 2017. Part II, Lecture Notes in Comput. Sci., Springer, Cham, 10402 (2017), 486-514.
|
[18] |
J.-C. Faugère, V. Gauthier-Umaña, A. Otmani, L. Perret and J. Tillich,
A distinguisher for high rate McEliece cryptosystems, IEEE Trans. Inform. Theory, 59 (2013), 6830-6844.
doi: 10.1109/TIT.2013.2272036. |
[19] |
M. Fischlin, B. Libert and M. Manulis,
Non-interactive and re-usable universally composable string commitments with adaptive security, Advances in Cryptology—ASIACRYPT 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7073 (2011), 468-485.
doi: 10.1007/978-3-642-25385-0_25. |
[20] |
E. Fujisaki,
Improving practical UC-secure commitments based on the DDH assumption, Security and Cryptography for Networks, Lecture Notes in Comput. Sci., Springer, [Cham], 9841 (2016), 257-272.
doi: 10.1007/978-3-319-44618-9_14. |
[21] |
J. A. Garay, Y. Ishai, R. Kumaresan and H. Wee,
On the complexity of UC commitments, Advances in Cryptology—EUROCRYPT 2014, Lecture Notes in Comput. Sci., Springer, Heidelberg, 8441 (2014), 677-694.
doi: 10.1007/978-3-642-55220-5_37. |
[22] |
D. Hofheinz and J. Müller-Quade,
Universally composable commitments using random oracles, Theory of cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 2951 (2004), 58-76.
doi: 10.1007/978-3-540-24638-1_4. |
[23] |
A. Jain, S. Krenn, K. Pietrzak and A. Tentes,
Commitments and efficient zero-knowledge proofs from learning parity with noise, Advances in Cryptology—ASIACRYPT 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7658 (2012), 663-680.
doi: 10.1007/978-3-642-34961-4_40. |
[24] |
J. Kilian, Founding cryptography on oblivious transfer, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, New York, NY, USA, ACM, (1988), 20–31. |
[25] |
E. Kirshanova,
Improved quantum information set decoding, Post-quantum cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 10786 (2018), 507-527.
doi: 10.1002/fld.4317. |
[26] |
Y. Lindell, Highly-efficient universally-composable commitments based on the DDH assumption, Advances in cryptology—EUROCRYPT 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6632 (2011), 446–466.
doi: 10.1007/978-3-642-20465-4_25. |
[27] |
P. Loidreau and N. Sendrier,
Weak keys in the McEliece public-key cryptosystem, IEEE Transactions on Information Theory, 47 (2001), 1207-1211.
doi: 10.1109/18.915687. |
[28] |
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. |
[29] |
R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, JPL DSN Progress Report, 44 (1978). |
[30] |
C. Peikert, V. Vaikuntanathan and B. Waters,
A framework for efficient and composable oblivious transfer, Advances in cryptology—CRYPTO 2008, Lecture Notes in Comput. Sci., Springer, Berlin, 5157 (2008), 554-571.
doi: 10.1007/978-3-540-85174-5_31. |
[31] |
P. W. Shor,
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26 (1997), 1484-1509.
doi: 10.1137/S0097539795293172. |
[32] |
X. Xie, R. Xue and M. Q. Wang,
Zero knowledge proofs from ring-LWE, Cryptology and network security, Lecture Notes in Comput. Sci., Springer, Cham, 8257 (2013), 57-73.
doi: 10.1007/978-3-319-02937-5_4. |
show all references
References:
[1] |
P. S. L. M. Barreto, B. David, R. Dowsley, K. Morozov and A. C. A. Nascimento, A Framework for Efficient Adaptively Secure Composable Oblivious Transfer in the ROM, Cryptology ePrint Archive, Report 2017/993, 2017, https://eprint.iacr.org/2017/993. |
[2] |
A. Becker, A. Joux, A. May and A. Meurer,
Decoding random binary linear codes in $2^{n/20}$: How $1+1 = 0$ improves information set decoding, Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7237 (2012), 520-536.
doi: 10.1007/978-3-642-29011-4_31. |
[3] |
M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, CCS '93 Proceedings of the 1st ACM Conference on Computer and Communications Security, (1993), 62–73.
doi: 10.1145/168588.168596. |
[4] |
E. R. Berlekamp, R. J. McEliece and H. C. A. van Tilborg,
On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory, 24 (1978), 384-386.
doi: 10.1109/tit.1978.1055873. |
[5] |
P. Branco, J. T. Ding, M. Goulão and P. Mateus, Universally Composable Oblivious Transfer Protocol Based on the RLWE Assumption, Cryptology ePrint Archive, Report 2018/1155, 2018, https://eprint.iacr.org/2018/1155. |
[6] |
Megha Byali, Arpita Patra, Divya Ravi and Pratik Sarkar., Fast and Universally-Composable Oblivious Transfer and Commitment Scheme with Adaptive Security, Cryptology ePrint Archive, Report 2017/1165, 2017, https://eprint.iacr.org/2017/1165. |
[7] |
J. Camenisch, M. Drijvers, T. Gagliardoni, A. Lehmann and G. Neven,
The wonderful world of global random oracles, Advances in cryptology—EUROCRYPT 2018. Part I, Lecture Notes in Comput. Sci., Springer, Cham, 10820 (2018), 280-312.
|
[8] |
R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, (2001), 136–145. |
[9] |
R. Canetti and M. Fischlin, Universally composable commitments, Advances in Cryptology—CRYPTO 2001, Berlin, Heidelberg, Springer Berlin Heidelberg, (2001), 19–40.
doi: 10.1007/3-540-44647-8_2. |
[10] |
R. Canetti, A. Jain and A. Scafuro, Practical UC security with a global random oracle, Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS '14, New York, NY, USA, ACM, (2014), 597–608.
doi: 10.1145/2660267.2660374. |
[11] |
R. Canetti, Y. Lindell, R. Ostrovsky and A. Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, (2002), 494–503.
doi: 10.1145/509907.509980. |
[12] |
I. Cascudo, I. Damgård, B. David, I. Giacomelli, J. B. Nielse and R. Trifiletti,
Additively homomorphic uc commitments with optimal amortized overhead, Public-Key Cryptography—PKC 2015, Berlin, Heidelberg, Springer Berlin Heidelberg, 9020 (2015), 495-515.
doi: 10.1007/978-3-662-46447-2_22. |
[13] |
I. Cascudo, I. Damgård, B. David, N. Döttling and J. B.Nielsen, Rate-1, linear time and additively homomorphic uc commitments, Advances in Cryptology—CRYPTO 2016, Berlin, Heidelberg, Springer Berlin Heidelberg, (2016), 179–207. |
[14] |
N. T. Courtois, M. Finiasz and N. Sendrier, How to achieve a McEliece-based digital signature scheme, Advances in Cryptology—ASIACRYPT 2001, Berlin, Heidelberg, Springer Berlin Heidelberg, 2248 (2001), 157–174.
doi: 10.1007/3-540-45682-1_10. |
[15] |
I. Damgård and J. B. Nielsen,
Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor, Advances in Cryptology—CRYPTO 2002, Berlin, Heidelberg, Springer Berlin Heidelberg, 2442 (2002), 581-596.
doi: 10.1007/3-540-45708-9_37. |
[16] |
T. Debris-Alazard, N. Sendrier and J.-P. Tillich, Wave: A New Code-Based Signature Scheme, Cryptology ePrint Archive, Report 2018/996, 2018, https://eprint.iacr.org/2018/996. |
[17] |
A. Esser, R. Kübler and A. May,
LPN decoded, Advances in cryptology—CRYPTO 2017. Part II, Lecture Notes in Comput. Sci., Springer, Cham, 10402 (2017), 486-514.
|
[18] |
J.-C. Faugère, V. Gauthier-Umaña, A. Otmani, L. Perret and J. Tillich,
A distinguisher for high rate McEliece cryptosystems, IEEE Trans. Inform. Theory, 59 (2013), 6830-6844.
doi: 10.1109/TIT.2013.2272036. |
[19] |
M. Fischlin, B. Libert and M. Manulis,
Non-interactive and re-usable universally composable string commitments with adaptive security, Advances in Cryptology—ASIACRYPT 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7073 (2011), 468-485.
doi: 10.1007/978-3-642-25385-0_25. |
[20] |
E. Fujisaki,
Improving practical UC-secure commitments based on the DDH assumption, Security and Cryptography for Networks, Lecture Notes in Comput. Sci., Springer, [Cham], 9841 (2016), 257-272.
doi: 10.1007/978-3-319-44618-9_14. |
[21] |
J. A. Garay, Y. Ishai, R. Kumaresan and H. Wee,
On the complexity of UC commitments, Advances in Cryptology—EUROCRYPT 2014, Lecture Notes in Comput. Sci., Springer, Heidelberg, 8441 (2014), 677-694.
doi: 10.1007/978-3-642-55220-5_37. |
[22] |
D. Hofheinz and J. Müller-Quade,
Universally composable commitments using random oracles, Theory of cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 2951 (2004), 58-76.
doi: 10.1007/978-3-540-24638-1_4. |
[23] |
A. Jain, S. Krenn, K. Pietrzak and A. Tentes,
Commitments and efficient zero-knowledge proofs from learning parity with noise, Advances in Cryptology—ASIACRYPT 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7658 (2012), 663-680.
doi: 10.1007/978-3-642-34961-4_40. |
[24] |
J. Kilian, Founding cryptography on oblivious transfer, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, New York, NY, USA, ACM, (1988), 20–31. |
[25] |
E. Kirshanova,
Improved quantum information set decoding, Post-quantum cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 10786 (2018), 507-527.
doi: 10.1002/fld.4317. |
[26] |
Y. Lindell, Highly-efficient universally-composable commitments based on the DDH assumption, Advances in cryptology—EUROCRYPT 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6632 (2011), 446–466.
doi: 10.1007/978-3-642-20465-4_25. |
[27] |
P. Loidreau and N. Sendrier,
Weak keys in the McEliece public-key cryptosystem, IEEE Transactions on Information Theory, 47 (2001), 1207-1211.
doi: 10.1109/18.915687. |
[28] |
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. |
[29] |
R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, JPL DSN Progress Report, 44 (1978). |
[30] |
C. Peikert, V. Vaikuntanathan and B. Waters,
A framework for efficient and composable oblivious transfer, Advances in cryptology—CRYPTO 2008, Lecture Notes in Comput. Sci., Springer, Berlin, 5157 (2008), 554-571.
doi: 10.1007/978-3-540-85174-5_31. |
[31] |
P. W. Shor,
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26 (1997), 1484-1509.
doi: 10.1137/S0097539795293172. |
[32] |
X. Xie, R. Xue and M. Q. Wang,
Zero knowledge proofs from ring-LWE, Cryptology and network security, Lecture Notes in Comput. Sci., Springer, Cham, 8257 (2013), 57-73.
doi: 10.1007/978-3-319-02937-5_4. |




[1] |
Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012 |
[2] |
Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281 |
[3] |
Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022026 |
[4] |
Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489 |
[5] |
Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013 |
[6] |
Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022031 |
[7] |
Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020132 |
[8] |
Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169 |
[9] |
Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249 |
[10] |
Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281 |
[11] |
Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089 |
[12] |
Yufeng Zhou, Bin Zheng, Jiafu Su, Yufeng Li. The joint location-transportation model based on grey bi-level programming for early post-earthquake relief. Journal of Industrial and Management Optimization, 2022, 18 (1) : 45-73. doi: 10.3934/jimo.2020142 |
[13] |
Brendan Weickert. Infinite-dimensional complex dynamics: A quantum random walk. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 517-524. doi: 10.3934/dcds.2001.7.517 |
[14] |
María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021018 |
[15] |
Xueke Pu, Boling Guo. Global existence and semiclassical limit for quantum hydrodynamic equations with viscosity and heat conduction. Kinetic and Related Models, 2016, 9 (1) : 165-191. doi: 10.3934/krm.2016.9.165 |
[16] |
Seok-Jin Kang and Jae-Hoon Kwon. Quantum affine algebras, combinatorics of Young walls, and global bases. Electronic Research Announcements, 2002, 8: 35-46. |
[17] |
Rod Cross, Hugh McNamara, Leonid Kalachev, Alexei Pokrovskii. Hysteresis and post Walrasian economics. Discrete and Continuous Dynamical Systems - B, 2013, 18 (2) : 377-401. doi: 10.3934/dcdsb.2013.18.377 |
[18] |
Wenjia Jing, Olivier Pinaud. A backscattering model based on corrector theory of homogenization for the random Helmholtz equation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (10) : 5377-5407. doi: 10.3934/dcdsb.2019063 |
[19] |
Kui Lin, Shuai Lu, Peter Mathé. Oracle-type posterior contraction rates in Bayesian inverse problems. Inverse Problems and Imaging, 2015, 9 (3) : 895-915. doi: 10.3934/ipi.2015.9.895 |
[20] |
Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]