The expansion of flip-chip technologies and a lack of backside protection make the integrated circuit (IC) vulnerable to certain classes of physical attacks mounted from the IC's backside. Laser-assisted probing, electromagnetic, and body-biasing injection attacks are examples of such attacks. Unfortunately, there are few countermeasures proposed in the literature, and none are available commercially. Those that do exist are not only expensive but also incompatible with current IC...

Non-malleable codes are fundamental objects at the intersection of cryptography and coding theory. These codes provide security guarantees even in settings where error correction and detection are impossible, and have found applications to several other cryptographic tasks. One of the strongest and most well-studied adversarial tampering models is $2$-split-state tampering. Here, a codeword is split into two parts which are stored in physically distant servers, and the adversary can then...

In this paper, we study the design of efficient signature and public-key encryption (PKE) schemes in the presence of both leakage and tampering attacks. Firstly, we formalize the strong leakage and tamper-resilient (sLTR) security model for signature, which provides strong existential unforgeability, and deals with bounded leakage and restricted tampering attacks, as a counterpart to the sLTR security introduced by Sun et al. (ACNS 2019) for PKE. Then, we present direct constructions...

The notion of ``efficiently testable circuits'' (ETC) was recently put forward by Baig et al.~(ITCS'23). Informally, an ETC compiler takes as input any Boolean circuit $C$ and outputs a circuit/inputs tuple $(C',\mathbb{T})$ where (completeness) $C'$ is functionally equivalent to $C$ and (security) if $C'$ is tampered in some restricted way, then this can be detected as $C'$ will err on at least one input in the small test set $\mathbb{T}$. The compiler of Baig et al. detects tampering...

Vehicular Social Networks (VSNs) rely on data shared by users to provide convenient services. Data is outsourced to the cloud server and the distributed roadside unit in VSNs. However, roadside unit has limited resources, so that data sharing process is inefficient and is vulnerable to security threats, such as illegal access, tampering attack and collusion attack. In this article, to overcome the shortcomings of security, we define a chain tolerance semi-trusted model to describe the...

Tampering attack is the act of deliberately modifying the codeword to produce another codeword of a related message. The main application is to find out the original message from the codeword. Non-malleable codes are introduced to protect the message from such attack. Any tampering attack performed on the message encoded by non-malleable codes, guarantee that output is either completely unrelated or original message. It is useful mainly in the situation when privacy and integrity of the...

The secret key of any encryption scheme that are stored in secure memory of the hardwired devices can be tampered using fault attacks. The usefulness of tampering attack is to recover the key by altering some regions of the memory. Such attack may also appear when the device is stolen or viruses has been introduced. Non-malleable codes are used to protect the secret information from tampering attacks. The secret key can be encoded using non-malleable codes rather than storing it in plain...

Homomorphic Encryption~(HE) is used in many fields including information storage, data protection, privacy preservation, blockchain, and authentication. HE allows an untrusted third party to perform algebraic operations on encrypted data. Protecting the results of HE against accidental or malicious tampering attacks is still an open research challenge. In this paper, we introduce a lightweight technique that allows a data owner to verify the integrity of HE results performed in the cloud....

The threat of chip-level tampering and its detection has been widely researched. Hardware Trojan insertions are prominent examples of such tamper events. Altering the placement and routing of a design or removing a part of a circuit for side-channel leakage/fault sensitivity amplification are other instances of such attacks. While semi- and fully-invasive physical verification methods can confidently detect such stealthy tamper events, they are costly, time-consuming, and destructive. On the...

In this work, we put forward the notion of ``efficiently testable circuits'' and provide circuit compilers that transform any circuit into an efficiently testable one. Informally, a circuit is testable if one can detect tampering with the circuit by evaluating it on a small number of inputs from some test set. Our technical contribution is a compiler that transforms any circuit $C$ into a testable circuit $(\widehat{C}, \widehat{T})$ for which we can detect arbitrary tampering with all...

In the setting of subversion, an adversary tampers with the machines of the honest parties thus leaking the honest parties' secrets through the protocol transcript. The work of Mironov and Stephens-Davidowitz (EUROCRYPT’15) introduced the idea of reverse firewalls (RF) to protect against tampering of honest parties' machines. All known constructions in the RF framework rely on the malleability of the underlying operations in order for the RF to rerandomize/sanitize the transcript. RFs are...

Non-malleable codes are a natural relaxation of error correction and error detection codes applicable in scenarios where error-correction or error-detection is impossible. Over the last decade, non-malleable codes have been studied for a wide variety of tampering families. Among the most well studied of these is the split-state family of tampering channels, where the codeword is split into two or more parts and each part is tampered independently. We survey various constructions and...

