Oblivious DFA evaluation on joint input and its applications. (English) Zbl 1459.68074
Summary: Oblivious deterministic finite automata (DFA) evaluation is a powerful two-party primitive that has been widely used in cryptographic protocols. It enables two mutually distrusted participants to obliviously evaluate a DFA (provided by one party) on an input string (provided by the other party), while preserving the privacy of each party from the other one. However, this primitive is not flexible and powerful enough, in the sense that it only supports evaluation on input string that is provided by one participant. In this paper, we propose oblivious DFA evaluation on joint input (denoted as \(\mathcal{F}_{\mathsf{ODFA}^{\mathsf{JI}}} )\), a variant that extends the functionality of traditional oblivious DFA evaluation protocols. The new primitive enables two participants to collaboratively evaluate a DFA on a joint input, where the input is a combination of two input strings provided by both of the participants. To enable modularized instantiation, we first propose and instantiate \(\mathcal{F}_{\mathsf{OT}^{\mathsf{JC}}} \) – oblivious transfer with joint choice – a functionality as modified oblivious transfer (OT), and then provide an efficient instantiation for \(\mathcal{F}_{\mathsf{ODFA}^{\mathsf{JI}}}\) in \(\mathcal{F}_{\mathsf{OT}^{\mathsf{JC}}} \)-hybrid model. Security proof demonstrates that the proposed protocol is secure under semi-honest model, and theoretical performance analysis shows that it achieves satisfactory efficiency and scalability. \( \mathcal{F}_{\mathsf{ODFA}^{\mathsf{JI}}}\) is a basic as well as an important building block for high-level secure outsourced computing tasks. In this paper, we use secure outsourced pattern matching as a case study and show how it can be applied to construct such high-level protocols.
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68M25 | Computer security |
| 68Q45 | Formal languages and automata |
| 94A60 | Cryptography |
Keywords:
secure computation; oblivious DFA evaluation; outsourcing; oblivious transfer; semi-honest modelReferences:
| [1] | Beaver, D.; Micali, S.; Rogaway, P., The round complexity of secure protocols, Proceedings of the ACM Symposium on Theory of Computing (STOC), 90, 503-513 (1990) |
| [2] | Benaloh, J., Dense Probabilistic Encryption, Proceedings of the Workshop on Selected Areas of Cryptography (SAC), 120-128 (1994) |
| [3] | Blanton, M.; Aliasgari, M., Secure outsourcing of dna searching via finite automata, Proceedings of the IFIP Annual Conference on Data and Applications Security and Privacy, 49-64 (2010), Springer |
| [4] | Chen, F.; Wang, D.; Lin, Q.; Chen, J.; Zhong, M.; Yu, W.; Qin, J., Towards dynamic verifiable pattern matching, IEEE Trans. Big Data (2018) |
| [5] | Damgård, I.; Jurik, M., A generalisation, a simplication and some applications of Paillier’s probabilistic public-key system, Proceedings of the International Workshop on Public Key Cryptography (PKC), 119-136 (2001), Springer · Zbl 0987.94032 |
| [6] | Darivandpour, J.; Atallah, M. J., Efficient and secure pattern matching with wildcards using lightweight cryptography, Comput. Secur., 77, 666-674 (2018) |
| [7] | Di Crescenzo, G.; Coan, B.; Kirsch, J., Privacy-preserving deterministic automata evaluation with encrypted data blocks, Data Privacy Management, Cryptocurrencies and Blockchain Technology, 275-294 (2017), Springer |
| [8] | Frikken, K. B., Practical private DNA string searching and matching through efficient oblivious automata evaluation, Proceedings of the IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), 81-94 (2009), Springer |
| [9] | Gennaro, R.; Hazay, C.; Sorensen, J. S., Text search protocols with simulation based security, Proceedings of the International Workshop on Public Key Cryptography (PKC), 332-350 (2010), Springer · Zbl 1281.94025 |
| [10] | Gentry, C., Fully homomorphic encryption using ideal lattices, Proceedings of the ACM Symposium on Theory of Computing (STOC), volume 9, 169-178 (2009) · Zbl 1304.94059 |
| [11] | Goldreich, O., Foundations of Cryptography: Volume 2, Basic Applications (2009), Cambridge University Press · Zbl 1179.94063 |
| [12] | Hazay, C.; Lindell, Y., Efficient Secure Two-Party Protocols: Techniques and Constructions (2010), Springer Science & Business Media · Zbl 1208.68005 |
| [13] | Ishai, Y.; Kilian, J.; Nissim, K.; Petrank, E., Extending oblivious transfers efficiently, Proceedings of the Annual International Cryptology Conference (CRYPTO), 145-161 (2003), Springer · Zbl 1122.94422 |
| [14] | Lindell, Y.; Pinkas, B., A proof of security of Yaos protocol for two-party computation, J. Cryptol., 22, 2, 161-188 (2009) · Zbl 1159.94364 |
| [15] | Mohassel, P.; Niksefat, S.; Sadeghian, S.; Sadeghiyan, B., An efficient protocol for oblivious DFA evaluation and applications, Proceedings of the Cryptographers’Track at the RSA Conference (CT-RSA), 398-415 (2012), Springer · Zbl 1292.94116 |
| [16] | Naor, M.; Pinkas, B.; Pinkas, B., Efficient oblivious transfer protocols, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 448-457 (2001), Society for Industrial and Applied Mathematics (SIAM) · Zbl 0991.94045 |
| [17] | Paillier, P., Public-key cryptosystems based on composite degree residuosity classes, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), 223-238 (1999), Springer · Zbl 0933.94027 |
| [18] | M.O. Rabin, How to exchange secrets with oblivious transfer, Harvard Aiken Computation Laboratory, Technical Report TR-81 (1981). |
| [19] | Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM J. Res. Dev., 3, 2, 114-125 (1959) · Zbl 0158.25404 |
| [20] | Rueppel, R. A., Stream ciphers, Analysis and Design of Stream Ciphers, 5-16 (1986), Springer · Zbl 0618.94001 |
| [21] | Samadani, M. H.; Berenjkoob, M.; Blanton, M., Secure pattern matching based on bit parallelism, Int. J. Inf. Secur., 18, 3, 371-391 (2019) |
| [22] | Sasakawa, H.; Harada, H.; duVerle, D.; Arimura, H.; Tsuda, K.; Sakuma, J., Oblivious evaluation of non-deterministic finite automata with application to privacy-preserving virus genome detection, Proceedings of the 13th Workshop on Privacy in the Electronic Society, 21-30 (2014) |
| [23] | Troncoso-Pastoriza, J. R.; Katzenbeisser, S.; Celik, M., Privacy preserving error resilient DNA searching through oblivious automata, Proceedings of the 14th ACM Conference on Computer and Communications Security (CCS), 519-528 (2007), ACM |
| [24] | Wei, L.; Reiter, M. K., Third-party private DFA evaluation on encrypted files in the cloud, Proceedings of the European Symposium on Research in Computer Security (ESORICS), 523-540 (2012), Springer |
| [25] | Wei, X.; Zhao, M.; Xu, Q., Efficient and secure outsourced approximate pattern matching protocol, Soft Comput., 22, 4, 1175-1187 (2018) · Zbl 1398.68710 |
| [26] | Yasuda, M.; Shimoyama, T.; Kogure, J.; Yokoyama, K.; Koshiba, T., Secure pattern matching using somewhat homomorphic encryption, Proceedings of the ACM Workshop on Cloud Computing Security (CCSW), 65-76 (2013), ACM |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
