The paper introduces a new concept called *on-the-fly multiparty computation (MPC)*, which allows a computationally powerful but untrusted "cloud" server to perform arbitrary, dynamically chosen computations on data from arbitrary sets of users without interaction. This extends the standard notion of fully homomorphic encryption (FHE), where users can only use the cloud to evaluate functions on their own encrypted data. In on-the-fly MPC, each user is involved only when uploading their encrypted data to the cloud and in a final output decryption phase, with the complexity of both phases independent of the function being computed or the number of users. The paper presents two main contributions: 1. **Multikey FHE**: A new type of encryption scheme that can operate on inputs encrypted under multiple, unrelated keys. A ciphertext resulting from a multikey evaluation can be jointly decrypted using the secret keys of all involved users. 2. **On-the-Fly MPC from Multikey FHE**: A construction of multikey FHE based on NTRU, an efficient public-key encryption scheme. The paper shows that any FHE scheme can be made multikey for a constant number of keys and that the Ring-LWE-based FHE scheme can handle a logarithmic number of keys. The paper also demonstrates how to achieve on-the-fly MPC using multikey FHE, with a protocol that is secure against semi-malicious corruptions. The protocol involves an offline phase where users encrypt their data and send it to the cloud, followed by an online phase where the cloud performs the computation and broadcasts the result. Users then decrypt the result using a generic MPC protocol. The paper discusses the security of the protocol, including the use of zero-knowledge proofs and succinct argument systems to ensure the correctness of the computation. Finally, the paper addresses the impossibility of achieving a completely non-interactive on-the-fly MPC, as it would require generic program obfuscation, which is not possible.The paper introduces a new concept called *on-the-fly multiparty computation (MPC)*, which allows a computationally powerful but untrusted "cloud" server to perform arbitrary, dynamically chosen computations on data from arbitrary sets of users without interaction. This extends the standard notion of fully homomorphic encryption (FHE), where users can only use the cloud to evaluate functions on their own encrypted data. In on-the-fly MPC, each user is involved only when uploading their encrypted data to the cloud and in a final output decryption phase, with the complexity of both phases independent of the function being computed or the number of users. The paper presents two main contributions: 1. **Multikey FHE**: A new type of encryption scheme that can operate on inputs encrypted under multiple, unrelated keys. A ciphertext resulting from a multikey evaluation can be jointly decrypted using the secret keys of all involved users. 2. **On-the-Fly MPC from Multikey FHE**: A construction of multikey FHE based on NTRU, an efficient public-key encryption scheme. The paper shows that any FHE scheme can be made multikey for a constant number of keys and that the Ring-LWE-based FHE scheme can handle a logarithmic number of keys. The paper also demonstrates how to achieve on-the-fly MPC using multikey FHE, with a protocol that is secure against semi-malicious corruptions. The protocol involves an offline phase where users encrypt their data and send it to the cloud, followed by an online phase where the cloud performs the computation and broadcasts the result. Users then decrypt the result using a generic MPC protocol. The paper discusses the security of the protocol, including the use of zero-knowledge proofs and succinct argument systems to ensure the correctness of the computation. Finally, the paper addresses the impossibility of achieving a completely non-interactive on-the-fly MPC, as it would require generic program obfuscation, which is not possible.