Non-malleable codes (Dziembowski, Pietrzak and Wichs, ICS 2010 & JACM 2018) allow protecting arbitrary cryptographic primitives against related-key attacks (RKAs). Even when using codes that are guaranteed to be non-malleable against a single tampering attempt, one obtains RKA security against poly-many tampering attacks at the price of assuming perfect memory erasures. In contrast, continuously non-malleable codes (Faust, Mukherjee, Nielsen and Venturi, TCC 2014) do not suffer from this...

Chakraborty, Prabhakaran, and Wichs (PKC'20) recently introduced a new tag-based variant of lossy trapdoor functions, termed cumulatively all-lossy-but-one trapdoor functions (CALBO-TDFs). Informally, CALBO-TDFs allow defining a public tag-based function with a (computationally hidden) special tag, such that the function is lossy for all tags except when the special secret tag is used. In the latter case, the function becomes injective and efficiently invertible using a secret trapdoor. This...

We give the first constructions in the plain model of 1) nonmalleable digital lockers (Canetti and Varia, TCC 2009) and 2) robust fuzzy extractors (Boyen et al., Eurocrypt 2005) that secure sources with entropy below 1/2 of their length. Constructions were previously only known for both primitives assuming random oracles or a common reference string (CRS). Along the way, we define a new primitive called a nonmalleable point function obfuscation with associated data. The associated data is...

We construct non-malleable codes in the split-state model with codeword length $m + 3\lambda$ or $m+5\lambda$, where $m$ is the message size and $\lambda$ is the security parameter, depending on how conservative one is. Our scheme is very simple and involves a single call to a block cipher meeting a new security notion which we dub entropic fixed-related-key security, which essentially means that the block cipher behaves like a pseudorandom permutation when queried upon inputs sampled from a...

Interactive Non-Malleable Codes were introduced by Fleischhacker et al. (TCC 2019) in the two party setting with synchronous tampering. The idea of this type of non-malleable code is that it "encodes" an interactive protocol in such a way that, even if the messages are tampered with according to some class $\mathcal{F}$ of tampering functions, the result of the execution will either be correct, or completely unrelated to the inputs of the participating parties. In the synchronous setting...

We study a tamper-tolerant implementation security notion for general purpose Multi-Party Computation (MPC) protocols, as an analogue of the leakage-tolerant notion in the MPC literature. An MPC protocol is tamper-tolerant, or more specifically, non-malleable (with respect to a certain type of tampering) if the processing of the protocol under corruption of parties (and tampering of some ideal resource assumed by the protocol) can be simulated by an ideal world adversary who, after the...

Physical attacks can compromise the security of cryptographic devices. Depending on the attack’s requirements, adversaries might need to (i) place probes in the proximity of the integrated circuits (ICs) package, (ii) create physical connections between their probes/wires and the system’s PCB, or (iii) physically tamper with the PCB’s components, chip’s package, or substitute the entire PCB to prepare the device for the attack. While tamper-proof enclosures prevent and detect physical access...

Physical attacks, including passive Side-Channel Analysis and active Fault Injection Analysis, are considered among the most powerful threats against physical cryptographic implementations. These attacks are well known and research provides many specialized countermeasures to protect cryptographic implementations against them. Still, only a limited number of combined countermeasures, i.e., countermeasures that protect implementations against multiple attacks simultaneously, were proposed in...

Logic locking is a design concealment mechanism for protecting the IPs integrated into modern System-on-Chip (SoC) architectures from a wide range of hardware security threats at the IC manufacturing supply chain. Logic locking primarily helps the designer to protect the IPs against reverse engineering, IP piracy, overproduction, and unauthorized activation. For more than a decade, the research studies that carried out on this paradigm has been immense, in which the applicability,...

Related-key attacks (RKA) are powerful cryptanalytic attacks, where the adversary can tamper with the secret key of a cryptographic scheme. Since their invention, RKA security has been an important design goal in cryptography, and various works aim at designing cryptographic primitives that offer protection against related-key attacks. At EUROCRYPT'03, Bellare and Kohno introduced the first formal treatment of related-key attacks focusing on pseudorandom functions and permutations. This was...

We present the first truly explicit constructions of non-malleable codes against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature. Prior works on NMC for polysize circuits, either required an untamperable CRS [Cheraghchi, Guruswami ITCS'14; Faust, Mukherjee, Venturi, Wichs EUROCRYPT'14] or very strong...

