.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "_autoexamples/Demo_8_HammingDist.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code .. rst-class:: sphx-glr-example-title .. _sphx_glr__autoexamples_Demo_8_HammingDist.py: Hamming Distance. ============================== This demo shows how to compute the Hamming Distance between two vectors {0,1}*. We will translate the hamming distance into a scalar product by translating the XOR op. to the arithmetic domain: xor(x,y) = (x-y)^2 = x + y - 2*(x*y) HD(x,y) = sum (x[i] xor y[i]) = sum(x[i]) + sum(y[i]) - 2*sum(x[i]*y[i]) To do so, we will encode both the vectors and their elementwise squared cumul_add in independent vectors, compute the scalar product and add the remaining terms. As in the scalar product, we encode each vector into one (if l <= n_slots) or several ciphertexts (l>n), then compute the SIMD multiplication and cumulative sum (via rotations and sums), to finally add the extra terms and decrypt. We perform this operation in BFV to get the exact result. CKKS could also be used, but the result would be an approximation. .. GENERATED FROM PYTHON SOURCE LINES 24-29 .. code-block:: Python # %% # ---------------------------------------------------------------------------- # # HAMMING DISTANCE WITH BFV # ---------------------------------------------------------------------------- # .. GENERATED FROM PYTHON SOURCE LINES 30-37 1. Vector Generation --------------------------- We will define a pair of 1D integer vectors of size l in {0,1}*. For the purpose of this demo, we will focus on the case #1 of ScalarProd: #1: small l (l <= n) and high v_max. --> encoding with trailing zeros Users can modify l. .. GENERATED FROM PYTHON SOURCE LINES 37-54 .. code-block:: Python import warnings import numpy as np rng = np.random.default_rng(42) l = 256 # Generate two random vectors with l elements of values <= |v_max| v1 = rng.integers(0, 2, size=l) v2 = rng.integers(0, 2, size=l) hdRes = np.sum(v1^v2) print("\nA1. Vector generation") print(f"\tv1 = {str(v1)[:40]+'...'}") print(f"\tv2 = {str(v2)[:40]+'...'}") print(f"\tvRes = {hdRes}") .. rst-class:: sphx-glr-script-out .. code-block:: none A1. Vector generation v1 = [0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0... v2 = [1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0... vRes = 132 .. GENERATED FROM PYTHON SOURCE LINES 55-58 2. Hamming Distance setup --------------------------- Parameter selection goes according to vector length and max element size. .. GENERATED FROM PYTHON SOURCE LINES 58-147 .. code-block:: Python from Pyfhel import Pyfhel # utilities to generate context parameters bitsize = lambda x: np.ceil(np.log2(x)) get_closest_power_of_two = lambda x: int(2**(bitsize(x))) def get_BFV_context_hammingDist( l: int, sec: int=128, use_n_min: bool=True ) ->Pyfhel: """ Returns the best context parameters to compute hamming dist. in BFV scheme. The important context parameters to set are: - n: the polynomial modulus degree (= n_slots) - t: the plaintext modulus (plaintext element size) *Optimal n*: Chosen among {2**12, 2**13, 2**14, 2**15}. The min value is: - n = 2**12 if sec in {128, 192} - n = 2**13 if sec = 256 The bigger n, the more secure the scheme, but the slower the computations. (it might be worth using n t_bits = 2 * bitsize(l) ^ ^ square | cumul. sum There is, however, a minimal size on t_bits for a given `n`: t_bits_min = 14 if n <= 2**11 t_bits_min = 16 if n <= 2**12 t_bits_min = 17 otherwise Arguments: l: vector length Returns: Pyfhel: context to perform homomorphic encryption """ #> OPTIMAL t --> minimum for chosen `n`, or big enough to hold v1@v2 t_bits_min = 17 t_bits = max(t_bits_min, 2*bitsize(l)) if t_bits > 60: raise ValueError(f"t_bits = {t_bits} > 60.") #> OPTIMAL n n_min = 2**12 if sec in [128, 192] else 2**13 if use_n_min: n = n_min # use n_min regardless of l elif 2*l < n_min: n = n_min # Smallest elif 2*l > 2**15: n = 2**15 # Largest else: n = get_closest_power_of_two(2*l) context_params = { 'scheme': 'BFV', 'n': n, # Poly modulus degree. BFV ptxt is a n//2 by 2 matrix. 't_bits': t_bits,# Plaintext modulus. 'sec': sec, # Security level. } # Increasing `n` to get enough noise budget for the c1*c2 multiplication. # Since the noise budget in a multiplication consumes t_bits (+...) noise # budget and we start with `total_coeff_modulus_bit_count-t_bits` budget, # we check if this is high enough to decrypt correctly. HE = Pyfhel() total_coeff_modulus_bit_count = 0 while total_coeff_modulus_bit_count - 2*t_bits <= 0: context_status = HE.contextGen(**context_params) total_coeff_modulus_bit_count = HE.total_coeff_modulus_bit_count # if (context_status != "success"): # warnings.warn(f" n={context_params['n']} Doesn't produce valid parameters. Trying 2*n") context_params['n'] *= 2 if context_params['n'] > 2**15: raise ValueError(f"n = {context_params['n']} > 2**15. Parameters are not valid.") return HE # Setup parameters for HE context HE = get_BFV_context_hammingDist(l, sec=128, use_n_min=True) HE.keyGen() HE.relinKeyGen() HE.rotateKeyGen() print("\n2. BFV context generation") print(f"\t{HE}") .. rst-class:: sphx-glr-script-out .. code-block:: none 2. BFV context generation .. GENERATED FROM PYTHON SOURCE LINES 148-150 3. BFV Encryption ----------------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 150-166 .. code-block:: Python # Encrypt each vector into one (if l <= n_slots) or several ciphertexts (l>n) c1 = [HE.encrypt(v1[j:j+HE.get_nSlots()]) for j in range(0,l,HE.get_nSlots())] c2 = [HE.encrypt(v2[j:j+HE.get_nSlots()]) for j in range(0,l,HE.get_nSlots())] sumx = np.expand_dims(np.sum(v1),0) sumy = np.expand_dims(np.sum(v2),0) c1_sumx = HE.encrypt(sumx) c2_sumy = HE.encrypt(sumy) print("\n3. Boolean Encryption as integers") print("->\tv1= ", str(v1)[:40],'...]\n\t--> c1= ', c1) print("->\tv2= ", str(v2)[:40],'...]\n\t--> c2= ', c2) print("->\tsumx= ", str(sumx),'\n\t--> c1_sumx= ', c1_sumx) print("->\tsumy= ", str(sumy),'\n\t--> c2_sumy= ', c2_sumy) .. rst-class:: sphx-glr-script-out .. code-block:: none 3. Boolean Encryption as integers -> v1= [0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 ...] --> c1= [] -> v2= [1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 ...] --> c2= [] -> sumx= [126] --> c1_sumx= -> sumy= [124] --> c2_sumy= .. GENERATED FROM PYTHON SOURCE LINES 167-170 4. BFV Hamming Distance Evaluation ----------------------------------------- Evaluate the scalar product, then add the independent terms .. GENERATED FROM PYTHON SOURCE LINES 170-187 .. code-block:: Python c_sp = HE.cumul_add(sum([~(c1[i]*c2[i]) for i in range(len(c1))])) # Hamming Distance c_hd = c1_sumx + c2_sumy - (c_sp*2) # Lets decrypt and check the result! res = HE.decrypt(c_hd)[0] print("\n4. Hamming Distance Evaluation") print("->\tHamming(c1, c2)= ", c_hd) print("->\tHE.decrypt(c1@c2)= ", res) print("->\tExpected: v1@v2= ", hdRes) assert res == hdRes, "Incorrect result!" print("---------------------------------------") .. rst-class:: sphx-glr-script-out .. code-block:: none 4. Hamming Distance Evaluation -> Hamming(c1, c2)= -> HE.decrypt(c1@c2)= 132 -> Expected: v1@v2= 132 --------------------------------------- .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.942 seconds) **Estimated memory usage:** 9 MB .. _sphx_glr_download__autoexamples_Demo_8_HammingDist.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: Demo_8_HammingDist.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: Demo_8_HammingDist.py ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_