Patent Description:
When secret data (such as secret key for encryption) is stored in secure" memory of the devices, attackers can still tamper with the "secure" memory using fault attacks. In fault attacks, values in a memory cell are altered, and an output of a secure function (e.g., in a secure element including the secure memory) that uses the secret data can be used to deduce the original secret data. Once the secret data is known to the attacker, she can use that to break the security of the relevant system, for example, by decrypting the ciphertexts encrypted with secret key(s), which are part of the recovered secret data. As other examples, an attacker could use the secret data in some authentication protocol to gain improper access to a resource. Such authentication could involve a digital signature using the improperly obtained secret data. Such an attack might occur when a phone is stolen or malware has been introduced.

The overall effectiveness of fault attacks as a method of hardware tampering and memory leakage makes them a widely-used technique for accessing private data stored on consumer devices. For example, fault attacks can be effective against RSA or elliptic curve Diffie-Helman techniques, as may be used in transport layer security (TLS). As such, a growing number of researchers are attempting to find coding schemes that protect data against the vulnerabilities of memory to fault attacks and similar forms of hardware tampering.

Such attacks can be partially addressed by using non-malleable codes, such that the secret data is stored by encoding with a non-malleable code. Such encoding does not need a key, and is thus different from encryption. Use of a non-malleable code can allow the secure element to detect whether tampering has been done, or result in a same output. However, non-malleable codes require a decoding function to be used in the secure element. It is possible that attacker malware can include or gain access to the decoding function, as well as include an encoding function. Such malware can recover the secret data using tampering. Existing protection techniques do not address such malware, and thus leave open vulnerabilities.

Embodiments described herein address these and other problems, individually and collectively.

"<NPL>) describes constructions of leaky space-bounded non-malleable codes based on proof of space. "<NPL>) describes constructions of proof of space from stacked expander graphs.

According to a first aspect, there is provided a method as defined by appended claim <NUM>. According to a second aspect, there is provided a device as defined by appended claim <NUM>.

Embodiments of the disclosure include systems, methods, and apparatuses for protecting a secret on a device with limited memory, while still providing tamper resistance. In particular, embodiments can protect the secret from continuous space-bounded tampering, in which tampering is done repeatedly by a small attacker that has limited available computational space and memory. To achieve security, an encoding computer applies a memory-hard function MHF to a secret S that is to be protected and determines a result Y. The encoding computer then determines a proof π for the result Y, to later prove that the result Y was computed with the secret S. The proof π may be a non-interactive proof of space, with an additional property of proof-extractability. Applying the memory-hard function and determining the proof π may take a large amount of space (e.g., on the order of gigabytes or terabytes). Then, the encoding computer sends a codeword C comprising the secret S and the proof π to a decoding computer. The decoding computer then stores the codeword C in persistent memory.

When the decoding computer wants to use the secret S, for example, to apply a cryptographic function to the secret S, the decoding computer retrieves the codeword C and parses the secret S and the proof π. The decoding device uses transient memory to decode the codeword C by verifying the proof π was generated with the secret S and the result Y. The decoding may be performed with a small amount of memory, much less than the encoding. When the correctness of the result Y is verified, the decoding device applies a cryptographic function to input data using the secret S (e.g., digitally signing a message). If the correctness of the result Y is not verified, this can indicate to the decoding computer that the codeword C has been tampered. The decoding computer can then self-destruct to prevent further tampering attempts. After decoding the codeword C, the decoding computer resets the transient memory to clear information about the secret S. A small amount of data is persisted in an extra-persistent space in the persistent memory.

According to one embodiment, a method decodes a secret on a decoding computer. A codeword C is stored in a persistent memory of the decoding computer. The codeword C comprises a proof value π and a secret S, and uses c bytes of memory. The persistent memory comprises P bytes of memory. The proof value π is determined using the secret S and a result Y, the result Y obtained by applying a memory-hard function MHF to the secret S or to a function of the secret S. Applying the memory-hard function MHF to the secret S requires at least N bytes of memory. More than one proof value is combinable with secret S to provide a valid codeword. P-c memory of the decoding computer forms an extra-persistent space. The method then includes receiving input data, retrieving the codeword C from the persistent memory, and parsing the codeword C to identify the proof value π and the secret S. A decoding of the codeword C is performed, using a transient memory of the decoding computer. The decoding of the codeword C is done by using the proof value π to verify a correctness of the result Y as being obtained from memory-hard function MHF using the secret S. The decoding function is operable to use K bytes of memory, and K is less than N. When the correctness is true, a cryptographic function is applied to the input data using the secret S to obtain output data. When the correctness is false, an error message is provided and the decoding computer is made inoperable to perform subsequent decoding operations. Then the transient memory of the decoding computer is refreshed. E bytes of memory of the decoding are persisted on the extra-persistent space. E is less than N and less than the size of the result Y.

These and other embodiments of the invention are described in detail below. For example, other embodiments are directed to systems, devices, and computer-readable media associated with methods described herein.

Further details regarding embodiments of the invention can be found in the Detailed Description and the Figures described herein.

"Non-malleable code(s)" (NMC) may refer to a coding scheme for which decoding a codeword that has been altered (e.g. by a tampering adversary) results in either the original (unaltered) message or a completely unrelated value from which no knowledge can be inferred.

"Space-bounded," "memory-bounded," or "memory-hard function" (MHF) may describe a function or task where the time needed to complete the task is mainly determined by the amount of usable memory required. For example, for a space-bounded computational problem, the efficiency of the particular computational process may be most affected by the rate at which data can be read and stored into memory (i.e. memory bandwidth) rather than by the clock speed of the processor. A memory hard function requires a certain number of storage bits to be performed. Strict memory hard hashing functions are an example of a memory-hard function. A memory-hard function needs time T and space S for ordinary computation, but the amount of time increases greatly if the amount of available space is less than S.

"Verifiable computation" may refer to a procedure to efficiently check correctness of a computation without performing the computation itself. A goal can be to develop a verification procedure that is much more resource (space/time)-efficient than the target computation itself. For example, one may consider a memory-intensive computation on a huge database over a cloud-server. A client wants the server to perform some computation (e.g. aggregation) on the database and can use verifiable computation to check whether the result is correct without performing the actual operation on the data.

A "proof function" may refer to a function that produces a "proof value" that can be used to verify a computation. The proof value may be succinct in that it can be computed with relatively low memory (space), thereby allowing the decoding to be produced in low space. The use of a MHF during encoding can ensure that high memory is required, even when the proof function itself can be performed in low memory.

A "verification function" may refer to a procedure for using a proof value to confirm that a code C is generated from a secret S by a specified encoding function.

A "security parameter" may refer to a fundamental system parameter that is specified according to the desired security level. All other metrics (for example, running time, memory required etc.) of a scheme may be measured in terms of the security parameter.

A "randomized algorithm" may refer to a computation that uses random bits extracted from a trusted source of randomness. The output of such an algorithm, on a particular input, can follow a probability distribution.

A "deterministic algorithm" may refer to a computation that does not use any randomness, and the output of such algorithm, on a particular input, is fixed as it is determined only by the input.

A "secure element" is a tamper-resistant platform (e.g., a one chip secure microcontroller) capable of securely hosting applications and their confidential and cryptographic data (e.g. key management) in accordance with the rules and security requirements set forth by a set of well-identified trusted authorities. Example form factors include Universal Integrated Circuit Card (UICC), embedded SE and microSD.

Sensitive data, such as secret keys, that is stored on a secure element of a device is still vulnerable to tampering. In particular, an attacker can modify the secret key on the secure element, such that when the secret key is used later it reveals information to the attacker. For example, a user can encrypt a message using the tampered secret key, where the encrypted output can be used to determine information about the original secret key.

Some attacks can be prevented by using space-bounded non-malleable codes to protect secret data. The secret is encoded as a codeword with an encoding function that takes a large amount of space to compute, and thus must be done outside of the device. The codeword can be decoded on the device in a small amount of space (e.g., orders of magnitude smaller than the encoding space). However, such solutions are only secure for a limited number of tampering attacks. The leakage is proportional to the number of attacks, so over time the entire secret can be discovered. An attacker could generate all possible combinations for a known decoder, and thus can determine which secret was used after sufficient leakage.

Some embodiments can protect data against tampering attacks, by using non-malleable codes, where the leakage is proportional to the logarithm of the number of tampering attacks. Thus, even with a large number of attacks, a small amount of information is leaked. To do so, a secret can be encoded with a non-interactive proof of space (NIPoS) that is proof-extractable. There may not be a one-to-one correspondence between secret and proof, so it is more difficult to completely explore the space of secret-proof pairs, since the possible combination is much larger, while still only having a relatively few proofs per secret that will actually work. Otherwise, an attacker could use an external device to determine all possible codewords, and then identify which one provides the same ciphertext output for a given input.

Such proofs can be constructed in a number of ways, including using graph labeling and challenge-hard graphs. As a result of using a proof-extractable NIPoS, an attacker that attempts to falsify a proof may need to compute numerous secret-proof pairs (codes) outside of the memory available for tampering (tampering space) on the device and use fault attacks to try possible codes before possibly gaining access to the secret. The number of secret-proof pairs that can be leaked is bounded by the available tampering space, and the description size of the tampering virus. Embodiments can also include a "self-destruct" mechanism. As an example, the "self-destruct" mechanism can cause the small-space device (e.g., a secure element) to erase its entire state (or make it non-functional) once a tampering is detected.

Some embodiments can preclude an attacker from partially computing the proof outside the device and then finishing computing the proof inside the device using a tampering virus that can access the secret S. For example, there can be some persistent space that stores the code (the secret S and the proof π) and some transient space used in the decoding that is refreshed periodically (e.g., after every valid decoding). If tampering is detected by the decoder, then the secure element can become unusable. A small amount of the persistent space ("extra-persistent space") is not taken up by the code and thus could be used to retain some information about a previous secret and proof. For example, the persistent space could be used to store previous codes that had been verified. Then, an attacker could analyze the previous codes (secrets-proof pairs) that have been verified to determine a relationship so that new valid codes could be generated at will. Once a code is verified by a decoder, the secrets of the various codes could then be used to encrypt known input data, where the encrypted output can be used explore the codeword space. However, the extra-persistent space can be made much smaller than the result that the proof π is derived from, thereby preventing sufficient leakage of information that could be used to determine the secret S.

Tampering of secure elements and non-malleable codes are first described below, followed by a description of NIPoS.

A mobile device may be provisioned with a secret sk for a variety of reasons. For example, the secret sk may be used as a secret key to encrypt communications. As another example, secret sk can be used for authentication purposes so that the mobile device can gain entry to a resource (e.g., a building, a computer, or an account). Depending on requirements, the mobile device can operate on input data (e.g., a challenge) using the secret sk to produce an authentication response when requested to an authentication computer.

<FIG> shows a mobile device <NUM> storing a secret (sk) <NUM> in a secure element <NUM>. Secure element <NUM> can store secret <NUM> in secure memory of secure element <NUM>. Secure element <NUM> can also include circuitry to perform a function <NUM>, identified as Fsk(·). Function <NUM> can operate on input <NUM> to provide output <NUM>. Mobile device <NUM> can then send output <NUM> to a recipient device <NUM>, which can decrypt output <NUM> to obtain input <NUM>.

Such an operation may occur when input <NUM> is to be encrypted and sent as output <NUM>, using secure <NUM> as an encryption key. Recipient device <NUM> could be previously provisioned with the same secret, potentially having initially provided the secret to mobile device <NUM>. As another example, recipient device <NUM> can provide input <NUM> as a challenge to mobile device <NUM>. Recipient device <NUM> can then compare output <NUM> to an expected result so as to authenticate mobile device <NUM>.

Unfortunately, an attacker can compromise a secure element, e.g., using a tampering function as a fault attack. Thus, the attacker can be a tampering function that was installed onto the mobile device. The tampering function can further infiltrate the secure element so that secret data is manipulated, thereby resulting in output data that can reveal the contents of the secret data. Accordingly, in such situations, repeated outputs of the secure element after tampering can be analyzed to reveal the secret data.

<FIG> shows a tampered secure element that may be inside a mobile device. Secure element <NUM> can perform a function <NUM> using a secret <NUM>. As shown, secret <NUM> has been tampered, illustrated as sk' resulting from an original secret sk. The tampering function A can be defined by sk' := A(sk). As examples, the tampering function A can result from malware infecting secure element <NUM> or a physical tampering, as may be done with a laser on the physical memory.

