Computer-implemented validation methods and systems

A computer-implemented method performed by a validation device, the computer-implemented method comprising:

• following transmission of a challenge message by a beacon device to each of one or more responder devices over a respective direct communication link, the challenge message inviting each of the one or more responder devices to prove an existence of a respective direct communication link by transmitting to a respective recipient device, distinct from the beacon device, a respective response message indicating knowledge of contents of the challenge message;
• the validation device obtaining an indication that a confirmation message from the beacon device has been received by a message store, the confirmation message indicating knowledge of the contents of the challenge message and having been transmitted by the beacon device a predetermined time period after transmission of the challenge message;
• the validation device, responsive to obtaining the indication, comparing contents of each response message which preceded the confirmation message in time, if any, to contents of the confirmation message and inferring therefrom which of the respective responder devices, if any, received the challenge message over the respective direct communication link;
• the validation device authenticating the one or more responder devices for two-way communication with the beacon device in dependence on timings of the respective response messages including authenticating a responder device whose response message was earliest and denying authentication of any other responder devices.

A computer-implemented method performed by a beacon device, the method comprising:

• the beacon device transmitting a challenge message to each of one or more responder devices over a respective direct communication link, to invite each responder device to prove an existence of the respective direct communication link by transmitting to a respective recipient device, distinct from the beacon device, a respective response message indicating knowledge of contents of the challenge message;
• the beacon device, a predetermined time period after transmission of the challenge message, transmitting a confirmation message to a message store, the confirmation message indicating knowledge of the contents of the challenge message such that a validation device can compare contents of each response message which preceded the confirmation message in time to contents of the confirmation message and infer therefrom which of the respective responder devices, if any, received the challenge message over the respective direct communication link;
• the beacon device receiving, from a device external to the beacon device, an external device challenge message portion;
• responsive thereto, the beacon device generating a beacon device challenge message portion;
• and
• responsive thereto, the beacon device constructing the challenge message as a non-separable function of two or more variables, the external device challenge message portion and the beacon device challenge message portion each comprising at least one of the variables,
• wherein transmitting the challenge message is responsive to constructing the challenge message.

A computer-implemented method performed by a beacon device, the method comprising:

• the beacon device transmitting a challenge message to each of one or more responder devices over a respective direct communication link, to invite each responder device to prove an existence of the respective direct communication link by transmitting to a respective recipient device, distinct from the beacon device, a respective response message indicating knowledge of contents of the challenge message;
• and
• the beacon device, a predetermined time period after transmission of the challenge message, transmitting a confirmation message to a message store, the confirmation message indicating knowledge of the contents of the challenge message such that a validation device can compare contents of each response message which preceded the confirmation message in time to contents of the confirmation message and infer therefrom which of the respective responder devices, if any, received the challenge message over the respective direct communication link,
• wherein the challenge message indicates a problem for the responder devices to solve and the confirmation message indicates one of the problem or a beacon device solution to the problem,
• and wherein at least one of:
• the beacon device determines the time period based on a predicted solving duration for a target solving device;
• the beacon device constructs the challenge message so that the problem has a predicted solving duration for a target solving device based on the predetermined time period;
• data in the challenge message indicating the problem comprise one or more codes constructed such that a predetermined threshold signal-to-noise ratio (SNR) is required at a responder device for the responder device to successfully decode them;
• the problem is dependent on a responder device identifier such that each response message indicates a different responder device solution;
• the beacon device constructs the confirmation message such that an outer problem must be solved to obtain the problem from the confirmation message;
• transmitting the challenge message comprises transmitting a plurality of temporally-separated challenge message fractions, constructed such that all of the challenge message fractions must be received in order to obtain the problem;
• the direct communication links are radio communication links, transmitting the challenge message comprises encoding the challenge message on one or more radio transmissions, the beacon device comprises directional transmission means and transmitting the challenge message comprises transmitting the challenge message in a first predetermined direction, and the method further comprises, before transmitting the confirmation message to the message store, the beacon device transmitting one or more directed repetitions of the challenge message in one or more respective further predetermined directions such that data relating to the location of each of the responder devices can be inferred from timings of each response message with respect to times the challenge message and the directed repetitions of the challenge message were transmitted;
• or
• the beacon device, prior to or at the same time as transmitting the challenge message, provides some but not all of the responder devices with an information advantage to assist with solving the problem.