FPGA bitstream encryption and authentication can be defeated by various techniques and it is critical to understand how these vulnerabilities enable extraction and tampering of commercial FPGA bitstreams. We exploit the physical vulnerability of bitstream encryption keys to readout using failure analysis equipment and conduct an end-to-end bitstream tamper attack. Our work underscores the feasibility of supply chain bitstream tampering and the necessity of guarding against such attacks in...

A randomness encoder is a generalization of encoding schemes with an efficient procedure for encoding \emph{uniformly random strings}. In this paper we continue the study of randomness encoders that additionally have the property of being continuous non-malleable. The beautiful notion of non-malleability for encoding schemes, introduced by Dziembowski, Pietrzak and Wichs (ICS’10), states that tampering with the codeword can either keep the encoded message identical or produce an...

Robust (fuzzy) extractors are very useful for, e.g., authenticated exchange from shared weak secret and remote biometric authentication against active adversaries. They enable two parties to extract the same uniform randomness with the ``helper'' string. More importantly, they have an authentication mechanism built in that tampering of the ``helper'' string will be detected. Unfortunately, as shown by Dodis and Wichs, in the information-theoretic setting, a robust extractor for an...

We study non-malleable secret sharing against joint leakage and joint tampering attacks. Our main result is the first threshold secret sharing scheme in the plain model achieving resilience to noisy-leakage and continuous tampering. The above holds under (necessary) minimal computational assumptions (i.e., the existence of one-to-one one-way functions), and in a model where the adversary commits to a fixed partition of all the shares into non-overlapping subsets of at most $t-1$ shares...

At ITCS 2010, Dziembowski, Pietrzak, and Wichs introduced Non-malleable Codes (NMCs) which protect against tampering of a codeword of a given message into the codeword of a related message. A well-studied model of tampering is the $2$-split-state model where the codeword consists of two independently tamperable states. As with standard error-correcting codes, it is of great importance to build codes with high rates. Following a long line of work, Aggarwal and Obremski (FOCS 2020) showed the...

Licensing of software that will run in offline environments introduces constraints on the licensing model that can be supported. The difficulty arises in cases where information needs to be recorded about the usage of the software, for example in a consumption-based licensing model. We describe a method that makes it harder for an adversary to tamper with the recorded data as well as ways for software vendors to detect if tampering with this information would still occur.

Non-malleable codes are introduced to protect the communication against adversarial tampering of data, as a relaxation of the error-correcting codes and error-detecting codes. To explicitly construct non-malleable codes is a central and challenging problem which has drawn considerable attention and been extensively studied in the past few years. Recently, Rasmussen and Sahai built an interesting connection between non-malleable codes and (non-bipartite) expander graphs, which is the first...

We extend the classical problem of privacy amplification to a setting where the active adversary, Eve, is also allowed to fully corrupt the internal memory (which includes the shared randomness, and local randomness tape) of one of the honest parties, Alice and Bob, before the execution of the protocol. We require that either one of Alice or Bob detects tampering, or they agree on a shared key that is indistinguishable from the uniform distribution to Eve. We obtain the following...

Time-lock puzzles are a mechanism for sending messages "to the future", by allowing a sender to quickly generate a puzzle with an underlying message that remains hidden until a receiver spends a moderately large amount of time solving it. We introduce and construct a variant of a time-lock puzzle which is non-malleable, which roughly guarantees that it is impossible to "maul" a puzzle into one for a related message without solving it. Using non-malleable time-lock puzzles, we achieve the...

Non-malleable codes allow one to encode data in such a way that, after tampering, the modified codeword is guaranteed to decode to either the original message, or a completely unrelated one. Since the introduction of the notion by Dziembowski, Pietrzak, and Wichs (ICS '10 and J. ACM '18), a large body of work has focused on realizing such coding schemes secure against various classes of tampering functions. It is well known that there is no efficient non-malleable code secure against all...