For example, an attacker may introduce faults to memory (e.g., flash memory or dynamic random-access memory (DRAM)) by selectively altering charge states of its capacitors (e.g. using a laser), and thus performing "bit flips" that cause leakage of a targeted row of bits in a memory cell between read and write operations (i.e., Rowhammer attacks). These types of attacks are especially prevalent in smaller devices, which have memory units designed specifically for minimal power consumption, such as smartphones, tablets, and other mobile personal devices.

Output <NUM> is generated from input <NUM> using function <NUM> and the stored secret, which is a tampered secret <NUM> (shown as sk') in this example. Since output <NUM> depends on the value of the stored secret, modifying the stored secret will affect output <NUM>. Accordingly, information about the original secret sk is leaked through output <NUM>. The sufficient set of data points for different inputs and outputs after multiple rounds of tampering, an attacker could reconstruct the original secret sk from the inputs and outputs. It would be advantageous to prevent such attacks.

The attacker's goal is to recover the secret. If a mobile devices is stolen, someone can use it but someone cannot recover the secret key as it is stored in a secure element. However, once they have tampered with the device and then try to use it, they will get a different kind of response from the device.

Tampering can be performed by physical means, such as using a laser to alter the secret. Such tampering causes the memory to actually store different values and therefore operate in a slightly different manner. The slight change in response can be compared to the original response and used to make conclusions about the secret. If you cause some sort of change in the device when it sends out a cryptogram or sends out another type of data message, it can differ in such a way that one is able to probe what the secret is. For example, if the first bit of a secret is zero, it will respond differently than if the first bit of the secret is one.

In one particular context, a mobile device may store a mobile payment application, and may subsequently have a secret stored somewhere in the application. An attacker can then rely on non-physical tampering means, such as by introducing malware to the application, to tamper with the secret stored therein. For example, the malware may blindly alter values sent to a trusted execution environment or hardware module.

Non-malleable codes can provide some level of protection from tampering attacks. For example, a secret message m can be encoded to provide a code c, which is stored. Even if the code is tampered, a decode function may still provide the secret message m. Or, the decode function can provide an error indicating that tampering was performed. If neither of these happens, then the decoded message can be one that is unrelated to the message originally encoded.

<FIG> shows the correctness property of non-malleable codes. A secret message m is encoded by encoding function <NUM> to obtain code c. A decoding function <NUM> decodes the code c to obtain the original secret message m when there is no tampering present.

<FIG> shows the non-malleability property of non-malleable codes. Again, the secure message m is encoded by encoding function <NUM> to obtain code c. But this time, an attacker <NUM> changes the code c to be code c'. As a result, decoding function <NUM> decodes code c' to get m'. The decoding process may be such that both code c and code c' decode to m, and thus m' equals m. In theory, the decoding function <NUM> can also include a verification function that can detect when m does not equal m', i.e., a detection. The value <NUM> indicates an error. But, how to determine such a verification function is not clear, particularly if the decoding function <NUM> needs to be performed on a mobile device. The error detection does not need to be perfectly accurate, as long as m' is unrelated to m, and thus no information can be obtained from an output generated using m'.

Thus, for non-malleable codes, an encoded message will either completely change when altered or not change at all, or an error will be detected. An example for error-detection code using verification of computation is algebraic manipulation detection (AMD) code (www. org/archive/eurocrypt2008/<NUM>/<NUM>. pdf or tampering-detection code.

An implementation of non-malleable codes in the context of a secret stored on a mobile device (e.g., as in <FIG>) is now described.

<FIG> show a use of non-malleable codes for protecting a secret stored in a secure element of a mobile device <NUM>. A secret (sk) <NUM> can be encoded by encoding function <NUM> to obtain a code c. Encoding function <NUM> can be implemented by a provisioning device outside of mobile device <NUM>. Examples of a provisioning device include a server that provisions over a network or a local device, e.g., via a direct wired or wireless connection (e.g., Bluetooth or WiFi). In various implementations, the provisioning can be performed by a manufacturer, a service provider (e.g., a cellular carrier), or a technician after a user has acquired the mobile device.

Code c can be provided to mobile device <NUM> and stored in secure element <NUM>. Secure element <NUM> can include circuitry (e.g., hardwired or programmable circuitry) for performing a function <NUM> (e.g., encryption) and for performing a decoding function <NUM>.

As part of executing an application (e.g., a authentication or encrypted communication), a processor (not shown) of mobile device <NUM> can provide input <NUM> to secure element <NUM> to obtain an output <NUM>, e.g., for sending to an external device. To generate output <NUM>, decoding function <NUM> retrieves code <NUM> from a secure memory and decodes code <NUM> to obtain the original secret <NUM>. Function <NUM> uses secret <NUM> to operate on input <NUM> to obtain output <NUM>.

A tampering class encompasses tampering functions/algorithms that a device can tolerate without exposing the underlying data. Typically, the encoding/decoding functions cannot tolerate all classes of tampering algorithms.

A popular tampering class is granular tampering. A secret can be encoded to get a codeword that has two parts, c1, c2. The two parts can be stored on a same device or two physically separate devices. The attack would have to be on the two different parts of codewords independently, with two different decoding functions that cannot see each other. The attacker knows there are two parts, but the tampering algorithms cannot contact each other because they are separated. The attacker may operate on one, but really needs both parts in order to expose information.

Another class is global tampering, which means that the attacker had access to the entire codeword. Such tampering classes assume that the attacked cannot decode or encode. In such a case, the attacker can only change the codeword a little bit and hope to decipher the original secret, which is very difficult. An example where the attacker cannot decode or encode is not provided.

<FIG> illustrates a benefit of using non-malleable codes in the context of storing a secret in a secure element for performing a cryptographic function. <FIG> shows the example implementations from <FIG> and <FIG> side-by-side.

Secure element <NUM> stores a secret sk for performing a function Fsk(·) on input <NUM> to obtain output <NUM>. Secure element <NUM> is susceptible to tampering attacks, as discussed above.

Secure element <NUM> stores a code c generated from secret sk using an encoding function. Secure element <NUM> decodes the code c to obtain the secret sk, which is then used for performing a function Fsk(·) on input <NUM> to obtain output <NUM>.

As shown, the code c has been tampered to obtain c'. Thus, the decoding function is shown outputting sk'. Assuming the attacker can only modify the code c, the value for sk' should provide three possibilities for an output.

For possibility <NUM>, sk' = sk, e.g., as the amount of change between c and c' is minimal, and thus the decoding function outputs the same value. For example, the decoding function can map more than one input to a same output. Such a procedure can be analogous to an "error-correction" mechanism, with one way to attain being adding redundancy into the codeword.

For possibility <NUM>, the decoding function can detect that the decoded value does not correspond to code c', and thus tampering is detected. If tampering is detected, the decoding function can output a predetermined error character of ⊥. How to determine such an inconsistency between code c' and the decoded value is described later.

For possibility <NUM>, the decoding function determines that c' and the decoded value are consistent with each other, but such a result should only be possible when sk and sk' are unrelated and thereby sk' does not reveal any meaningful information about sk. This may occur if the attacker overwrites the encoding of sk with an encoding of a known sk'; clearly in this case sk' is independent of sk as it is already known to the attacker. For a non-malleable code, if a single bit is altered when using an encoding algorithm, the response becomes completely unrelated to the original message, and thus introducing a fault could not be used to deduce the secret. Being "unrelated" covers both error-detection and correct decoding with an unrelated sk'. An attacker would be unable to isolate a change relating to a single bit-flip due to the non-malleable property of the code. In the case of malware introduced to an application, even if the malicious program were to override a secret stored in the application with its own secret, it would be unable to infer any information about the original secret.

Secure element <NUM> can still be susceptible to tampering attacks, e.g., if the attacker can perform encoding and decoding. The particular encoding and decoding techniques may be public, e.g., as part of a standard. Thus, it is feasible that an attacker could generate malware that performs these functions.

Intuitively, an encoding scheme (Encode, Decode) is called non-malleable with respect to a class of tampering adversaries (modeled as functions or algorithms) <IMG> if for any adversary A ∈ <IMG> and any message x, the output Decode ∘ A ∘ Encode(x) is independent of x, unless it is equal to x. It is straightforward to see that <IMG> cannot contain all efficiently computable functions because in that case it is always possible to just decode a codeword c to x, modify (for example add <NUM>) and re-encode x + <NUM>; hence one must consider a restricted class <IMG> that excludes functions able to encode. Therefore, one can focus on constructing encoding schemes that are non-malleable against a meaningful, broad class of tampering functions; notice that non-malleability against a broader <IMG> translates to protection against stronger tampering attacks.

In one type of attack, an adversary can be separated into two parts: a "big adversary" which is a probabilistic polynomial time (PPT) adversary with no space-bound, and a "small adversary" (e.g. malware) that is a space-bounded poly-time adversary. The big adversary can begin interacting with a challenger (e.g., a decoding device), and then output small adversaries which will then have access to a target codeword (or proof) and execute tampering in a space-bounded manner. If the small adversary has a huge description, it might not even fit into a small-space device (e.g. a mobile device), let alone executing tampering. So, it may be reasonable to assume that such adversary has a bounded size description. In particular, a class of space-bounded adversaries can be defined as <MAT> containing all poly-time adversaries that have a description of size at most f -bit and which require at most s-bit to execute.

One interesting tampering class is space-bounded tampering, in that the only restriction on <IMG> is that any (efficient) tampering algorithm in this class can only use a limited amount of memory. Space-bounded tampering captures the essence of mauling attacks performed by malware that infect small-space devices like mobile devices. However, for such tampering class, it is unreasonable to assume that a tampering algorithm cannot decode. For example, if decoding requires more space than what is available for the attacker, then the encoded secret becomes unusable inside the device. The encoding algorithm, on the other hand, can be reasonably space-intense and performed outside the device. Therefore, it is possible to assume the space-bounded adversary cannot perform encoding, therefore avoiding the aforementioned impossibility.

Moreover, even if <IMG> includes only Decode, "full-fledged" non-malleability is still not achievable. To see this, consider an attacker that decodes c, learns the message x and based on the first bit of x overwrites the memory of the device with a precomputed encoding - leaking the first bit (this can be extended to an attack that leaks any log(|x|) bits by tampering once). However, it may be possible to guarantee that the leakage is "not too much". This weaker notion may be defined as leaky non-malleability, which guarantees that an encoding scheme satisfying the notion would leak only a limited amount of information about x. Some encoding techniques may be use leaky non-malleability to resist tampering for a bounded number of attacks. That is, they can leak some information about the message x, but if more than a predetermined number of tampering attacks occur, the entire message x can be compromised. It is thus desireable to have an encoding scheme that is resistant to continuous attacks, where the number of tampering attacks is very large.

In some embodiments, the tampering algorithms can be assumed to be deterministic, sequential and (s, f)-total-space-bounded, where <MAT> are tunable parameters and are usually functions of the security parameter λ. The class of all such algorithms may be denoted by <MAT> or <IMG> for simplicity. Generally any <MAT> will be often referred to as a space-bounded tampering algorithm. In some embodiments, the tampering algorithm can be assumed to have access to the public parameter may not be explicitly hardwired inside A and hence it is neither accounted for in the bound f nor in s. The public parameter pp may be considered to be untamperable. In some embodiments, the public parameter pp can be part of a read-only memory to which the attacker does not have write access.

In some embodiments, if the parameter f is such that adversaries from <MAT> can have valid encodings (c<NUM>, c<NUM>) of two different messages hard-wired into their description, the leakage ℓ can be (approximately) at least as big as the size of the "extra persistent space" p - n, where p is the size of the persistent space and n is the size of the codeword. Otherwise, the distinguisher D can send a space-bounded adversary A with hard-wired (c<NUM>, c<NUM>), which first copies any p - n bits of the target message into the extra persistent space and then depending on the first bit of that overwrites the target encoding with c<NUM> or c<NUM>. Repeating this process, D learns the entire extra persistent space after only a few (θ ≈ p - n) tampering. Therefore, in some embodiments that allow sufficiently large f and any unbounded θ ∈ poly(λ), the leakage ℓ may contain p - n as an additive factor.

In an interactive proof-of-space (PoS) protocol, a prover P interactively proves that they have "sufficient amount of space/memory" to a space-bounded verifier V. The entire proof can be represented as one single string, e.g., πid, with respect to an identity id, allowing the prover P to non-interactively prove thay they have suffient amount of memory in a non-interactive proof-of-space (NIPoS). The verifier is able to verify the pair (id, πid) within bounded space. Extractability of NIPoS guarantees that given an honestly generated pair (id, πid), if a space-bounded "small adversary" A is able to compute another valid (i.e. correctly verified) pair (id', πid') such that id ≠ id', then id' can be efficiently extracted from random oracle queries made by the "big adversary" B (that has no space-restriction and may be represented by a PPT algorithm) given a "small hint".

Given a NIPoS, Faust et al. 's (Faust et al. , 2017a) encoding scheme works as follows. On input a message x, the space-intense encoding algorithm runs the prover of NIPoS on an identity x to generate a proof πx. The codeword c is the pair (x, πx). The space-bounded decoding algorithm, on receiving c = (x, πx), runs the (space-bounded) verifier. If the verification passes, it returns x, otherwise it returns ⊥ denoting the invalidity ofc. Intuitively, non-malleability follows from the guarantee provided by NIPoS; namely, whenever the small adversary tampers to a valid codeword (x', πx'), the new message x' must be independent of the input message.

To be slightly more formal, to show that this encoding scheme is non-malleable against space-bounded attacker, one needs to simulate the tampering experiment with "a small leakage" on x. Given the extractability, the simulator can be constructed as follows: the leakage is obtained using the "small hint". As guaranteed by the extractability of NIPoS, since the "small hint" (of length η, say) is sufficient to extract id', each tampering can be simulated by first obtaining the hint as a leakage and then running the NIPoS-extractor to obtain id'. Clearly, this strategy runs into problem for unbounded continuous tampering as the overall leakage ℓ becomes proportional to θ · η (where θ denotes the number of tampering queries).

At a high level, the NIPoS scheme is designed as follows. Let M be a memory-hard function and (Gen, Prove, Ver) a publicly verifiable scheme. The NIPoS prover on input id first queries the random oracle to obtain x: =<IMG> (id) and then runs the algorithm Prove on input x and outputs whatever the algorithm outputs, i.e. the value y: = M(x) and the proof of correct computation πvc. The NIPoS verifier on input id and the proof of space (y, πvc) first queries the random oracle to obtain x:= <IMG>(id) and the runs the algorithm Ver on input x, y, πvc and outputs whatever the algorithm outputs.

Intuitively, a NIPoS allows a prover to convince a verifier that she has a lot of space/memory. Importantly, the verification done on the verifier's side is space efficient.

A main building block of our NMC construction is Non-Interactive Proof of Space (for short NIPoS). Intuitively, a NIPoS allows a prover to convince a verifier that she has a lot of space/memory. Importantly, the verification done on the verifier's side is space efficient.

We start by recalling the definition of NIPoS from Faust et al. (Faut et al. , 2017a) adjusted to (s, f, t)-bounded algorithms. We split the definitions completeness and extractability here. Then we define property called proof-extractability. We made some syntactical changes to the definition of extractability to align it with the proof-extractability definition. Finally, we define a new quantitative measure of NIPoS called uniqueness and show that uniqueness, when combined with extractability gives proof extractability.

Definition <NUM> (Non-interactive proof of space (NIPoS)). For parameters <MAT> with sV ≤ s < sP an (kpos, npos, sP, sV)-non-interactive proof of space scheme (NIPoS for short) in the ROM consists of a tuple of PPT algorithms ( <MAT>) with the following syntax.

<IMG>(<NUM>λ): This is a randomized polynomial-time (in λ) algorithm with no space restriction. It takes as input the security parameter and outputs public parameters pppos ∈ {<NUM>,<NUM>}*. <MAT>: This is a probabilistic polynomial-time (in λ) algorithm that is sP-space-bounded. It takes as input an identity id ∈ {<NUM>,<NUM>}kpos and hard-wired public parameters pppos, and it returns a proof of space π ∈ {<NUM>,<NUM>}npos. <MAT>: This algorithm is sV-space-bounded and deterministic. It takes as input an identity id, hard-wired public parameters pppos, and a candidate proof of space π, and it returns a decision bit.

A NIPoS may have a completeness condition:
For all id ∈ {<NUM>,<NUM>}kpos, we have that <MAT> where the probability is taken over the internal random coins of the algorithms Setup and P, and over the choice of the random oracle.

We define the extractability of a NIPoS separately as follows.

Definition <NUM> (Extractability of NIPoS). Let NIPoS = (<IMG>) be an (kpos, npos, sP, sV)-non-interactive proof of space scheme. Let <MAT> and εpos ∈ [<NUM>,<NUM>) be parameters with sV ≤ s < sP. Then a NIPoS is (s, f, t, η, εpos)-extractable (Ext-NIPoS) if there exists a polynomial-time deterministic algorithm K (the knowledge extractor) and a deterministic efficiently computable function Fhint: {<NUM>,<NUM>}* → {<NUM>,<NUM>}η such that for any probabilistic polynomial-time algorithm B, we have <MAT> for the game <MAT> defined as follows:
Game <MAT>:.

where the set <IMG>(B) contains the sequence of queries of B to <IMG> and the corresponding answers, and where the probability is taken over the coin tosses of Setup, B, P and over the choice of the random oracle.

Note that, we made two changes from the one used in Faust et al. (Faut et al. , 2017a): first we introduce a new hint-producing function which can return a "small string" (for example, the index of ĩd in the RO table <IMG>(B)) and given that hint, the extractor can now find out the target identity from the same table. Secondly, the extractor here only returns the target identity instead of all identities found in the table (as done in Faust et al. (Faut et al. In embodiments, the parameter η may be small, as otherwise the definition is trivially satisfied. The final measure of leakage in the NMC construction can be controlled by the size of this hint.

The above discussion shows that we possibly need a stronger guarantee from the underlying NIPoS to make a CSNMC. Towards that, a stronger property of a NIPoS can be introduced called proof-extractability (PExt - NIPoS). It guarantees that, given a "small hint" (e.g., of length η'), it is possible to construct a stronger extractor that extracts not only the changed identity, but also the changed proof: (id', πid'). Intuitively, this means that if a small adversary computes a valid pair (id', πid'), then the "big adversary" must have computed the entire proof πid' (as opposed to a part of the proof as for NIPoS) outside the small-space device.

Extractability guarantees that if the space bounded adversary A successfully tampers to a new pair ( <MAT>, π̃), the identity <MAT> can be extracted from the query table of the algorithm B, i.e., the pair ( <MAT>, π̃) was (partially) precomputed by B. Knowledge of ĩd does not generally imply knowledge of the entire pair ( <MAT>, π̃). This is because there might be many different π̃ for which the verification is correct, unless, of course, there is a unique such π̃. In order guarantee extraction of the entire pair ( <MAT>, π̃), we need NIPoS to satisfy a stronger extractability property, called Proof-Extractability.

Definition <NUM> (Proof-Extractability of NIPos) Let NIPoS: = (<IMG>) be a (kpos, npos, sP, sV)-non-interactive proof of space scheme. Let <MAT> and εp-ext ∈ [<NUM>,<NUM>) be parameters such that sV ≤ s < sP. Then NIPoS is called (s, f, t, η, εp-ext)-proof extractable (PExt-NIPoS) if there exists a polynomial time deterministic algorithm K (the proof-extractor) and an efficiently computable deterministic function Fhint:{<NUM>,<NUM>}* → {<NUM>,<NUM>}η such that for any PPT algorithm B and any identity id ∈ {<NUM>,<NUM>}kpos, it holds that <MAT> for the game <MAT> defined as follows:
Game <MAT>:.

where the set <IMG>(B) is the random oracle query table of B. Note that B does not make RO queries after outputting the small adversary A. The probability is over the choice of the random oracle, and the coin tosses of Setup, B.

In the above definition, the hint-producing function takes the pair (ĩd, π̃) as opposed to only ĩd as in Definition <NUM>. Intuitively this means that, given some small hint, the extractor does not only return the changed identity, but the identity-proof pair. Clearly this makes the later definition stronger.

As mentioned above, when there is a unique valid proof corresponding to each identity, then proof-extractability reduces to simply extractability. Nevertheless, it may also be possible that only a part of the proof is uniquely determined. We formalize this by the following definition.

Definition <NUM> (Uniqueness of NIPoS) Let NIPoS: = (<IMG>) be a (kpos, npos, sP, sV)-NIPoS. Then NIPoS is called (upos, εunique)-unique (where upos ≤ <MAT> and εunique ∈ negl(λ)) if for any <MAT>, there is a deterministic function J:{<NUM>,<NUM>}* × {<NUM>,<NUM>}kpos → {<NUM>,<NUM>}upos such that for pppos ← <IMG>(λ), any identity id ∈ {<NUM>,<NUM>}kpos and any π ∈ {<NUM>,<NUM>}npos, if <MAT>, then J(pppos, id) = π[<NUM>. upos] with probability at least <NUM> - εunique (where the probability is over the randomnesses of<IMG> and <IMG>).

Intuitively, the definition can state that for a valid proof π,a part of π (first upos bits in this case) can be uniquely and efficiently determined given the id and the public parameters pp with overwhelming probability.

In the following lemma, we formally show that uniqueness and extractability together imply proof-extractability. To see this, observe that, e.g., maximal uniqueness implies that given ĩd, the corresponding πĩd is fixed and hence it suffices to provide the PExt - NIPoS hint-producer only with ĩd.

Lemma <NUM> Let NIPoS: = (<IMG>) be a (kpos, npos, sP, sV)-NIPoS that is (upos, εunique)-unique and (s, f, t, η, εpos)-extractable. Then NIPoS is (s, f, t, η', εp-ext)-proof-extractable where <MAT>.

Given the hint-producing function Fhint and the extractor K for the extractable NIPoS we construct a hint-producing function Fhint' and an extractor K' for proof-extractability as follows:.

It is clear that, whenever the standard extractor K is able to extract the correct ĩd, the proof-extractor will be able to extract the correct pair (ĩd, π̃) as the part of π̃ was uniquely derived by J and the rest of it is obtained from the additional hint. Therefore, the only case when K' would fail is exactly when (i) K fails or (ii) J fails. Hence we have εp-ext ≤ εpos + εunique. On the other hand, since Fhint' needs to output an additional hint of π̃[upos + <NUM>. npos] the hint η' is more than η by exactly npos - upos and hence we have η' = η + npos - upos. This completes the proof.

If a NIPoS has a special property, called uniqueness, then it satisfies proof-extractability. Intuitively, uniqueness means for a fixed identity id, there exists exactly one string πid such that πid verifies correctly with respect to id. Unfortunately, we do not know how to construct a NIPoS with such property (even under heuristic assumptions). Therefore, to have a more relaxed and fine-grained notion, we define uniqueness as a quantitative measure: a NIPoS has upos-uniqueness means that, for any identity id, the first upos bits of any valid πid are fixed and can be computed efficiently with overwhelming probability. Intuitively, the definition can state that for a valid proof π, a part of π (first upos bits in this case) can be uniquely and efficiently determined given the id and the public parameters pp with overwhelming probability.

Embodiments show that any NIPoS can be upgraded to a PExt - NIPoS if it has uniqueness, which we define as a quantitative measure of a NIPoS. Notice that the parameters of the resulting PExt - NIPoS (and consequently the CSNMC scheme yielded) is directly related to the uniqueness parameter of the starting NIPoS. For example, if a NIPoS has "maximal uniqueness", then the resulting CSNMC incurs "minimal leakage", which is equal to p - |c| bits, where p is the available (persistent) space. In embodiments, the entire space in the device is split into two parts, the persistent space which is reusable, and the transient space which is refreshed after each tampering. An impossibility shown in Faust et al. (Faut et al. , 2017a) restricts the persistent space to remain relatively small when θ is unbounded. In fact, the NIPoS used in Faust et al. (Faut et al. , 2017a) has poor uniqueness parameters and thus, when adapted to our proof-extractability technique, yields a CSNMC which suffers from a leakage that is as large as ≈ p - |x|.

<FIG> shows an example of an attacker not able to successfully perform an attack on an encoded secret stored in a device due to proof-extractability of the encoding function according to embodiments.

At block <NUM>, attacker A can generate a plurality of potential secrets id<NUM>, id<NUM>,. The attacker A can then generate a proof for each of the potential secrets π<NUM>, π<NUM>,. The attacker A can then compute a plurality of codewords c<NUM>, c<NUM>,. , cm using a the plurality of potential secrets id<NUM>, id<NUM>,. , idm and the plurality of proofs π<NUM>, π<NUM>,. The attacker A may have an unlimited ability to precompute and store proofs π<NUM>, π<NUM>,. The codewords c<NUM>, c<NUM>,. , cm, may then be provided to a space-bounded attacker. The number of codewords c<NUM>, c<NUM>,. , cm provided to the space-bounded attacker may depend on the size of the space bounded attacker. For example, each codeword c<NUM>, c<NUM>,. , cm may have a size of <NUM> MB and the space-bounded attacker may have <NUM> MB of space. The space-bounded attacker may tamper with the secure element of the device.

At block <NUM>, there may be a codeword c stored on the secure element of the device, comprising a secret key sk and a proof π. The secret key sk may be a random value (e.g., generated by a provisioning device) and the proof π may be generated by the provisioning device based on the secret key sk. The space-bounded attacker may then attempt to use one of the pre-computed codewords c<NUM>, c<NUM>,. , cm to affect the verification process on the device.

At block <NUM>, the output may be a codeword c' based on a secret id* and a proof π*. However, the space-bounded attacker may not be able to use information about the secret key sk or the proof π on the secure element. Thus there are only two options: c = c', and the tampering was unsuccessful, or c' is verified and output because it was based on a valid pair submitted by the attacker A and has no relationship to the secret key sk. The space-bounded attacker does not have enough space to modify the secret key sk and generate a new proof. The space-bound attacker also may not be able to use part of a proof to generate a valid proof based on the secret key, because the non-interactive proof of space is proof-extractable.

Memory hard functions may be based on graph labeling or graph pebbling. The graph labeling or pebbling may be done using directed acyclic graphs (DAGs).

<FIG> shows an example of a graph with <NUM> nodes. Each node may have a number. There may be a hash function H. The nodes in the bottom layer of the may be labeled by hashing the number of the node with a secret id. For example, node <NUM> may be numbered as <NUM> and may have a label <NUM> of L<NUM> = H(id, <NUM>). Subsequent nodes on higher layers may be labeled with the secret id, the number of the node, and the label of all nodes on which the node depends. For example, node <NUM> may be numbered as <NUM> may have a label <NUM> of L<NUM> = H(id, <NUM>, L<NUM>, L<NUM>). This may continue for all nodes in the graph. Because each labeling depends on each of the labelings below it, it cannot be computed in parallel and each labeling must be stored simultaneously. Thus a full labeling L can be generated and stored. In order to generate the labeling L, the generating device must store the labeling of each graph. A proof π can then be generated based on the labeling L or the hash of the labeling L. The proof π may be generated with a probabilistic proof function. The proof function may select a number of challenge nodes, representing that the full labeling has been computed.

Labeling of a graph can be described. Let <IMG>: {<NUM>,<NUM>}* → <IMG> be a hash function (often modeled as a random oracle). The <IMG>-labeling of a graph G is a function which assigns a label to each vertex in the graph; more precisely, it is a function label: V → <IMG> which maps each vertex v ∈ V to a bit string label(v): = <IMG>(qv), where we denote by |{v(<NUM>),. , v(deg)}| = deg(v) and let <MAT>.

An algorithm A labels a subset of vertices W ⊆ V if it computes label(W). Specifically, A labels the graph G if it computes label(V).

Additionally, for m ≤ |V|, we define the <IMG>-labeling of the graph G with m faults as a function label: V → <IMG> such that, for some subset of vertices M ⊂ V of size m, <MAT> <MAT> label (v) = <IMG>(qv) for every v ∈ V\M, and label(v) ≠ <IMG>(qv) for every v ∈ M. Sometimes we refer to labeling with faults as partial labeling.

When <IMG> is modeled as a random oracle one can show an interesting property about graph labeling as we present next as a lemma that appeared in form of a discussion in Ling Ren and Srinivas Devadas. It is based on an observation previously made in Stefan Dziembowski et al. (Dziembowski et al.

Lemma <NUM> Suppose <IMG> is modeled as a random oracle. Let <IMG> be an (s, t)-bounded algorithm which computes the labeling of a DAG G with <MAT> faults. Then there exists an (s + m · <IMG>, t)-bounded algorithm <IMG> that computes the labeling of G without faults but gets m correct labels to start with (they are initially stored in the memory of <IMG> and sometimes called initial labels).

Intuitively the above lemma follows because the algorithm <IMG> can overwrite the additional space it has, once the initial labels stored there are not needed.

A pebbling game can now be described. The pebbling of a DAG G = (V, E) is defined as a single-player game. The game is described by a sequence of pebbling configurations P = (P<NUM>,. , PT), where Pi ⊆ V is the set of pebbled vertices after the i-th move. In our model, the initial configuration P<NUM> does not have to be empty. The rules of the pebbling game are the following. During one move (translation from Pi to Pi+<NUM>), the player can place one pebble on a vertex v if v is an input vertex or if all predecessors of v already have a pebble. After placing one pebble, the player can remove pebbles from arbitrary many vertices. The sequence P can be said to pebble a set of vertices W ⊆ V if W ⊆ Ui∈[<NUM>,T] Pi.

The time complexity of the pebbling game P is defined as the number of moves t(P): = T. The space complexity of P is defined as the maximal number of pebbles needed at any pebbling step; formally, s(P): = maxi∈[<NUM>,T]{|Pi|}.

Ex-post-facto pebbling of a DAG (in the random oracle model) can now be described. Let <IMG>: {<NUM>,<NUM>}* → <IMG> be a random oracle. Let <IMG> be an algorithm that computes the (partial) <IMG>-labeling of a DAG G. The ex-post-facto pebbling bases on the transcript of the graph labeling. It processes all oracle queries made by <IMG> during the graph labeling (one at a time and in the order they were made). Informally, every oracle query of the form qv, for some v ∈ V, results in placing a pebble on the vertex v in the ex-post-facto pebbling game. This provides us a link between labeling and pebbling of the graph G. The formal definition follows.

Let <IMG>: {<NUM>,<NUM>}* → <IMG> be a random oracle and <IMG> a table of all random oracle calls made by <IMG> during the graph labeling. Then we define the ex-post-facto pebbling P of the graph G as follows:
The initial configuration P<NUM> contains every vertex v ∈ V such that label(v) has been used for some oracle query (e.g. some query of the form <IMG>(··· ∥ label(v) ∥ ··· )) at some point in the transcript but the query qv is not listed in the part of the transcript preceding such query.

Assume that the current configuration is Pi, for some i ≥ <NUM>. Then find the next unprocessed oracle query which is of the form qv, for some vertex v, and define Pi+<NUM> as follows:.

Lemma <NUM> (Labeling Lemma (in the ROM)) Let <IMG>: {<NUM>,<NUM>}* → <IMG> be a random oracle. Let G be a DAG. Consider an (s, t)-bounded adversary <IMG> which computes the <IMG>-labeling of the graph G. Also assume that <IMG> does not guess any correct output of <IMG> without querying it. Then the ex-post facto pebbling strategy P described above pebbles the graph G, and the complexity of P is <MAT> <MAT>.

By definition of ex-post-facto pebbling, it is straightforward to observe that if <IMG> computes the <IMG>-labeling of the graph G, then the ex-post-facto pebbling P pebbles the graph. Since we assume that the adversary does not guess the correct label, the only way<IMG> can learn the label of the vertex v is by querying the random oracle. The bound on t(P) is immediate. Again, by definition of the ex-post-facto pebbling, there is no unnecessary pebble at any time. Thus, the number of required pebbles is equal to the maximum number of labels that <IMG> needs to store at once. Hence, the space bound follows directly from the fact that each label consists of <IMG> bits and that the algorithm <IMG> is s-space bounded.

We define a new family of "memory-hard graphs" called challenge-hard-graphs (CHG) and construct PExt - NIPoS for the class of space-bounded adversaries <MAT> from that. We provide two instantiations of CHG that may be used in embodiments, although other instantiations may be used as well. The first one extends the stack of local expanders (SoLEG) used by Ren and Devadas (Ren and Devadas, <NUM>), in the context of proof-of-space, and the second one uses the graph designed by Paul et al. (Paul et al. , <NUM>) and used by Dziembowski et al. (Dziembowski et al. Both of the constructions use standard graph-pebbling techniques to ensure memory-hardness (and challenge-hardness) and work in the random oracle model. Plugging-in these PExt - NIPoS constructions into the encoding scheme of Faust et al. (Faut et al. , 2017a), we obtain CSNMC schemes with "almost minimal leakage" ℓ ≈ p - |c|.

Recall that, special types of DAGs are used for memory-hardness and for constructing proof-of-space via graph-labeling games. Usually, labels not "compressible". In a graph-based proof of space constructions (e.g. Ling Ren and Srinivas Devadas (Ren and Devadas, <NUM>)), an honest prover computes the labeling of the entire graph ensuring the usage of significant amount of space. Small-space verification is done by checking the labels of a few randomly selected nodes (or challenge nodes) of the graph - this guarantees that the "small adversary" cannot put too many fake labelings (a. faults) without storing them and thereby ending up using less memory.

However, such verification leaves room for computing a small part of the proof inside the small-space device - for example, consider a multi-layered DAG (e.g. a stack of bipartite graphs), for which a "big adversary" computes the labeling of the entire graph except for a single node in the last layer, and the "small adversary" easily computes the label of the node inside the small-space device. As a result the entire proof cannot be extracted only from B's RO queries, making proof-extractability impossible.

To remedy this issue, we replace the traditional memory hard graphs with CHG, which contains another carefully chosen set of challenges and guarantees that, even if a "big adversary" computes the labeling of the entire graph except for a few nodes and send a bounded hint to the "small adversary", it is still infeasible to compute the labels of the new challenge nodes with a small-space device. Let us remark that such a guarantee is only possible when the small adversary has a small description size (i.e., the hint from the "big adversary" is small), as otherwise the small adversary, for example, can hard-code the entire labeling for whole graph including all possible challenges, making challenge hardness impossible.

Informally challenge-hard graphs satisfy the following property with respect to graph pebbling: with small budget on the number of pebbles available (for example if an algorithm is space-bounded) no pebbling strategy can put pebbles on multiple random challenge vertices of the graph in a reasonable amount of time. Thus for a challenge-hard graph comprising a plurality of challenge nodes, in addition to other graph nodes, determining a graph labeling for the plurality of challenge nodes may require at least N bytes of memory. The N bytes of memory may be available an encoding computer but not available to a small-space attacker. The plurality of challenge nodes may be randomly selected from the set of nodes that comprise the challenge-hard graph. Successfully determining a graph labeling for the plurality of challenge nodes may occur with exponential time. Put another way, a device with a small available space (e.g., space-bounded) may not have a way to successfully complete multiple challenge vertices of a challenge-hard graph in a reasonable time. The property should hold even if the player gets a few (but not too many) pebbles on arbitrary vertices at the beginning.

Challenge-hard graphs may be graphs where the entire labeling require a lot of space. A proof based on a challenge-hard graph may be produced with the entire labeling,. In some embodiments, the associated proof cannot be produced without storing the entire label, and the label may be the result of a memory-hard function. This may be in contrast to graph labelings based on other memory hard graphs, where the proof can be produced with only a portion of the graph labeling stored. This can better enforce space restrictions on the encoding process.

Challenge hard graphs are parameterized by the following variables:
Nc, β, N, τc, t, ε, where N is the size of the graph; τc is the number of challenge nodes, where all the challenges are in a pre-defined target set Vc; Nc is the size of the target set Vc; β · Nc = Ω(Nc) is the budget on the number of pebbles available; t is an upper bound on the running time of pebbling strategies; and ε is an upper bound on the winning probability of the pebbling challenge game.

Challenge Hard Graphs (NIPoS) can be defined as follows. A family of directed acyclic graphs <MAT> (with constant in-degree) is (β, Nc, N, τc, t, ε)-challenge-hard (where β ∈ (<NUM>,<NUM>) is a constant, and other parameters are functions of λ), if for every <MAT> and graph G = Gλ = (V, E) (with N = N(λ) vertices), there exist τc target sets (possibly with overlapping) <MAT> such that the union of the target sets <MAT> has Nc vertices, and the following property is satisfied:.

For any pebbling strategy B = (B<NUM>, B<NUM>) it holds that <MAT> where the pebbling game <MAT> is defined as follows. Game <MAT>:.

We define Nc/τc and N/Nc as the challenge sparseness and graph compactness of G.

Intuitively, challenge sparseness defines what fraction of the target nodes will be challenged. Graph compactness determines what fraction of all node in the graph are in the target set. These two metrics of CHG can affect the determination of the parameters of the NIPoS and the encoding schemes.

Some embodiments use localized expander graphs as well.

A (Nc, γ<NUM>, γ<NUM>)-bipartite expander, for <NUM> < γ<NUM> < γ<NUM> < <NUM>, is a DAG with Nc sources and Nc sinks such that any γ<NUM>Nc sinks are connected to at least γ<NUM>Nc sources. We can define a DAG G'Nc,kG,γ<NUM>,γ<NUM> by stacking kG ( <MAT>) bipartite expanders. Informally, stacking means that the sinks of the i-th bipartite expander are the sources of the i+<NUM>-st bipartite expander. It is easy to see that such a graph has Nc(kG + <NUM>) nodes which are partitioned into kG + <NUM> sets (which we call layers) of size Nc. A Stack of Localized Expander Graphs (SoLEG) is a DAG GNc,kG,γ<NUM>,γ<NUM> obtained by applying the transformation called localization (Ren and Devadas, <NUM>) on each layer of the graph G'Nc,kG,γ<NUM>,γ<NUM>.

Lemma <NUM> Let <IMG>: {<NUM>,<NUM>}* → <IMG> be a random oracle. Let GNc,kG,γ<NUM>,γ<NUM> be a SoLEG where β: = γ<NUM> - <NUM>γ<NUM> > <NUM>. Let P = (P<NUM>,. , Pt(P)) be a pebbling strategy that pebbles at least γ<NUM>Nc output vertices of the graph GNc,kG,γ<NUM>,γ<NUM> which were not initially pebbled, where the initial pebbling configuration is such that |P<NUM>| ≤ βNc, and the space complexity of P is bounded by s(P) ≤ βNc. Then the time complexity of P has the following lower bound: <MAT>.

Then the time complexity of P has the following lower bound: t(P) ≥ <NUM>kGγ<NUM>Nc.

Lemma <NUM> Let GNc,kG,γ<NUM>,γ2 be a SoLEG and <IMG>: {<NUM>,<NUM>}* → <IMG> be a random oracle. There exists a polynomial time algorithm <IMG> that computes the <IMG>-labeling of the graph GNc,kG,γ<NUM>,γ<NUM> in Nc<IMG>-space.

Now a PExt-NIPoS construction based on challenge-hard graphs can be described. The construction may satisfy proof-extractability.

The scheme consists of three algorithms (<IMG>) that use the following ingredients:
A DAG G = (V, E) with N = |V| vertices and maximal in-degree deg ∈ O(<NUM>), which has τc target sets [Note that the target sets can have overlapping parts, that is they may share some nodes] <MAT> such that <MAT> and Vc has Nc vertices.

A set of random oracles <MAT> defined as follows: <MAT> for every id ∈ {<NUM>,<NUM>}kpos; <MAT>; <MAT> takes as input a <MAT>-bit string and outputs a random challenge set check plus τc challenge nodes: <MAT>.

For simplicity of explanation, we assume that the output length of <IMG> is exactly <IMG> (where <IMG> ≥ τ · log|V| + τc · log|Vc|), and we define the corresponding challenge sets (check, chal) as the first τ · log|V| + τc · log|Vc| bits of the RO output. For ease of explanation, we assume that |V| and |Vc| are powers of <NUM>. Note that by a typical domain separation technique (e.g., used in Giuseppe Ateniese et al. (Ateniese et al. , <NUM>) and Mohammad Mahmoody et al. (Mahmoody et al. <NUM>)), we can instantiate the three random oracles using a unified random oracle <IMG>: {<NUM>,<NUM>}* → <IMG>.

The construction is presented in detail in <FIG>. We provide a high-level overview here. The prover first computes the labeling of a graph G = (V, E), and then commits the labeling using a Merkle tree. From the merkle root value φ̃ℓ, the prover computes the Fiat-Shamir challenge <IMG>(φ̃ℓ), which consists of two sets (check, chal). The set check contains τ random nodes in V, and the set chal has τc random nodes in a target set Vc ⊆ V. The proof is the Merkle tree opening paths for nodes in check ∪ pred(check) ∪ chal, where pred(check) are the parents of nodes in check.

In our PExt-NIPoS construction, the honest prover has to store the complete labeling of the graph G plus the entire Merkle tree, thus the size of the prover's space is <MAT> where <IMG> is the random oracle output length. On the other hand, the verifier only needs to store a single proof-of-space, which consists of a Merkle root value, two challenge sets, and τ · (deg + <NUM>) + τc tree paths. Since each tree path is of length logN, the size of the verifier's space is given by: <MAT>.

It is not hard to see that our PExt-NIPoS scheme satisfies completeness. We formally show that our NIPoS scheme satisfies proof extractability by proving the theorem stated next.

Theorem <NUM> Let λ be a security parameter. Suppose G: = Ghαrd is a (β, Nc, N, τc, t, εpeb)-challenge hard graph with indegree deg = O(<NUM>); <IMG>: {<NUM>,<NUM>}* →<IMG> is a hash function modeled as a random oracle; and ΠG is a (τc, τ, v)-Merkle-tree-based PExt-NIPoS scheme (defined in <FIG>) built upon G, where <MAT> For any <MAT> such that there exists a constant δ* ∈ (<NUM>,<NUM>) where s + f ≤ (β - δ* - <NUM>) · Nc · <IMG>, it holds that ΠG is a (kpos, npos, sP, sV)-NIPoS that is (s, f, t, η, εp-ext)-proof-extractable, (s, f, t, v, εp-ext)-proof-extractable, as long as <MAT> <MAT> where κ = τ · Nc · δ*/N. The polynomial factor in εp-ext depends on the number of RO queries made by the adversary. We refer to Inequality <NUM> for the exact probability upper bound.

To guarantee that the verifier space sV: = v · <IMG> is smaller than the tampering space s, we require τc to be significantly smaller than Nc/logN. Hence the underlying CHG may be at least Ω(logN)-challenge sparse (defined as Nc/τc).

If the big adversary B computes the graph labeling and the Merkle commitment herself, that is, the RO input-output pairs in (ĩd, π̃) are queried by B, then a knowledge extractor can extract (ĩd, π̃) from the query table of B.

Otherwise, we can bound the advantage of the proof extractability game by the advantage of a pebbling challenge game. By challenge-hardness of the graph, the probability that a space-bounded adversary A generates a new proof-of-space in time bound t is negligible.

We consider a restricted storage model where the adversary always stores the graph labels in their entirety before using them, that is, the adversary never compress the graph labels. We leave the proof of Theorem <NUM> in the general storage model (where the adversary can store arbitrary function of the graph labels) as an interesting open question.

To bound the advantage of proofextractability game, we first bound the probability of a few bad events. Conditioned on bad events do not happen, it is guaranteed that the space-bounded adversary A wins the game only if it outputs a (ĩd, π̃) such that i) the merkle root value φ̃ℓ ∈ π̃ is a commitment of a graph labeling that is mostly consistent with the <IMG>-labeling of graph G, and ii) π̃ contains the opening labels of a few random challenge nodes, that is, the challenge nodes set is unpredictable for A. Hence the winning probability can be naturally bounded by the advantage of a labeling challenge game, which in turn can be in transformed to a pebbling challenge game. And thus we can bound the advantage of proof-extractability game by the advantage of pebbling challenge game, which finishes the proof.

First note that a family of SoLEG (with constant in-degree) is already challenge hard if the number of challenge nodes (i.e., τc) satisfies that τc > (β + γ<NUM>) · Nc. However, the challenge sparseness of the graph (i.e., Nc/τc) is O(<NUM>) which too small for our application. We need a challenge-hard graph with Ω(logN)-challenge sparseness. We resolve this by constructing challenge-hard graphs with larger challenge sparseness by extending a family of SoLEGs. For ease of explanation, in the following we assume that Nc is divisible by τc. We note that a similar result holds if Nc/τc is not an integer.

<FIG> shows an example construction and verification of a NIPoS based on a labeling of a challenge-hard graph according to embodiments. The construction may be done by an encoding device (e.g., a provisioning device) and the verification may be done by a decoding device (e.g., a mobile device).

At block <NUM> the proof can be setup by the encoding device using algorithm <IMG>(<NUM>λ). The setup algorithm <NUM> can take as input a security parameter λ in form of <NUM>λ. It then outputs public parameters pppos. τc is the number of challenge nodes. N is the size of the graph. Nc is the size of the target set, and the challenge set is all of the challenges.

At block <NUM> the proof can be computed by the encoding device using proof algorithm <MAT>. The proof algorithm consists of a number of substeps.

At block <NUM>, the labeling l of the graph can be computed by the encoding device.

At block <NUM>, given the labeling l of the graph G, the encoding device can compute a Merkle commitment. The Merkle commitment may be a hash of the labeling l. In computing the Merkle commitment, the encoding device may compute a Merkle root.

At block <NUM>, the encoding device can determine the set of challenges using the secret id and the Merkle root φl. The set of challenges may be a set of nodes that will be used to verify the labeling l.

At block <NUM>, the encoding device can compute and output the proof π. The proof π may comprise the Merkle-root (i.e., the hash of the labeling l) and the two challenge sets (a check set check and a challenge set chal). A second component of the proof π can comprise the Merkle-tree opening paths for nodes that are in the union of the check set, in the predecessors of the check set, and the challenge set.

At block <NUM>, given public parameters pppos, identity id ∈ {<NUM>,<NUM>}kpos and a candidate proof-of-space π ∈ {<NUM>,<NUM>}npos, the decoding device can check the correctness of π with respec to id as follows:.

At block <NUM>, the decoding device can parse the proof π. In parsing the proof π, the decoding device can identify parts of the proof π, such as the Merkle root φl, the check set check and the challenge set chal, and the Merkle-tree opening paths for nodes that are in the union of the check set, in the predecessors of the check set, and the challenge set.

At block <NUM>, the decoding device can check the challenge check set. (check, chal) may contain a set of indexes of nodes that are to be checked. The set of indexes may be generated by applying the hash function to φl. This set may be checked to ensure that an attacker cannot change the set to falsify a result.

At block <NUM>, the decoding device can check the hash of each node in the check set against the hash of its parents. The decoding device can check the hashes by determining if the hash of each node is equal to the hash of its parents.

At block <NUM>, the decoding device can check all of the nodes in the check set, the parents of the check set, and the challenge set to verify that the labels have been computed correctly.

At block <NUM>, the decoding device can output a '<NUM>' if and only if all of the checks pass, indicating that the correctness is verified, otherwise it can output a '<NUM>'.

Some embodiments use a SoLEG based construction. Given <MAT> (where Nc/τc, is an integer), the challenge-hard graph Ghard is a τc-extension of a SoLEG. It consists of a SoLEG, τc gadget graphs, and edges from SoLEG's sink vertices to the gadget graphs.

For every i (<NUM> ≤ i ≤ τc), the ith gadget graph <MAT> consists of Nc/τc lines. For every j (<NUM> ≤ j ≤ Nc/τc), the jth line <MAT> (in <MAT>) consists of Nc/τc vertices and a path from the first vertex to the last vertex. For every j (<NUM> ≤ j ≤ Nc/τc), we denote by <MAT> the sink of <MAT>, the ith target set <MAT> is then defined to be <MAT>.

And we see that the union of the target sets <MAT> contains Nc vertices.

Besides the edges in the SoLEG and gadget graphs, there are also edges from SoLEG's sink vertices to the gadget graphs. In particular, for every i (<NUM> ≤ i ≤ τc) and every k (<NUM> ≤ k ≤ Nc/τc), the ((i - <NUM>)Nc/τc + k)-th sink vertex of the SoLEG has Nc/τc outgoing edges to the gadget graph <MAT>, where the jth (<NUM> ≤ j ≤ Nc/τc) outgoing edge points to the kth vertex of the jth line <MAT>.

Let GNc,kG,γ<NUM>,γ2 be the SoLEG, the number of vertices in Ghard is <MAT>.

It is easy to observe that the challenge sparseness is Nc/τc and the graph compactness of the graph is kG + Nc/τc for the above construction. We prove the following lemma about our construction.

Lemma <NUM> Let GNc,kG,γ<NUM>,γ<NUM> be a SoLEG with parameters <MAT>, γ<NUM>, γ<NUM> ∈ (<NUM>,<NUM>). Denote by β: = γ<NUM> - <NUM>γ<NUM> > <NUM> and ε: = <NUM> - β - γ<NUM> > <NUM>. For any <MAT> (such that Nc/τc is an integer), let Ghard: = (V, E) be the τc-extension of GN,kG,γ<NUM>,γ<NUM>. Then it holds that Ghard is ( <MAT>)-challenge hard.

Fix any adversary B = (B<NUM>, B<NUM>) and consider the pebbling challenge game <MAT>. Denote by P<NUM> ⊆ V the initial pebbled set output by B<NUM>. Denote by n<NUM>: = δ<NUM> · Nc the number of output vertices (in GNc,k,γ<NUM>,γ2) that were initially pebbled. For every i (<NUM> ≤ i ≤ τc), recall that the target subset <MAT> consists of Nc/τc lines, and we denote by ni: = δi · Nc/τc the number of lines that have at least one pebble on it (i.e., the lines whose intersection with P<NUM> are non-empty). Since |P<NUM>| ≤ β · Nc, by definition of the game, we have <MAT>.

By rewriting the second inequality, we have <MAT>.

For every i (<NUM> ≤ i ≤ τc), we define a random variable Xi G {<NUM>,<NUM>} for the ith challenge node: Denote by chali ⊆ Vc(i) the challenge node in the ith target set Vc(i); we set Xi: = <NUM> if the line that contains chali has no initially pebbled vertex (i.e., the line has no intersection with P<NUM>); and we set Xi: = <NUM> otherwise. We define <MAT>.

Note Pr[Xi = <NUM>] = <NUM> - δi (over the randomness of chali), and random variables {Xi}i∈[τc] are independent. Recall that ε: = <NUM> - β - γ<NUM> > <NUM>, thus by Hoeffding inequality, we have <MAT>.

Next we show that if <MAT>, then it takes at least t: = <NUM>kG · γ<NUM> · Nc steps to pebble all the challenge vertices, and hence finish the proof.

Claim <NUM> Denote by ε: = <NUM> - β - γ<NUM> > <NUM>. If the challenge set chai is chosen so that <MAT> then it takes the adversary B<NUM> at least t: = <NUM>kG · γ<NUM> · Nc steps to pebble all the challenge vertices.

First, we show that the adversary B<NUM> has to pebble at least X · Nc/τc output vertices (in GNc,kG,γ<NUM>,γ) to answer all challenges: For every i (<NUM> ≤ i ≤ τc), if Xi = <NUM>, then the line that contains chali has no initially pebbled vertex. Thus to pebble the sink node chali, the adversary has to pebble the vertices (on the line) step by step, which in turn requires the pebbling of the output vertices [(i - <NUM>) · Nc/τc + <NUM>,. , i · Nc/τc] of GNc,k,γ<NUM>,γ<NUM>. Since X = <MAT>, the adversary has to pebble at least X · Nc/τc output vertices in total.

Fix any adversary B = (B<NUM>, B<NUM>) and consider the pebbling challenge game <MAT>. Denote by P<NUM> ⊆ V the initial pebbled set output by B<NUM>. Denote by n<NUM>: = δ<NUM> · Nc the number of output vertices (in GNc,kG,γ<NUM>,γ<NUM>) that were initially pebbled. For every i (<NUM> ≤ i ≤ τc), recall that the target subset <MAT> consists of Nc/τc lines, and we denote by ni: = δi · Nc/τc the number of lines that have at least one pebble on it (i.e., the lines whose intersection with P<NUM> are non-empty). Since |P<NUM>| < β · Nc, by definition of the game, we have <MAT>.

For every i (<NUM> ≤ i ≤ τc), we define a random variable Xi G {<NUM>,<NUM>} for the ith challenge node: Denote by <MAT> the challenge node in the ith target set <MAT>; we set Xi: = <NUM> if the line that contains chali has no initially pebbled vertex (i.e., the line has no intersection with P<NUM>); and we set Xi: = <NUM> otherwise. We define <MAT>.

First, we show that the adversary B<NUM> has to pebble at least X · Nc/τc output vertices (in GNc,kG,γ<NUM>,γ<NUM>) to answer all challenges: For every i (<NUM> ≤ i ≤ τc), if Xi = <NUM>, then the line that contains chali has no initially pebbled vertex. Thus to pebble the sink node chali, the adversary has to pebble the vertices (on the line) step by step, which in turn requires the pebbling of the output vertices [(i - <NUM>) · Nc/τc + <NUM>,. , i · Nc/τc] of GN,kG,γ<NUM>,γ<NUM>. Since X = <MAT>, the adversary has to pebble at least X · Nc/τc output vertices in total.

Combining the above arguments, with probability at least <NUM> - exp(-<NUM> · ε<NUM> · τc) (over the choice of the challenge set), it takes at least t: = <NUM>kG · γ<NUM> · Nc steps to pebble all the challenge vertices, and thus the graph Ghard is (β, Nc, N, τc, <NUM>kG · γ<NUM> · Nc, exp(-ε<NUM> · τc))-challenge hard.

As observed by Stefan Dziembowski et al. , (Dziembowski et al. , <NUM>), the graph introduced by Paul, Tarjan and Celoni (Paul et al. , <NUM>), in short, PTC's graph, does satisfy challenge hardness. Adapting Theorem <NUM> of Stefan Dziembowski et al. (Dziembowski et al. , <NUM>), into the multiple challenge setting, we obtain the following lemma.

Lemma <NUM> Let <MAT> be a family of PTC's graph (DAG) with graph parameters Nc = Nc(λ), N: = NclogNc and in-degree <NUM>. Then for any <MAT> and any <MAT>, Gλ is (β, Nc, N, τc, ∞, (<NUM> - β)τc)-challenge-hard where β = <NUM>/<NUM>.

Two challenge-hard graph constructions, SoLEG-based and PTC's graph-based, can be compared. By setting ε = <NUM>-<NUM>, the pebbling budget β · Nc: = <NUM><NUM>, and time bound to be <NUM><NUM>, we calculate the concrete values of the other parameters.

Corollary <NUM> (CHG based on SoLEGs (concrete)). For the SoLEG-extension, to obtain <NUM>-bit security in the pebbling game (i.e., <MAT>), the challenge parameter τc can be approximated to <NUM><NUM>. For the pebbling budget bound β · Nc: = <NUM><NUM> and a typical time bound t: = <NUM><NUM>, the target set size Nc is no more than <NUM><NUM>, and the graph size N is about <NUM><NUM>.

Corollary <NUM> (CHG based on~PTC's graphs (concrete)). For the PTC's graph, for a typical <NUM>-bit security of the pebbling game (i.e., <MAT>), the challenge parameter τc can be approximated to ≈ <NUM><NUM>. For a typical pebbling budget β · Nc: = <NUM><NUM>, we have to set the target set size Nc to be <NUM><NUM>, and the graph size should be at least N: = <NUM><NUM>.

Some instantiations of PExt-NIPoS from CHGs can be discussed.

Corollary <NUM> (PExt- NIPoS from SoLEG-ext. (concrete)). Let us fix [We set the bound for εp-ext to be <NUM>-<NUM>] <MAT> and consider the NIPoS built upon SoLEG-based CHGs. To guarantee that sV ≤ s, the graph size of the SoLEG-based CHG is at least N ∦ <NUM>,<NUM>,<NUM>. The resulting NIPoS is a (kpos, npos, sP, sV)-NIPoS that is (s, f, t, η, εp-ext)-proof extractable, where (s, f, t, v ≈ 12KB, εp-ext)-proof extractable, where <MAT> <MAT>.

Corollary <NUM> (PExt-NIPoS from PTC (concrete)) Let us fix: <MAT> and consider the NIPoS built upon CHGs in Wolfgang J Paul et al. (Paul et al. To guarantee that sV ≤ s, the graph size of the CHG is at least N ∦ <NUM>,<NUM>,<NUM>,<NUM>. The resulting NIPoS is a (kpos, npos, sP, sV)-NIPoS that is (s, f, t, η, εp-ext)-proof extractable, where (s, f, t, v ≈ 4MB, εp-ext)-proof extractable, where <MAT> <MAT>.

Let us first give some intuition. Since the no (s, f, t)-bounded adversary can compute the function M on a random input <IMG>(id), B's best bet to make the output of the <MAT> is to either (i) compute another function, that is not memory-hard and "fake" the proof or (ii) guess the random-oracle output <IMG>(id) correctly. The probabilities are bounded by εvc and ≈ <NUM>/<NUM>k respectively for those events and hence the probability of <MAT> outputting <NUM> can be bounded by ≈ εvc + <NUM>-k.

In order to achieve reasonable security, the concrete parameters of these constructions may become impractical in some embodiments. For example, for a message of size 1MB, the size of a codeword is almost 800MB for the CHG-based NMC constructions (see Table <NUM>). To complement this, we propose a simple and practical instantiation of NIPoS based on heuristic assumptions. The construction uses a concrete instantiation of a memory-hard-function (MHF), and applies a (non-interactive) publicly verifiable computation where the verification requires small space. When the MHF is instantiated with the SoLEG-based construction of Ren and Devadas (Ren and Devadas, <NUM>), the resulting NIPoS has extractability and a "good measure of uniqueness". This yields a PExt - NIPoS with very good parameters and, consequently, plugging-in that to the encoding scheme of Faust et al. (Faut et al. , 2017a) we obtain a CSNMC with very small proof size (in kilobytes), that also allows a leakage, as small as p - <NUM>|c|, in certain settings.

While the above scheme is practical, it is not provably secure. Instead, we rely on heuristic assumptions that intuitively state that the MHF remains memory-hard when the random oracle is instantiated with a standard hash function like SHA3.

In this section we propose a simple construction of NIPoS with extractability. Our construction is based on memory - hard functions (MHF for short) and verifiable computations. Intuitively, an MHF requires that any time-bounded algorithm needs to use significant memory to compute such function on a randomly chosen input. We remark that we treat the hash functions inside the MHF as concrete hash functions and not modeled as random oracles. In particular, we require that an MHF is concretely described and can be represented as a circuit. This is crucial in our context as we use verifiable computation which requires non-black-box access to the function (i.e. an MHF) to be verified. Indeed, we pay a price for that. We do not have a provable guarantee for the memory-hardness, because the only known way to have such guarantee is to use ROM (that gives provable guarantees based on pebbling-games) which is not compatible with our setting. Instead, we heuristically assume that a hash-based MHF construction, that has provable memory-hardness guarantee in the ROM, is memory-hard when the random oracle is instantiated with a standard hash function (for example SHA3).

Definition <NUM> (Memory-hard Functions (MHF)) Let <IMG>: {<NUM>,<NUM>}* → {<NUM>,<NUM>}k be a random oracle. For parameters <MAT> and εmhf ∈ [<NUM>,<NUM>), where smhf ≥ s, a function M: {<NUM>,<NUM>}k → {<NUM>,<NUM>}n is called a (k, n, smhf, tmhf, s, f, t, εmhf)-memory-hard function (or MHF for short) in the ROM if:
M is computable by a (smhf, tmhf)-space-time-bounded algorithm.

For any (s, f, t)-bounded deterministic algorithm <IMG>, any x ∈ {<NUM>,<NUM>}* we have that: <MAT>.

In this section, we construct a partially-unique NIPoS with extractability based on a MHF and a VC with space-bounded verification. At a high level, the NIPoS scheme is designed as follows. Let M be a memory-hard function and (Gen, Prove, Ver) a publicly verifiable scheme. The NIPoS prover on input id first queries the random oracle to obtain x: = <IMG>(id) and then runs the algorithm Prove on input x and outputs whatever the algorithm outputs, i.e. the value y: = M(x) and the proof of correct computation πvc. The NIPoS verifier on input id and the proof of space (y, πvc) first queries the random oracle to obtain x: = <IMG>(id) and the runs the algorithm Ver on input x, y, πvc and outputs whatever the algorithm outputs.

For a construction, according to embodiments, let M be a (k, n, smhf, tmhf, s, f, t, εmhf)-MHF, (Gen, Prove, Ver) be a (smhf, tmhf, <MAT>, k, n, nvc, εvc)-VC scheme for M and <IMG>: {<NUM>,<NUM>}* → {<NUM>,<NUM>}k be a hash-function modeled as random oracle such that <MAT> and <MAT> <MAT>. Then define the following algorithms:
Setup(<NUM>λ): On input the security parameter, run (vkM, ekM) ← GenM(<NUM>λ) and set PPpos: = (vkM, ekM). <MAT>: Given public parameters pppos: = (vkM, ekM) and an identity id ∈ {<NUM>,<NUM>)kpos, compute the proof-of-space as follows:.

<MAT>: Given public parameters pppos: = (vkM, ekM) an identity id E {<NUM>,<NUM>}kpos and a candidate proof π ∈ {<NUM>,<NUM>}npos, check the correctness of π with respect to id as follows:.

On input x ∈ {<NUM>,<NUM>}k, define the MHF MG,Hash as follows: consider the SoLEG GNc,kG,γ<NUM>,γ<NUM>; recall that the number of nodes of GNc,kG,γ<NUM>,γ<NUM> is given by N = Nc(kG + <NUM>) and the in-degree is deg ∈ O(<NUM>). Let Hash: {<NUM>,<NUM>}* -> {<NUM>,<NUM>}nhs be a standard hash function (for example SHA3) with collision-probability εhs. On input x ∈ {<NUM>,<NUM>}k, first compute a Hashx-labeling of GN,kG,γ<NUM>. Denote the labeling by z = (z<NUM>,. , zN) ∈ {<NUM>,<NUM>}nhsN, where each zi ∈ {<NUM>,<NUM>}nhs. Output y where y: = <IMG>(z) ∈ {<NUM>,<NUM>}nhs.

For the hash function Hash: {<NUM>,<NUM>}* -> {<NUM>,<NUM>}ns and for our construction based on a SoLEG GNc,kG,γ<NUM>. γ<NUM> with N = Nc(kG + <NUM>) nodes and deg = O(<NUM>) in-degree: <MAT> <MAT>.

Then, for any δ E (<NUM>, β), any ε > <NUM> and any <MAT> our construction is a (k, n, smhf, tmhf, s, f, t, εmhf)-MHP for t, f, tmhf E poly(λ) and: <MAT> <MAT>.

Furthermore, for making εmhf ≈ <NUM>-<NUM>, we need to have λ ≈ <NUM>. Choosing standard values for other parameters, δ = <NUM>, β = <NUM>, γhs = <NUM> we get concrete parameters for our MHF-construction as: <MAT>.

Our NIPoS construction can be instantiated with any VC for which the verification can be done in small space (compared to computing the function itself). Some embodiments make use of a scheme, known as Pinocchio (Parno et al.

Without giving formal arguments on the space-bound, we rely on the following assumption on the Pinocchio verification algorithm. Note that these bounds are independent of the space-bound of the function (in this case that is MG,Hash) to be verified.

Assumption <NUM> (Space-bounded Verification). Let <IMG> be a (as considered in Bryan Parno et al. (Pamo et al. , <NUM>)) cyclic subgroup of points in <MAT> denotes an elliptic curve over <MAT> where p ∈ exp(λ) is a prime. To achieve <NUM>-bits of security, as suggested by Aurore Guillevic and Francois Morain (Guillevic and Morain), we will set <MAT>. Then for a function F: {<NUM>,<NUM>}k -> {<NUM>,<NUM>}n, the Pinocchio verification algorithm (see Protocol <NUM> of Bryan Parno et al. (Parno et al. , <NUM>)) requires k + n + O(λ)-bit space asymptotically and <MAT> bits concretely.

First notice that the size of the proof is equal to <NUM> elements of a group <IMG>. Hence, the size of the proof is upper bounded by <MAT>. The verifier has the verifiaction key vkF hardcoded and it gets as input (i) the input and output values of the function F, i.e. k + n bits in total, and (ii) a proof of correct computation, πvc which consists of <NUM> group elements. Thus, on high level, the verifier needs to store the input and output, has to be able to further store constant number of group elements, have enough space to add two points on the curve and compute a non-trivial bilinear map e: <MAT> (Boneh and Franklin, <NUM>) where <MAT> is subgroup of <MAT> and the target group <MAT> is a subgroup of <MAT>.

A point on an elliptic curve can be stored using constantly many field elements. Addition of two curve points requires only constantly more space than performing an arithmetic operation in the field for which we need O(log(p)) space. Computing the bilinear map requires constantly more space than adding two curve points. Thus, asymptotically, the space complexity of the verifier can be assumed to be k + n + O(log(p)) = k + n + O(λ). It is more challenging to have a reasonable measurement of the concrete space complexity of the verifier since it depends not only on the concrete implementation of the verification algorithm itself but also on the concrete implementation of all its subprotocols including the basic arithmetic operations in the finite field <MAT>. Assuming that Ver is implemented in a sequential manner, e is the modified Weil pairing as defined in Dan Boneh and Matthew K. Franklin (Boneh and Franklin, <NUM>) computed using Miller's algorithm (Miller, <NUM>), we can roughly assume the space complexity of the verifier as <MAT>.

The space requirement of the prover algorithm ProveekF (with hardcoded evaluation-key ekF) mainly depends on the space-complexity of the function F to be verified. Suppose that F can be computed by a (sF, tF)-bounded algorithm, then the space requirement of ProveekF must be at least max(sF, nvc) because the prover also outputs the proof of computation of length nvc. For Pinocchio, nvc is equal to <MAT>. But since we are concerned with memory-hard functions, we simply assume that sF » nvc. However, in reality it could be much larger than that as the prover has to (i) evaluate the circuit (ii) interpolate a polynomial of degree d, that is upper bounded by the number of gates in the circuit (more precisely, it is equal to the number of multiplication gates in the circuit) (iii) divide two polynomials of degree d (iv) finish the computation of the proof (that consists of <NUM> group elements of size <MAT>) by scalar multiplications and additions of points on elliptic curve (for more details we refer to Bryan Parno et al.

Corollary <NUM>. Let <MAT> be the security parameter and let F: {<NUM>,<NUM>}k -> {<NUM>,<NUM>}n be a deterministic function that is computable by an (sF, poly(λ))-space-time bounded algorithm. Then there exists an explicit (sF, poly(λ), <MAT>, poly(λ), <MAT>, poly(λ), k, n, nvc, negl(λ))-non-interactive publicly verifiable computation construction, where: <MAT> Furthermore, in concrete terms, to get εvc ≈ <NUM>-<NUM>, choosing <MAT> (following Aurore Guillevic and Francois Morain (Guillevic and Morain) we can have estimations of the verifier's space <MAT> and the proof-size nvc ≈ 3KB.

Putting together the instantiations of MHF and VC, we can get a (partially) unique extractable NIPoS.

Corollary <NUM> (MHF-based NIPoS with uniqueness). For any ε > <NUM> and a δ ∈ (<NUM>,<NUM>) there is an explicit construction of (kpos, npos, sP, sV)-NIPoS which has (upos, εunique)-uniqueness and (s, f, t, η, εpos)-extractabilityfor any f, t ∈ poly(λ) as long as: <MAT> <MAT>.

Instantiating this construction with λ = <NUM> to get εpos ≈ <NUM>-<NUM>, and setting kpos = 4KB, |<IMG>(B)| ≤ <NUM><NUM> and δ = <NUM>, we obtain a (kpos, npos, sP, sV)-NIPoS which has (upos, εunique)-uniqueness and (s, f, t, η, εpos)-extractability where f, t can be set to any large enough value and <MAT> <MAT>.

<FIG> depicts a device <NUM> comprising a memory <NUM> and a self-destruct module <NUM>. The device <NUM> may be, for example, a mobile device. The memory <NUM> may be memory of a secure element (not pictured), and may thus be referred to as secure memory. The memory <NUM> may be limited in size, e.g., on the order of megabytes. In some embodiments, the memory <NUM> may be larger and store a larger codeword. The codeword may be stored in secure memory. In embodiments, the size of the codeword may be on the order of the size of the memory <NUM>. The self-destruct module <NUM> may enact a "self-destruct" mechanism once tampering is detected on the device. As an example, the self-destruct mechanism can cause the device <NUM> (e.g., a secure element) to erase its entire state (or make it non-functional). In particular, the secure element may flip a control bit from <NUM> to <NUM> when tampering is detected. The secure element may become inoperable when the control bit is set to <NUM>, preventing the secure element from performing further decoding or cryptographic functions.

<FIG> further depicts the memory <NUM>. The memory <NUM> may comprise a persistent space <NUM> that is retained over time and a transient space <NUM> that is refreshed periodically (e.g., after each decoding). The persistent space <NUM> may store a codeword c comprising a secret sk (e.g., a cryptographic key) and a proof πsk based on the secret sk. The codeword c may use most of the persistent space <NUM>, but there may be some space unused that makes up an extra-persistent space <NUM>. In embodiments, the size of the extra-persistent space <NUM> may be set to <NUM> bits.

<FIG> shows a method <NUM> of encoding a codeword according to embodiments. The encoding process can be performed by an encoding computer. The encoding computer may also be a provisioning computer. The encoding computer may have unbounded space.

At block <NUM>, a memory hard function MHF may be applied to a secret S. Secret S may be a private key for an encryption scheme. The memory hard function MHF may be an encoding function for a proof-extractable proof of space. In some embodiments, the memory hard function MHF may be a graph labeling or graph pebbling function of challenge-hard graphs. Applying the memory hard function MHF to the secret S generates a result Y. In some embodiments, the encoding device may compute a function of the result Y, such as a hash function. Computing the function Y may use N bytes of memory. Prior to computing the result Y, public parameters pp may be retrieved. The encoding computer may then use the public parameters pp to compute the result Y.

At block <NUM>, a proof function may be used to determine a proof value π based on the secret S and the result Y. In some embodiments, the proof value π may be determined with a function of the result Y.

At block <NUM>, a codeword C can be assembled from the proof value π and the secret S. For example, the proof value π and the secret S may be concatenated to form the codeword C.

At block <NUM>, the codeword C may be sent to a decoding device. The encoding device may also send the result Y. The encoding device may also send the public parameters pp.

The encoding scheme of Sebastian Faust et al. (Faust et al. , 2017a) can now be described. Let (<IMG>) be a (k, n, sP, sV)-NIPoS in the ROM where <IMG>: {<NUM>,<NUM>}' -> <IMG> denotes the random oracle for some <IMG> ∈ poly(λ). We define a (k, n)-coding scheme Π = (<IMG>) as follows.

For the initialization, given as input a security parameter λ, <IMG> generates the public parameters for the NIPoS as pppos ← $ <IMG>(<NUM>λ), and outputs pp: = pppos.

For the encoding, given as input the public parameters pp = pppos and a message x E {<NUM>,<NUM>}k, <IMG> runs the NIPoS prover to generate a proof of space <MAT> using the message x as identity. Then it outputs c: = (x, π) ∈ {<NUM>,<NUM>}n as a codeword.

For the decoding, given a codeword c, <IMG> first parses c as (x, π). Then it runs the NIPoS verifier <MAT>. If b = <NUM> it outputs x, otherwise it outputs <NUM>.

The above construction is a continuous non-malleable code for any θ ∈ poly(λ).

<FIG> shows a method <NUM> illustrating a decoding process using a codeword for use in a cryptographic function according to embodiments of the present invention. Method <NUM> may be performed by a mobile device or other verification device, particularly a device that is memory-limited. For instance, a secure element of the device may be memory limited.

At block <NUM>, a codeword C is received from an encoding computer. The codeword C comprises a proof value π and a secret S. The secret S may be a cryptographic key, such as a private key. In some embodiments, the codeword C may also comprise a result Y obtained by applying a memory-hard function MHF to the secret S. The application of the memory-hard function MHF to the secret S or a function of the secret S requires at least N bytes of memory. The decoding device may also receive public parameters pp. The decoding device then stores the codeword C in a secure memory of a secure element. The codeword C is stored in a persistent memory of the decoding device.

At block <NUM>, input data is received. The input data may be received at the secure element. As an example, the input data can include a message that is to be encrypted before sending to a recipient.

At block <NUM>, the codeword C is retrieved from the secure memory. In some embodiments, the decoding device may also retrieve the result Y.

At block <NUM>, the codeword C is parsed to identify the proof value π and the secret S. Additionally, one or more public parameters used by a memory-hard function MHF to obtain the result Y may be retrieved.

At block <NUM>, the proof value π is used to verify the correctness of the result Y as being obtained by applying the memory-hard function MHF on the secret S. The decoding may be done in a small space. The decoding is operable to use K bytes of memory. K may be at least <NUM> times less than N.

At block <NUM>, when the correctness is true (T), a cryptographic function is applied to the input data using the secret S. Output data from the cryptographic function may then be output from the secure element. For example, the decoding device may sign the input data. The cryptographic function may be a hash function.

At block <NUM>, when the correctness is false (F), an error message is provided, e.g., a value of ⊥ may be output. The secure element may also self-destruct when the correctness is false. For example, the secure element may flip a control bit from <NUM> to <NUM> when the correctness is false and tampering is detected. The secure element becomes inoperable when the control bit is set to <NUM>, preventing the secure element from performing further decoding or cryptographic functions.

At block <NUM>, the transient memory is refreshed. The information in the transient memory may be deleted.

At block <NUM>, E bytes of memory is persisted on the extra-persistent space. The memory persisted on the extra-persistent space may the information about the decoding.

Embodiments may include four constructions of space-bounded (leaky) non-malleable codes that support unbounded tampering. All of them are based on NIPoS. Two require proof-extractability whereas the other two are based on standard extractability. In this section we provide asymptotic bounds for parameters of each construction. Additionally, we compare all constructions with respect to concrete values. Let us begin by summarizing all our constructions briefly:.

Construction-<NUM> (based on SoLEG-extension): This encoding scheme is constructed from poof-extractable NIPoS. The proof-extractable NIPoS is instantiated with the challenge-hard graph built in this paper via SoLEG-extension.

Construction-<NUM> (based on PTC's graph): This encoding scheme is also constructed from poof-extractable NIPoS. The proof-extractable NIPoS is instantiated with the PTC's challenge-hard graph proposed in Wolfgang J Paul et al. (Paul et al.

Construction-<NUM> (based on NIPoS of Faust et al. (Faut et al. , 2017a)): This encoding scheme is constructed from an extractable NIPoS. The underlying NIPoS is an instantiation is from Faust et al. (Faust et al. , 2017a), which is in turn a variant of Ling Ren and Srinivas Devadas's (Ren and Devadas, <NUM>) proof-of-space construction. The parameters of the NIPoS can be found in Faust et al. (Faust et al.

Construction-<NUM> (based on MHF): This encoding scheme is again constructed from an extractable NIPoS with partial uniqueness. The underlying NIPoS is instantiated by a (heuristic) memory-hard function and a verifiable computation scheme. Corollary <NUM> summarizes the parameters of this NIPoS construction.

Since our constructions are obtained from different techniques and achieve different bounds, it is important to fix a common measure with respect to which a comparison makes sense. We choose to fix a standard security measure. Other parameters (namely, k, n, ℓ, s, f, p, d) may be chosen to get <NUM>-bit security. The number of tampering queries may also be determined as θ = <NUM><NUM>. This value may be set much higher without affecting the main parameters significantly. Whenever there is a term that depends on the number of RO queries made by a poly-time adversary, we set that to <NUM><NUM>. Some embodiments may use an assumption that a poly-time adversary runs for <NUM><NUM> time steps. Since in our setting ℓ may be as big as p - n we compare the parameters considering p ≈ n to have minimal leakage. In some embodiments small values for k (close to ℓ) can be considered, although for most constructions much higher k is supported.

Using concrete instantiations of PExt - NIPoS (resp. Ext - -NIPoS), the following concrete parameters for the resulting CSNMCs may be determined. In this table, k may be the size of the message, n may be the size of the proof, p may be the size of the persistent space, ℓ may be the size of the leakage, d may be the size of the size of the decoding function, s may be space available for executing functions, and f may be the size of the description. In embodiments, the size of the extra persistent space may be <NUM> bits.

Table <NUM>: This table shows approximate concrete parameters for the setting when p ≈ n. Note that for PExt-NIPoS-based constructions the last column has bound on s + f, whereas for Ext-NIPoS-based constructions the bound is only on s as f can be set to arbitrary large value.

Note that in embodiments, the size of each proof may be <NUM> MB, or greater. The size of the persistent space may be <NUM> times less than the size of the proof.

The provisioning device and mobile device are now described.

<FIG> shows a block diagram of a provisioning device <NUM> according to embodiments. Modules of provisioning device <NUM> can be implemented in hardware or software, e.g., stored in a computer readable medium and executed by a processor. Provisioning device <NUM> includes a data store <NUM>, a parameter generation module <NUM>, a memory-hard module <NUM>, a proof generation module <NUM>, an encoding module <NUM>, a communication module <NUM>, and a network interface <NUM>. Provisioning device <NUM> may implement method <NUM>.

Data store <NUM> can store a secret S to be encoded and a security parameter λ. The data store may be implemented in various ways, e.g., in a cache of a processor, RAM, flash memory, or a hard drive.

Parameter generation module <NUM> can receive the security parameter λ and information about the function F, which includes a memory-hard function MHF) to be used (e.g., an identifier indicating which memory-hard function is used or some parameters of F). Parameter generation module <NUM> can generate one or more public parameters PP based on the memory-hard function F and the security parameter λ. Other modules can also use the security parameter λ. In some embodiments, aspects of the function F can be hardcoded to parameter generation module <NUM>, and thus no information may need to be sent from data <NUM>. The one or more public parameters PP may include key(s). Thus, parameter generation module <NUM> may be a key generation module for verifiable computation. Once the one or more public parameters pp are generated, they can be stored for access by other modules, as well as other devices, e.g., for public access.

Memory-hard module <NUM> can implement a memory-hard function F that requires memory <NUM> to be of sufficient size. Data store <NUM> can be part of memory <NUM>, and thus can be a same memory structure. Memory-hard module <NUM> can receive the one or more public parameters PP and secret S and provide a result Y, which can be used to generate a proof. Memory-hard module can include other functions than the memory-hard function F, e.g., an initial hashing function, as described herein.

Proof generation module <NUM> can receive the secret S and the result Y, where Y results from operation of memory-hard module on secret S. Proof generation module <NUM> provides a proof π that can be used to efficiently verify that Y is indeed the result from applying the memory-hard function F to secret S. A corresponding decoding function can use perform such a verification.

Encoding module <NUM> can receive the proof π, and result Y, and the secret S for forming a code C. The code C can be provided to communications module <NUM> that may put the code C into a message (e.g., an encrypted message) that is sent to mobile device <NUM> by network interface <NUM>. Communications module <NUM> can use any suitable network protocols, e.g., TCP/IP or Ethernet, as may occur for a wired connection. Once provisioned, mobile device <NUM> can store code C in a secure element and decode C to implement cryptographic functionality. The decoding function that uses the proof π can be sufficiently succinct such that the decoding can be performed on a mobile device, e.g., in a secure element that may only have <NUM> kB, <NUM> kB, <NUM> kB, <NUM> kB, or <NUM> MB of memory.

<FIG> shows a block diagram of a mobile device <NUM> according to embodiments. Mobile device <NUM> can send a request for an encoded secret, e.g., as code C. A provisioning computer can send a response with code C to mobile device <NUM>, which can store code C in secure memory <NUM>. Mobile device <NUM> is an example of a decoding computer.

Mobile device <NUM> includes a processor <NUM>, a computer readable medium <NUM> (e.g., for storing software to execute on processor <NUM>), input/output components <NUM> (e.g., a touchscreen, microphone, and speakers), a communications module <NUM>, a secure memory <NUM>, and a secure element <NUM>, each of which may be connected to a communications bus for communicating to each other. In some implementations, secure element <NUM> may include secure memory <NUM>.

Communications module <NUM> can receive a codeword C via antenna <NUM>. Secure memory <NUM> can store the codeword C comprising a proof value π, a secret S, a result Y obtained by applying a memory-hard function F to the secret S, and one or more public parameters used by a memory-hard function F to obtain the result Y. The memory-hard function F may be implemented by a provisioning computer, where the application of the memory-hard function F to the secret S can require at least N bytes of memory. As an example, N may be at least one gigabyte.

As shown, secure element <NUM> includes a parsing module <NUM>, a decoding module <NUM>, a decision module <NUM>, and a cryptographic module <NUM>. Secure element <NUM> can receive input data on which to perform a cryptographic function. Parsing module <NUM> can retrieve the codeword C from secure memory <NUM>, and parse the codeword C to identify the proof value π, the secret S, the result Y, and one or more public parameters.

Decoding module <NUM> can decode the codeword C by using the proof value π to verify a correctness of the stored result Y as being obtained by applying the memory-hard function F on the secret S. Decoding module <NUM> can be operable to use K bytes of memory. As an example, K may be at least <NUM> times less than N. Decoding module <NUM> can output whether the correctness is verified (true) or not (false).

Decision module <NUM> can use the output from decoding module <NUM> to determine whether to output an error message or to engage cryptographic module <NUM>. When the correctness is true, cryptographic module <NUM> can be applied to the input data using the secret S to obtain output data that is output from the secure element. When the correctness is false, an error message can be output from secure element <NUM>. Additionally, a self-destruct mechanism may be implemented to render the decoding module <NUM> inoperable.

Any of the computer systems mentioned herein may utilize any suitable number of subsystems. Examples of such subsystems are shown in <FIG> in computer system <NUM>. In some embodiments, a computer system includes a single computer apparatus, where the subsystems can be the components of the computer apparatus. In other embodiments, a computer system can include multiple computer apparatuses, each being a subsystem, with internal components. A computer system can include desktop and laptop computers, tablets, mobile phones and other mobile devices.

The subsystems shown in <FIG> are interconnected via a system bus <NUM>. Additional subsystems such as a printer <NUM>, keyboard <NUM>, storage device(s) <NUM>, monitor <NUM>, which is coupled to display adapter <NUM>, and others are shown. Peripherals and input/output (I/O) devices, which couple to I/O controller <NUM>, can be connected to the computer system by any number of means known in the art such as input/output (I/O) port <NUM> (e.g., USB, FireWire®). For example, I/O port <NUM> or external interface <NUM> (e.g. Ethernet, Wi-Fi, etc.) can be used to connect computer system <NUM> to a wide area network such as the Internet, a mouse input device, or a scanner. The interconnection via system bus <NUM> allows the central processor <NUM> to communicate with each subsystem and to control the execution of a plurality of instructions from system memory <NUM> or the storage device(s) <NUM> (e.g., a fixed disk, such as a hard drive, or optical disk), as well as the exchange of information between subsystems. The system memory <NUM> and/or the storage device(s) <NUM> may embody a computer readable medium. Another subsystem is a data collection device <NUM>, such as a camera, microphone, accelerometer, and the like. Any of the data mentioned herein can be output from one component to another component and can be output to the user.

A computer system can include a plurality of the same components or subsystems, e.g., connected together by external interface <NUM>, by an internal interface, or via removable storage devices that can be connected and removed from one component to another component. In some embodiments, computer systems, subsystem, or apparatuses can communicate over a network. In such instances, one computer can be considered a client and another computer a server, where each can be part of a same computer system. A client and a server can each include multiple systems, subsystems, or components.

Aspects of embodiments can be implemented in the form of control logic using hardware circuitry (e.g. an application specific integrated circuit or field programmable gate array) and/or using computer software with a generally programmable processor in a modular or integrated manner. As used herein, a processor can include a single-core processor, multicore processor on a same integrated chip, or multiple processing units on a single circuit board or networked, as well as dedicated hardware. Based on the disclosure and teachings provided herein, a person of ordinary skill in the art will know and appreciate other ways and/or methods to implement embodiments of the present invention using hardware and a combination of hardware and software.

The software code may be stored as a series of instructions or commands on a computer readable medium for storage and/or transmission. A suitable non-transitory computer readable medium can include random access memory (RAM), a read only memory (ROM), a magnetic medium such as a hard-drive, or an optical medium such as a compact disk (CD) or DVD (digital versatile disk), flash memory, and the like.

Claim 1:
A method (<NUM>) for decoding a secret, the method (<NUM>) comprising performing on a decoding computer:
storing (<NUM>) a codeword C comprising a proof value π and a secret S in a persistent memory of the decoding computer, the persistent memory comprising P bytes of memory, wherein the codeword C uses c bytes, wherein the proof value π is determined using the secret S and a result Y, the result Y obtained by applying a memory-hard function MHF to the secret S or to a function of the secret S, wherein the applying of the memory-hard function MHF to the secret S requires at least N bytes of memory, and wherein P-c memory forms extra-persistent space;
receiving (<NUM>) input data;
retrieving (<NUM>) the codeword C from the persistent memory;
parsing (<NUM>) the codeword C to identify the proof value π and the secret S;
performing, using a transient memory of the decoding computer, a decoding of the codeword C by:
using (<NUM>) the proof value π to verify a correctness of the result Y as being obtained from memory-hard function MHF using the secret S, wherein the decoding function is operable to use K bytes of memory, K being less than N;
when the correctness is true, applying (<NUM>) a cryptographic function to the input data using the secret S to obtain output data; and
when the correctness is false, providing (<NUM>) an error message and causing the decoding computer to be inoperable to perform subsequent decoding operations;
refreshing (<NUM>) the transient memory of the decoding computer; and
persisting (<NUM>) E bytes of memory of the decoding on the extra-persistent space, wherein E is less than N and less than the size of the result Y.