# US 10,484,186 B2 · Cascading multivariate quadratic identification schemes for chain of trust > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,484,186 B2 - Document ID: US10484186B2 - Status: Granted - Kind: B2 - Application number: 15/281,262 - Filed: 2016-09-30 - Published: 2018-04-05 - Granted: 2019-11-19 - Earliest claimed: 2016-09-30 - Assignees: Intel Corporation - Applicants: Intel Corporation - Inventors: Brent M. Sherman - Web page: https://patentgrep.com/patent/US10484186B2 ## CPC - H04L 9/3271: {using challenge-response} - G06F 21/572: {Secure firmware programming, e.g. of basic input output system [BIOS]} - H04L 9/007: {involving hierarchical structures} - H04L 9/3218: {using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs} - G06F 2221/2103: Challenge-response - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method, computing system, and computer-readable medium comprising instructions to establish a chain of trust for components of a computing environment. A respective public/private key pair is generated using a multivariate quadratic function F for each component of the computing environment. In response to a challenge from a verifier, a current prover component sends a response that the verifier uses to determine whether to trust the current prover component. The response may include a first commitment value and a second commitment value, which are determined for the current prover component using a public key of a previous prover component. At least one of the first and second commitment values can be determined using a polar function G, which is a polar form of the multivariate quadratic function F. ## Claims ### Claim 1 A system comprising: at least one hardware processor to execute instructions; at least one non-transitory storage medium including instructions that when executed by the processor enable the system to generate a respective public/private key pair for each component of a plurality of components of a computing environment using a multivariate quadratic function F, determine a first commitment value and a second commitment value for a first component of the plurality of components in the first component using a public key of a respective public/private key pair for a previous component, including to determine at least one of the first and second commitment values for the first component using a polar function G, wherein the polar function G is a polar form of the multivariate quadratic function F, provide the first commitment value, the second commitment value and the public key of the respective public/private key pair for the previous component to a verifier in response to a challenge from the verifier, and add the first component to a chain of trust for the computing environment if the first commitment value is equal to a first expected commitment value and the second commitment value is equal to a second expected commitment value. ### Claim 2 (depends on 1) The system of claim 1, wherein the at least one non-transitory storage medium further comprises instructions that when executed enable the system to calculate the first and second commitment values as a hash function of at least the public key of the previous component. ### Claim 3 (depends on 1) The system of claim 1, wherein the at least one non-transitory storage medium further comprises instructions that when executed enable the system to break the chain of trust for the computing environment if the first and second commitment values are not equal to the first expected commitment value and the second expected commitment value. ### Claim 4 At least one non-transitory computer-readable medium comprising instructions that, when executed by a processor, cause a computing system to: generate a respective public/private key pair for each component of a plurality of components of a computing environment, wherein each respective public/private key pair is generated using a multivariate quadratic function F; provide a response from a first component of the plurality of components to a challenge from a second component of the plurality of components, wherein the response comprises at least a first commitment value and a second commitment value, wherein each of the first and second commitment values is determined using a public key of a respective public/private key pair of a third component of the plurality of components, and at least one of the first and second commitment values is determined using a polar function G, wherein the polar function G is a polar form of the multivariate quadratic function F; and add the first component to a chain of trust for the computing environment if the first commitment value is equal to a first expected commitment value and the second commitment value is equal to a second expected commitment value. ### Claim 5 (depends on 4) The at least one non-transitory computer-readable medium of claim 4, wherein the third component has provided a previous response to a previous challenge from the first component. ### Claim 6 (depends on 4) The at least one non-transitory computer-readable medium of claim 4, wherein the first and second commitment values are determined as a hash function of at least the public key of the respective public/private key pair of the third component. ### Claim 7 (depends on 4) The at least one non-transitory computer-readable medium of claim 4, wherein the first expected commitment value and the second expected commitment value are provided by the first component to the second component prior to receiving the challenge from the second component. ### Claim 8 (depends on 4) The at least one non-transitory computer-readable medium of claim 4, wherein the first component is not added to the chain of trust for the computing environment if the first commitment value does not equal the first expected commitment value or the second commitment value does not equal the second expected commitment value. ### Claim 9 (depends on 4) The at least one non-transitory computer-readable medium of claim 4, wherein providing the response from the first component comprises providing the response on behalf of the first component by a trusted container or sandbox within the computing environment. ### Claim 10 At least one non-transitory computer-readable medium comprising instructions that, when executed by a processor, cause a computing system to: generate a secret key si for a component, of a computing environment; calculate a public key vi, wherein the public key vi is a multivariate quadratic function F of the secret key si, wherein v F(si), i represents a current prover i, and vi is a public key for the current prover i; determine a value for each element of a tuple using the secret key si the multivariate quadratic function F, and a polar function G, wherein the polar function G is a polar form of the multivariate quadratic function F; calculate a first commitment value and a second commitment value, wherein calculating the first and second commitment values comprises using a string commitment function, at least one element of the tuple and a public key vi−1, wherein i−1 represents a previous prover i−1, vi−1 is a public key for the previous prover i−1, and vi−1 is determined as the multivariate quadratic function F of a corresponding secret key for the previous prover i−1; provide the public key vi−1 and the first and second commitment values to a verifier; and add the component to a chain of trust for the computing environment if the first and second commitment values are equal to a first expected commitment value and a second expected commitment value. ### Claim 11 (depends on 10) The at least one non-transitory computer-readable medium of claim 10, wherein the instructions further cause the computing system to: provide a second tuple containing values for selected elements of the tuple in response to a challenge from the verifier; wherein the verifier uses the public key vi−1 to verify the current prover i if a first expected value matches one of the first and second commitment values, and a second expected value matches another one of the first and second commitment values. ### Claim 12 (depends on 10) The at least one non-transitory computer-readable medium of claim 10, wherein at least one of the first and second commitment values is determined using the polar function G. ### Claim 13 (depends on 10) The at least one non-transitory computer-readable medium of claim 10, wherein the component, is not added to the chain of trust for the computing environment if the first and second commitment values do not equal the first expected commitment value and the second expected commitment value. ### Claim 14 A method comprising: generating, in a computing system, a public/private key pair for each component of a plurality of components of the computing system, wherein each public/private key pair is generated using a multivariate quadratic function F; providing a response from a first component of the plurality of components to a challenge from a second component of the plurality of components, wherein the response comprises at least a first commitment value and a second commitment value, wherein each of the first and second commitment values is determined using a public key of a respective public/private key pair of a third component of the plurality of components and at least one of the first and second commitment values for the first component is determined using a polar function G, wherein the polar function G is a polar form of the multivariate quadratic function F; and adding the first component to a chain of trust for the computing system if the first commitment value is equal to a first expected commitment value and the second commitment value is equal to a second expected commitment value. ### Claim 15 (depends on 14) The method of claim 14, further comprising: breaking the chain of trust for the computing environment if the first commitment value does not equal the first expected commitment value or the second commitment value does not equal the second expected commitment value.