US-20260127254-A1 - AUTHENTICATION METHOD

US20260127254A1US 20260127254 A1US20260127254 A1US 20260127254A1US-20260127254-A1

Abstract

An authentication method is disclosed in which a knowledge graph is provided for a user, wherein nodes of the knowledge graph represent entities associated with the user and edges of the knowledge graph represent semantic relationships between the entities. The method involves selecting a first node of the knowledge graph, identifying a second node of the knowledge graph such that information associated with the second node has a higher expected obviousness to the user than to an attacker, and generating an authentication challenge for the user based on the information associated with the second node. Also disclosed are a corresponding data processing apparatus, computer program and computer-readable data carrier.

Inventors

Max SMITH-CREASEY
Jonathan ROSCOE

Assignees

BRITISH TELECOMMUNICATIONS PUBLIC LIMITED COMPANY

Dates

Publication Date: 20260507
Application Date: 20230919
Priority Date: 20221003

Claims (15)

1 . A computer-implemented authentication method comprising: providing a knowledge graph for a user, wherein nodes of the knowledge graph represent entities associated with the user and edges of the knowledge graph represent semantic relationships between the entities; selecting a first node of the knowledge graph; identifying a second node of the knowledge graph such that information associated with the second node has a higher expected obviousness to the user than to an attacker; and generating an authentication challenge for the user based on the information associated with the second node.
2 . A method according to claim 1 , further comprising receiving a successful response to the authentication challenge and authenticating the user.
3 . A method according to claim 1 , further comprising determining a path length and a count of paths between the first node and each node of a plurality of nodes of the knowledge graph other than the first node, wherein the second node is identified based on the determined path length and count of paths for each node of the plurality of nodes.
4 . A method according to claim 3 , wherein identifying the second node comprises: ranking each node of the plurality of nodes based on the path length and/or the count of paths; iterating through the plurality of nodes randomly or in order of the ranking until information associated with a candidate node of the plurality of nodes has a higher expected obviousness to the user than to the attacker; and selecting the candidate node as the second node.
5 . A method according to claim 3 , wherein identifying the second node comprises: ranking each node of the plurality of nodes based on the path length and/or the count of indirect paths; randomly selecting candidate nodes of the plurality of nodes having a ranking in a predetermined top percentile range until a candidate node is selected for which information associated with the candidate node has a higher expected obviousness to the user than to the attacker; and selecting the candidate node as the second node.
6 . A method according to claim 1 , wherein identifying the second node comprises determining an expected attacker obviousness value and verifying that the expected attacker obviousness value is less than a predetermined attacker obviousness threshold value.
7 . A method according to claim 1 , wherein identifying the second node comprises determining an expected user obviousness value and verifying that the expected user obviousness value is greater than a predetermined user obviousness threshold value.
8 . A method according to claim 1 , wherein identifying the second node comprises: identifying a plurality of nodes in the knowledge graph, other than the first node, associated with information having an expected user obviousness value that is greater than a predetermined user obviousness threshold value and an expected attacker obviousness value that is less than a predetermined attacker obviousness threshold value; and selecting one of the plurality of nodes as the second node.
9 . A method according to claim 8 , wherein selecting one of the plurality of nodes as the second node comprises selecting a node of the plurality of nodes associated with information having a lowest expected attacker obviousness value.
10 . A method according to claim 8 , wherein selecting one of the plurality of nodes as the second node comprises selecting a node of the plurality of nodes at random.
11 . A method according to claim 1 , wherein expected obviousness to the user and/or expected obviousness to the attacker is based on at least one of: a category of the first node and the second node, an entry time of at least one of the first node and the second node, a total number of direct connections between the first node and the second node, a total number of indirect paths between the first node and the second node, and a path length between the first node and the second node.
12 . A method according to claim 1 , wherein selecting the first node comprises calculating a centrality value for each node in the knowledge graph and selecting a node having the highest centrality value as the first node.
13 . A data processing apparatus comprising one or more processors configured to perform the method of claim 1 .
14 . A computer program comprising instructions which, when executed by a computer, cause the computer to carry out the method of claim 1 .
15 . A computer-readable data carrier comprising the computer program of claim 14 .

Description

FIELD OF THE INVENTION The present disclosure relates to an authentication method. BACKGROUND Authentication is generally required whenever a user is granted access to a secure system or location. Most authentication methods confirm user identities by presenting the user with one or more authentication challenges which require the user to respond with something they know (e.g. a password or PIN), something they have (e.g. a one-time password) and/or something they are (e.g. biometric information). Multi-factor authentication techniques require at least two of these factors for successful authentication, such as a password known by the user and one-time token generated by a smartphone app. However, there are limitations to each of these factors. Knowledge-based factors require the user to remember special information such as a password, which is susceptible to being forgotten (e.g. if the user has not accessed a service for a prolonged period). Factors based on something a user has require the user to always carry a device or token with them, which can be inconvenient. Factors based on biometric information require access to specialist sensors such as fingerprint readers or facial recognition cameras, but not all systems have such capabilities. Accordingly, there is a need for authentication methods that do not require specialised hardware and do not require users to remember special information. SUMMARY OF THE INVENTION According to a first aspect of the invention, there is provided a computer-implemented authentication method comprising: providing a knowledge graph for a user, wherein nodes of the knowledge graph represent entities associated with the user and edges of the knowledge graph represent semantic relationships between the entities; selecting a first node of the knowledge graph; identifying a second node of the knowledge graph such that information associated with the second node has a higher expected obviousness to the user than to an attacker; and generating an authentication challenge for the user based on the information associated with the second node. The knowledge graph for the user may be any knowledge graph in which the nodes represent entities (such as people/objects/places/events/information/data/concepts etc.) and the edges represent semantic relationships between the entities (e.g. family/friendship/geographic proximity/ownership etc.). As an example, the knowledge graph may be generated based on data associated with a social media account of the user. The knowledge graph and/or the data contained therein may be retrieved or otherwise received from a database or other form of local or remote storage (e.g. local memory). The first node may be selected arbitrarily (e.g. if one of the nodes represents the user or the name of the user then this node may be selected) or the first node may be selected based upon a node attribute such as centrality or degree. For example, a centrality value may be calculated for each node in the knowledge graph and the node having the greatest centrality value may be selected as the first node. Alternatively, a degree value (number of edges each node has) may be calculated for each node and the node having the greatest degree value may be selected as the first node. Using the node with the highest centrality or degree as the first node increases the expected obviousness to the user (the user is more likely to know information associated with a central/highly connected node). The method may further comprise determining a path length and a count of paths (or indirect paths) between the first node and each node of a plurality of nodes of the knowledge graph other than the first node, wherein the second node is identified based on the determined path length and count of paths. The plurality of nodes of the knowledge graph other than the first node may include all nodes in the knowledge graph other than the first node, or it may include only a (proper) subset of all nodes other than the first node. When a subset of nodes is used, this subset may be chosen to include all nodes that are not directly connected to the first node and/or that are within a predetermined distance of the first node. An indirect path refers to any path between two nodes that goes via one or more nodes other than the first and second nodes (such paths by definition require at least two edges). To avoid double counting, the count of paths should preferably exclude cycles (i.e. paths that include the same edge more than once); such paths are referred to herein as non-cycling paths. The path length and count of indirect paths may be computed using any suitable method, such as Dijkstra's algorithm. The count of indirect paths may optionally be truncated to include only paths that are shorter than a predetermined maximum path length. The path length between any two nodes may be the shortest path between the nodes, or it may be an average (i.e. mean, median or mode) of all (non-cycling) paths be