A computer-implemented method performed by a beacon device, the method comprising:

• the beacon device transmitting a challenge message to each of one or more responder devices over a respective direct communication link, to invite each responder device to prove an existence of the respective direct communication link by transmitting to a respective recipient device, distinct from the beacon device, a respective response message indicating knowledge of contents of the challenge message, wherein the direct communication links are optical fiber communication links and transmitting the challenge message comprises encoding the challenge message on an optical signal;
• and
• the beacon device, a predetermined time period after transmission of the challenge message, transmitting a confirmation message to a message store, the confirmation message indicating knowledge of the contents of the challenge message such that a validation device can compare contents of each response message which preceded the confirmation message in time to contents of the confirmation message and infer therefrom which of the respective responder devices, if any, received the challenge message over the respective direct communication link,
• wherein there are a plurality of responder devices and transmitting the challenge message comprises:
• encoding the challenge message as a series of qubits or qudits, each qubit or qudit of the series being a weak coherent optical pulse or a single photon,
• stochastically directing each qubit or qudit of the series to a respective one of the responder devices, and
• repeating transmission of the series of qubits or qudits in this way, such that responder devices can decode the complete challenge message after multiple repetitions.

A computer-implemented method performed by a beacon device, the method comprising:

• the beacon device transmitting a challenge message to each of one or more responder devices over a respective direct communication link, to invite each responder device to prove an existence of the respective direct communication link by transmitting to a respective recipient device, distinct from the beacon device, a respective response message indicating knowledge of contents of the challenge message;
• the beacon device, a predetermined time period after transmission of the challenge message, transmitting a confirmation message to a message store, the confirmation message indicating knowledge of the contents of the challenge message such that a validation device can compare contents of each response message which preceded the confirmation message in time to contents of the confirmation message and infer therefrom which of the respective responder devices, if any, received the challenge message over the respective direct communication link;
• and
• the beacon device either engaging in or eschewing subsequent two-way communication with each of the one or more responder devices over the respective direct communication link, in dependence on the existence and the timing of a respective response message.

A computer-implemented method performed by a responder device, the method comprising:

• the responder device receiving a challenge message comprising a beacon device problem portion from a beacon device over a direct communication link, the challenge message inviting the responder device to prove an existence of that direct communication link by transmitting to a recipient device a response message indicating knowledge of the challenge message;
• the responder device receiving, from a device external to the beacon device, over a further direct communication link, an external device problem portion message comprising an external device problem portion, the external device problem portion message inviting the responder device to prove the existence of the further direct communication link by transmitting to the recipient device a response message indicating knowledge of the external device problem portion message;
• the responder device solving a problem constructed as a non-separable function of two or more variables, the external device problem portion and the beacon device problem portion each comprising at least one of the variables;
• and
• the responder device transmitting a response message comprising a solution to the problem, such that the responder device can be validated as having direct communication links with both the beacon device and the external device by:
• comparing contents of the response message to contents of:
• a confirmation message transmitted by the beacon device indicating knowledge of the contents of the challenge message, the confirmation message having been transmitted by the beacon device to a message store a predetermined time period after transmission of the challenge message;
• and
• a further confirmation message transmitted by the external device indicating knowledge of the external device problem portion, the further confirmation message having been transmitted by the external device to a further message store a predetermined time period after transmission of the external device problem portion message;
• and
• inferring that:
• the responder device received the challenge message over the direct communication link;
• and
• the responder device received the external device problem portion over the further direct communication link.