Secret sharing enables a dealer to split a secret into a set of shares, in such a way that certain authorized subsets of share holders can reconstruct the secret, whereas all unauthorized subsets cannot. Non-malleable secret sharing (Goyal and Kumar, STOC 2018) additionally requires that, even if the shares have been tampered with, the reconstructed secret is either the original or a completely unrelated one. In this work, we construct non-malleable secret sharing tolerating $p$-time {\em...

The common approach in secure communication channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example is the case with TLS or SSH. However, protocols like QUIC or DTLS which run over a non-reliable transport such as UDP, do not---and in fact...

Two-source non-malleable extractors are pseudorandom objects which extract randomness even when an adversary is allowed to learn the behavior of the extractor on tamperings of the input weak sources, and they have found important applications in non-malleable coding and secret sharing. We begin by asking how hard it is to improve upon the best known constructions of such objects (Chattopadhyay, Goyal, Li, STOC 2016, and Li, STOC 2017). We show that even small improvements to these...

Neural networks have become increasingly prevalent in many real-world applications including security-critical ones. Due to the high hardware requirement and time consumption to train high-performance neural network models, users often outsource training to a machine-learning-as-a-service (MLaaS) provider. This puts the integrity of the trained model at risk. In 2017, Liu et. al. found that, by mixing the training data with a few malicious samples of a certain trigger pattern, hidden...

We introduce a natural generalization of two-source non-malleable extractors (Cheragachi and Guruswami, TCC 2014) called as \textit{multi-source non-malleable extractors}. Multi-source non-malleable extractors are special independent source extractors which satisfy an additional non-malleability property. This property requires that the output of the extractor remains close to uniform even conditioned on its output generated by tampering {\it several sources together}. We formally define...

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials. Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable code that is secure against tampering by bounded-size arithmetic circuits. We show applications of our non-malleable code in constructing non-malleable...

We introduce the notion of Witness Maps as a cryptographic notion of a proof system. A Unique Witness Map (UWM) deterministically maps all witnesses for an $\mathbf{NP}$ statement to a single representative witness, resulting in a computationally sound, deterministic-prover, non-interactive witness independent proof system. A relaxation of UWM, called Compact Witness Map (CWM), maps all the witnesses to a small number of witnesses, resulting in a ``lossy'' deterministic-prover,...

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs in ICS 2010, have emerged in the last few years as a fundamental object at the intersection of cryptography and coding theory. Non-malleable codes provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a...

In this paper, we propose coded Merkle tree (CMT), a novel hash accumulator that offers a constant-cost protection against data availability attacks in blockchains, even if the majority of the network nodes are malicious. A CMT is constructed using a family of sparse erasure codes on each layer, and is recovered by iteratively applying a peeling-decoding technique that enables a compact proof for data availability attack on any layer. Our algorithm enables any node to verify the full...

In recent years, there has been exciting progress on building two-source extractors for sources with low min-entropy. Unfortunately, all known explicit constructions of two-source extractors in the low entropy regime suffer from non-negligible error, and building such extractors with negligible error remains an open problem. We investigate this problem in the computational setting, and obtain the following results. We construct an explicit 2-source extractor, and even an explicit...

Memory fault attacks, inducing errors in computations, have been an ever-evolving threat to cryptographic schemes since their discovery for cryptography by Boneh et al. (Eurocrypt 1997). Initially requiring physical tampering with hardware, the software-based rowhammer attack put forward by Kim et al. (ISCA 2014) enabled fault attacks also through malicious software running on the same host machine. This led to concerning novel attack vectors, for example on deterministic signature schemes,...

Deterministic generation of per-signature randomness has been a widely accepted solution to mitigate the catastrophic risk of randomness failure in Fiat--Shamir type signature schemes. However, recent studies have practically demonstrated that such de-randomized schemes, including EdDSA, are vulnerable to differential fault attacks, which enable adversaries to recover the entire secret signing key, by artificially provoking randomness reuse or corrupting computation in other ways. In order...

We study leakage-resilient continuously non-malleable secret sharing, as recently introduced by Faonio and Venturi (CRYPTO 2019). In this setting, an attacker can continuously tamper and leak from a target secret sharing of some message, with the goal of producing a modified set of shares that reconstructs to a message related to the originally shared value. Our contributions are two fold. -- In the plain model, assuming one-to-one one-way functions, we show how to obtain...

Non-malleable codes are encoding schemes that provide protections against various classes of tampering attacks. Recently Faust et al. (CRYPTO 2017) initiated the study of space- bounded non-malleable codes that provide such protections against tampering within small- space devices. They put forward a construction based on any non-interactive proof-of-space (NIPoS). However, the scheme only protects against an a priori bounded number of tampering attacks. We construct non-malleable codes...

Logging is a key mechanism in the security of computer systems. Beyond supporting important forward security properties, it is critical that logging withstands both failures and intentional tampering to prevent subtle attacks leaving the system in an inconsistent state with inconclusive evidence. We propose new techniques combining forward security with crash recovery for secure log data storage. As the support of specifically forward integrity and the online nature of logging prevent...

There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question: "When can we rule out the existence of a non-malleable code for a tampering class $\mathcal{F}$?" We show that non-malleable codes are impossible to construct for three different tampering classes: 1. Functions that change $d/2$ symbols, where $d$ is the distance of...

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs in ICS 2010, have emerged in the last few years as a fundamental object at the intersection of cryptography and coding theory. Non-malleable codes provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a...

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by decision trees of depth $d = n^{1/4-o(1)}$. In particular, each bit of the tampered codeword is set arbitrarily after adaptively reading up to $d$ arbitrary locations within the original codeword. Prior to this work, no efficient unconditional non-malleable codes were known for decision trees beyond depth $O(\log^2 n)$. Our result also yields efficient, unconditional...

In this paper, we consider the setting where a party uses correlated random tapes across multiple executions of a cryptographic algorithm. We ask if the security properties could still be preserved in such a setting. As examples, we introduce the notion of correlated-tape zero knowledge, and, correlated-tape multi-party computation, where, the zero-knowledge property, and, the ideal/real model security must still be preserved even if a party uses correlated random tapes in multiple...

We revisit the concept of *non-malleable* secret sharing (Goyal and Kumar, STOC 2018) in the computational setting. In particular, under the assumption of one-to-one one-way functions, we exhibit a *computationally* private, *threshold* secret sharing scheme satisfying all of the following properties. -) Continuous non-malleability: No computationally-bounded adversary tampering independently with all the shares can produce mauled shares that reconstruct to a value related to the original...

