Misnomer: det heter egentlig linearly homomorphic commitments og straight-line/online extractability. Prosjekt med Tjerand; idéen er å bruke Katsumata sin Extractable Commitment Protocol til å lage tighte signaturer i [[Quantum Random Oracle Model]], som lar seg compose til et PQ-bevis for Shuffle. ## Neste steg - [x] 🎓 Sjekk med Katsumata om extractable-protokollen skal gi alternativ commitment også eller ikke, og om den tar alternativ challenge inn som input. - [ ] 🎓 Vis hvordan protokollen kan instantiere et proof of linear relation - [ ] 🎓 Gjenta for proof of multiplicative relation - [ ] 🎓 Les [PKC25-artikkelen til Vadim og de som bygger på Tjerands arbeid](https://eprint.iacr.org/2025/658.pdf) - [ ] 🎓 Skriv nytt bevis som fikser buggen de identifiserte (og samtidig bruker MLWE heller enn RLWE) #### Fullførte steg - [x] 🎓 Fiks definisjonen av online extractability for XC-schemes - [x] 🎓 Skriv nytt bevis for online extractability av transformert sigma scheme ### Old notes Liten bekymring, må gi ordentlig sammenligning med related work for andre teknikker for online extractability, dvs mer enn bare å nevne dem: - Har ikke sett på Fishlin-transform, ekstremt relevant, der var det også en CiC-artikkel nylig. Men er kostbar. - Unruh-transform må vi også sammenligne med, men denne sammenlignet Katsumata allerede også med. Også kostbar. - Katz-Wang, se oppdatert versjon av Vadims Lattice-survey, høres veldig lignende ut umiddelbart. CCS 2003, Jonathan Katz og Nan Wang, "Efficiency Improvements for Signatures" elns. Type kryptere vitnet også; kan man kalle dette også en extractable commitment? *Må* være en ganske grundig intro her. Det vi ikke har sett på er hvordan ville våre teknikker NB: *Klassisk* vil vi få statistical zero-knowledge, men vi vet ikke om dette lar seg gjør kvantisk! Se Katsumata, p. 7: ![[Pasted image 20241017162845.png|600]] Mulige publikasjonsvenues: 1. [CiC](https://cic.iacr.org), neste frist 7. april 2. [ISC](https://isc25.skku.edu) (i Seoul!), frist 4. juni (AoE) 3. [CSF](https://www.ieee-security.org/CSFWweb/), neste frist [28. mai](https://csf2025.ieee-security.org/cfp.html) ### 2. Materiale til [[Forskningskø]] #### Leseliste 4. Carsten/Sabine/Ivan/Vadim/Chris Peikert, [More Efficient Commitments from Structured Lattice Assumptions](https://eprint.iacr.org/2016/997.pdf) 5. Tjerand et al., [RSA:ABGST21 - Lattice-Based Proof of Shuffle and Applications to Electronic Voting](https://eprint.iacr.org/2021/338) 6. Lyubashevsky et al., [Practical Product Proofs for Lattice Commitments](https://eprint.iacr.org/2020/517.pdf) 7. [PQ insecurity from LWE](https://eprint.iacr.org/2022/869.pdf) 8. Khanh og Vadim (et al.)s paper som bruker "The Katsumata Transform": [2023/560](https://eprint.iacr.org/2023/560.pdf) 9. Don, Fehr, Majenz, Schaffner: [EC:DFMS22 – Online-Extractability in the Quantum Random-Oracle Model](https://eprint.iacr.org/2021/280) 10. Wikström, [CiC:Wikstrom24b – Special Soundness in the Random Oracle Model](https://cic.iacr.org/p/1/3/26) 11. [INDOCRYPT:FKMV12 – On the Non-malleability of the Fiat-Shamir Transform](https://eprint.iacr.org/2012/704.pdf), første til å definere online extractability for [[Fiat-Shamir]]-NIZKs? (Se Katsumata, side 15, fotnote 15.) 12. Relevant? [Tessaro et al. – Straight-Line Knowledge Extraction for Multi-Round Protocols](https://eprint.iacr.org/2024/1724) ### 3. Zero-knowledge workshop talk Short talk (5 mins + 2 min for questions) Talk Title: **Quantum secure proof of shuffle** Talk abstract: > Katsumata [Kat21] recently gave a technique that lifts lattice-based zero-knowledge proofs of knowledge to make them online-extractable, side-stepping the need for rewinding in the proof of soundness, thus yielding a NIZK with provable soundness also in the quantum random oracle model. We leverage his technique to construct a shuffle protocol that is provably post-quantum secure, and with tighter bounds than those achieved by previous constructions. This was the final piece missing for a provably post-quantum secure electronic voting protocol. ### 3. Gammelt - gå gjennom og merge #### Tjerandmøter [[12024-06-19]]: For proof of linear relation, Carsten et al. hadde et Lemma (8) for en annen protokoll, og så viste de hvordan man kan endre det beviset for å vise for lineær-protokollen. Kan være en god idé og en fin øvelse å skrive dette beviset fullt ut (men ikke strengt tatt *nødvendig*—kan også bare referere til artikkelen). Dette beviset + vårt teorem -> online extractable proof of linear relation som et korollar (og tilsvarende for multiplikativ relasjon). Proof of mult. rel.: Se C:AttLyuSei20, fig. 3; det følgende upubliserte paragrafet fra Tjerand et al. kan også være til inspirasjon: ![[proof-of-mult-rel_unpublished-tjerandparagraf.png]] (Her sjekker de også for korthet av den hemmelige meldingen $s$, men det trenger ikke være nødvendig generelt.) [[12024-01-23]]: - Katsumata lets Sig.Com take the witness as input when defining sigma protocols, even though neither Schnorr nor Lyubashevsky uses this. Meaning we can likely make our definition equally general, and show that the construction satisfies it. - [[12024-05-06]] **Next steps:** - Starte med å instansiere med Katsumata - Putte inn i Lyubashevsky, Katsumata Fig. 8 og se at beviset funker innad i rammeverket - Utvide med bevis av lineær relasjon - blir da tre hovedpuslebrikker: - commitmentsene fra ZK-protokollen - commitmentsene fra Katsumatas LinHC - commitments man skal bevise lineær relasjon til - se Fig. 5 her: https://eprint.iacr.org/2016/997.pdf - få denne protokollen inn i vår protokoll - så nå blir statement to commitments - eller flere! det som trengs i Shuffle - får da "gratis" PQ-bevis for Shuffle! Literatur å sjekke ut: - [Toward Practical Lattice-based Proof of Knowledge from Hint-MLWE](https://eprint.iacr.org/2023/623) ### Gamle notater (todo: gå gjennom og reintegrer/slett) Relevant litteratur? - Eike et al.: "Group action key encapsulation and non-interactive key exchange in the QROM" Look at: https://eprint.iacr.org/2021/927.pdf First step: - Re-prove the results of Sect. 4 ("How to use ExLinHC")yourself. - Assume black-box access to ExLinHC, and see if this is enough to get the desired results. Next step: - Definisjon 19.2 i Boneh/Shoup, trenger det til å definere relasjoner og vitner: https://toc.cryptobook.us/book.pdf NB: see Sect. 3.3 - Extractable LinHC Specialized for Lattices. >"In most, if not all, lattice-based Σ-protocols, the witness being proven is a “short” vector. Therefore, throughout this work, we assume such shortness condition holds by default and integrate it into the definition of the extractable LinHC protocol." Can we ignore this? Alternatively show that it's a possible add-on feature of the kind "if witness is short then protocol is more efficient". ![[Generalized Schnorr]] Emil vil mest sanns. bli trukket inn som en del av dette prosjektet. Pedersen commitment: - c erlik g opphøyd i m ganger h opphøyd i r - er lineært homomorf, men ikke committment - er det som ville vært LinHC for Schnorr, men problem at den ikke er trapdoorable - dersom vi i tillegg antar pairings derimot kan vi få det - https://eprint.iacr.org/2009/007.pdf - da kan vi få straight line extractable Schnorr, ville vært morsomt - har det blitt gjort før? Definisjon av lineær homomorfi: - $\Phi = [\phi, \xi]$ slik at $\phi, \xi$ er funksjoner fra og til det samme domenet - dette domenet er mengder av com hhv. op slik at det eksisterer ck og op resp. com slik at verifisering returnerer true (med høy sannsynlighet) - OG $m_1 + m_2$, $c \cdot m$ (hvordan baker jeg dette inn i definisjonen?) Dette er en misforståelse: $\Phi$ er ikke noe vi skal legge til på toppen. Det vi trenger er muligheten for at ExtCom.com *algoritmen* oppfyller definisjonen på en lineær homomorfi. Kall binæroperasjonen over meldingene for stjerne og den over committmentene for trekant, for å unngå forvirring. Anbefalt faglig påfyll: - [Ivan Damgård om Sigma-protokoller](https://www.cs.au.dk/~ivan/Sigma.pdf) - [Alessandro Chiesa om Foundations of Probabilistic Proofs](https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC)