The performance of error correcting codes in discrete and continuous fuzzy pairing protocols

• Henrique de Rocha Deus UFMG
• Vladimir Portela Parente UFMG
• Jeroen van de Graaf UFMG

DOI: https://doi.org/10.5753/sbseg.2017.19518

Resumo

In fuzzy pairing, two parties compare two bit strings which are supposed to be similar, but almost never identical. So A and B engage in a protocol to verify whether d(s_A, s_B) is less than some threshold T; if not, the parties abort and authentication failed. Here d() is to be taken as the Hamming distance. One standard protocol is the code-offset method: A computes a random vector x such that s_A − x is a code word of some pre-agreed error-correcting x. Together they verify whether the code and sends x to B, who decodes s_B − two decoded codewords are the same. A common secret key can be obtained subsequently, We cast this problem in a different context, in which A and B want to compare continuous signals, instead of discrete bit strings. We test the code offset method for four classes of error-correcting codes: Reed-Solomon (RS) Codes, Low Density Parity Check (LDPC) Codes, Repeat-Accumulate Codes (RAC) and Low Density Lattice Codes (LDLC). For similar error correction capability our results show that RS codes perform slowly, while LDPC and RAC which very similar are both really fast. LDLC has the best correction capabilities, but are slower because of their mathematical complexity. Our results can be generalized to fuzzy extractors.

Referências

Bennett, C. H., Brassard, G., Crépeau, C., and Maurer, U. M. (1995). Generalized privacy amplification. IEEE Transactions on Information Theory, 41(6):1915–1923.

Bose, R. C. and Ray-Chaudhuri, D. K. (1960). On a Class of Error Correcting Binary Group Codes. Information and control, 3(1):68–79.

Brassard, G. and Salvail, L. (1993). Secret-key reconciliation by public discussion. In Workshop on the Theory and Application of of Cryptographic Techniques, pages 410–423. Springer.

Brassard, G. and Salvail, L. (1994). Secret-Key Reconciliation by Public Discussion. In advances in Cryptology-EUROCRYPT 93, pages 410–423. Springer.

Buhan, I., Doumen, J., Hartel, P., and Veldhuis, R. (2007a). Constructing Practical Fuzzy Extractors Using QIM. Technical report, Technical Report TR-CTIT-07-52, Centre for Telematics and Information Technology University of Twente.

Buhan, I., Doumen, J., Hartel, P., and Veldhuis, R. (2007b). Fuzzy Extractors for Continuous Distributions. In Proceedings of the 2nd ACM symposium on Information, computer and communications security, pages 353–355. ACM.

Chang, Y.-J., Zhang, W., and Chen, T. (2004). Biometrics-Based Cryptographic Key Generation. In Multimedia and Expo, 2004. ICME’04. 2004 IEEE International Conference on, volume 3, pages 2203–2206. IEEE.

Dodis, Y., Ostrovsky, R., Reyzin, L., and Smith, A. (2008). Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM journal on computing, 38(1):97–139.

Gallager, R. (1962). Low-density parity-check codes. IRE Transactions on information theory, 8(1):21–28.

Goodrich, M. T., Sirivianos, M., Solis, J., Tsudik, G., and Uzun, E. (2006). Loud and Clear: Human-Verifiable Authentication Based on Audio. In Distributed Computing Systems, 2006. ICDCS 2006. 26th IEEE International Conference on, pages 10–10. IEEE.

Johnson, S. J. (2009). Iterative error correction: Turbo, low-density parity-check and repeat-accumulate codes. Cambridge University Press.

Juels, A. and Sudan, M. (2006). A Fuzzy Vault Scheme. Designs, Codes and Cryptography, 38(2):237–257.

Kirovski, D., Sinclair, M., and Wilson, D. (2007a). The Martini Synch. Technical report, Technical Report MSR-TR-2007-123, Microsoft Research.

Kirovski, D., Sinclair, M., andWilson, D. (2007b). The Martini Synch: Using Accelerometers for Device Pairing. Technical report, Citeseer.

Kumar, A., Saxena, N., Tsudik, G., and Uzun, E. (2009). Caveat emptor: A comparative study of secure device pairing methods. In Seventh Annual IEEE International Conference on Pervasive Computing and Communications, PerCom 2009, 9-13 March 2009, Galveston, TX, USA, pages 1–10.

Kurkoski, B. M., Dauwels, J., and Loeliger, H.-A. (2009). Power-constrained communications using ldlc lattices. In Information Theory, 2009. ISIT 2009. IEEE International Symposium on, pages 739–743. IEEE.

Lin, S. and Costello, D. J. (2004). Error Control Coding, Second Edition. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.

Linnartz, J.-P. and Tuyls, P. (2003). New Shielding Functions to Enhance Privacy and Prevent Misuse of Biometric Templates. In Audio-and Video-Based Biometric Person Authentication, pages 393–402. Springer.

MacKay, D. J. (2003). Information Theory, Inference and Learning Algorithms. Cambridge university press.

Mayrhofer, R. (2007). The Candidate Key Protocol for Generating Secret Shared Keys from Similar Sensor Data Streams. In Security and Privacy in Ad-hoc and Sensor Networks, pages 1–15. Springer.

Mayrhofer, R. and Gellersen, H. (2007). Shake Well Before Use: Authentication Based on Accelerometer Data. In Pervasive computing, pages 144–161. Springer.

Mayrhofer, R. and Gellersen, H. (2009). Shake Well Before Use: Intuitive and Secure Pairing of Mobile devices. Mobile Computing, IEEE Transactions on, 8(6):792–806.

Poltyrev, G. (1994). On coding without restrictions for the awgn channel. IEEE Transactions on Information Theory, 40(2):409–417.

Premnath, S. N., Gowda, P. L., Kasera, S. K., Patwari, N., and Ricci, R. (2014). Secret Key Extraction Using Bluetooth Wireless Signal Strength Measurements. In Sensing, Communication, and Networking (SECON), 2014 Eleventh Annual IEEE International Conference on, pages 293–301. IEEE.

Reed, I. S. and Solomon, G. (1960). Polynomial Codes Over Certain Finite Fields. Journal of the society for industrial and applied mathematics, 8(2):300–304.

Schurmann, D. and Sigg, S. (2013). Secure Communication Based on Ambient Audio. Mobile Computing, IEEE Transactions on, 12(2):358–370.

Sommer, N., Feder, M., and Shalvi, O. (2008). Low-density lattice codes. IEEE Transactions on Information Theory, 54(4):1561–1585.

Sommer, N., Feder, M., and Shalvi, O. (2009). Shaping methods for low-density lattice codes. In Information TheoryWorkshop, 2009. ITW 2009. IEEE, pages 238–242. IEEE.

Tuyls, P., Akkermans, A. H., Kevenaar, T. A., Schrijen, G.-J., Bazen, A. M., and Veldhuis, R. N. (2005). Practical Biometric Authentication with Template Protection. In Audioand Video-Based Biometric Person Authentication, pages 436–446. Springer.

Verbitskiy, E. A., Tuyls, P., Obi, C., Schoenmakers, B., and Skoric, B. (2010). Key Extraction from General Nondiscrete Signals. Information Forensics and Security, IEEE Transactions on, 5(2):269–279.

Zheng, G., Li, W., and Zhan, C. (2006). Cryptographic Key Generation from Biometric Data Using Lattice Mapping. In Pattern Recognition, 2006. ICPR 2006. 18th International Conference on, volume 4, pages 513–516. IEEE.