Publication: Research › Ph.D. thesis

- Bernardo Machado Davids thesis
Final published version, 1 MB, PDF-document

- Bernardo Machado DavidBernardo Machado David

Commitment schemes are a fundamental primitive in modern cryptography, serving as a building block for a myriad of complex protocols and applications. Universally composable commitment schemes are of particular interest, since they can be seamlessly combined with other universally composable primitives and protocols while retaining security guarantees. Moreover, commitments with homomorphic properties enable significantly more efficient constructions of protocols for applications such as zero knowledge proofs, two-party computation through garbled circuits and multiparty computation. However, achieving universal composability for commitment schemes often sacrifices both concrete and asymptotic efficiency, specially if homomorphic properties are required.

In this thesis we bridge the gap between stand alone and universally composable commitment schemes, for which we achieve optimal efficiency while obtaining homomorphic properties. We obtain schemes with amortized linear computational complexity and an optimal amortized ratio between message length and the amount of communication required to commit to a message, which we call \emph{rate}. We also construct schemes with additive and/or multiplicative homomorphism. Our best scheme achieves linear complexity for both the sender and the receiver, rate-1 and additive homomorphism. On the other hand, schemes with both multiplicative and additive homomorphism based on our approach can only achieve poly-logarithmic overhead for both communication and computational complexity.

We develop a technique for constructing universally composable commitments schemes that allow for an \emph{unlimited} number of commitments using solely cheap symmetric key operations after a setup phase that requires only a small number of expensive public key operations completely independent from both the number of commitments to be executed later and their contents. The downside of achieving universal composability for most interesting two party and multiparty functionalities lies on the fact that some form of \emph{setup} is required. We use a number of oblivious transfers only related to a statistical security parameter as a setup. The rest of our constructions leverage secret sharing and coding theory techniques, including a novel method for verifying that a large number of strings are codewords of a given linear code with linear complexity.

In this thesis we bridge the gap between stand alone and universally composable commitment schemes, for which we achieve optimal efficiency while obtaining homomorphic properties. We obtain schemes with amortized linear computational complexity and an optimal amortized ratio between message length and the amount of communication required to commit to a message, which we call \emph{rate}. We also construct schemes with additive and/or multiplicative homomorphism. Our best scheme achieves linear complexity for both the sender and the receiver, rate-1 and additive homomorphism. On the other hand, schemes with both multiplicative and additive homomorphism based on our approach can only achieve poly-logarithmic overhead for both communication and computational complexity.

We develop a technique for constructing universally composable commitments schemes that allow for an \emph{unlimited} number of commitments using solely cheap symmetric key operations after a setup phase that requires only a small number of expensive public key operations completely independent from both the number of commitments to be executed later and their contents. The downside of achieving universal composability for most interesting two party and multiparty functionalities lies on the fact that some form of \emph{setup} is required. We use a number of oblivious transfers only related to a statistical security parameter as a setup. The rest of our constructions leverage secret sharing and coding theory techniques, including a novel method for verifying that a large number of strings are codewords of a given linear code with linear complexity.

Original language | English |
---|

Place of Publication | Aarhus, Denmark |
---|---|

Publisher | Department of Computer Science, University of Aarhus |

Number of pages | 106 |

State | Published - 5 May 2017 |

- Universal Composability, Commitment, Verifiable Secret Sharing, Provable Security, Information Theory

See relations at Aarhus University Citationformats

ID: 109205418