0
$\begingroup$

I am new to this encryption scheme, so I may not be exactly sure of its implementation. I have a list of (u, v) ciphertext pairs to decrypt, each of them are 1-bit.

          { "u": [ 1, 19, 3, 2, 24 ], "v": 16 },
          { "u": [ 3, 20, 22, 26, 15 ], "v": 21 },
          { "u": [ 7, 3, 24, 26, 22 ], "v": 13 },
          { "u": [ 9, 20, 7, 25, 14 ], "v": 5 },
          { "u": [ 28, 11, 26, 22, 16 ], "v": 23 },
          { "u": [ 18, 11, 20, 23, 8 ], "v": 26 },
          { "u": [ 16, 27, 3, 10, 14 ], "v": 18 },
          { "u": [ 15, 4, 16, 9, 17 ], "v": 11 },
          { "u": [ 15, 4, 16, 9, 17 ], "v": 26 },
          { "u": [ 12, 4, 11, 20, 9 ], "v": 18 },
          { "u": [ 9, 27, 2, 0, 14 ], "v": 0 },
          { "u": [ 12, 11, 6, 24, 9 ], "v": 14 },
          { "u": [ 12, 20, 12, 14, 22 ], "v": 27 },
          { "u": [ 3, 20, 22, 26, 15 ], "v": 7 },
          { "u": [ 24, 19, 1, 14, 20 ], "v": 9 },
          { "u": [ 9, 11, 1, 6, 1 ], "v": 6 },
          { "u": [ 9, 20, 7, 25, 14 ], "v": 5 },
          { "u": [ 1, 19, 3, 2, 24 ], "v": 1 },
          { "u": [ 21, 4, 1, 8, 16 ], "v": 9 },
          { "u": [ 0, 27, 12, 12, 7 ], "v": 24 },
          { "u": [ 27, 6, 28, 7, 0 ], "v": 2 },
          { "u": [ 13, 5, 22, 25, 6 ], "v": 6 },
          { "u": [ 9, 11, 1, 6, 1 ], "v": 21 },
          { "u": [ 16, 18, 26, 20, 1 ], "v": 5 },
          { "u": [ 16, 18, 26, 20, 1 ], "v": 20 },
          { "u": [ 28, 11, 26, 22, 16 ], "v": 8 },
          { "u": [ 16, 27, 3, 10, 14 ], "v": 18 },
          { "u": [ 12, 20, 12, 14, 22 ], "v": 27 },
          { "u": [ 12, 4, 11, 20, 9 ], "v": 4 },
          { "u": [ 13, 5, 22, 25, 6 ], "v": 6 },
          { "u": [ 15, 4, 16, 9, 17 ], "v": 26 },
          { "u": [ 11, 10, 15, 22, 14 ], "v": 19 }

My secret key, s and prime q to decrypt these ciphertexts are given below.

"sk": [ 2, 21, 3, 6, 23 ]
"q": 29,

This is the Python code that I have used to retrieve the binary message value, m.

import numpy as np
import json

m = ''

def computeM(u, v, q, s):
    global m
    res=(np.subtract(v, np.dot(s, u))) % q
  
    if (res > q//4):
        m += '1' 
    else:
        m += '0'

# retrieve u and v from JSON 

f = open('CarlDavisJSON.json')
  
data = json.load(f)


# Extract the u and v values from the messages array
u_json = []
v_json = []
s = ""


for message in data['exercise']['messages'][0]['cipher']:
    u_json.append(message['u'])
    v_json.append(message['v'])



s = data['exercise']['alice']['sk']
q = data['exercise']['alice']['q']


# store u and v in numpy array

u_list = np.array(u_json)
v_list = np.array(v_json)


# compute each binary from u and v


for i in range(len(u_list)):
    u = np.array(u_list[i])
    v = np.array(v_list[i])

    # print(v)
    computeM(u, v, q, s)
    

print(m)

When I implemented this algorithm, I got the binary value 11101111111100010110110111100111 instead of the intended value 01100111011000010110110101100101 which is the binary message for 'game', the message that was encrypted using the same keys.

Can I know what has went wrong with the implementation?

$\endgroup$

1 Answer 1

1
$\begingroup$

There may not be anything wrong with your implementation. You should understand that Learning with Errors designs come with a probability of failure. This probability of failure applies to each bit of $m$. On the other hand, there is one part of your code that might be incorrect. Are you sure that when checking the size of res you don't want to check that it lies in the range $q/4<{\tt res}<3q/4$ rather than the range $q/4<{\tt res}<q$? This would correspond to encoding messages by adding $q/2$ when the message bit is a 1 and 0 when the message bit is 0.

For systems used in practice, the probability of failure is designed to be so small that it should almost never occur by chance, but for toy examples such as yours, it may be more common. As there are six disagreeing positions out of thirty-two, this corresponds to significant agreement, but perhaps a failure rate of around 1/5, but equally an incorrect range on the res check would introduce an error rate of about 1/4.

Looking at the positions where there is disagreement, the first bit corresponds to a res value of 28. If this were just subtract 1 from our dot product, res would become 0 and the correct bit would be recovered. Alternatively, if we use the range $q/4<{\tt res}<3q/4$ we recover the correct value. Similarly for the 5th, 9th, 12th and 31st bits we have the value 28 for res and for the 25th bit we have 27. Noting that a revised range check would correct all of these, I suspect that that is your issue.

$\endgroup$
1
  • $\begingroup$ The range that you have given for res is correct. It has been able to retrieve the right binary values. Thanks for helping. $\endgroup$
    – user108142
    Mar 13, 2023 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.