CWI Cryptology Group

Abstract: Compressed Σ-protocols present a strengthening of the well-established Σ-protocol theory, yielding (zero-knowledge) interactive proofs with low communication complexity. They show how to compress the communication complexity of basic Σ-protocols from linear down to (poly)logarithmic, using a recursive ``folding-technique'' adapted from Bulletproofs (Bootle et al., EUROCRYPT 2016, and Bünz et al., S&P 2018), at the expense of a logarithmic number of rounds. This abstract modular theory can be instantiated from a variety of cryptographic hardness assumptions, i.e., the discrete-logarithm, strong-RSA, knowledge-of-exponent and short-integer-solution assumption. The analysis of these and other interactive proofs requires the construction of a so-called knowledge extractor, showing that dishonest provers without knowledge of a secret witness cannot falsely convince a verifier. However, prior proof techniques are no longer directly applicable. More precisely, the multi-round nature of these interactive proofs renders prior knowledge extractors inefficient. In this talk, we will introduce compressed Σ-protocol theory and present several new techniques for analyzing the knowledge soundness of multi-round interactive proofs.

Abstract: The Internet Computer offers publicly accessible and globally available trustworthy computing via powerful web-enabled smart contracts. Over the last year it has added capability to do http requests and native Bitcoin integration. The Bitcoin integration enable smart contracts to receive and transfer bitcoin, where outgoing transactions are signed using a threshold ECDSA signing service. The design of the threshold ECDSA service uses a couple of optimizations. BIP32 additive key derivation allows the Internet Computer to use a single ECDSA master public key to derive individual public keys for smart contracts, which simplifies key management to a single secret-shared signing key. It is common in threshold ECDSA signing protocols to precompute certain group elements to reduce the online computation when signing. Motivated by the Bitcoin integration and development of a decentralized ECDSA signing service, we analyze the security of plain ECDSA with additive key derivation and pre-computation in the generic group model. Our analysis shows that additive key generation is secure and pre-computation is secure, but combining additive key derivation and pre-computation leads to non-tight security. Fortunately, we can save the combination and tighten security through public re-randomization of the precomputation. In this overview talk, I’ll give an introduction to the Internet Computer and take a tour from Bitcoin integration and threshold ECDSA signing to our cryptographic security analysis of ECDSA.

Abstract: In his landmark paper at TCC 2008 Paul Valiant introduced the notion of “incrementally verifiable computation” which enables a prover to incrementally compute a succinct proof of correct execution of a (potentially) long running process. The paper later won the 2019 TCC test of time award. The construction was proven secure in the random oracle model without any further computational assumptions. However, the overall proof was given using a non-standard version of the random-oracle methodology where sometimes the hash function is a random oracle and sometimes it has a short description as a circuit. Valiant clearly noted that this model is non-standard, but conjectured that the standard random oracle methodology would not suffice. This conjecture has been open for 14 years. We prove that if the proof system can receive a long witness as input in an incremental manner and is also zero-knowledge then the conjecture is true. Valiant’s original construction does not have these properties but can easily be extended to have them in his model. We relate our result to recent possibility and impossibility results for SNARKs and incrementally verifiable computation.