Using the lock fuse bits is definitely the correct step here. Unlocking is not a problem, since the memory will be erased in that step and you cannot prevent reflashing anyway.

You didn't include details on the handshake. An important attack route would be to just sniff on the Arduinos Serial interface. Unless your handshake itself is encrypted locking the Arduino will not prevent attackers from getting it.

There are encryption libraries for Arduino (like this one on github). Based on your thread model and the needed resources (since the Uno is rather constrained especially in RAM) you can choose a fitting library and a fitting encryption algorithm. One important attack route would be a replay attack, where the attacker just resends the serial data, that he recorded in the last successfull transmission. One way to prevent that would be a rolling code (like modern garage door openers often use). Or you can create One-Time-Passwords (for example by combining the handshake secret with a timestamp and encrypting/hashing that; you need synchronized time for that).

Using the lock fuse bits is definitely the correct step here. Unlocking is not a problem, since the memory will be erased in that step and you cannot prevent reflashing anyway.

Very important note from Gerben in the comments:

Note that setting the lock bits is pointless, while the Arduino bootloader is installed. The bootloader can still read out the program, even with the lock bits set. You'd have to remove the bootloader and upload the code using the ISP interface (ArduinoAsISP).

The lock bits only work for the ISP interface, which can be used to program the Arduino. The bootloader (which is part of the program on the Arduino) still can read the program memory (it has to, since it is executed from there). Thus to prevent someone from reading out the program through the bootloader, you need to remove the bootloader. Programming is then done just like you are setting the fuses: Through ISP (for example via a second Arduino).

You didn't include details on the handshake. An important attack route would be to just sniff on the Arduinos Serial interface. Unless your handshake itself is encrypted locking the Arduino will not prevent attackers from getting it.

There are encryption libraries for Arduino (like this one on github). Based on your thread model and the needed resources (since the Uno is rather constrained especially in RAM) you can choose a fitting library and a fitting encryption algorithm. One important attack route would be a replay attack, where the attacker just resends the serial data, that he recorded in the last successfull transmission. One way to prevent that would be a rolling code (like modern garage door openers often use). Or you can create One-Time-Passwords (for example by combining the handshake secret with a timestamp and encrypting/hashing that; you need synchronized time for that).

Using the lock fuse bits is definitely the correct step here. Unlocking is not a problem, since the memory will be erased in that step and you cannot prevent reflashing anyway.

You didn't include details on the handshake. An important attack route would be to just sniff on the Arduinos Serial interface. Unless your handshake itself is encrypted locking the Arduino will not prevent attackers from getting it. There are encryption libraries for Arduino (like this one on github). Based on your thread model and the needed resources (since the Uno is rather constrained especially in RAM) you can choose a fitting library and a fitting encryption algorithm.

Using the lock fuse bits is definitely the correct step here. Unlocking is not a problem, since the memory will be erased in that step and you cannot prevent reflashing anyway.

You didn't include details on the handshake. An important attack route would be to just sniff on the Arduinos Serial interface. Unless your handshake itself is encrypted locking the Arduino will not prevent attackers from getting it. 

There are encryption libraries for Arduino (like this one on github). Based on your thread model and the needed resources (since the Uno is rather constrained especially in RAM) you can choose a fitting library and a fitting encryption algorithm. One important attack route would be a replay attack, where the attacker just resends the serial data, that he recorded in the last successfull transmission. One way to prevent that would be a rolling code (like modern garage door openers often use). Or you can create One-Time-Passwords (for example by combining the handshake secret with a timestamp and encrypting/hashing that; you need synchronized time for that).