
-
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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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). Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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). Google Scholar |
[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] |
Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139 |
[2] |
Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048 |
[3] |
Timothy Chumley, Renato Feres. Entropy production in random billiards. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1319-1346. doi: 10.3934/dcds.2020319 |
[4] |
Linhao Xu, Marya Claire Zdechlik, Melissa C. Smith, Min B. Rayamajhi, Don L. DeAngelis, Bo Zhang. Simulation of post-hurricane impact on invasive species with biological control management. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 4059-4071. doi: 10.3934/dcds.2020038 |
[5] |
Bing Sun, Liangyun Chen, Yan Cao. On the universal $ \alpha $-central extensions of the semi-direct product of Hom-preLie algebras. Electronic Research Archive, , () : -. doi: 10.3934/era.2021004 |
[6] |
Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020451 |
[7] |
Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020295 |
[8] |
Xiuli Xu, Xueke Pu. Optimal convergence rates of the magnetohydrodynamic model for quantum plasmas with potential force. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 987-1010. doi: 10.3934/dcdsb.2020150 |
[9] |
Patrick W. Dondl, Martin Jesenko. Threshold phenomenon for homogenized fronts in random elastic media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 353-372. doi: 10.3934/dcdss.2020329 |
[10] |
Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020440 |
[11] |
José Luis López. A quantum approach to Keller-Segel dynamics via a dissipative nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020376 |
[12] |
Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121 |
[13] |
Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020390 |
[14] |
Bixiang Wang. Mean-square random invariant manifolds for stochastic differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1449-1468. doi: 10.3934/dcds.2020324 |
[15] |
Josselin Garnier, Knut Sølna. Enhanced Backscattering of a partially coherent field from an anisotropic random lossy medium. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1171-1195. doi: 10.3934/dcdsb.2020158 |
[16] |
Shuyang Dai, Fengru Wang, Jerry Zhijian Yang, Cheng Yuan. A comparative study of atomistic-based stress evaluation. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020322 |
[17] |
Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019 |
[18] |
Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 |
[19] |
Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080 |
[20] |
Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020168 |
2019 Impact Factor: 0.734
Tools
Article outline
Figures and Tables
[Back to Top]