<figure><img src="image_1.png" /></figure>

HAL
open science

# Efficient Almost Strongly Universal Hash Function for Quantum Key Distribution

Bo Liu, Baokang Zhao, Chunqing Wu, Wanrong Yu, Ilsun You

<figure><img src="image_2.png" /></figure>

## ► To cite this version:

Bo Liu, Baokang Zhao, Chunqing Wu, Wanrong Yu, Ilsun You. Efficient Almost Strongly Universal Hash Function for Quantum Key Distribution. 3rd International Conference on Information and Communication Technology-EurAsia (ICT-EURASIA) and 9th International Conference on Research and Practical Issues of Enterprise Information Systems (CONFENIS), Oct 2015, Daejon, South Korea. pp.282-285, 10.1007/978-3-319-24315-3_29. hal-01466229

HAL Id: hal-01466229

https://inria.hal.science/hal-01466229

Submitted on 13 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Extended Abstract

Efficient Almost Strongly Universal Hash Function for
Quantum Key Distribution

Bo Liu, Baokang Zhao¹, Chunqing Wu, Wanrong Yu

School of Computer Science

National University of Defense Technology

Changsha, Hunan, CHINA

liubo.eecs@gmail.com, {bkzhao,wuchunqing, wryu}@nudt.edu.cn

Ilsun You

School of Information Science

Korean Bible University

Seoul, Korea

isyou@bible.ac.kr

**Abstract.** Quantum Key Distribution (QKD) technology, based on principles of quantum mechanics, can generate unconditional security keys for communication parties. Information-theoretically secure (ITS) authentication, the compulsory procedure of QKD systems, avoids the man-in-the-middle attack during the security key generation. the construction of hash functions is the paramount concern within the ITS authentication. In this extended abstract, we proposed a novel Efficient NTT-based ε-Almost Strongly Universal Hash Function. The security of our NTT-based ε-ASU hash function meets $\epsilon \le L(n+1)/2^{n-2}$.

With ultra-low computational amounts of construction and hashing procedures, our proposed NTT-based ε-ASU hash function is suitable for QKD systems.

**Keywords:** Almost strongly universal hash, quantum key distribution

# 1 Introduction

With the rapid development of computing technologies, the importance of secure communication is growing daily [21-24]. Unlike conventional cryptography which based on the computational complexity, Quantum Key Distribution (QKD) can achieve the unconditional security communication [1, 2] [18, 19, 20]. By transmitting security key information with quantum states, the final key generated by QKD system is information-theoretically secure (ITS), which is guaranteed by the non-cloning theorem and measuring collapse theorem in quantum physics [3, 4]. Nowadays, QKD

¹ The corresponding author: Dr. Baokang Zhao, email address: bkzhao@nudt.edu.cn.
has been one of the research focuses around the world. In recent years, the famous QKD network projects mainly include SECOQC in Europe [5], UQCC in Tokyo [6] and NQCB in China [7] and so on.

ITS authentication is the compulsory procedure of QKD system and also the key procedure which ensures the security of generated keys between communication parties [4, 8]. Otherwise, QKD is vulnerable to the man-in-the-middle attack [9-11]. The main challenge about the research of ITS authentication is the construction of hash functions which are suitable for ITS authentication with less security key [9, 12-14].

Usually, ε-Almost Strongly Universal (ε-ASU) hash functions can be used to construct ITS authentication schemes in a natural way. Majority construction schemes focus on the ε-ASU₂ hash function families, such as Wegman-Carter's and Krawczyk's construction schemes [13, 14]. Nowadays, the photon transmission frequency has reached to about ten GHz [15, 16]. With heavy computational amounts, ITS authentication schemes which based on ε-ASU₂ hash functions cannot meet the high performance requirement of QKD systems [9, 13, 17].

