Opendata, web and dolomites


Cryptography with Low Complexity

Total Cost €


EC-Contrib. €






Project "CLC" data sheet

The following table provides information about the project.


Organization address
address: RAMAT AVIV
city: TEL AVIV
postcode: 69978

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Israel [IL]
 Project website
 Total cost 1˙265˙750 €
 EC max contribution 1˙265˙750 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2014-STG
 Funding Scheme ERC-STG
 Starting year 2015
 Duration (year-month-day) from 2015-05-01   to  2021-04-30


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    TEL AVIV UNIVERSITY IL (TEL AVIV) coordinator 1˙265˙750.00


 Project objective

The efficiency of cryptographic constructions is a fundamental question. Theoretically, it is important to understand how much computational resources are needed to guarantee strong notions of security. Practically, highly efficient schemes are always desirable for real-world applications. More generally, the possibility of cryptography with low complexity has wide applications for problems in computational complexity, combinatorial optimization, and computational learning theory.

In this proposal we aim to understand what are the minimal computational resources needed to perform basic cryptographic tasks. In a nutshell, we suggest to focus on three main objectives. First, we would like to get better understanding of the cryptographic hardness of random local functions. Such functions can be computed by highly-efficient circuits and their cryptographic hardness provides a strong and clean formulation for the conjectured average-case hardness of constraint satisfaction problems - a fundamental subject which lies at the core of the theory of computer science. Our second objective is to harness our insights into the hardness of local functions to improve the efficiency of basic cryptographic building blocks such as pseudorandom functions. Finally, our third objective is to expand our theoretical understanding of garbled circuits, study their limitations, and improve their efficiency.

The suggested project can bridge across different regions of computer science such as random combinatorial structures, cryptography, and circuit complexity. It is expected to impact central problems in cryptography, while enriching the general landscape of theoretical computer science.


year authors and title journal last update
List of publications.
2017 Benny Applebaum, Ivan Damgård, Yuval Ishai, Michael Nielsen, Lior Zichron
Secure Arithmetic Computation with Constant Computational Overhead
published pages: 223-254, ISSN: , DOI: 10.1007/978-3-319-63688-7_8
Annual International Cryptology Conference CRYPTO 2017: Advances in Cryptology – CRYPTO 2017 2019-07-22
2017 Benny Applebaum, Jonathan Avron, Chris Brzuska
Arithmetic Cryptography
published pages: 1-74, ISSN: 0004-5411, DOI: 10.1145/3046675
Journal of the ACM 64/2 2019-07-22
2016 Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions
published pages: 349-418, ISSN: 1016-3328, DOI: 10.1007/s00037-016-0128-9
computational complexity 25/2 2019-07-22
2017 Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-Bounds, and Separations
published pages: 727-757, ISSN: , DOI: 10.1007/978-3-319-63688-7_24
Annual International Cryptology Conference CRYPTO 2017: Advances in Cryptology – CRYPTO 2017 2019-07-22
2016 Benny Applebaum, Pavel Raykov
From Private Simultaneous Messages to Zero-Information Arthur–Merlin Protocols and Back
published pages: , ISSN: 0933-2790, DOI: 10.1007/s00145-016-9239-3
Journal of Cryptology 2019-07-22
2018 Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz
The Communication Complexity of Private Simultaneous Messages, Revisited
published pages: 261-286, ISSN: , DOI: 10.1007/978-3-319-78375-8_9
2016 Benny Applebaum
Cryptographic Hardness of Random Local Functions
published pages: 667-722, ISSN: 1016-3328, DOI: 10.1007/s00037-015-0121-8
computational complexity 25/3 2019-07-22
2017 Benny Applebaum
Garbled Circuits as Randomized Encodings of Functions: a Primer
published pages: 1-44, ISSN: , DOI: 10.1007/978-3-319-57048-8_1
Tutorials on the Foundations of Cryptography 2019-07-22
2018 Benny Applebaum, Shachar Lovett
Algebraic Attacks against Random Local Functions and Their Countermeasures
published pages: 52-79, ISSN: 0097-5397, DOI: 10.1137/16M1085942
SIAM Journal on Computing 47/1 2019-07-22
2016 Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
Minimizing Locality of One-Way Functions via Semi-private Randomized Encodings
published pages: , ISSN: 0933-2790, DOI: 10.1007/s00145-016-9244-6
Journal of Cryptology 2019-07-22

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "CLC" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "CLC" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)


The Enemy of the Good: Towards a Theory of Moral Progress

Read More  

HOLI (2019)

Deep Learning for Holistic Inference

Read More  


The Power of Randomness and Continuity in Submodular Optimization

Read More