thesis.pdf (1.3 MB)

Download file# ON THE EFFICIENCY OF CRYPTOGRAPHIC CONSTRUCTIONS

Cryptography allows us to do magical things ranging from private communication over a
public channel to securely evaluating functions among distrusting parties. For the real-world
implementation of these tasks, efficiency is usually one of the most desirable objectives. In
this work, we advance our understanding of efficient cryptographic constructions on several
fronts.

Non-malleable codes are a natural generalization of error-correcting codes. It provides
a weaker yet meaningful security guarantee when the adversary may tamper with the
codeword such that error-correcting is impossible. Intuitively, it guarantees that the
tampered codeword either encodes the original message or an unrelated one. This line
of research aims to construct non-malleable codes with a high rate against sophisticated
tampering families. In this work, we present two results. The first one is an explicit rate1 construction against all tampering functions with a small locality. Second, we present
a rate-1/3 construction for three-split-state tampering and two-lookahead tampering.

In multiparty computation, fair computation asks for the most robust security, namely,
guaranteed output delivery. That is, either all parties receive the output of the protocol,
or no party does. By relying on oblivious transfer, we know how to construct MPC
protocols with optimal fairness. For a long time, however, we do not know if one can
base optimal fair protocol on weaker assumptions such as one-way functions. Typically,
symmetric-key primitives (e.g., one-way functions) are much faster than public-key primitives (e.g., oblivious transfer). Hence, understanding whether one-way functions enable
optimal fair protocols has a significant impact on the efficiency of such protocols. This
work shows that it is impossible to construct optimal fair protocols with only black-box
uses one-way functions. We also rule out constructions based on public-key encryptions
and f-hybrids, where f is any incomplete function.

Collective coin-tossing considers a coin-tossing protocol among n parties. A Byzantine
adversary may adaptively corrupt parties to bias the output of the protocol. The security
ε is defined as how much the adversary can change the expected output of the protocol.
In this work, we consider the setting where an adversary corrupts at most one party.
10
Given a target security ε, we wish to understand the minimum number of parties n
required to achieve ε-security. In this work, we prove a tight bound on the optimal
security. In particular, we show that the insecurity of the well-known threshold protocol
is at most two times the optimal achievable security.

## Funding

### CRII: SaTC: Computational Correlations: A New Tool for Cryptography

Directorate for Computer & Information Science & Engineering

Find out more...### TWC: Small: General and Modular Secure Computation in the Offline-Online Paradigm

Directorate for Computer & Information Science & Engineering

Find out more...