In this extended abstract, with NTT technology, we proposed a novel Efficient ε-Almost Strongly Universal Hash Function. With the special features of number-theoretic transforms (NTT) technology, our ε-ASU hash function family is constructed in the prime ring $Z_p^L$. In order to construct the NTT-based ε-ASU hash function efficiently, we assume that $L = 2^{\lambda}$, and the prime number $p = \nu L + 1$. We assume that the set of all messages is $R$, where $R \in Z_p^L$ with length of $L$, and the length of authentication tag is $n$, where $n = \lceil \log_2 p \rceil$. The security of our NTT-based ε-ASU hash function meets $\varepsilon \le L(n+1)/2^{n-2}$ and the consumed key length of ITS authentication scheme is less than $3n+1$.

## 2 NTT-based Almost Strongly Universal Hash Function

Since the construction has to consume a very long key, Gilles's NTT-based almost universal hash function is not suitable for ITS authentication [18]. With a partially known security key and a LFSR structure [13], a random bit stream can be generated to construct the NTT-based almost strongly universal (NASU) hash functions.

Let $\mathbf{R}$ be the set of messages, where $\mathbf{R} \in Z_p^L$. We take only the first $\beta$ elements of the hashing result. Let $f(x)$ be an irreducible polynomial with degree $\beta \lceil \log_2 p \rceil$ of $GF(2)$ and $s_{init} = (s_0, s_1, \cdots, s_{\beta \lceil \log_2 p \rceil - 1})^T$ be an initial state of the LFSR structure defined by the feedback function $f(x)$. $s_{init}$ and $f(x)$ are both generated from the partially known key with length of $2\beta \lceil \log_2 p \rceil + 1$. Let $\mathbf{f} = (f_0, f_1, \cdots, f_{\beta \lceil \log_2 p \rceil - 1})^T$ be the coefficient vector of $f(x)$ and $s_{[i-\beta \lceil \log_2 p \rceil, i-1]} = (s_{i-\beta \lceil \log_2 p \rceil}, s_{i-\beta \lceil \log_2 p \rceil + 1}, \cdots, s_{i-1})^T$, where $i \ge \beta \lceil \log_2 p \rceil$.
Thus, we can gain the random bit

$$s_i = s_{[i-\beta^{\lfloor \log_2 p \rfloor}, i-1]}^T f \mod 2. \quad (1)$$

Let $1 \le \beta \le L$ and $K = (2^0, 2^1, \dots, 2^{\lceil \log_2 p \rfloor-1})$. For $C, R \in \mathbb{Z}_p^L$, let $h_C(R) = (F^{-1}(C \cdot R))_{0,1,\dots,\beta-1}$ be the inverse NTT of their component-wise product, taking only the $\beta$ first elements of the result. Assume that $u = \lceil \log_2 p \rceil$, we define that the set

$$H_{p,L,\beta,s,f} = \{h_C : C_i = K s_{[(i+\beta)u, (i+\beta+1)u-1]} \mod p, \forall i\} \quad (2)$$

is an almost strongly universal family of hash functions with $\varepsilon \le (L+2L\beta\lceil \log_2 p \rceil+2)/2^{\beta\lceil \log_2 p \rceil}$. Assume that $n = \beta u$, we have $\varepsilon \le (L+2nL+2)/2^n$.

### 3 Potential Advantages

Comparing with ASU₂ hash functions, our proposed NASU hash functions have the following potential advantages:

(a) NASU hash functions can be easily constructed with a partially known security key and a LFSR structure.

(b) With the special features of number-theoretic transforms (NTT) technology, the computational amounts of our NASU hashing procedure is much less than Krawczyk's scheme and other ASU₂ hash functions.

(c) Treating the elements of input messages as non-binary integers of the ring $\mathbb{Z}_p^L$, our proposed NTT-based $\varepsilon$-ASU hash function is very suitable for ITS authentication in QKD systems.

In the future, we will explore the detailed security proof of NASU hash functions and its deployment within the QKD system.

### References

1. Scarani, V., Bechmann-Pasquinucci, H., Cerf, N., Dušek, M., Lütkenhaus, N., Peev, M.: The security of practical quantum key distribution. Reviews of Modern Physics 81, 1301-1350 (2009)

