CryptoDB
How Low Can We Go?
| Authors: |
|
|---|---|
| Download: | |
| Honor: | Invited talk |
| Abstract: | Given a cryptographic task, such as encrypting a message or securely computing a given function, a natural question is to find the "minimal cost" of carrying out this task. The question can take a variety of forms, depending on the cost measure. For instance, one can try to minimize computation, communication, rounds, or randomness. In the case of computational cost, one can consider different computation models, such as circuits or branching programs, and different cost metrics, such as size or depth. The answer to the question may further depend on the type of computational assumptions one is willing to make. The study of this question, for different cryptographic tasks and clean asymptotic cost measures, has led to a rich body of work with useful and often unexpected results. The talk will survey some of this work, highlighting connections between different research areas in cryptography and relevance beyond cryptography. In addition to the direct interest in minimizing well-motivated complexity measures, there are cases in which ``high-end' cryptographic tasks, such as secure multiparty computation or program obfuscation, call for minimizing different cost measures of lower-end primitives that would otherwise seem poorly motivated. I will give some examples of this kind. Finally, I will make the case that despite the progress already made, there is much more to be explored. Research in this area can greatly benefit from more cooperation between theoretical and applied cryptographers, as well as between cryptographers and researchers from other fields, including computational complexity, algorithms, computational learning theory, coding and information theory. |
BibTeX
@misc{pkc-2020-30325,
title={How Low Can We Go?},
url={https://eprint.iacr.org/2020/576.pdf},
note={Invited talk},
author={Yuval ishai},
year=2020
}