On Continual Leakage of Discrete Log Representations.
Bibliographic record
Abstract
Let G be a group of prime order q, and let g1, . . . , gn be random elements of G. We say that a vector x = (x1, . . . , xn) ∈ Zq is a discrete log representation of some some element y ∈ G (with respect to g1, . . . , gn) if g1 1 · · · gn n = y. Any element y has many discrete log representations, forming an affine subspace of Zq . We show that these representations have a nice continuous leakage-resilience property as follows. Assume some attacker A(g1, . . . , gn, y) can repeatedly learn L bits of information on arbitrarily many random representations of y. That is, A adaptively chooses polynomially many leakage functions fi : Zq → {0, 1}, and learns the value fi(xi), where xi is a fresh and random discrete log representation of y. A wins the game if it eventually outputs a valid discrete log representation x∗ of y. We show that if the discrete log assumption holds in G, then no polynomially bounded A can win this game with non-negligible probability, as long as the leakage on each representation is bounded by L ≈ (n− 2) log q = (1− 2 n ) · |x|. As direct extensions of this property, we design very simple continuous leakage-resilient (CLR) one-way function (OWF) and public-key encryption (PKE) schemes in the so called “invisible key update” model introduced by Alwen et al. at CRYPTO’09. Our CLR-OWF is based on the standard Discrete Log assumption and our CLR-PKE is based on the standard Decisional Diffie-Hellman assumption. Prior to our work, such schemes could only be constructed in groups with a bilinear pairing. As another surprising application, we show how to design the first leakage-resilient traitor tracing scheme, where no attacker, getting the secret keys of a small subset of decoders (called “traitors”) and bounded leakage on the secret keys of all other decoders, can create a valid decryption key which will not be traced back to at least one of the traitors. ∗UCLA. E-mail: shweta@cs.ucla.edu. Partially supported by DARPA/ONR PROCEED award, and NSF grants 1118096, 1065276, 0916574 and 0830803. †NYU E-mail: dodis@cs.nyu.edu. Partially supported by NSF Grants CNS-1065288, CNS-1017471, CNS-0831299 and Google Faculty Award. ‡University of Toronto. E-mail: vinodv@cs.toronto.edu. Partially supported by an NSERC Discovery Grant, by DARPA under Agreement number FA8750-11-2-0225. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA or the U.S. Government. §IBM Research, T.J. Watson. E-mail: danwichs@us.ibm.com
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.000 |
| Bibliometrics | 0.001 | 0.000 |
| Science and technology studies | 0.000 | 0.001 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.002 | 0.003 |
| Research integrity | 0.000 | 0.001 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".