Code-Based Conjunction Obfuscation

ZHANG Zheng; ZHANG Zhuoran; ZHANG Fangguo

doi:10.23919/cje.2020.00.377

Volume 32 Issue 2

Mar. 2023

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2023 > 32(2): 237-247

ZHANG Zheng, ZHANG Zhuoran, ZHANG Fangguo. Code-Based Conjunction Obfuscation[J]. Chinese Journal of Electronics, 2023, 32(2): 237-247. doi: 10.23919/cje.2020.00.377

Citation:

ZHANG Zheng, ZHANG Zhuoran, ZHANG Fangguo. Code-Based Conjunction Obfuscation[J]. Chinese Journal of Electronics, 2023, 32(2): 237-247. doi: 10.23919/cje.2020.00.377

ZHANG Zheng, ZHANG Zhuoran, ZHANG Fangguo. Code-Based Conjunction Obfuscation[J]. Chinese Journal of Electronics, 2023, 32(2): 237-247. doi: 10.23919/cje.2020.00.377

Citation:

ZHANG Zheng, ZHANG Zhuoran, ZHANG Fangguo. Code-Based Conjunction Obfuscation[J]. Chinese Journal of Electronics, 2023, 32(2): 237-247. doi: 10.23919/cje.2020.00.377

PDF( 2824 KB)

Code-Based Conjunction Obfuscation

doi: 10.23919/cje.2020.00.377

ZHANG Zheng^{1, 2
,},
ZHANG Zhuoran^{1, 2
,},
ZHANG Fangguo^{1, 2
,}

1.
School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China
2.
Guangdong Province Key Laboratory of Information Security Technology, Guangzhou 510006, China

Funds: This work was supported by Guangdong Major Project of Basic and Applied Basic Research (2019B030302008) and the National Natural Science Foundation of China (61972429)

More Information

Author Bio:
Zheng ZHANG was born in 1994. She received the Ph.D. degree in computer science and engineering from Sun Yat-sen University, Guangzhou, China. Her research interests include secure obfuscation, garbled circuits, and functional encryption. (Email: zhangzh65@mail2.sysu.edu.cn)

Zhuoran ZHANG was born in 1995. She received the Ph.D. degree in computer science and engineering from Sun Yat-sen University. Her research interests include code-based cryptography. (Email: zhangzhr26@mail2.sysu.edu.cn)

Fangguo ZHANG (corresponding author) was born in 1972. He received the Ph.D. degree from the School of Communication Engineering, Xidian University, Xi’an, China, in 2001. He is currently a Professor at the School of Computer Science and Engineering of Sun Yat-sen University, China. He is the Co-director of Guangdong Key Laboratory of Information Security Technology. His research mainly focuses on cryptography and its applications. Specific interests are elliptic curve cryptography, secure obfuscation, blockchain, anonymity and privacy, etc. (Email: isszhfg@mail.sysu.edu.cn)
Received Date: 2020-11-15
Accepted Date: 2022-07-18

Available Online: 2022-07-26

Publish Date: 2023-03-05

Abstract

Abstract

The pattern-matching problem with wildcards can be formulated as a conjunction where an accepting string is same as the pattern for all non-wildcards. A scheme of conjunction obfuscation is a algorithm that “encrypt” the pattern to prevent some adversary from forging any accepting string. Since 2013, there are abundant works about conjunction obfuscation which discussed with weak/strong functionality preservation and distributed black-box security. These works are based on generic group model, learning with error assumption, learning with noise assumption, etc. Our work proposes the first conjunction obfuscation with strong functionality preservation and distributed black-box security from a standard assumption. Our scheme with some parameter constraints can also resist some related attacks such as the information set decoding attack and the structured error arrack.
- Obfuscation,
- Conjunction,
- Random linear code,
- General decoding problem,
- Virtual black-box security

FullText(HTML)

References(40)

References

