Leakage-resilient public-key encryption
A leakage-resilient public-key encryption scheme is a PKE scheme that remains CPA-secure when the adversary, after seeing and before the challenge, adaptively learns the values of efficiently computable functions of of total output length at most — AGV09, NS09.
Syntax
The syntax is that of PKE: a tuple of efficient algorithms with secret keyspace , public keyspace , message space and ciphertext space :
- , a randomized algorithm sampling a secret key and a public key ,
- , a randomized algorithm encrypting a message to a ciphertext ,
- , a deterministic algorithm outputting a message or .
The leakage bound is a parameter of the security notion; is the leakage rate.
Properties
Correctness
A scheme is -correct if for all and ,
over and the randomness of . When , is perfectly correct.
Leakage-resilient CPA security
The game extends the CPA game with a leakage oracle : on the description of an efficiently computable function with output bits, returns as long as the output lengths of all queries sum to at most . Each may depend on and on earlier answers. An admissible adversary submits with and queries only before receiving : a single query after the challenge, , reveals — standard.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{lr\text{-}cpa}}_{\PKE,\ell,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\sk, \pk) \gets \KeyGen(1^\secpar)$; $b \getsr \bits$; $t \gets 0$
\State $(m_0, m_1, \stA) \gets \calA^{\calL}(1^\secpar, \pk)$
\Comment{$m_0,m_1 \in \calM$ and $|m_0|=|m_1|$}
\State $c^* \gets \Enc(\pk, m_b)$
\State $b' \gets \calA(c^*, \stA)$
\Comment{No leakage queries after $c^*$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calL(f)$}
\begin{algorithmic}
\If{$t + \ell_f > \ell$}
\Return $\bot$
\EndIf
\State $t \gets t + \ell_f$
\Comment{$f$ efficiently computable with $\ell_f$ output bits}
\Return $f(\sk)$
\end{algorithmic}
\end{algorithm}
A PKE scheme is -leakage-resilient if for all admissible efficient ,
is negligible. For the game is the CPA game, so every -leakage-resilient scheme is CPA-secure (LR-PKE ⇒ CPA-secure PKE). The model is the memory-attack model of AGV09. As an object, leakage-resilient PKE denotes a scheme that is -leakage-resilient for some ; each result states its bound.
Variations
Chosen-ciphertext security with key leakage
In the leakage-resilient CCA1 and CCA2 games, also has the decryption oracle of the CCA1 or CCA2 game, and leakage queries are still answered only before — NS09. The Naor–Yung double-encryption paradigm of NY90 carries over to key leakage, and NS09 obtain from it CCA2-secure schemes tolerating bits of leakage for the secret-key length; variants of the Cramer–Shoup cryptosystem are CCA1-secure under about bits and CCA2-secure under about bits of leakage — NS09.
Auxiliary-input leakage
The adversary receives, with , the value of one fixed efficiently computable function with no bound on its output length; need only be hard to invert, in that no efficient algorithm given outputs with probability more than , and may determine information-theoretically. A scheme is CPA-secure with auxiliary inputs from a class of such functions if for every and all efficient the CPA advantage of given is negligible — DGKPV10. DKL09 introduce the model and construct symmetric-key encryption secure with exponentially hard-to-invert auxiliary input under the learning subspace with noise assumption; DGKPV10 construct public-key encryption secure with auxiliary inputs under DDH and under LWE, using a Goldreich–Levin theorem over large fields.
Continual memory leakage
A continual-leakage-resilient PKE scheme adds a randomized algorithm that refreshes the secret key using fresh local randomness, with unchanged; decryption under every refreshed key satisfies correctness. In the security game may trigger updates before the challenge, evaluates each query on the current secret key, and bounds the total output length by within each period between two consecutive updates, with no bound over the lifetime of the key — BKKV10, DHLW10. BKKV10 also allow a smaller amount of leakage on the computation of each update. As an object, continual-leakage-resilient PKE tolerates bits per period. A scheme that is never updated meets the bounded definition (CLR-PKE ⇒ LR-PKE).
BKKV10 construct PKE, identity-based encryption and signatures in this model (Bilinear pairing + DLIN ⇒ CLR-PKE). DHLW10 construct continual-leakage-resilient one-way relations, signatures, identification schemes and authenticated key agreement, instantiated under the -Linear assumption in bilinear groups.
Other results
- In the bounded-retrieval model the secret key grows with the leakage bound , which may be very large, while the public key, the communication and the number of secret-key locations an honest party reads stay independent of ; ADW09 give leakage-resilient identification, signature and authenticated key agreement schemes that extend to this model, the signatures (via Fiat–Shamir) and the key agreement in the random oracle model.
- Non-interactive encryption cannot tolerate leakage after the ciphertext is seen, and the authenticated key agreement protocol of ADW09, which tolerates leakage before and after an execution, serves as an interactive encryption scheme with this guarantee — ADW09.
Participates in
Builds on Leakage-resilient public-key encryption
Produces Leakage-resilient public-key encryption