About the author:
Daniel is CTO at rhome GmbH, and Co-Founder at Aqarios GmbH. He holds a M.Sc. in Computer Science from LMU Munich, and has published papers in reinforcement learning and quantum computing. He writes about technical topics in quantum computing and startups.
jrnl · home about list ventures publications LinkedIn Join my Slack

# Oblivious Transfer Example With Physically Unclonable Function (PUF)

Physically Unclonable Functions (PUFs) are an extremely interesting and hot topic in cryptography. The basic gist is, you have a certain physical object that cannot be cloned due to the extremely intricate properties of it (e.g. the atomic structure of a DVD) that depend on the manufacturing process. The assumption is that each DVD is unique when looking at its atomic structure. Now, when measuring the reflection of a DVD with a high precision device of some sort, these differences show up. Imagine you put a chip in a capsule which inner walls consist of such reflective material. The chip has a device that measures the reflection and based on that generates a key pair (a public and a private one). This public key pair can be used to communicate with the device and identify it, and if someone were to try to tamper with the device by drilling into it - the reflective material would break, changing the measurement and thus the public key. Lastly, an additional digital signature on the device ensures that anyone can check for tampering (the public key is contained in the digital signature). The most important part is that the device is secret-free. The 'secret' is the material and there is no way to clone that material to re-use the secret and there is no way to find out the private key without breaking the whole thing. Pretty cool concept.

PUFs can be used for many cryptographic primitives, one of which is Oblivious Transfer (OT). The point of OT is: A wants to get a certain information from B based on A's choice. B should stay oblivious of the choice of A in the process however, and A should not be able to get all of the options from B. Pretty specific, I know. But being a cryptographic primitive has lots of uses. See the paper Founding Cryptography on Oblivious Transfer - Efficiently, which builds secure two-party computation based on OT.

Anyways, enough of introduction. The main contribution of this small post is to show an example calculation of how Oblivious Transfer would work with PUFs. In the figure below you can see how the scheme works. A uses the PUF to create a list of challenge-response pairs (CRPs) and sends over the PUF to B. B chooses two values x0 and x1 and sends those to A. A now chooses one of those and sends back the challenge XOR'd with the chosen value. B measures the response of the PUF of the two challenges v XOR x0 and v XOR x1. The interesting thing here is that depending on the choice of A, one of those challenges ends up being the real challenge C of A (e.g. if A chooses x0, v XOR x0 = C XOR x0 XOR x0 = C). B sends both choices (s0, s1) back, but XOR'd with both responses. A chooses the correct one based on its choice and since it has the response for C, can compute y0 XOR R = s0 (if continuing with the example of choosing x0).

Now, an example calculation.

s0 = 5
s1 = 6

# A chooses random C and a choice b (can be 0 or 1).
C = 5412
R = 7777
b = 1

# B chooses random x0, x1.
x0 = 44
x1 = 66

# A calculates (remember, A chose 1):
v = C ^ x1 = 5412 ^ 66 = 5478

# B measures the two challenges.
R0 = v ^ x0 = 5478 ^ 44 = 5450 = 9999
R1 = v ^ x1 = 5478 ^ 66 = 5412 = 7777

# B sends back both choices XOR'd with both responses.
y0 = s0 ^ R0
y1 = s1 ^ R1

# A XORs the second reply from B (first one is garbage) and gets the choice value they wanted.
s1 = y1 ^ R = 6

In summary, what we just observed: A lets B compute both options so B doesn't know the chosen bit b. And B computes both options in a way that the option not chosen is garbled, while the option chosen can be deduced by A.

Published on