We study the *rate* of so-called *continuously* non-malleable codes, which allow to encode a message in such a way that (possibly adaptive) continuous tampering attacks on the codeword yield a decoded value that is unrelated to the original message. Our results are as follows: -) For the case of bit-wise independent tampering, we establish the existence of rate-one continuously non-malleable codes with information-theoretic security, in the plain model. -) For the case of split-state...

In this work we present a collection of compilers that take secret sharing schemes for an arbitrary access structures as input and produce either leakage-resilient or non-malleable secret sharing schemes for the same access structure. A leakage-resilient secret sharing scheme hides the secret from an adversary, who has access to an unqualified set of shares, even if the adversary additionally obtains some size-bounded leakage from all other secret shares. A non-malleable secret sharing...

A threshold secret sharing scheme (with threshold $t$) allows a dealer to share a secret among a set of parties such that any group of $t$ or more parties can recover the secret and no group of at most $t-1$ parties learn any information about the secret. A non-malleable threshold secret sharing scheme, introduced in the recent work of Goyal and Kumar (STOC'18), additionally protects a threshold secret sharing scheme when its shares are subject to tampering attacks. Specifically, it...

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against a powerful adaptive adversary who may learn some ``leaked'' information about all the shares. We say that a secret sharing scheme is $p$-party leakage-resilient, if the secret remains statistically hidden even after an adversary learns a bounded amount of leakage, where each bit of leakage can depend jointly on the shares of an adaptively chosen subset of $p$ parties. A lot of works...

Non-malleable codes were introduced by Dziembowski, Pietrzak, and Wichs (JACM 2018) as a generalization of standard error correcting codes to handle severe forms of tampering on codewords. This notion has attracted a lot of recent research, resulting in various explicit constructions, which have found applications in tamper-resilient cryptography and connections to other pseudorandom objects in theoretical computer science. We continue the line of investigation on explicit constructions of...

We construct efficient non-malleable codes (NMC) that are (computationally) secure against tampering by functions computable in any fixed polynomial time. Our construction is in the plain (no-CRS) model and requires the assumptions that (1) $\mathbf{E}$ is hard for $\mathbf{NP}$ circuits of some exponential $2^{\beta n}$ ($\beta>0$) size (widely used in the derandomization literature), (2) sub-exponential trapdoor permutations exist, and (3) $\mathbf{P}$ certificates with sub-exponential...

A point obfuscator is an obfuscated program that indicates if a user enters a previously stored password. A digital locker is stronger: outputting a key if a user enters a previously stored password. The real-or-random transform allows one to build a digital locker from a composable point obfuscator (Canetti and Dakdouk, Eurocrypt 2008). Ideally, both objects would be nonmalleable, detecting adversarial tampering. Appending a non-interactive zero knowledge proof of knowledge adds...

In this paper, we introduce a new framework for constructing public-key encryption (PKE) schemes resilient to joint post-challenge/after-the-fact leakage and tampering attacks in the bounded leakage and tampering (BLT) model, introduced by Damgård et al. (Asiacrypt 2013). All the prior formulations of PKE schemes considered leakage and tampering attacks only before the challenge ciphertext is made available to the adversary. However, this restriction seems necessary, since achieving security...

Goyal and Kumar (STOC'18) recently introduced the notion of non-malleable secret sharing. Very roughly, the guarantee they seek is the following: the adversary may potentially tamper with all of the shares, and still, either the reconstruction procedure outputs the original secret, or, the original secret is ``destroyed" and the reconstruction outputs a string which is completely ``unrelated" to the original secret. Prior works on non-malleable codes in the 2 split-state model imply...

We present Steady: an end-to-end secure logging system engineered to be simple in terms of design, implementation, and assumptions for real-world use. Steady gets its name from being based on a steady (heart)beat of events from a forward-secure device sent over an untrusted network through untrusted relays to a trusted collector. Properties include optional encryption and compression (with loss of confidentiality but significant gain in goodput), detection of tampering, relays that can...

Non-malleable codes for the split-state model allow to encode a message into two parts, such that arbitrary independent tampering on each part, and subsequent decoding of the corresponding modified codeword, yields either the same as the original message, or a completely unrelated value. Continuously non-malleable codes further allow to tolerate an unbounded (polynomial) number of tampering attempts, until a decoding error happens. The drawback is that, after an error happens, the system...

Non-Malleable Codes (NMC) were introduced by Dziembowski, Pietrzak and Wichs in ICS 2010 as a relaxation of error correcting codes and error detecting codes. Faust, Mukherjee, Nielsen, and Venturi in TCC 2014 introduced an even stronger notion of non-malleable codes called continuous non-malleable codes where security is achieved against continuous tampering of a single codeword without re-encoding. We construct information theoretically secure CNMC resilient to bit permutations and...

In this work, we show negative results on the tamper-resilience of a wide class of cryptographic primitives with uniqueness properties, such as unique signatures, verifiable random functions, signatures with unique keys, injective one-way functions, and encryption schemes with a property we call unique-message property. Concretely, we prove that for these primitives, it is impossible to derive their (even extremely weak) tamper-resilience from any common assumption, via black-box reductions....

At ICS 2010, Dziembowski, Pietrzak and Wichs introduced the notion of *non-malleable codes*, a weaker form of error-correcting codes guaranteeing that the decoding of a tampered codeword either corresponds to the original message or to an unrelated value. The last few years established non-malleable codes as one of the recently invented cryptographic primitives with the highest impact and potential, with very challenging open problems and applications. In this work, we focus on so-called...

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs (ICS '10) and its main application is the protection of cryptographic devices against tampering attacks on memory. In this work, we initiate a comprehensive study on non-malleable codes for the class of partial functions, that read/write on an arbitrary subset of codeword bits with specific cardinality. Our constructions are efficient in terms of information rate, while allowing the attacker to access...

Recently, Faust et al. (TCC'14) introduced the notion of continuous non-malleable codes (CNMC), which provides stronger security guarantees than standard non-malleable codes, by allowing an adversary to tamper with the codeword in continuous way instead of one-time tampering. They also showed that CNMC with information theoretic security cannot be constructed in 2-split-state tampering model, and presented a construction of the same in CRS (common reference string) model using...

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay and Li (STOC 2017), which had codeword length $2^{O(\sqrt{k})}$. Our construction remains efficient for...

A non-malleable code is an unkeyed randomized encoding scheme that offers the strong guarantee that decoding a tampered codeword either results in the original message, or in an unrelated message. We consider the simplest possible construction in the computational split-state model, which simply encodes a message $m$ as $k||E_k(m)$ for a uniformly random key $k$, where $E$ is a block cipher. This construction is comparable to, but greatly simplifies over, the one of Kiayias et al. (ACM CCS...

Algebraic Manipulation Detection (AMD) codes [CDF+08] are keyless message authentication codes that protect messages against additive tampering by the adversary assuming that the adversary cannot "see" the codeword. For certain applications, it is unreasonable to assume that the adversary computes the added offset without any knowledge of the codeword c. Recently, Ahmadi and Safavi-Naini [AS13], and then Lin, Safavi-Naini, and Wang [LSW16] gave a construction of leakage-resilient AMD codes...

Non-malleable Codes (NMCs), introduced by Dziembowski, Peitrzak and Wichs (ITCS 2010), serve the purpose of preventing "related tampering" of encoded messages. The most popular tampering model considered is the $2$-split-state model where a codeword consists of 2 states, each of which can be tampered independently. While NMCs in the $2$-split state model provide the strongest security guarantee, despite much research in the area we only know how to build them with poor rate...

We show a general framework for constructing non-malleable codes against tampering families with average-case hardness bounds. Our framework adapts ideas from the Naor-Yung double encryption paradigm such that to protect against tampering in a class F, it suffices to have average-case hard distributions for the class, and underlying primitives (encryption and non-interactive, simulatable proof systems) satisfying certain properties with respect to the class. We instantiate our scheme in a...

There are natural cryptographic applications where an adversary only gets to tamper a high- speed data stream on the fly based on her view so far, namely, the lookahead tampering model. Since the adversary can easily substitute transmitted messages with her messages, it is farfetched to insist on strong guarantees like error-correction or, even, manipulation detection. Dziembowski, Pietrzak, and Wichs (ICS–2010) introduced the notion of non-malleable codes that provide a useful message...

Austrin, Chung, Mahmoody, Pass and Seth (Crypto'14) studied the notion of bitwise $p$-tampering attacks over randomized algorithms in which an efficient `virus' gets to control each bit of the randomness with independent probability $p$ in an online way. The work of Austrin et al. showed how to break certain `privacy primitives' (e.g., encryption, commitments, etc.) through bitwise $p$-tampering, by giving a bitwise $p$-tampering biasing attack for increasing the average $E[f(U_n)]$ of...

Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs (ITCS 2010), generalize the classical notion of error correcting codes by providing a powerful guarantee even in scenarios where error correcting codes cannot provide any guarantee: a decoded message is either the same or completely independent of the underlying message, regardless of the number of errors introduced into the codeword. Informally, NMCs are defined with respect to a family of tampering functions $F$ and...

We revisit the setting of coding for interactive communication, CIC, (initiated by Schulman 96') for non-threshold tampering functions. In a nutshell, in the (special case of) the communication complexity setting, Alice and Bob holding inputs $x,y$ wish to compute a function $g(x,y)$ on their inputs over the identity channel using an interactive protocol. The goal here is to minimize the total communication complexity (CC). A "code" for interactive communication is a compiler transforming...

Non-malleable codes---introduced by Dziembowski, Pietrzak and Wichs at ICS 2010---are key-less coding schemes in which mauling attempts to an encoding of a given message, w.r.t.\ some class of tampering adversaries, result in a decoded value that is either identical or unrelated to the original message. Such codes are very useful for protecting arbitrary cryptographic primitives against tampering attacks against the memory. Clearly, non-malleability is hopeless if the class of tampering...

Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography. In particular, progress in the study of non-malleable codes and the related notion of...

Secure Message Transmission (SMT) is a two-party cryptographic scheme by which a sender securely and reliably sends messages to a receiver using $n$ channels. Suppose that an adversary corrupts at most $t$ out of $n$ channels and makes eavesdropping or tampering over the corrupted channels. It is known that if $t < n/2$ then the perfect SMT (PSMT) in the information-theoretic sense is achievable and if $t\ge n/2$ then no PSMT scheme is possible to construct. If we are allowed to use a public...

In a recent result, Dachman-Soled et al.(TCC '15) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering. The bounded retrieval model (BRM) (cf. [Alwen et al.,...

Algebraic manipulation detection codes are a class of error detecting codes which have found numerous applications in cryptography. In this paper we extend these codes to defeat general algebraic attacks - we call such codes general algebraic manipulation detection (GAMD) codes. Positive results are shown for the existence of GAMDs for the families of tampering functions corresponding to point additions and polynomial functions over a finite field. Compared to non-malleable codes, we...

We show that a family of quantum authentication protocols introduced in [Barnum et al., FOCS 2002] can be used to construct a secure quantum channel and additionally recycle all of the secret key if the message is successfully authenticated, and recycle part of the key if tampering is detected. We give a full security proof that constructs the secure channel given only insecure noisy channels and a shared secret key. We also prove that the number of recycled key bits is optimal for this...

In a recent result, Dachman-Soled et al.~(TCC '15) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering. Unfortunately, the locality of their construction in...

Non-Malleable Codes for the split state model allow to encode a mes- sage into two parts such that arbitrary independent tampering on the parts either destroys completely the content or maintains the message untouched. If the code is also leakage resilient it allows limited independent leakage from the two parts. We propose a model where the two parts can be refreshed independently. We give an abstract framework for building codes for this model, instantiate the construc- tion under the...

Smart contracts are computer programs that can be correctly executed by a network of mutually distrusting nodes, without the need of an external trusted authority. Since smart contracts handle and transfer assets of considerable value, besides their correct execution it is also crucial that their implementation is secure against attacks which aim at stealing or tampering the assets. We study this problem in Ethereum, the most well-known and used framework for smart contracts so far. We...

Non-malleable codes are kind of encoding schemes which are resilient to tampering attacks. The main idea behind the non-malleable coding is that the adversary can't be able to obtain any valuable information about the message. Non-malleable codes are used in tamper resilient cryptography and protecting memory against tampering attacks. Several kinds of definitions for the non-malleability exist in the literature. The Continuous non-malleability is aiming to protect messages against the...

We revisit the question of constructing public-key encryption and signature schemes with security in the presence of bounded leakage and tampering memory attacks. For signatures we obtain the first construction in the standard model; for public-key encryption we obtain the first construction free of pairing (avoiding non-interactive zero-knowledge proofs). Our constructions are based on generic building blocks, and, as we show, also admit efficient instantiations under fairly standard...

Non-malleable codes were introduced by Dziembowski et al. (ICS 2010) as coding schemes that protect a message against tampering attacks. Roughly speaking, a code is non-malleable if decoding an adversarially tampered encoding of a message m produces the original message m or a value m' (eventually abort) completely unrelated with m. It is known that non-malleability is possible only for restricted classes of tampering functions. Since their introduction, a long line of works has established...

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are \emph{seeded non-malleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless non-malleable extractors}, introduced by Cheraghchi and Guruswami \cite{CG14b}; and \emph{non-malleable codes}, introduced by Dziembowski, Pietrzak and Wichs ...

We show how to construct efficient, unconditionally secure non-malleable codes for bounded output locality. In particular, our scheme is resilient against functions such that any output bit is dependent on at most $n^{\delta}$ bits, where $n$ is the total number of bits in a codeword and $0 \leq \delta < 1$ a constant. Notably, this tampering class includes $\mathsf{NC}^0$.

Cryptographic protection of memory is an essential ingredient for any technology that allows a closed computing system to run software in a trustworthy manner and handle secrets, while its external memory is susceptible to eavesdropping and tampering. An example for such a technology is Intel's emerging Software Guard Extensions technology (Intel SGX) that appears in the latest processor generation, Architecture Codename Skylake. This technology operates under the assumption that the...

A non-malleable encoding scheme is a keyless encoding scheme which is resilient to tampering attacks. Such a scheme is said to be continuously secure if the scheme is resilient to attacks containing more than one tampering procedure. Also, such a scheme is said to have tamper-detection property if any kind of tampering attack is detected. In [S. Faust, et al., Continuous nonmalleable codes, TCC Proc., LNCS Vol. 8349, 2014.] a general continuous non-malleable encoding scheme based on NIZK...

In the ordinary security model for signature schemes, we consider an adversary that may forge a signature on a new message using only his knowledge of other valid message and signature pairs. To take into account side channel attacks such as tampering or fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In RKA for signature schemes, the adversary can also manipulate the signing key and obtain...

Non-malleable codes are a generalization of classical error-correcting codes where the act of ``corrupting'' a codeword is replaced by a ``tampering'' adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the original message m, or a completely unrelated one. In the common split-state model, the codeword consists of multiple blocks (or states) and each block is tampered with independently. The central goal in the split-state model is to...

Error correcting codes, though powerful, are only applicable in scenarios where the adversarial channel does not introduce ``too many" errors into the codewords. Yet, the question of having guarantees even in the face of many errors is well-motivated. Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), address precisely this question. Such codes guarantee that even if an adversary completely over-writes the codeword, he cannot transform it into a codeword for a...

Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography. A large body of the recent work has focused on various constructions of non-malleable codes in...

We present the first stateless construction of a cryptographically-secure Physical Unclonable Function. Our construct requires no non-volatile (permanent) storage, secure or otherwise, and its computational security can be clearly reduced to the hardness of Learning Parity with Noise (LPN) in the random oracle model. The construction is ``stateless,'' because there is \emph{no} information stored between subsequent queries, which mitigates attacks against the PUF via tampering. Moreover,...

Given the increasing adoption of Bitcoin, the number of transactions and the block sizes within the system are only expected to increase. To sustain its correct operation in spite of its ever-increasing use, Bitcoin implements a number of necessary optimizations and scalability measures. These measures limit the amount of information broadcast in the system to the minimum necessary. In this paper, we show that current scalability measures adopted by Bitcoin come at odds with the security of...