  Outsourced computing is widely used today. However, current approaches for
protecting client data in outsourced computing fall short: use of cryptographic
techniques like fully-homomorphic encryption incurs substantial costs, whereas
use of hardware-assisted trusted execution environments has been shown to be
vulnerable to run-time and side-channel attacks.
  We present Blinded Memory (BliMe), an architecture to realize efficient and
secure outsourced computation. BliMe consists of a novel and minimal set of
instruction set architecture (ISA) extensions implementing a taint-tracking
policy to ensure the confidentiality of client data even in the presence of
server vulnerabilities. To secure outsourced computation, the BliMe extensions
can be used together with an attestable, fixed-function hardware security
module (HSM) and an encryption engine that provides atomic decrypt-and-taint
and encrypt-and-untaint operations. Clients rely on remote attestation and key
agreement with the HSM to ensure that their data can be transferred securely to
and from the encryption engine and will always be protected by BliMe's
taint-tracking policy while at the server.
  We provide an RTL implementation BliMe-BOOM based on the BOOM RISC-V core.
BliMe-BOOM requires no reduction in clock frequency relative to unmodified
BOOM, and has minimal power ($<\!1.5\%$) and FPGA resource ($\leq\!9.0\%$)
overheads. Various implementations of BliMe incur only moderate performance
overhead ($8--25\%$). We also provide a machine-checked security proof of a
simplified model ISA with BliMe extensions.
