Publications |
-
We show that the Learning with Errors (LWE) problem is classically at least as hard as
standard worst-case lattice problems, even with polynomial modulus.
Previously this was only known under quantum reductions.
Our techniques capture the tradeoff between the dimension and the modulus of LWE instances,
leading to a much better understanding of the
landscape of the problem. The proof is inspired by techniques from
several recent cryptographic constructions, most notably fully
homomorphic encryption schemes.
Zvika
Brakerski and Moni Naor
Fast Algorithms for Interactive Coding
SODA 2013.
[Abstract] [PDF]
Consider two parties who wish to communicate in order to execute some
interactive protocol $\pi$. However, the communication channel
between them is noisy: An adversary sees everything that is
transmitted over the channel and can change a constant
fraction of the bits as he pleases, thus interrupting the
execution of $\pi$ (which was designed for an errorless
channel). If $\pi$ only contains a single long message, then a
good error correcting code would overcome the noise with only
a constant overhead in communication. However, this solution
is not applicable to interactive protocols consisting of
many short messages.
Schulman (FOCS 92, STOC 93) presented the notion of interactive
coding: A simulator that, given any protocol $\pi$, is able to
simulate it (i.e.\ produce its intended transcript) even with
constant rate adversarial channel errors, and with only constant
(multiplicative) communication overhead. Until recently, however,
the running time of all known simulators was exponential (or
sub-exponential) in the communication complexity of $\pi$ (denoted
$N$ in this work). Brakerski and Kalai (FOCS 12) recently presented
a simulator that runs in time $\poly(N)$. Their simulator is
randomized (each party flips private coins) and has failure
probability roughly $2^{-N}$.
In this work, we improve the computational complexity of interactive
coding. While at least $N$ computational steps are required (even
just to output the transcript of $\pi$), the BK simulator runs in
time $\tilde\Omega(N^2)$.
We present two efficient algorithms for interactive coding: The first with computational complexity $O(N \log N)$ and exponentially small (in $N$) failure probability; and the second with computational complexity $O(N)$, but failure probability $1/\poly(N)$. (Computational complexity is measured in the RAM model.)
Zvika
Brakerski, Craig
Gentry and Shai Halevi
Packed Ciphertexts in LWE-based Homomorphic Encryption
PKC 2013.
[Abstract] [PDF]
We observe that the Peikert-Vaikuntanathan-Waters (PVW) method of packing many plaintext elements in a single Regev-type ciphertext, can be used for performing SIMD homomorphic operations on packed ciphertext. This provides an alternative to the Smart-Vercauteren (SV) ciphertext-packing technique that relies on polynomial-CRT. While the SV technique is only applicable to schemes that rely on ring-LWE (or other hardness assumptions in ideal lattices), the PVW method can be used also for cryptosystems whose security is based on standard LWE (or more broadly on the hardness of ``General-LWE'').
Although using the PVW method with LWE-based schemes leads to worse asymptotic efficiency than using the SV technique with ring-LWE schemes, the simplicity of this method may still offer some practical advantages. Also, the two techniques can be used in tandem with ``general-LWE'' schemes, suggesting yet another tradeoff that can be optimized for different settings.
Zvika
Brakerski
When Homomorphism Becomes a Liability
TCC 2013.
[Abstract] [PDF]
We show that an encryption scheme cannot have a simple decryption circuit and be homomorphic at the same time. Specifically, if a scheme can homomorphically evaluate the majority function, then its decryption circuit cannot be a linear function of the secret key (or even a succinct polynomial), even if decryption error is allowed.
An immediate corollary is that known schemes that are based on the hardness of decoding in the presence of noise withlow hamming weight cannot be fully homomorphic. This applies to known schemes such as LPN-based symmetric or public key encryption.
An additional corollary is that the recent candidate fully homomorphic encryption, suggested by Bogdanov and Lee (ePrint '11, henceforth BL), is insecure. In fact, we show two attacks on the BL scheme: One by applying the aforementioned general statement, and another by directly attacking one of the components of the scheme.
Zvika
Brakerski and Yael Tauman Kalai
Efficient Interactive Coding Against Adversarial Noise
FOCS 2012.
[Abstract] [PDF]
In this work, we study the fundamental problem of constructing interactive protocols that are robust to noise,
a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given an interactive protocol which is designed to run on an error-free channel, construct a protocol that evaluates the same function (or, more generally, simulates the execution of the original protocol) over a noisy channel. As in (non-interactive) error correcting codes, the noise can be either stochastic, i.e. drawn from some distribution, or adversarial, i.e. arbitrary subject only to a global bound on the number of errors.
We show how to efficiently simulate any interactive protocol in the presence of constant-rate adversarial noise, while incurring only a constant blow-up in the communication complexity ($\cc$).
Our simulator is randomized, and succeeds in simulating the original protocol with probability at least $1-2^{-\Omega(\cc)}$.
Previous solutions are either inefficient or are resilient only to stochastic noise.
Zvika Brakerski
Fully Homomorphic Encryption
without Modulus Switching from Classical GapSVP
CRYPTO 2012.
[Abstract] [PDF] We present a new tensoring technique for LWE-based fully homomorphic encryption. While in all previous works, the ciphertext noise grows quadratically ($B \to B^2\cdot\poly(n)$) with every multiplication (before ``refreshing''), our noise only grows linearly ($B \to B\cdot\poly(n)$).
We use this technique to construct a \emph{scale-invariant} fully homomorphic encryption scheme, whose properties only depend on the ratio between the modulus $q$ and the initial noise level $B$, and not on their absolute values.
Our scheme has a number of advantages over previous candidates: It uses the same modulus throughout the evaluation process (no need for ``modulus switching''), and this modulus can take arbitrary form, including a power of $2$ which carries obvious advantages for implementation. In addition, security can be classically reduced to the worst-case hardness of the GapSVP problem (with quasi-polynomial approximation factor), whereas previous constructions could only exhibit a quantum reduction to GapSVP.
Zvika Brakerski, Craig Gentry and Vinod Vaikuntanathan
(Leveled) Fully Homomorphic Encryption without Bootstrapping
ITCS 2012.
[Abstract] [PDF]
We present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and
bases security on weaker assumptions.
A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), without Gentry's bootstrapping procedure.
Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or ring-LWE (RLWE) problems that have $2^k$ security against known attacks. For RLWE, we have:
- A leveled FHE scheme that can evaluate $L$-level arithmetic circuits with $\tilde{O}(k \cdot L^3)$ per-gate computation -- i.e., computation quasi-linear in the security parameter. Security is based on RLWE for an approximation factor exponential in $L$. This construction does not use the bootstrapping procedure.
- A leveled FHE scheme that uses bootstrapping as an optimization, where the per-gate computation (which includes the bootstrapping procedure) is $\tilde{O}(k^2)$, independent of $L$. Security is based on the hardness of RLWE for quasi-polynomial factors (as opposed to the sub-exponential factors needed in previous schemes).
We obtain similar results to the above for LWE, but with worse performance.
Based on the Ring LWE assumption, we introduce a number of further optimizations to our schemes. As an example, for circuits of large width -- e.g., where a constant fraction of levels have width at least $k$ --
we can reduce the per-gate computation of the bootstrapped version to $\tilde{O}(k)$, independent of $L$,
by batching the bootstrapping operation.
Previous FHE schemes all required $\tilde{\Omega}(k^{3.5})$ computation per gate.
At the core of our construction is a much more effective approach for managing the noise level
of lattice-based ciphertexts as homomorphic operations are performed, using some new techniques recently introduced by Brakerski and Vaikuntanathan (FOCS 2011).
Zvika Brakerski and Vinod Vaikuntanathan
Efficient Fully Homomorphic Encryption from (Standard) LWE
FOCS 2011.
[Abstract] [PDF]
We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices. Additionally, relying on LWE makes our scheme very natural to understand (and implement).
Our construction improves on previous works in two aspects:
- We show that ``somewhat homomorphic'' encryption can
be based on LWE, using a new re-linearization technique. In contrast, all
previous schemes relied on complexity assumptions related to ideals in various
rings.
- We deviate from the
``squashing paradigm'' used in all previous
works. We introduce a new dimension-modulus reduction technique, which shortens the
ciphertexts and reduces the decryption complexity of our scheme, {\em without
introducing additional assumptions}. In contrast, all previous works required an
additional, very strong assumption (namely, the sparse subset sum assumption).
Our scheme has very short ciphertexts and we therefore use it to construct an
asymptotically efficient LWE-based single-server private information
retrieval (PIR) protocol. The communication complexity of our protocol (in the
public-key model) is kpolylog(k)+log |DB| bits per single-bit
query, which is better than any known scheme (here, k is a security parameter).
Zvika Brakerski and Yael Tauman Kalai
A Parallel Repetition Theorem for Leakage Resilience
TCC 2012.
[Abstract] [PDF]
A leakage resilient encryption scheme is one which stays secure even against an attacker
that obtains a bounded amount of side information on the secret key (say
$\lambda$ bits of ``leakage''). A fundamental question is whether
parallel repetition amplifies leakage resilience. Namely, if we
secret share our message, and encrypt the shares under two independent keys,
will the resulting scheme be resilient to $2\lambda$ bits of leakage?
Surprisingly, Lewko and Waters (FOCS 2010) showed that this is false. They gave an
example of a public-key encryption scheme that is resilient to $\lambda$ bits
of leakage, and yet its $2$-repetition is not resilient to even
$(1+\epsilon)\lambda$ bits of leakage. In their counter-example, the repeated
schemes share secretly generated public parameters.
In this work we show that under a reasonable strengthening of the definition of
leakage resilience (one that captures known proof techniques for achieving non-trivial
leakage resilience), parallel repetition does in fact amplify
leakage. In particular, if fresh public parameters are used for each copy of the Lewko-Waters scheme, then
their negative result does not hold, and leakage is amplified by parallel repetition.
More generally, we show that given $t$ schemes that are resilient to
$\lambda_1, \ldots, \lambda_t$ bits of leakage, respectfully, their direct
product is resilient to $\sum (\lambda_i-1)$ bits. We present our
amplification theorem in a general framework that applies other cryptographic primitives as well.
Zvika Brakerski and Vinod Vaikuntanathan
Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages
CRYPTO 2011.
[Abstract] [PDF]
We present a somewhat homomorphic encryption scheme that is both very simple to describe and analyze, and whose security (quantumly) reduces to the worst-case hardness of problems on ideal lattices. We then transform it into a fully homomorphic encryption scheme using standard ``squashing'' and ``bootstrapping'' techniques introduced by Gentry (STOC 2009).
One of the obstacles in going from ``somewhat'' to full homomorphism is the requirement that the somewhat homomorphic scheme be circular secure, namely, the scheme can be used to securely encrypt its own secret key. For all known somewhat homomorphic encryption schemes, this requirement was not known to be achievable under any cryptographic assumption, and had to be explicitly assumed. We take a step forward towards removing this additional assumption by proving that our scheme is in fact secure when encrypting polynomial functions of the secret key.
Our scheme is based on the ring learning with errors (RLWE) assumption that was recently introduced by Lyubashevsky, Peikert and Regev (Eurocrypt 2010). The RLWE assumption is reducible to worst-case problems on ideal lattices, and allows us to completely abstract out the lattice interpretation, resulting in an extremely simple scheme. For example, our secret key is s, and our public key is (a,b=as+2e), where s,a,e are all degree (n-1) integer polynomials whose coefficients are independently drawn from easy to sample distributions.
Zvika Brakerski and Gil Segev
Better Security for Deterministic Public-Key Encryption: The Auxiliary-Input Setting
CRYPTO 2011.
[Abstract] [PDF]
Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O'Neill (CRYPTO '07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security when the plaintext is distributed over a small set. Bellare et al. addressed this difficulty by requiring semantic security to hold only when the plaintext has high min-entropy from the adversary's point of view.
In many applications, however, an adversary may obtain auxiliary information that is related to the plaintext. Specifically, when deterministic encryption is used as a building block of a larger system, it is rather likely that plaintexts do not have high min-entropy from the adversary's point of view. In such cases, the framework of Bellare et al. might fall short from providing robust security guarantees.
We formalize a framework for studying the security of deterministic public-key encryption schemes with respect to auxiliary inputs. Given the trivial requirement that the plaintext should not be efficiently recoverable from the auxiliary input, we focus on hard-to-invert auxiliary inputs. Within this framework, we propose two schemes: the first is based on the decisional Diffie-Hellman (and, more generally, on the $d$-linear) assumption, and the second is based on a rather general class of subgroup indistinguishability assumptions (including, in particular, quadratic residuosity and Paillier's composite residuosity). Our schemes are secure with respect to any auxiliary input that is subexponentially hard to invert (assuming the standard hardness of the underlying computational assumptions). In addition, our first scheme is secure even in the multi-user setting where related plaintexts may be encrypted under multiple public keys. Constructing a scheme that is secure in the multi-user setting (even without considering auxiliary inputs) was identified by Bellare et al. as an important open problem.
Zvika Brakerski, Jonathan Katz, Gil Segev and Arkady Yerukhimovich
Limits on the Power of Zero-Knowledge Proofs in Cryptographic Constructions
TCC 2011.
[Abstract] [PDF]
For over 20 years, black-box impossibility results have been used
to argue the infeasibility of constructing certain cryptographic
primitives (e.g., key agreement) from others (e.g., one-way
functions). A widely recognized limitation of such impossibility
results, however, is that they say nothing about the usefulness of
(known) nonblack-box techniques. This is
unsatisfying, as we would at least like to rule out constructions
using the set of techniques we have at our disposal.
With this motivation in mind, we suggest a new framework for
black-box constructions that encompasses constructions with a
nonblack-box flavor: specifically, those that rely on
zero-knowledge proofs relative to some oracle. We show that
our framework is powerful enough to capture the Naor-Yung/Sahai
paradigm for building a (shielding) CCA-secure public-key encryption
scheme from a CPA-secure one, something ruled out by prior
black-box separation results. On the other hand, we show that several
black-box impossibility results still hold even in a
setting that allows for zero-knowledge proofs.
Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz and Vinod Vaikuntanathan
Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage
FOCS 2010.
[Abstract] [PDF]
In recent years, there has been a major effort to design cryptographic schemes that remain secure even if part of the secret key is leaked. This is due to a recent proliferation of side channel attacks which, through various physical means, can recover part of the secret key. We explore the possibility of achieving security even with continual leakage, i.e., even if some information is leaked each time the key is used.
We show how to securely update a secret key while information is leaked: We construct schemes that remain secure even if an attacker, at each time period, can probe the entire memory (containing a secret key) and ``leak'' up to a $(1-o(1))$ fraction of the secret key. The attacker may also probe the memory during the updates, and leak $O(\log k)$ bits, where $k$ is the security parameter (relying on subexponential hardness allows $k^\epsilon$ bits of leakage during each update process). All of the above is achieved without restricting the model as is done in previous works (e.g. by assuming that ``only computation leaks information'' [Micali-Reyzin, TCC04]).
Specifically, under the decisional linear assumption on bilinear groups (which allows for a leakage rate of $(1/2-o(1))$) or the symmetric external Diffie-Hellman assumption (which allows for a leakage rate of $(1-o(1))$), we achieve the above for public key encryption, identity-based encryption, and signature schemes. Prior to this work, it was not known how to construct public-key encryption schemes even in the more restricted model of [MR].
The main contributions of this work are (1) showing how to securely update a secret key while information is leaked (in the more general model) and (2) giving a public key encryption (and IBE) schemes that are resilient to continual leakage.
Zvika Brakerski and Shafi Goldwasser
Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability
(or: Quadratic Residuosity Strikes Back)
CRYPTO 2010.
[Abstract] [PDF]
The main results of this work are new public-key encryption schemes
that, under the quadratic residuosity (QR) assumption (or
Paillier's decisional composite residuosity (DCR) assumption), achieve key-dependent
message security as well as high resilience to secret key leakage
and high resilience to the presence of auxiliary input information.
In particular, under what we call the subgroup
indistinguishability assumption, of which the QR and DCR are special
cases, we can construct a scheme that has:
- Key-dependent message (circular) security. Achieves security
even when encrypting affine functions of its own secret key (in fact,
w.r.t.\ affine ``key-cycles'' of predefined length). Our scheme also
meets the requirements for extending key-dependent message security to
broader classes of functions beyond affine functions using previous
techniques of [BGK, ePrint09] or [BHHI, Eurocrypt10].
- Leakage resiliency.
Remains secure even if any
adversarial low-entropy (efficiently computable) function of the
secret key is given to the adversary. A proper selection of parameters
allows for a ``leakage rate'' of $(1-o(1))$ of the length of the secret key.
- Auxiliary-input security. Remains secure even if
any sufficiently \emph{hard to invert} (efficiently computable) function of the
secret key is given to the adversary.
Our scheme is the first to achieve key-dependent security and auxiliary-input
security based on the DCR and QR assumptions. Previous schemes that achieved
these properties relied either on the DDH or LWE assumptions. The proposed
scheme is also the first to achieve leakage resiliency for leakage rate
$(1-o(1))$ of the secret key length, under the QR assumption. We note that
leakage resilient schemes under the DCR and the QR assumptions, for the
restricted case of composite modulus product of safe primes, were implied by
the work of [NS, Crypto09], using hash proof systems. However, under the QR
assumption, known constructions of hash proof systems only yield a leakage rate
of $o(1)$ of the secret key length.
Zvika Brakerski and Yael Tauman Kalai
A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model
Manuscript, 2010.
[Abstract] [PDF]
In this work, we present a generic framework for constructing efficient signature scheme, ring signature schemes, and identity based encryption schemes, all in the standard model (without relying on random oracles).
We start by abstracting the recent work of Hohenberger and Waters (Crypto 2009), and specifically their ``prefix method''. We show a transformation taking a signature scheme with a very weak security guarantee (a notion that we call a-priori-message unforgeability under static chosen message attack) and producing a fully secure signature scheme (i.e., existentially unforgeable under adaptive chosen message attack). Our transformation uses the notion of chameleon hash functions, defined by Krawczyk and Rabin (NDSS 2000) and the ``prefix method''. Constructing such weakly secure schemes seems to be significantly easier than constructing fully secure ones, and we present simple constructions based on the RSA assumption, the short integer solution (SIS) assumption, and the computational Diffie-Hellman (CDH) assumption over bilinear groups.
Next, we observe that this general transformation also applies to the regime of ring signatures. Using this observation, we construct new (provably secure) ring signature schemes: one is based on the short integer solution (SIS) assumption, and the other is based on the CDH assumption over bilinear groups. As a building block for these constructions, we define a primitive that we call ring trapdoor functions. We show that ring trapdoor functions imply ring signatures under a weak definition, which enables us to apply our transformation to achieve full security.
Finally, we show a connection between ring signatures and identity based encryption (IBE) schemes. Using this connection, and using our new constructions of ring signature schemes, we obtain two IBE schemes: The first is based on the learning with error (LWE) assumption, and is similar to recently introduced IBE schemes; The second is based on the $d$-linear assumption over bilinear groups.
Zvika Brakerski, Shafi Goldwasser and Yael Tauman Kalai
Black-Box Circular-Secure Encryption Beyond Affine Functions
TCC 2011.
[Abstract] [PDF]
We show how to achieve public-key encryption schemes that can securely encrypt
nonlinear functions of their own secret key.
Specifically, we show that for any constant $d\in\mathbb{N}$, there exists a
public-key encryption scheme that can securely encrypt any function $f$ of its
own secret key, assuming $f$ can be expressed as a polynomial of total
degree $d$. Such a scheme is said to be key-dependent message (KDM) secure
w.r.t. degree-$d$ polynomials. We also show that for any constants $c,e$,
there exists a public-key encryption scheme that is KDM secure w.r.t. all
Turing machines with description size $c\log \lambda$ and running time
$\lambda^e$, where $\lambda$ is the security parameter. The security of such
public-key schemes can be based either on the standard decision Diffie-Hellman
(DDH) assumption or on the learning with errors (LWE) assumption (with certain
parameters settings).
In the case of functions that can be expressed as degree-$d$ polynomials, we
show that the resulting schemes are also secure with respect to key
cycles of any length. Specifically, for any polynomial number $n$ of key
pairs, our schemes can securely encrypt a degree-$d$ polynomial whose variables
are the collection of coordinates of all $n$ secret keys. Prior to this work,
it was not known how to achieve this for nonlinear functions.
Our key idea is a general transformation that amplifies KDM security. The
transformation takes an encryption scheme that is KDM secure w.r.t.
some functions even when the secret keys are weak (i.e. chosen from an
arbitrary distribution with entropy $k$), and outputs a scheme that is KDM
secure w.r.t. a richer class of functions. The resulting scheme may no
longer be secure with weak keys. Thus, in some sense, this transformation
converts security with weak keys into amplified KDM security.
Zvika Brakerski and Boaz Patt-Shamir
Distributed Discovery of Large Near-Cliques
PODC 2009 (Brief Announcement), DISC 2009, Distributed Computing 2011.
[Abstract] [PDF]
Given an undirected graph and $0\le\epsilon\le1$, a set of nodes is called $\epsilon$-near clique if all but an $\epsilon$ fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size $\epsilon$-near clique if there exists an $\epsilon^3$-near clique of linear size in the graph. The algorithm uses messages of $O(\log n)$ bits. The failure probability can be reduced to $n^{-\Omega(1)}$ in $O(\log n)$ time, and the algorithm also works if the graph contains a clique of size $\Omega(n/\log^{\alpha}\log n)$ for some $\alpha \in (0,1)$.
-
Public-key
encryption schemes rely for their IND-CPA security on per-message fresh
randomness. In practice, randomness may be of poor quality for a variety of
reasons, leading to failure of the schemes. Expecting the systems to improve
is unrealistic. What we show in this paper is that we can, instead, improve
the cryptography to offset the lack of possible randomness. We provide
public-key encryption schemes that achieve IND-CPA security when the randomness they
use is of high quality, but, when the latter is not the case, rather than
breaking completely, they achieve a weaker but still useful notion of
security that we call IND-CDA. This hedged public-key encryption provides
the best possible security guarantees in the face of bad randomness. We
provide simple RO-based ways to make in-practice IND-CPA schemes hedge
secure with minimal software changes. We also provide non-RO model schemes
relying on lossy trapdoor functions (LTDFs) and techniques from
deterministic encryption. They achieve adaptive security by establishing
and exploiting the anonymity of LTDFs which we believe is of independent
interest.
Zvika Brakerski and Oded Goldreich
From Absolute Distinguishability to Positive Distinguishability
Studies in Complexity and
Cryptography 2011 (Book Chapter).
[Abstract] [PDF]
We study methods of converting algorithms that distinguish pairs
of distributions with a gap that has an absolute value that is noticeable
into corresponding algorithms in which the gap is always positive.
Our focus is on designing algorithms that, in addition to the tested string,
obtain a fixed number of samples from each distribution.
Needless to say, such algorithms can not provide a very reliable
guess for the sign of the original distinguishability gap,
still we show that even guesses that are noticeably better than random
are useful in this setting.
-
Verifiable random functions (VRFs), introduced by Micali, Rabin and Vadhan, are
pseudorandom functions in which the owner of the seed produces a public-key
that constitutes a commitment to all values of the function and can then
produce, for any input $x$, a proof that the function has been evaluated
correctly on $x$, preserving pseudorandomness for all other inputs. No
public-key (even a falsely generated one) should allow for proving more than
one value per input.
VRFs are both a natural and a useful primitive, and previous works have
suggested a variety of constructions and applications. Still, there are many
open questions in the study of VRFs, especially their relation to more widely
studied cryptographic primitives and constructing them from a wide variety of
cryptographic assumptions.
In this work we define a natural relaxation of VRFs that we call weak
verifiable random functions, where pseudorandomness is required to hold only
for randomly selected inputs. We conduct a study of weak VRFs, focusing on
applications, constructions, and their relationship to other cryptographic
primitives. We show:
- Constructions. We present constructions of weak VRFs based on
a variety of assumptions, including general assumptions such as (enhanced)
trapdoor permutations, as well as constructions based on specific
number-theoretic assumptions such as the Diffie-Hellman assumption in bilinear
groups.
- Separations.
Verifiable random functions (both weak and standard) cannot be constructed from
one-way permutations in a black-box manner. This constitutes the first result
separating (standard) VRFs from any cryptographic primitive.
- Applications. Weak VRFs capture the essence of
constructing non-interactive zero-knowledge proofs for all NP languages.
Zvika Brakerski
Local Property Restoring
Manuscript, 2008.
[Abstract] [PDF]
In this paper we present the new notion of local restoring of
properties. A restorer gets implicit access, in the form of oracle
queries, to a function (which may correspond to an object such as a graph, a
code or a matrix) that is close to having a property, such as function
monotonicity or graph bipartiteness. The restorer then, using a small number of
queries to the function, can locally compute the value of a ``corrected''
function in any desired point. The corrected function is required to be both
close to the original function and strictly have the property. In the
case of error correcting codes, this corresponds to local self-correcting. Here
we extend the definition and study for general functions and properties.
We define the new notion and go on to give restorers for properties in the
dense graph model: Bipartiteness and $\rho$-Clique, and for function
monotonicity. We also show some general relations between property restoring
and other notions such as property testing and tolerant property testing.
Zvika Brakerski and Boaz Patt-Shamir
Jitter-Approximation Tradeoff for Periodic Scheduling
IPDPS 2004, Wireless Networks 2006.
[Abstract] [PDF] We consider an asymmetric wireless communication setting, where a
server periodically broadcasts data items to different
mobile clients. The goal is to serve items in to a prescribed
rate, while minimizing the energy consumption of the mobile
users. Abstractly, we are presented with a set of jobs, each with a
known execution time and a requested period, and the task is to
design a schedule for these jobs over a single shared resource
without preemption.
Given any solution
schedule, its period approximation is the
maximal factor by which the average period of a job in the schedule
is blown up w.r.t. its requested period, and the jitter is roughly
the maximal variability of times between two
consecutive occurrences of the same job. Schedules with
low jitter allow the mobile devices to save power by
having their receivers switched off longer.
In this paper we consider a
scenario where clients may be willing to settle for non-optimal
period approximation so that the jitter is improved.
We present a parametric jitter-approximation tradeoff algorithm that
allows us to choose various combinations between jitter optimality
and period optimality for any given set of jobs.
Zvika Brakerski, Aviv Nisgav and Boaz Patt-Shamir
General Perfectly Periodic Scheduling
PODC 2002, Algorithmica 2006.
[Abstract] [PDF]
In a perfectly periodic schedule, each job must be scheduled
precisely every some fixed number of time units after its previous
occurrence. Traditionally, motivated by centralized systems, the
perfect periodicity requirement is relaxed, the main goal being to
attain the requested average rate. Recently, motivated by mobile
clients with limited power supply, perfect periodicity seems to be
an attractive alternative that allows clients to save energy by
reducing their ``busy waiting'' time. In this case, clients may be
willing to compromise their requested service rate in order to get
perfect periodicity. In this paper, we study a general model of
perfectly periodic schedules, where each job has a requested period
and a length; we assume that $m$ jobs can be served in parallel for
some given $m$. Job lengths may not be truncated, but granted
periods may be different than the requested periods.
We present an algorithm which computes schedules such that the
worst-case proportion between the requested period and the granted
period is guaranteed to be close to the lower bound. This algorithm
improves on previous algorithms for perfect schedules in providing a
worst-case guarantee rather than an average-case guarantee, in
generalizing unit length jobs to arbitrary length jobs, and in
generalizing the single-server model to multiple servers.
Zvika Brakerski, Vladimir Dreizin and Boaz Patt-Shamir
Dispatching in Perfectly-Periodic Schedules
J. Algorithms 2003.
[Abstract] [PDF]
In a perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots, called the period of that client. Periodic schedules are useful in mobile communication where they can help save power in the mobile device, and they also enjoy the best possible smoothness. In this paper we study the question of dispatching in a perfectly periodic schedule, namely how to find the next item to schedule, assuming that the schedule is already given somehow. Simple dispatching algorithms suffer from either linear time complexity per slot or from exponential space requirement. We show that if the schedule is given in a natural tree representation, then there exists a way to get the best possible running time per slot for a given space parameter, or the best possible space (up to a polynomial) for a given time parameter. We show that in many practical cases, the running time is constant and the space complexity is polynomial.
|
