International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Andrej Bogdanov

Publications

Year
Venue
Title
2022
TCC
Public-Key Encryption from Homogeneous CLWE
The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known. We present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge oracle.
2021
TCC
Acyclicity Programming for Sigma-Protocols 📺
Cramer, Damgård, and Schoenmakers (CDS) built a proof system to demonstrate the possession of subsets of witnesses for a given collection of statements that belong to a prescribed access structure P by composing so-called sigma-protocols for each atomic statement. Their verifier complexity is linear in the size of the monotone span program representation of P. We propose an alternative method for combining sigma-protocols into a single non-interactive system for a compound statement in the random oracle model. In contrast to CDS, our verifier complexity is linear in the size of the acyclicity program representation of P, a complete model of monotone computation introduced in this work. We show that the acyclicity program size of a predicate is never larger than its de Morgan formula size and it is polynomially incomparable to its monotone span program size. We additionally present an extension of our proof system, with verifier complexity linear in the monotone circuit size of P, in the common reference string model. Finally, considering the types of statement that naturally reduce to acyclicity programming, we discuss several applications of our new methods to protecting privacy in cryptocurrency and social networks.
2021
JOFC
2021
JOFC
Unconditionally Secure Computation Against Low-Complexity Leakage
We consider the problem of constructing leakage-resilient circuit compilers that are secure against global leakage functions with bounded output length. By global, we mean that the leakage can depend on all circuit wires and output a low-complexity function (represented as a multi-output Boolean circuit) applied on these wires. In this work, we design compilers both in the stateless (a.k.a. single-shot leakage) setting and the stateful (a.k.a. continuous leakage) setting that are unconditionally secure against $$\mathsf {AC}^0$$ AC 0 leakage and similar low-complexity classes. In the stateless case, we show that the original private circuits construction of Ishai, Sahai, and Wagner (Crypto 2003) is actually secure against $$\mathsf {AC}^0$$ AC 0 leakage. In the stateful case, we modify the construction of Rothblum (Crypto 2012), obtaining a simple construction with unconditional security. Prior works that designed leakage-resilient circuit compilers against $$\mathsf {AC}^0$$ AC 0 leakage had to rely either on secure hardware components (Faust et al., Eurocrypt 2010, Miles-Viola, STOC 2013) or on (unproven) complexity-theoretic assumptions (Rothblum, Crypto 2012).
2020
ASIACRYPT
Non-Interactive Composition of Sigma-Protocols via Share-then-Hash 📺
Proofs of partial knowledge demonstrate the possession of certain subsets of witnesses for a given collection of statements x_1,\dots,x_n. Cramer, Damg{\aa}rd, and Schoenmakers (CDS), built proofs of partial knowledge, given "atomic" protocols for individual statements x_i, by having the prover randomly secret share the verifier's challenge and using the shares as challenges for the atomic protocols. This simple and highly-influential transformation has been used in numerous applications, ranging from anonymous credentials to ring signatures. We consider what happens if, instead of using the shares directly as challenges, the prover first hashes them. We show that this elementary enhancement can result in significant benefits: - the proof contains a {\em single} atomic transcript per statement x_i, - it suffices that the atomic protocols are k-special sound for k \geq 2, - when compiled using the Fiat-Shamir heuristic, the protocol retains its soundness in the {\em non-programmable} random oracle model. None of the above features is satisfied by the CDS transformation.
2019
CRYPTO
Unconditionally Secure Computation Against Low-Complexity Leakage 📺
We consider the problem of constructing leakage-resilient circuit compilers that are secure against global leakage functions with bounded output length. By global, we mean that the leakage can depend on all circuit wires and output a low-complexity function (represented as a multi-output Boolean circuit) applied on these wires. In this work, we design compilers both in the stateless (a.k.a. single-shot leakage) setting and the stateful (a.k.a. continuous leakage) setting that are unconditionally secure against $$\mathsf {AC}^0$$ leakage and similar low-complexity classes.In the stateless case, we show that the original private circuits construction of Ishai, Sahai, and Wagner (Crypto 2003) is actually secure against $$\mathsf {AC}^0$$ leakage. In the stateful case, we modify the construction of Rothblum (Crypto 2012), obtaining a simple construction with unconditional security. Prior works that designed leakage-resilient circuit compilers against $$\mathsf {AC}^0$$ leakage had to rely either on secure hardware components (Faust et al., Eurocrypt 2010, Miles-Viola, STOC 2013) or on (unproven) complexity-theoretic assumptions (Rothblum, Crypto 2012).
2016
CRYPTO
2016
TCC
2016
TCC
2016
TCC
2016
JOFC
2015
TCC
2013
CRYPTO

Program Committees

Crypto 2021
TCC 2021
TCC 2020
Eurocrypt 2019
TCC 2018
TCC 2016