[1]	Y. Zhang, D. He, Y. Li, et al., “Efficient obfuscation for encrypted identity-based Signatures in wireless body area networks,” IEEE System Journal, vol.14, no.4, pp.5320–5328, 2020. doi: 10.1109/JSYST.2020.2974892
[2]	M. Zhang, Y. Jiang, H. Shen, et al, “Cloud-based data-sharing scheme using verifiable and CCA-secure re-encryption from indistinguishability obfuscation,” in Information Security and Cryptology – INSCRYPT 2018, Lecture Notes in Computer Science (vol.11449), Springer, Cham, pp.240–259, 2019.
[3]	M. Zhang, Y. Zhang, Y. Jiang, et al., “Obfuscating eves algorithm and its application in fair electronic transactions in public cloud systems,” IEEE System Journal, vol.13, no.2, pp.1478–1486, 2019. doi: 10.1109/JSYST.2019.2900723
[4]	S. Goldwasser, S. D. Gordon, V. Goyal, et al, “Multi-input functional encryption,” in Advances in Cryptology – EUROCRYPT 2014, Lecture Notes in Computer Science (vol.8441), Springer, Berlin, Heidelberg, pp.578–602, 2014.
[5]	D. Boneh and M. Zhandry, “Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation,” Algirithmica, vol.79, pp.1233–1285, 2017. doi: 10.1007/s00453-016-0242-8
[6]	A. Sahai and B. Waters, “How to use indistinguishability obfuscation deniable encryption and more,” in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC’14), New York, NY, USA, pp.475–484, 2014.
[7]	S. Garg, C. Gentry, S. Halevi, et al, “Candidate indistinguishability obfuscation and functional encryption for all circuits,” in Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS’13), Berkeley, CA, USA, pp.40–49, 2013.
[8]	N. Bitansky and V. Vaikuntanathan, “Indistinguishability obfuscation from functional encryption,” in Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15), Berkeley, CA, USA, pp.171–190, 2015.
[9]	P. Ananth and A. Jain, “Indistinguishability obfuscation from compact functional encryption,” in Advances in Cryptology – CRYPTO 2015, Lecture Notes in Computer Science (vol.9215), Springer, Berlin, Heidelberg, pp.308–326, 2015.
[10]	S. Garg, C. Gentry and S. Halevi, “Candidate multilinear maps from ideal lattices,” Advances in Cryptology – EUROCRYPT 2013, Lecture Notes in Computer Science, (vol.7881), Springer, Berlin, Heidelberg, pp.1–17, 2013.
[11]	J. S. Coron, T. Lepoint and M. Tibouchi. “Practical multilinear maps over the integers,” in Advances in Cryptology – CRYPTO 2013, Lecture Notes in Computer Science (vol.8042), Springer, Berlin, Heidelberg, pp.476-493, 2013.
[12]	C. Gentry, S. Gorbunov, and S. Halevi, “Graph-induced multilinear maps from lattices,” in Theory of Cryptography – TCC 2015, Lecture Notes in Computer Science (vol.9015), Springer, Berlin, Heidelberg, pp.498–527, 2015.
[13]	J. S. Coron, C. Gentry, and S. Halevi, “Zeroizing without low-Level zeroes: New MMAP attacks and their limitations,” in Advances in Cryptology – CRYPTO 2015, Lecture Notes in Computer Science (vol.9215), Springer, Berlin, Heidelberg, pp.247–266, 2015.
[14]	E. Miles, A. Sahai, and M. Zhandry, “Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13,” in Advances in Cryptology – CRYPTO 2016, Lecture Notes in Computer Science (vol.9815), Springer, Berlin, Heidelberg, pp.629–658, 2016.
[15]	Y. Chen, V. Vaikuntanathan, and H. Wee, “GGH15 beyond permutation branching programs: Proofs, attacks, and candidates,” in Advances in Cryptology – CRYPTO 2018, Lecture Notes in Computer Science (vol.10992), Springer, Berlin, Heidelberg, pp.577–607, 2018.
[16]	B. Barak, N. Bitansky, R. Canetti, et al., “Obfuscation for evasive functions,” in Theory of Cryptography – TCC 2014, Lecture Notes in Computer Science (vol.8349), Springer, Berlin, Heidelberg , pp.26–51, 2014.
[17]	H. Wee, “On obfuscating point functions,” in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC’05), Baltimore, MD, USA, pp.523–532, 2005.
[18]	C. Brzuska and A. Mittelbach, “Indistinguishability obfuscation versus multi-bit point obfuscation with auxiliary input,” in Advances in Cryptology – ASIACRYPT 2014, Lecture Notes in Computer Science (vol.8874), Springer, Berlin, Heidelberg, pp.142–161, 2014.
[19]	S. Goldwasser and Y. T. Kalai, “On the impossibility of obfuscation with auxiliary input,” in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), Pittsburgh, PA, USA, pp.553–562, 2005.
[20]	R. Canetti and R.R. Dakdouk, “Obfuscating point functions with multibit output,” in Advances in Cryptology – EUROCRYPT 2008, Lecture Notes in Computer Science, (vol.4965), Springer, Berlin, Heidelberg, pp.489–508, 2008
[21]	M. Bellare and I. Stepanovs, “Point-function obfuscation: A framework and generic constructions,” in Theory of Cryptography – TCC 2016, Lecture Notes in Computer Science (vol.9563), Springer, Berlin, Heidelberg, pp.565–594, 2016.
[22]	R. Canetti, G. N. Rothblum, and M. Varia, “Obfuscation of hyperplane membership,” in Theory of Cryptography – TCC 2010, Lecture Notes in Computer Science (vol.5978), Springer, Berlin, Heidelberg, pp.72–89, 2010.
[23]	R. Goyal, V. Koppula, and B. Waters, “Lockable obfuscation,” in Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS’17), Berkeley, CA, USA, pp.612–621, 2017.
[24]	D. Wichs and G. Zirdelis, “Obfuscating compute-and-compare programs under LWE,” in Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS’18), Berkeley, CA, USA, pp.600–611, 2017.
[25]	Z. Brakerski and G.N. Rothblum, “Obfuscating conjunctions,” Advances in Cryptology – CRYPTO 2013, Lecture Notes in Computer Science (vol.8043), Springer, Berlin, Heidelberg, pp.416–434, 2013.
[26]	Z. Brakerski, V. Vaikuntanathan, H. Wee, et al, “Obfuscating conjunctions under entropic ring LWE,” in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016), Cambridge, MA, USA, pp.147–156, 2016.
[27]	A. Bishop, L. Kowalczyk, T. Malkin, et al, “A simple obfuscation scheme for pattern-matching with wildcards,” in Advances in Cryptology–CRYPTO 2018, Lecture Notes in Computer Science (vol.10993), Springer, Berlin, Heidelberg, vol.10993, pp.731–752, 2018.
[28]	J. Bartusek, T. Lepoint, F. Ma, et al, “New techniques for obfuscating conjunctions,” in Advances in Cryptology – EUROCRYPT 2019, Lecture Notes in Computer Science (vol.11478), Springer, Berlin, Heidelberg, pp.636–666, 2019.
[29]	S. D. Galbraith and L. Zobernig, “Obfuscated fuzzy hamming distance and conjunctions from subset product problems,” in Theory of Cryptography – TCC 2019, Lecture Notes in Computer Science (vol.11891), Springer, Berlin, Heidelberg, pp.81–110, 2019.
[30]	R. Niebuhr, “Attacking and defending code-based cryptosystems: towards secure efficient cryptographic applications based on error-correcting codes,” Ph.D Thesis, Technische Universität Darmstadt, Germany, 2012.
[31]	E. R. Berlekamp, R. J. Maceliece, and H. Van Tilborg, “On the inherent intractability of certain coding problems (Corresp.),” IEEE Transactions on Information Theory, vol.24, no.3, pp.384–386, 1978. doi: 10.1109/TIT.1978.1055873
[32]	A. Barg, “Complexity issues in coding theory,” Electronic Colloquium on Computaional Complexity (ECCC), vol.4, no.46, pp.1–115, 1997.
[33]	C. Cooper, “On the distribution of rank of a random matrix over a finite field,” Random Structures and Algorithms, vol.17, no.3-4, pp.197–212, 2000.
[34]	E. Prange, “The use of information sets in decoding cyclic codes,” IRE Transactions on Information Theory, vol.8, no.5, pp.5–9, 1962. doi: 10.1109/TIT.1962.1057777
[35]	C. Peters, “Information-set decoding for linear codes over $\mathbf{F}_q $,” in Post-Quantum Cryptography – PQCrypto 2010, Lecture Notes in Computer Science (vol.6061), Springer, Berlin, Heidelberg, pp.81–94, 2010.
[36]	R. Niebuhr, P. L. Cayrel, S. Bulygin, et al, “On lower bounds for information set decoding over $\mathbf{F}_q $,” in Proceeding of the 2nd International Conference on Symbolic Computation and Cryptography (SCC 2010), Egham, UK, pp.143–157, 2010.
[37]	A. May and I. Ozerov, “On computing nearest neighbors with applications to decoding of binary linear codes,” in Advances in Cryptology – EUROCRYPT 2015, Lecture Notes in Computer Science (vol.9056), Springer, Berlin, Heidelberg, pp.203–228, 2015.
[38]	S. Hirose, “May-ozerov algorithm for nearest-neighbor problem over $\mathbf{F}_q $ and its application to information set decoding,” in Innovative Security Solutions for Information Technology and Communications – SECITC 2016, Lecture Notes in Computer Science (vol.10006), Springer, Cham., pp.115–126
[39]	C. T. Gueye, J. B. Klamti, and S. Hirose, “Generalization of BJMM-ISD using may-ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbf{F}_q $,” in Codes, Cryptology and Information Security – C2SI 2017, Lecture Notes in Computer Science(10194), Springer, Cham., pp.96–109, 2017.
[40]	S. Arora and R. Ge, “New algorithms for learning in presence of errors,” in Automata, Languages and Programming – ICALP 2011, Lecture Notes in Computer Science (vol.6755), Springer, Berlin, Heidelberg, pp.403–415, 2011.