2. Wang, L., Chen, L., Ju, L., Xu, M., Zhao, Y., Chen, K., Chen, Z., Chen, T.-Y., Pan, J.-W.: Experimental multiplexing of quantum key distribution with classical optical communication. Appl. Phys. Lett. 106, (2015)
3. Bennett, C.H., Brassard, G.: Quantum cryptography: Public key distribution and coin tossing. In: Proceedings of IEEE International Conference on Computers, Systems and Signal Processing. New York, (Year)

4. Ma, X., Fung, C.-H.F., Boileau, J.C., Chau, H.F.: Universally composable and customizable post-processing for practical quantum key distribution. Computers and Security 30, 172-177 (2011)

5. Leverrier, A., Karpov, E., Grangier, P., Cerf, N.J.: Unconditional security of continuous-variable quantum key distribution. arXiv preprint arXiv:0809.2252 (2008)

6. Sasaki, M., Fujiwara, M., et al.: Field test of quantum key distribution in the Tokyo QKD Network. Optics Express 19, 10387-10409 (2011)

7. http://www.quantum2011.org/

8. Ma, X.: Practical Quantum key Distribution post-processing. (2011)

9. Abidin, A.: Authentication in Quantum Key Distribution: Security Proof and Universal Hash Functions. Department of Electrical Engineering, vol. PhD. Linkoping University (2013)

10. Pacher, C., Abidin, A., Lorunser, T., Peev, M., Ursin, R., Zeilinger, A., Larsson, J.-A.: Attacks on quantum key distribution protocols that employ non-ITS authentication. arXiv preprint arXiv:1209.0365 (2012)

11. Ioannou, L.M., Mosca, M.: Unconditionally-secure and reusable public-key authentication. arXiv preprint arXiv:1108.2887 (2011)

12. Portmann, C.: Key Recycling in Authentication. arXiv preprint arXiv:1202.1229 (2012)

13. Krawczyk, H.: LFSR-based Hashing and Authentication. Advances in Cryptology-CRYPTO'94 129-139 (1994)

14. Wegman, M.N., Carter, J.L.: New hash functions and their use in authentication and set equality. Journal of computer and system sciences 22, 265-279 (1981)

15. Wang, S., Chen, W., Guo, J., Yln, Z., Li, H., Zhou, Z., Guo, G., Han, Z.: 2 GHz clock quantum key distribution over 260 km of standard telecom fiber. Optics Letters 37, (2012)

16. Tanaka, A., Fujiwara, M., et al.: High-Speed Quantum Key Distribution System for 1-Mbps Real-Time Key Generation. IEEE Journal of Quantum Electronics 48, (2012)

17. Carter, J.L., Wegman, M.N.: Universal classes of hash functions. In: Proceedings of the ninth annual ACM symposium on Theory of computing, pp. 106-112. ACM, (Year)

18. Liu B, Zhao B, Wei Z, et al. Qphone: A quantum security VoIP phone[C]. In: Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM.ACM, 2013. 477-478.

19. Liu B, Zhao B, Liu B, et al. A Security Real-time Privacy Amplification Scheme in QKD System.[J]. J. UCS. 2013, 19(16): 2420-2436.

20. S. Sun, M. Jiang, X. Ma, C. Li, and L. Liang, "Hacking on decoy-state quantum key distribution system with partial phase randomization," Scientific Reports, 2013.

21. Yujing Liu, Wei Peng, Jinshu Su: "A study of IP prefix hijacking in cloud computing networks", Security and Communication Networks 7(11): 2201-2210, 2014.

22. Rieke, Roland, Maria Zhdanova, and Jürgen Repp. "Security Compliance Tracking of Processes in Networked Cooperating Systems." Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA) 6.2 (2015): 21-40.

23. Kotenko I. Guest Editorial: Security in Distributed and Network-Based Computing[J]. Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA) 6.2 (2015).

24. Skovoroda, A., & Gamayunov, D. (2015). Securing Mobile Devices: Malware Mitigation Methods. Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA), 6(2), 78-97.