BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//ENSL/CWI/KCL/IRISA Joint Online Cryptography Seminars//https://j
cs.trusted-third-party///
BEGIN:VEVENT
SUMMARY:Two-Round Threshold Signature from Algebraic One-More Learning wit
h Errors by Kaoru Takemure
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20241118T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20241118T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202411181300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThreshold signatures have recently seen a renewed interest
due to applications in cryptocurrency while NIST has released a call for
multi-party threshold schemes\, with a deadline for submission expected fo
r the first half of 2025. So far\, all lattice-based threshold signatures
requiring two-rounds or less are based on heavy tools such as (fully) homo
morphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This
is not unexpected considering that most efficient two-round signatures fr
om classical assumptions either rely on idealized model such as algebraic
group models or on one-more type assumptions\, none of which we have a nic
e analogue in the lattice world.\n\nIn this work\, we construct the first
efficient two-round lattice-based threshold signature without relying on F
HE or HTDC. It has an offline-online feature where the first round can be
preprocessed without knowing message or the signer sets\, effectively maki
ng the signing phase non-interactive. The signature size is small and show
s great scalability. For example\, even for a threshold as large as 1024 s
igners\, we achieve a signature size roughly 11 KB. At the heart of our co
nstruction is a new lattice-based assumption called the algebraic one-more
learning with errors (AOMMLWE) assumption. We believe this to be a strong
inclusion to our lattice toolkits with an independent interest. We establ
ish the selective security of AOMMLWE based on the standard MLWE and MSIS
assumptions\, and provide an in depth analysis of its adaptive security\,
which our threshold signature is based on.\n\nI'm a postdoctoral researche
r at PQShield under the supervision of Shuichi Katsumata. I'm aslo a colla
borative researcher at AIST. I hold a PhD degree from the University of El
ectro-Communications\, Japan. I have mainly been working on classical and
(lattice-based) post-quantum aggregatable signatures\, e.g.\, aggregate si
gnature\, multi-signature\, and threshold signature.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cryptanalysis of Lattice-Based Sequentiality Assumptions and Proof
s of Sequential Work by Yi Tang
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20241028T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20241028T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202410281300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThis work *completely breaks* the sequentiality assumption
(and broad generalizations thereof) underlying the candidate lattice-base
d proof of sequential work (PoSW) recently proposed by Lai and Malavolta a
t CRYPTO 2023.\nIn addition\, it breaks an essentially identical variant o
f the PoSW\, which differs from the original in only an arbitrary choice t
hat is immaterial to the design and security proof (under the falsified as
sumption).\nThis suggests that whatever security the original PoSW may hav
e is fragile\, and further motivates the search for a construction based o
n a sound lattice-based assumption.\n\nSpecifically\, for sequentiality pa
rameter $T$ and SIS parameters $n\,q\,m = n \\log q$\, the attack on the s
equentiality assumption finds a solution of quasipolynomial norm $m^{\\lce
il \\log T \\rceil}$ (or norm $O(\\sqrt{m})^{\\lceil \\log T \\rceil}$ wit
h high probability) in only *logarithmic* ~$O_{n\,q}(\\log T)$ depth\; thi
s strongly falsifies the assumption that finding such a solution requires
depth *linear* in $T$.\n(The ~${O}$ notation hides polylogarithmic factors
in the variables appearing in its subscript.)\nAlternatively\, the attack
finds a solution of polynomial norm $m^{1/\\varepsilon}$\nin depth ~$O_{n
\,q}(T^{\\varepsilon})$\, for any constant $\\varepsilon > 0$.\nSimilarly\
, the attack on the (slightly modified) PoSW constructs a valid proof in *
polylogarithmic* ~${O}_{n\,q}(\\log^2 T)$ depth\, thus strongly falsifying
the expectation that doing so requires linear sequential work.\n\nYi is c
urrently a PhD student in CSE at University of Michigan.\nYi works on latt
ice problems with Chris Peikert\, and applied cryptography with Paul Grubb
s.\n\nYi got his Master's degree in CS at Courant Institute of Mathematica
l Sciences\, New York University.\nDuring that time Yi worked on lattice p
roblems with Oded Regev\, and applied cryptography with Yevgeniy Dodis.
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Systematic Study of Sparse LWE by Sagnik Saha
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20241014T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20241014T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202410141300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nIn this work\, we introduce the sparse LWE assumption\, an
assumption that draws inspiration from both Learning with Errors (Regev J
ACM 10) and Sparse Learning Parity with Noise (Alekhnovich FOCS 02). Exact
ly like LWE\, this assumption posits indistinguishability of ( A\, sA+e mo
d p) from (A\, u) for a random u where the secret s\, and the error vector
e is generated exactly as in LWE. However\, the coefficient matrix A in s
parse LPN is chosen randomly from Z^{n \\times m}_p so that each column ha
s Hamming weight exactly k for some small k. We study the problem in the
regime where k is a constant or polylogarithmic. The primary motivation fo
r proposing this assumption is efficiency. Compared to LWE\, the samples c
an be computed and stored with roughly O(n/k) factor improvement in effici
ency. Our results can be summarized as:\n\nFoundations: We show several pr
operties of sparse LWE samples\, including: 1) The hardness of LWE/LPN wit
h dimension k implies the hardness of sparse LWE/LPN with sparsity k and a
rbitrary dimension n >= k. 2) When the number of samples m=Omega(n log p)
\, length of the shortest vector of a lattice spanned by rows of a random
sparse matrix is large\, close to that of a random dense matrix of the sam
e dimension (up to a small constant factor). 3) Trapdoors with small polyn
omial norm exist for random sparse matrices with m = O(n log p) columns. 4
) Efficient algorithms for sampling such matrices together with trapdoors
exist when the number of columns\, m = Otilde(n^2).\n\nCryptanalysis: We
examine the suite of algorithms that have been used to break LWE and spars
e LPN. While naively many of the attacks that apply to LWE do not exploit
sparsity\, we consider natural extensions that make use of sparsity. We pr
opose a model to capture all these attacks. Using this model we suggest he
uristics on how to identify concrete parameters. Our initial cryptanalysis
suggests that concretely sparse LWE with a modest k and slightly bigger d
imension than LWE will satisfy similar level of security as LWE with simil
ar parameters.\n\nApplications: We show that the hardness of sparse LWE im
plies very efficient homomorphic encryption schemes for low degree computa
tions. We obtain the first secret key Linearly Homomorphic Encryption (LH
E) schemes with slightly super-constant\, or even constant\, overhead\, wh
ich further has applications to private information retrieval\, private se
t intersection\, etc. We also obtain secret key homomorphic encryption fo
r arbitrary constant-degree polynomials with slightly super-constant\, or
constant\, overhead. \n\nWe stress that our results are preliminary. Howev
er\, our results make a strong case for further investigation of sparse LW
E.\n\nI'm a 2nd-year PhD Student at Carnegie Mellon University advised by
Prof. Aayush Jain. Before starting my PhD\, I used to work as a software e
ngineer at Google. I completed my Bachelors' and Masters' degrees from Mas
sachusetts Institute of Technology in 2018 and 2019 respectively.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Flood and Submerse: Distributed Key Generation and Robust Threshol
d Signature from Lattices by Guilhem Niot
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240930T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240930T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202409301300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThreshold cryptography has recently been a very active fie
ld of research\, notably following the NIST call for threshold primitives.
Notable works in post-quantum cryptography built threshold signatures by
relying on noise flooding [dPKM+23\,EKT24\,BKLM+24]\, and designed short a
nd efficient schemes. They however left opened the questions of distributi
ng the key generation\, and of making the signing process robust - i.e. gu
aranteeing that a valid signature is output even in the present of malicio
us parties.\nIn this talk\, I will present our novel techniques for buildi
ng Distributed Key Generation and Robust Threshold Signatures. To do so\,
we introduced a novel framework for constructing verifiable short secret s
haring based on random submersions — that is projection over a random su
bspace blinded by a small Gaussian noise. Our techniques apply to all the
aforementionned work\, and we also showcased their applications to Plover
[EENP+24] to build the first hash-and-sign threshold signature\, additiona
lly having a DKG and robust signing procedure.\n\nI am a PhD student at PQ
Shield and Univ Rennes 1 under the supervision of Thomas Prest and Pierre-
Alain Fouque. I am especially interested in applied cryptography and the c
onstruction of efficient primitives and protocols. My works so far include
d lattice-based constructions for masking-friendly signatures\, threshold
signatures\, and also secure messaging.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Threshold Raccoon: Practical Threshold Signatures from Standard La
ttice Assumptions by Mary Maller
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240923T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240923T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202409231300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThreshold signatures improve both availability and securit
y of digital signatures by splitting the signing key into shares handed ou
t to different parties. Later on\, any subset of at least parties can coop
erate to produce a signature on a given message. While threshold signature
s have been extensively studied in the pre-quantum setting\, they remain s
parse from quantum-resilient assumptions.\n\nWe present the first efficien
t lattice-based threshold signatures with signature size 13~KiB and commun
ication cost 40~KiB per user\, supporting a threshold size as large as 102
4~signers. We provide an accompanying high performance implementation. The
security of the scheme is based on the same assumptions as Dilithium\, a
signature recently selected by NIST for standardisation which\, as far as
we know\, cannot easily be made threshold efficiently.\n\nAll operations u
sed during signing are due to symmetric primitives and simple lattice oper
ations\; in particular our scheme does not need heavy tools such as thresh
old fully homomorphic encryption or homomorphic trapdoor commitments as in
prior constructions. The key technical idea is to use _one-time additive
masks_ to mitigate the leakage of the partial signing keys through partial
signatures.\n\nI am a cryptography researcher at the Ethereum Foundation
and PQShield. I am generally interested in public key cryptography with a
heavy focus on zero-knowledge proofs. I am also interested in threshold c
ryptography. I enjoy building and analysing practical cryptographic solut
ions to real world problems.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Don’t Use It Twice! Solving Relaxed Linear Code Equivalence Prob
lems by Alessandro Budroni
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240624T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240624T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202406241300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThe Linear Code Equivalence (LCE) Problem has received inc
reased attention in recent years due to its applicability in constructing
efficient digital signatures. Notably\, the LESS signature scheme based on
LCE is under consideration for the NIST post-quantum standardization proc
ess\, along with the MEDS signature scheme that relies on an extension of
LCE to the rank metric\, namely Matrix Code Equivalence (MCE) Problem. Bui
lding upon these developments\, a family of signatures with additional pro
perties\, including linkable ring\, group\, and threshold signatures\, has
been proposed. These novel constructions introduce relaxed versions of LC
E (and MCE)\, wherein multiple samples share the same secret equivalence.
Despite their significance\, these variations have often lacked a thorough
security analysis\, being assumed to be as challenging as their original
counterparts. Addressing this gap\, our work delves into the sample comple
xity of LCE and MCE --- precisely\, the sufficient number of samples requi
red for efficient recovery of the shared secret equivalence. Our findings
reveal\, for instance\, that one shouldn't use the same secret twice in th
e LCE setting since this enables a polynomial time (and memory) algorithm
to retrieve the secret. Consequently\, our results unveil the insecurity o
f two advanced signatures based on variants of the LCE Problem.\n\nAlessan
dro Budroni is a researcher at the Technology Innovation Institute of Abu
Dhabi. He defended his Ph.D. in 2022 at the University of Bergen under the
supervision of Professor Igor Semaev. Before that\, he obtained a master'
s degree at the University of Trento and worked as a cryptography engineer
at Miracl\, London. His research interests range from cryptography with c
odes and lattices to efficient algorithms for secure cryptographic impleme
ntations.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lattice-Based Functional Commitments: Constructions and Cryptanaly
sis by David Wu
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240603T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240603T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202406031300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nA functional commitment allows a user to commit to an inpu
t x and later open up the commitment to a value f(x) for an arbitrary func
tion f. We require that the size of the commitment and the size of the ope
ning be sublinear in the length of the input x. In this talk\, I first des
cribe how to construct functional commitments from the recently-introduced
\\ell-succint SIS assumption (this is a falsifiable q-type generalization
of the classic SIS assumption). Then\, I will highlight some challenges i
n constructing lattice-based extractable functional commitments (which are
equivalent to succinct non-interactive arguments of knowledge) and descri
be a (heuristic) attack on recently-proposed lattice-based knowledge assum
ptions underlying extractable functional commitments and SNARKs.\n\nBased
on joint work with Hoeteck Wee\n\nDavid Wu is an assistant professor in th
e Department of Computer Science at the University of Texas at Austin. He
is broadly interested in applied and theoretical cryptography as well as c
omputer security. Previously\, David received a PhD in computer science fr
om Stanford University in 2018 and was an assistant professor at the Unive
rsity of Virginia from 2019 to 2021. He has received the NSF CAREER Award\
, the Microsoft Research Faculty Fellowship\, and a Google Research Schola
r Award. His work has been recognized with a Best Paper Award at CRYPTO (2
022)\, two Best Young-Researcher Paper Awards at CRYPTO (2017\, 2018) and
an Outstanding Paper Award at ESORICS (2016).\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Abuse-Resistant Location Tracking: Balancing Privacy and Safety in
the Offline Finding Ecosystem by Gabrielle Beck
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240422T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240422T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202404221300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nLocation tracking accessories (or ``tracking tags'') such
as those sold by Apple\, Samsung\, and Tile\, allow owners to track the lo
cation of their property via offline finding networks. The tracking protoc
ols were designed to ensure that no entity (including the vendor) can use
a tag's broadcasts to surveil its owner. These privacy guarantees\, howeve
r\, seem to be at odds with the phenomenon of {\\em tracker-based stalkin
g}\, where attackers use these very tags to monitor a target's movements.
Numerous such criminal incidents have been reported\, and in response\, ma
nufacturers have chosen to substantially weaken privacy guarantees in orde
r to allow users to detect stalker tags. This compromise has been adopted
in a recent IETF draft jointly proposed by Apple and Google. \n \n\nWe put
forth the notion of {\\em abuse-resistant offline finding protocols} that
aim to achieve a better balance between user privacy and stalker detectio
n. We present an efficient protocol that achieves stalker detection under
realistic conditions without sacrificing honest user privacy. At the heart
of our result\, and of independent interest\, is a new notion of {\\em mu
lti-dealer secret sharing} which strengthens standard secret sharing with
novel privacy and correctness guarantees. We show that this primitive can
be instantiated efficiently on edge devices using variants of Interleaved
Reed-Solomon codes combined with new lattice-based decoding algorithms.\n\
nGabrielle Beck is an independent researcher and consultant who defended h
er PhD at Johns Hopkins last semester. Before Hopkins\, she completed her
bachelor's degree at the University of Michigan where she studied computer
science. Her research interests mainly involve developing new practical c
ryptographic constructions to solve the problems of everyday people with a
special focus in metadata-hiding and other unconventional problem areas.
Separately\, she has recently become very interested in some select topics
within coding theory.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Quantum Oblivious LWE Sampling and Insecurity of Standard Model La
ttice-Based SNARKs by Pouria Fallahpour
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240325T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240325T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202403251300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThe Learning With Errors (LWE) problem asks to find s from
an input of the form\n(A\, b = As + e) ∈ (Z/qZ)^{m×n} × (Z/qZ)^{m}\,
for a vector e that has small-magnitude entries. In\nthis work\, we do not
focus on solving LWE but on the task of sampling instances. As these are\
nextremely sparse in their range\, it may seem plausible that the only way
to proceed is to first\ncreate s and e and then set b = As + e. In partic
ular\, such an instance sampler knows the\nsolution. This raises the quest
ion whether it is possible to obliviously sample (A\, As+e)\, namely\,\nwi
thout knowing the underlying s. A variant of the assumption that oblivious
LWE sampling\nis hard has been used in a series of works constructing Suc
cinct Non-interactive Arguments\nof Knowledge (SNARKs) in the standard mod
el. As the assumption is related to LWE\, these\nSNARKs have been conjectu
red to be secure in the presence of quantum adversaries.\nOur main result
is a quantum polynomial-time algorithm that samples well-distributed LWE\n
instances while provably not knowing the solution\, under the assumption t
hat LWE is hard.\nMoreover\, the approach works for a vast range of LWE pa
rametrizations\, including those used\nin the above-mentioned SNARKs.\n\nI
am a PhD student at ENS Lyon under the supervision of Prof. Damien Stehl
é. I am interested in a wide range of topics in theoretical computer scie
nce. I am currently working on qunatum cryptanalysis of lattice-based prim
itives.
END:VEVENT
BEGIN:VEVENT
SUMMARY:A New Sieving-Style Information-Set Decoding Algorithm by Vu Nguy
en
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240311T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240311T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202403111300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThe problem of decoding random codes is a fundamental prob
lem for code-based cryptography\, including recent code-based candidates i
n the NIST post-quantum standardization process.\nIn this paper\, we prese
nt a novel sieving-style information-set decoding (ISD) algorithm\, addres
sing the task of solving the syndrome decoding problem. Our approach invol
ves maintaining a list of weight-$2p$ solution vectors to a partial syndro
me decoding problem and then creating new vectors by identifying pairs of
vectors that collide in $p$ positions.\nBy gradually increasing the parity
-check condition by one and repeating this process iteratively\, we find t
he final solution(s). We show that our novel algorithm performs better tha
n other ISDs in the memory-restricted scenario when applied to McEliece.
Notably\, in the case of problem instances with very low relative weight\,
it seems to significantly outperform all previous algorithms. In particul
ar\, for code-based candidate BIKE\, the algorithm has lower bit complexit
y than the previous best results.\n\nI am Ph.D. student at Lund University
. My main research interest is code-based post-quantum cryptography. I als
o performed cryptanalysis on a few LPN-based post-quantum schemes (wPRF\,
Firekite).
END:VEVENT
BEGIN:VEVENT
SUMMARY:Two-Round Threshold Lattice Signatures from Threshold Homomorphic
Encryption by Tjerand Silde
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240212T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240212T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202402121300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nMuch recent work has developed efficient protocols for thr
eshold signatures\, where $n$ parties share a signing key and some thresho
ld $t$ of those parties must interact to produce a signature. Yet efficien
t threshold signatures with post-quantum security have been elusive\, with
the state-of-the-art being a two-round scheme by Damgård et al. (PKC'21)
based on lattices that supports only the full threshold case (i.e.\, $t=n
$).\n\nWe show here a two-round threshold signature scheme based on standa
rd lattice assumptions that supports arbitrary thresholds $t\\leq n$. Esti
mates of our scheme's performance at the $128$-bit security level show tha
t in the 3-out-of-5 case\, we obtain signatures of size $20$ KB and public
keys of size $14$ KB. We achieve improved parameters if only a small numb
er of signatures are ever issued with the same key.\n\nAs an essential bui
lding block and independent contribution\, we construct an actively secure
threshold (linearly) homomorphic encryption scheme that supports arbitrar
y thresholds $t \\leq n$.\n\nThis is joint work with Kamil Doruk Gur and J
onathan Katz at the University of Maryland\, and the paper is available at
: https://eprint.iacr.org/2023/1318.\n\nI am an Associate Professor in Cry
ptology at the Department of Information Security and Communication Techno
logy at the Norwegian University of Science and Technology (NTNU) in Trond
heim\, where I am the Research Group Leader of the NTNU Applied Cryptology
Lab. My main foci of research are lattice-based cryptography and zero-kno
wledge protocols. My interests also span the areas of post-quantum cryptog
raphy\, anonymous communication\, multiparty computation\, homomorphic enc
ryption\, electronic voting and secure implementation.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Finding short integer solutions when the modulus is small by Eamon
n Postlethwaite
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240129T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240129T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202401291300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nWe present cryptanalysis of the inhomogenous short integer
solution (ISIS) problem for anomalously small moduli by exploiting the ge
ometry of BKZ reduced bases of q-ary lattices.\n\nWe apply this cryptanaly
sis to examples from the literature where taking such small moduli has bee
n suggested. A recent work [Espitau–Tibouchi–Wallet–Yu\, CRYPTO 2022
] suggests small versions of the lattice signature scheme FALCON and its v
ariant MITAKA.\n\nFor one small parametrisation of FALCON we reduce the es
timated security against signature forgery by approximately 26 bits. For o
ne small parametrisation of MITAKA we successfully forge a signature in se
conds.\n\nWe also show that our attack applies to the ``distortion'' techn
ique suggested in [Espitau–Tibouchi–Wallet–Yu\, CRYPTO 2022].\n\nI a
m currently a postdoctoral researcher at Centrum Wiskunde en Informatica (
CWI) with Léo Ducas focussing on constructions from and cryptanalysis of
lattice based cryptography.\nI will start as a junior lecturer at King's C
ollege London in January.
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the Hardness of S|LWE> with Gaussian and Other Amplitudes by Yi
lei Chen
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20231120T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20231120T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202311201300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nS|LWE> is a quantum variant of LWE where the error term is
encoded in the amplitude of a quantum state. The S|LWE> problem was origi
nally studied by Chen\, Liu\, Zhandry [Eurocrypt 2022]\, motivated by solv
ing a variant of SIS problem. \nIn this talk I will talk about the previou
s result by Chen\, Liu\, Zhandry\, as well as a recent paper on the hardne
ss and algorithms for S|LWE> with Gaussian and other amplitudes. Our main
results in the recent paper are\n1. There exist quantum reductions from st
andard LWE or worst-case GapSVP to S|LWE> with Gaussian amplitude with unk
nown phase\, and arbitrarily many samples.\n2. There is a subexponential t
ime algorithm for with Gaussian amplitude with known phase\, given subexpo
nentially many quantum samples. The algorithm is modified from Kuperberg's
sieve\, and in fact works for more general amplitudes as long as the ampl
itudes and phases are completely known.\nOne way of interpreting our new r
esult is: to show a sub-exponential time quantum algorithm for standard LW
E\, all we need is to handle phases in amplitudes better\, either in the a
lgorithm or the reduction.\nBased on two papers\, one with Qipeng Liu\, Ma
rk Zhandry (eprint: https://eprint.iacr.org/2021/1093)\, and another with
Zihan Hu\, Qipeng Liu\, Han Luo\, Yaxin Tu (eprint https://eprint.iacr.org
/2023/1498).\n\nYilei is an assistant professor at Tsinghua University Ins
titute for Interdisciplinary Information Science (IIIS). Yilei's main rese
arch interests are lattice-based cryptography and quantum computation.
END:VEVENT
BEGIN:VEVENT
SUMMARY:New Coding-Theoretic Assumptions for Correlated Pseudorandomness G
eneration by Lisa Kohl (CWI) & Nicolas Resch (UvA) .
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20231106T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20231106T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202311061300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nA fundamental concept in cryptography is pseudorandomness\
, namely the ability to efficiently generate many bits that look indisting
uishable from random. For example\, if two parties can agree on a short ra
ndom seed\, a pseudorandom generator allows them to later obtain long rand
om strings that look essentially uniform. \n\nMotivated by concerns in sec
ure multiparty computation\, a recent generalization of this primitive has
been designed and studied. Namely\, from two short correlated seeds\, lon
g correlated strings can be generated later\, without requiring any furthe
r communication from the parties. Such objects\, termed pseudorandom corre
lation generators (PCGs)\, result in some of the most efficient secure com
putation protocols.\n\nIn this presentation\, we will first discuss a gene
ral recipe for PCGs\, studying the important special case of the oblivious
transfer (OT) correlation. We will observe that a crucial ingredient is a
pseudorandom generator that has sufficient linear structure\; i.e.\, a ps
eudorandom generator derived from a “learning parity with noise”-type
assumption. In the second half of the talk\, we will discuss new coding-th
eoretic assumptions which have been proposed to design highly-efficient PC
Gs. As a particular highlight\, we will discuss a PCG requiring only linea
r time to expand short seeds into many OT instances. \n\nBased on joint wo
rks with Elette Boyle\, Geoffroy Couteau\, Niv Gilboa\, Yuval Ishai\, and
Peter Scholl.\n\nLisa Kohl is a senior researcher with the CWI Cryptology
Group in Amsterdam. A special focus of her research work lies in exploring
new directions for secure computation\, with the goal of developing pract
ical post-quantum secure protocols. Website: lisakohl.me\n\nNicolas Resch
is an assistant professor with the Theoretical Computer Science Group from
the Informatics Institute of the University of Amsterdam. His research fo
cusses on error-correcting codes and cryptography and (naturally) their in
tersection. Website: nicolas-resch.caard.co
END:VEVENT
BEGIN:VEVENT
SUMMARY:Applications of relation lattices\, and open questions by Steven G
albraith
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20231023T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20231023T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202310231300@https://jcs.trusted-third-party/
DESCRIPTION:Also: Bush House (SE) 1.06\n\nLet $G$ be a finite abelian grou
p and let $g_1\,...\,g_n \\in G$. Define the relation lattice $L = \\{ (x_
1\,...\,x_n) \\in Z^n : \\sum_{i=1}^n x_i g_i = 0 \\}$. Ducas and Pierrot
(Designs\, Codes and Cryptography\, 2019) showed how relation lattices can
provide families of dense lattices with a polynomial-time bounded distanc
e decoding algorithm. Li\, Ling\, Xing and Yeo (IEEE Transactions on Infor
mation Theory 2020) proposed using a relation lattice for a version of the
McEliece code-based post-quantum encryption scheme. I will survey these r
esults and discuss some improvements to the cryptosystem of Li\, Ling\, Xi
ng and Yeo.\n\nProfessor Galbraith is a researcher in mathematics of publi
c key cryptography at the University of Auckland in New Zealand. He has he
ld positions at Royal Holloway\, Bristol\, Institute of Experimental Mathe
matics (Essen)\, and Waterloo.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Doubly Efficient Private Information Retrieval and Fully Homomorph
ic RAM Computation from Ring LWE by Wei-Kai Lin
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20231009T150000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20231009T160000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202310091500@https://jcs.trusted-third-party/
DESCRIPTION:\n\nCan we design a private variant of "Google search" that wo
uld enable users to search the Internet privately without revealing their
queries to Google? Fully homomorphic encryption gives a solution to this p
roblem\, where users would send their search queries to Google encrypted i
n a way that allows Google to compute the encrypted search results\, witho
ut learning anything about the query itself. However\, this solution would
require Google to run a huge computation that touches the entire content
of the Internet to answer each encrypted search query\, making it realisti
cally infeasible! Is there a way for Google to preprocess the Internet con
tent into a special data structure that would allow it to answer any encry
pted query efficiently by only accessing some small number of locations in
the data structure? We give a solution to this problem as a special case
of our work.\n\nConcretely\, we construct the first schemes for "doubly ef
ficient private information retrieval" and "fully homomorphic encryption i
n the RAM model" under standard cryptographic hardness assumptions (Ring L
earning with Errors). Previously we only had heuristic candidate construct
ions that only satisfied relaxed variants of these primitives. Our new sol
utions combine tools from cryptography together with data structures for f
ast polynomial evaluation (Kedlaya and Umans '08).\n\nJoint work with Etha
n Mook and Daniel Wichs.\n\nI am an assistant professor in the Computer Sc
ience Department at University of Virginia. Earlier\, I was a postdoctoral
researcher at Northeastern University\, advised by Professor Daniel Wichs
. I got my Ph.D. in Computer Science at Cornell and then worked as a postd
oc at CMU\, both advised by Professor Elaine Shi. Prior to that\, I got my
B.S. and M.S. degrees from National Taiwan University\, and then I was a
software engineer.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Efficient Laconic Cryptography from Learning With Errors by Russel
l W. F. Lai
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230626T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230626T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202306261300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nLaconic cryptography is an emerging paradigm that enables
cryptographic primitives with sublinear communication complexity in just t
wo messages. In particular\, a two-message protocol between Alice and Bob
is called laconic if its communication and computation complexity are esse
ntially independent of the size of Alice's input. This can be thought of a
s a dual notion of fully-homomorphic encryption\, as it enables "Bob-optim
ized" protocols. This paradigm has led to tremendous progress in recent ye
ars. However\, all existing constructions of laconic primitives are consid
ered only of theoretical interest: They all rely on non-black-box cryptogr
aphic techniques\, which are highly impractical.\n\nThis work shows that n
on-black-box techniques are not necessary for basic laconic cryptography p
rimitives. We propose a completely algebraic construction of laconic encry
ption\, a notion that we introduce in this work\, which serves as the corn
erstone of our framework. We prove that the scheme is secure under the sta
ndard Learning With Errors assumption (with polynomial modulus-to-noise ra
tio). We provide proof-of-concept implementations for the first time for l
aconic primitives\, demonstrating the construction is indeed practical: Fo
r a database size of \n\, encryption and decryption are in the order of si
ngle digit milliseconds.\n\nLaconic encryption can be used as a black box
to construct other laconic primitives. Specifically\, we show how to const
ruct:\n\n- Laconic oblivious transfer\n- Registration-based encryption sch
eme \n- Laconic private-set intersection protocol\n\nAll of the above have
essentially optimal parameters and similar practical efficiency. Furtherm
ore\, our laconic encryption can be preprocessed such that the online encr
yption step is entirely combinatorial and therefore much more efficient. U
sing similar techniques\, we also obtain identity-based encryption with an
unbounded identity space and tight security proof (in the standard model)
.\n\nRussell W. F. Lai is an Assistant Professor at the Department of Comp
uter Science of Aalto University since 2022. He works on a range of topics
in cryptography including lattice-based cryptography\, succinct arguments
\, and anonymous systems. He obtained his PhD degree from Friedrich-Alexan
der University Erlangen-Nuremberg in 2022.
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Structure-Preserving Cryptography and Lattices by Dennis Hofhei
nz
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230612T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230612T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202306121300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThe Groth-Sahai proof system is a highly efficient pairing
-based proof system for a specific class of group-based languages. Cryptog
raphic primitives that are compatible with these languages (such that we c
an express\, e.g.\, that a ciphertext contains a valid signature for a giv
en message) are called “structure-preserving”. The combination of stru
cture-preserving primitives with Groth-Sahai proofs allows to prove comple
x statements that involve encryptions and signatures\, and has proved usef
ul in a variety of applications. However\, so far\, the concept of structu
re-preserving cryptography has been confined to the pairing setting.\n\nIn
this talk\, I will outline a strategy for structure-preserving cryptograp
hy from lattices. At the heart of this framework lies a lattice-based argu
ment system for “noisy” languages (formalized as “structure-preservi
ng sets”)\, and the observation that this proof system is compatible wit
h a number of existing lattice-based primitives. We demonstrate the useful
ness of our framework with a lattice-based construction of verifiably encr
ypted signatures. As a secondary contribution\, we present a more efficien
t variant of Rückert's signature scheme. I should note that (like in the
group-based setting of structure-preserving cryptography)\, all our constr
uctions are in the standard model.\n\n\nBefore joining ETH Zurich's CS dep
artment in 2020\, I used to work at the Karlsruhe Institute of Technology
in Germany\, and before that at the Centrum Wiskunde en Informatica in Ams
terdam\, the Netherlands. I work on the foundations of cryptography\, and
in particular on the design and analysis of cryptographic building blocks
(such as public-key encryption and signatures).
END:VEVENT
BEGIN:VEVENT
SUMMARY:Witness Encryption\, Null IO\, and Evasive LWE by Hoeteck Wee
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230515T150000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230515T160000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202305151500@https://jcs.trusted-third-party/
DESCRIPTION:\n\nI will present our work on witness encryption and null IO\
, as well as some musings on the evasive LWE assumption (in particular\, r
elation to prior zeroizing attacks on IO). Based on joint works with Vinod
Vaikuntanathan\, Daniel Wichs\, and David Wu.\n\nHoeteck is a senior scie
ntist at NTT Research\, currently on leave from CNRS and ENS\, Paris.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fast Practical Lattice Reduction through Iterated Compression by K
eegan Ryan
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230417T160000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230417T170000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202304171600@https://jcs.trusted-third-party/
DESCRIPTION:Note the changed time.\n\nWe introduce a new lattice basis red
uction algorithm with approximation guarantees analogous to the LLL algori
thm and practical performance that far exceeds the current state of the ar
t. We achieve these results by iteratively applying precision management t
echniques within a recursive algorithm structure and show the stability of
this approach. We analyze the asymptotic behavior of our algorithm\, and
show that the heuristic running time is $O(n^{\\omega}(C+n)^{1+\\varepsilo
n})$ for lattices of dimension $n$\, $\\omega\\in (2\,3]$ bounding the cos
t of size reduction\, matrix multiplication\, and QR factorization\, and $
C$ bounding the log of the condition number of the input basis $B$. This y
ields a running time of $O\\left(n^\\omega (p + n)^{1 + \\varepsilon}\\rig
ht)$ for precision $p = O(\\log \\|B\\|_{max})$ in common applications. Ou
r algorithm is fully practical\, and we have published our implementation.
We experimentally validate our heuristic\, give extensive benchmarks agai
nst numerous classes of cryptographic lattices\, and show that our algorit
hm significantly outperforms existing implementations.\n\nKeegan Ryan is a
4th year PhD student advised by Prof. Nadia Heninger at the University of
California\, San Diego. His research interests include practical cryptana
lysis of real-world systems\, particularly problems involving lattice redu
ction.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Private Re-Randomization for Module LWE and Applications to Quasi-
Optimal ZK-SNARKs by Ron Steinfeld
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230417T090000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230417T100000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202304170900@https://jcs.trusted-third-party/
DESCRIPTION:Note the changed time.\n\nWe introduce the first candidate lat
tice-based Designated Verifier (DV) ZK-SNARK protocol with \\emph{quasi-op
timal proof length} (quasi-linear in the security/privacy parameter)\, avo
iding the use of the exponential smudging technique. Our ZK-SNARK also ach
ieves significant improvements in proof length in practice\, with proofs l
ength below 6 KB for 128-bit security/privacy level. \nOur main technical
result is a new regularity theorem for `private' re-randomization of Modul
e LWE (MLWE) samples using discrete Gaussian randomization vectors\, also
known as a lattice-based leftover hash lemma with leakage\, which applies
with a discrete Gaussian re-randomization parameter that is polynomial in
the statistical privacy parameter. \nTo obtain this result\, we obtain bou
nds on the smoothing parameter of an intersection of a random q-ary SIS mo
dule lattice\, Gadget SIS module lattice\, and Gaussian orthogonal module
lattice over standard power of 2 cyclotomic rings\, and a bound on the min
imum of module gadget lattices. We then introduce a new candidate \\emph{l
inear-only} homomorphic encryption scheme called Module Half-GSW (HGSW)\,
which is a variant of the GSW somewhat homomorphic encryption scheme over
modules\, and apply our regularity theorem to provide smudging-free circui
t-private homomorphic linear operations for Module HGSW.\n\nRon Steinfeld
is an Associate Professor at Monash University. His research focuses on po
st-quantum cryptography and its applications. He obtained his Ph.D. degree
in cryptography at Monash University in 2003. He was a postdoctoral ARC R
esearch Fellow at Macquarie University. He joined Monash University in 201
2.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Circuit Privacy for FHEW/TFHE-Style Fully Homomorphic Encryption i
n Practice by Kamil Kluczniak
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230306T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230306T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202303061300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nA fully homomorphic encryption (FHE) scheme allows a clien
t to encrypt and delegate its data to a server that performs computation o
n the encrypted data that the client can then decrypt. While FHE gives con
fidentiality to clients' data\, it does not protect the server's input and
computation. Nevertheless\, FHE schemes are still helpful in building del
egation protocols that reduce communication complexity\, as the ciphertext
's size is independent of the size of the computation performed on them. \
n\nWe can further extend FHE by a property called circuit privacy\, which
guarantees that the result of computing on ciphertexts reveals no informat
ion on the computed function and the inputs of the server. Thereby\, circu
it private FHE gives rise to round optimal and communication efficient sec
ure two-party computation protocols. Unfortunately\, despite significant e
fforts and much work put into the efficiency and practical implementations
of FHE schemes\, very little has been done to provide useful and practica
l FHE supporting circuit privacy. In this work\, we address this gap and d
esign the first randomized bootstrapping algorithm whose single invocation
sanitizes a ciphertext and\, consequently\, serves as a tool to provide c
ircuit privacy. We give an extensive analysis\, propose parameters\, and p
rovide a C++ implementation of our scheme. Our bootstrapping can sanitize
a ciphertext to achieve circuit privacy at an 80-bit statistical security
level in 1.2 or 1.4 seconds\, depending on whether the parameter set targe
ts a fast Fourier or a number theoretic transform-based implementation. In
addition\, we can perform non-sanitized bootstrapping in around 0.27 or 0
.14 seconds on a laptop where the additional sanitization key takes less t
han $0.5$ MB of memory. Crucially\, we do not need to increase the paramet
ers to perform computation before or after sanitization takes place. For c
omparison's sake\, we revisit the Ducas-Stehl\\'e washing machine method.
In particular\, we give a tight analysis\, estimate efficiency\, review ol
d\, and provide new parameters. \n\nKamil Kluczniak is currently a Researc
h Group Leader at CISPA Helmholtz Center for Information Security. His wor
k focuses on efficient fully homomorphic encryption schemes. He obtained
his Ph.D. degree in cryptography from the Polish Academy of Sciences in 20
16. In 2017 he worked as a postdoctoral researcher at the Hong Kong Polyt
echnique University. In 2018 he joined the CISPA-Stanford Center\, and fro
m 2019-2021 he was a visiting assistant professor at Stanford University.\
n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Quantum Rewinding for Many-Round Protocols by Nick Spooner
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230220T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230220T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202302201300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nWe investigate the security of succinct arguments against
quantum adversaries. Our main result is a proof of knowledge-soundness in
the post-quantum setting for a class of multi-round interactive protocols\
, including those based on the recursive folding technique of Bulletproofs
.\n\nTo prove this result\, we devise a new quantum rewinding strategy\, t
he first that allows for rewinding across many rounds. This technique appl
ies to any protocol satisfying natural multi-round generalizations of spec
ial soundness and collapsing. For our main result\, we show that recent Bu
lletproofs-like protocols based on lattices satisfy these properties\, and
are hence sound against quantum adversaries.\n\nNick Spooner is an Assist
ant Professor of Computer Science at the University of Warwick. His work f
ocuses on post-quantum proof systems. His interests include interactive pr
oof systems and zero knowledge in general\, post-quantum cryptography\, qu
antum information\, coding theory and computational complexity. Previously
he was a postdoc at Boston University\, and he received his PhD from UC B
erkeley in 2020.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Post-Quantum Insecurity from LWE by Willy Quach
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230109T150000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230109T160000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202301091500@https://jcs.trusted-third-party/
DESCRIPTION:Note the changed time.\n\nWe show that for many fundamental cr
yptographic primitives\, proving classical security under the learning-wit
h-errors (LWE) assumption\, does \\emph{not} imply post-quantum security.
This is despite the fact that LWE is widely believed to be post-quantum se
cure\, and our work does not give any evidence otherwise. Instead\, it sho
ws that post-quantum insecurity can arise inside cryptographic constructio
ns\, even if the assumptions are post-quantum secure. \n\nConcretely\, our
work provides (contrived) constructions of pseudorandom functions\, CPA-s
ecure symmetric-key encryption\, message-authentication codes\, signatures
\, and CCA-secure public-key encryption schemes\, all of which are proven
to be classically secure under LWE via black-box reductions\, but demonstr
ably fail to be post-quantum secure. All of these cryptosystems are statel
ess and non-interactive\, but their security is defined via an interactive
game that allows the attacker to make oracle queries to the cryptosystem.
The polynomial-time quantum attacker can break these schemes by only makin
g a few \\emph{classical} queries to the cryptosystem\, and in some cases\
, a single query suffices. \n\nPreviously\, we only had examples of post-q
uantum insecurity under post-quantum assumptions for stateful/interactive
protocols. Moreover\, there appears to be a folklore belief that for state
less/non-interactive cryptosystems with black-box proofs of security\, a q
uantum attack against the scheme should translate into a quantum attack on
the assumption. This work shows otherwise. Our main technique is to caref
ully embed interactive protocols inside the interactive security games of
the above primitives.\n\nAs a result of independent interest\, we also sho
w a 3-round \\emph{quantum disclosure of secrets (QDS)} protocol between a
classical sender and a receiver\, where a quantum receiver learns a secre
t message in the third round but\, assuming LWE\, a classical receiver doe
s not.\n\nJoint work with Alex Lombardi\, Ethan Mook\, and Daniel Wichs. E
print: https://eprint.iacr.org/2022/869\n\nWilly Quach is a 6th year PhD s
tudent at Northeastern University advised by Daniel Wichs.
END:VEVENT
BEGIN:VEVENT
SUMMARY:How to Sample a Discrete Gaussian (and more) from a Random Oracle
by George Lu
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20221128T150000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20221128T160000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202211281500@https://jcs.trusted-third-party/
DESCRIPTION:Note the changed time.\n\nThe random oracle methodology is cen
tral to the design of many practical\ncryptosystems. A common challenge f
aced in several systems is the need to have\na random oracle that outputs
from a structured distribution $\\mathcal{D}$\, even though most \nheurist
ic implementations such as SHA-3 are best suited for outputting bitstrings
. \n\n\nOur work explores the problem of sampling from discrete Gaussian (
and related) distributions \nin a manner that they can be programmed into
random oracles. We make the following contributions:\n\n-We provide a defi
nitional framework for our results. We say that a sampling algorithm $\\ma
thsf{Sample}$ for \na distribution is explainable if there exists an algor
ithm $\\mathsf{Explain}$ where\, for a $x$ in the domain\, we have that\n$
\\mathsf{Explain}(x) \\rightarrow r \\in \\{0\,1\\}^n$ such that $\\mathsf
{Sample}(r)=x$. Moreover\, if $x$ is sampled from $\\mathcal{D}$ the expla
ined \ndistribution is statistically close to choosing $r$ uniformly at ra
ndom. We consider a variant of this definition\nthat allows the statistica
l closeness to be a "precision parameter'' given to the $\\mathsf{Explain}
$ algorithm. We show that sampling algorithms which satisfy our `explainab
ility' property can be programmed as a random oracle.\n\n-We provide a sim
ple algorithm for explaining \\emph{any} sampling algorithm that works\nov
er distributions with polynomial sized ranges.\nThis includes discrete Gau
ssians with small standard deviations. \n\n-We show how to transform a (no
t necessarily explainable) sampling algorithm $\\mathsf{Sample}$ for a dis
tribution\ninto a new $\\mathsf{Sample}'$ that is explainable. The require
ments for doing this is that (1) the probability density function\nis effi
ciently computable (2) it is possible to efficiently uniformly sample from
all elements that have a probability density\nabove a given threshold $p$
\, showing the equivalence of random oracles to these distributions and ra
ndom oracles to uniform bitstrings. \nThis includes a large class of distr
ibutions\, including all discrete Gaussians.\n\n-A potential drawback of t
he previous approach is that the transformation requires an additional\nco
mputation of the density function. We provide a more customized approach t
hat shows the Miccancio-Walter\ndiscrete Gaussian sampler is explainable a
s is. This suggests that other discrete Gaussian samplers\nin a similar ve
in might also be explainable as is.\n\nGeorge is a fourth year PhD student
at UT Austin advised by Dr. Brent Waters.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowle
dge Proofs by Thibauld Feneuil
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20221114T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20221114T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202211141300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nIn this talk\, I will present a new zero-knowledge proof o
f knowledge for the syndrome decoding (SD) problem on random linear codes.
Instead of using permutations like most of the existing protocols\, we re
ly on the MPC-in-the-head paradigm in which we reduce the task of proving
the low Hamming weight of the SD solution to proving some relations betwee
n specific polynomials. Specifically\, we propose a 5-round zero-knowledge
protocol that proves the knowledge of a vector x such that $y=Hx$ and $wt
(x)\\leq w$ and which achieves a soundness error close to $1/N$ for an arb
itrary $N$.\n\nWhile turning this protocol into a signature scheme\, we ac
hieve a signature size of 11-12 KB for 128-bit security when relying on th
e hardness of the SD problem on binary fields. Using larger fields (like $
\\mathbb{F}_{256}$)\, we can produce fast signatures of around 8 KB. This
allows us to outperform Picnic3 and be competitive with $\\text{SPHINCS}^{
+}$. Since the security relies on the hardness of the syndrome decoding pr
oblem for random linear codes which is known to be NP-hard and for which t
he cryptanalysis state of the art has been stable for many years\, it resu
lts in a conservative signature scheme. Moreover\, our scheme outperforms
all the former code-based signature schemes for the common “signature si
ze + public key size” metric.\n\nJoint work with [Antoine Joux](https://
cispa.de/en/people/c01anjo) and [Matthieu Rivain](https://www.matthieuriva
in.com/).\n\nThibauld Feneuil is a PhD student at CryptoExperts & Sorbonne
University (France). He is working on zero-knowledge proofs in post-quant
um cryptography.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Some Easy Instances of Ideal-SVP and Implications on the Partial V
andermonde Knapsack Problem by Katharina Boudgoust
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20221017T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20221017T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202210171300@https://jcs.trusted-third-party/
DESCRIPTION:This will be a hybrid seminar. The speaker will be giving the
talk from ENS de Lyon. \n\nThis talk focuses on the shortest vector proble
m over so-called ideal lattices. Whereas it is believed to be hard in the
worst-case\, prior works have shown that there are several specific cases\
, where the problem becomes easy to solve. We continue this line of work a
nd provide a simple condition under which an ideal lattice defines an easy
instance of the shortest vector problem. Namely\, we show that the more a
utomorphisms stabilize the ideal\, the easier it is to find a short vector
in it. This observation was already made for prime ideals in Galois field
s\, and we extend it to any ideal (whose prime factors are not ramified) o
f any number field\, generalizing the works of Pan et al. (Eurocrypt'21) a
nd Porter et al. (ArXiv'21). We then provide a cryptographic application o
f this result by showing that particular instances of the partial Vandermo
nde knapsack problem\, also known as partial Fourier recovery problem\, ca
n be solved classically in polynomial time. As a proof of concept\, we imp
lemented our attack and managed to solve those particular instances for co
ncrete parameter settings proposed in the literature. For random instances
\, we can halve the lattice dimension with non-negligible probability. We
conclude the presentation by clarifying the impacts of our results to latt
ice-based cryptography.\nThis is a joint work with Erell Gachon and Alice
Pellet-Mary.\n\n\nKatharina Boudgoust is a postdoctoral researcher in the
Cryptography and Security team of the Aarhus University\, Denmark\, under
the supervision of Peter Scholl. She is interested in lattice-based crypto
graphy\, and more specifically in the computational hardness assumptions u
nderlying lattice-based cryptosystems and threshold cryptography. From Sep
tember 2018 to November 2021\, Katharina was a PhD student with the EMSEC
team at IRISA Laboratory in Rennes\, France\, under the supervision of Ade
line Roux-Langlois and Pierre-Alain Fouque. Her PhD thesis focused on the
theoretical hardness of algebraically structured Learning With Errors.\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Codes and Learning With Errors over Function Fields by Maxime B
ombar
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20221003T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20221003T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202210031300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nIt is a long standing open problem in code-based cryptogra
phy to find search to decision reductions for _structured_ versions of the
decoding problem (_e.g. for quasi-cyclic codes_). Such results in the lat
tice-based setting have been carried out using number fields: Polynomial-L
WE\, Ring-LWE\, Module-LWE ...\n\nIn this talk\, I will present a function
field analogue of the LWE problem. This new framework leads to another po
int of view on structured codes\, strengthening the connections between la
ttice-based and code-based cryptography.\n\nThis framework can be instanti
ated with function field analogues of the cyclotomic number fields\, namel
y _Carlitz_ extensions\, leading to the first search to decision reduction
s on various structured versions of the decoding problem\, and Ring-LPN\,
which have applications to secure multi party computation. and to an authe
ntication protocol.\n\nThis is a joint work with Alain Couvreur and Thomas
Debris-Alazard.\n\n\nMaxime is a PhD student at LIX (Laboratoire d'Inform
atique de l'École Polytechnique) & Inria\, France. He is interested in th
e hardness of various problems related to algebraically structured codes (
either in the Hamming or the rank metric).
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lattice-Based Zero-Knowledge Proofs and Applications: Shorter\, Si
mpler\, and More General by Ngoc Khanh Nguyen
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220711T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220711T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202207111300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nWe present a much-improved practical protocol\, based on t
he hardness of Module-SIS and Module-LWE problems\, for proving knowledge
of a short vector s satisfying As = t mod q. The currently most-efficient
technique for constructing such a proof works by showing that the L_\\inft
y norm of sis small using CRT slots technique (Esgin et al.\, Asiacrypt 20
20). In this work\, we show that there is a more direct and more efficient
way to prove that s has a small L_2 norm which does not require an equivo
cation with the L_\\infty norm\, nor any conversion to the CRT representat
ion. We observe that the inner product between two vectors r and s can be
made to appear as a coefficient of a product (or sum of products) between
polynomials with coefficient vectors r and s. Thus\, by using a polynomial
product proof system and hiding all but one coefficient\, we can prove kn
owledge of the inner product of two vectors (or of a vector with itself) m
odulo q. Using a cheap\, "approximate range proof"\, one can then lift the
proof to be over Z instead of Zq. Our protocols for proving short norms w
ork over all (interesting) polynomial rings but are particularly efficient
for rings like Z[X]/(X^n+1) in which the function relating the inner prod
uct of vectors and polynomial products happens to be a "nice" automorphism
.\n\nThe new proof system can be plugged into constructions of various lat
tice-based privacy primitives in a black-box manner. As examples\, we ins
tantiate a verifiable encryption scheme and a group signature scheme which
are more than twice as compact as the previously best solutions.\n\nNgoc
Khanh Nguyen is a fourth-year PhD student at IBM Research Europe - Zurich
and ETH Zurich\, Switzerland\, supervised by Dr Vadim Lyubashevsky and Pro
f. Dennis Hofheinz. Previously\, Khanh obtained his B.Sc. and M.Eng. degre
es in Mathematics and Computer Science at the University of Bristol\, UK.\
n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anonymity of NIST PQC Round-3 KEMs by Keita Xagawa
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220627T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220627T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202206271300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThis paper investigates __anonymity__ of all NIST PQC Roun
d~3 KEMs: Classic McEliece\, Kyber\, NTRU\, Saber\, BIKE\, FrodoKEM\, HQC\
, NTRU Prime (Streamlined NTRU Prime and NTRU LPRime)\, and SIKE. \n\nWe s
how the following results: \n\n* NTRU is anonymous in the quantum random o
racle model (QROM) if the underlying deterministic PKE is strongly disjoin
t-simulatable. NTRU is collision-free in the QROM. A hybrid PKE scheme con
structed from NTRU as KEM and appropriate DEM is anonymous and robust. (Si
milar results for BIKE\, FrodoKEM\, HQC\, NTRU LPRime\, and SIKE hold exce
pt for one of three parameter sets of HQC.)\n* Classic McEliece is anonymo
us in the QROM if the underlying PKE is strongly disjoint-simulatable and
a hybrid PKE scheme constructed from it as KEM and appropriate DEM is anon
ymous.\n* Grubbs\, Maram\, and Paterson pointed out that Kyber and Saber h
ave a gap in the current IND-CCA security proof in the QROM (EUROCRYPT 202
2). \n\nWe found that Streamlined NTRU Prime has another technical obstac
le for the IND-CCA security proof in the QROM. \n\nThose answer the open p
roblem to investigate the anonymity and robustness of NIST PQC Round~3 KEM
s posed by Grubbs\, Maram\, and Paterson (EUROCRYPT 2022). \nWe use strong
disjoint-simulatability of the underlying PKE of KEM and strong pseudoran
domness and smoothness/sparseness of KEM as the main tools\, which will be
of independent interest.\n\nThe full paper is available at https://eprint
.iacr.org/2021/1323\n\nKeita Xagawa received his B.S. degree from Kyoto Un
iversity and M.S. and D.S. degrees from Tokyo Institute of Technology in 2
005\, 2007\, and 2010\, respectively. He joined NTT Corporation in 2010.\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rigorous computation of class group and unit group by Alice Pellet
-Mary
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220613T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220613T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202206131300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nComputing the class group and the unit group of a number f
ield is an important problem of algorithmic number theory. Recently\, it h
as also become an important problem in cryptography\, since it is used in
multiple algorithms solving the shortest vector problem in ideal lattices.
\n\nSubexponential algorithms (in the discriminant of the number field) ar
e known to solve this problem in any number fields\, but they heavily rely
on heuristics. The only non-heuristic known algorithm\, due to Hafner and
McCurley\, is restricted to imaginary quadratic number fields.\n\nIn this
talk\, I will present a rigorous subexponential algorithm computing units
and class group (and more generally T-units) in any number field\, assumi
ng the extended Riemann hypothesis.\n\nThis is a joint work with Koen de B
oer and Benjamin Wesolowski.\n\nAlice is a CNRS researcher (chargée de re
cherche) at the university of Bordeaux. She is part of the Institut de Mat
hématiques de Bordeaux (IMB) and of the Lfant inria team. She is interest
ed in lattice based cryptography\, and more specifically in the hardness o
f algorithmic problems related to algebraically structured lattices.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anonymous\, Robust Post-Quantum Public Key Encryption by Varun Mar
am
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220516T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220516T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202205161300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nA core goal of the NIST PQC competition is to produce publ
ic-key encryption (PKE) schemes which\, even if attacked with a large-scal
e quantum computer\, maintain the security guarantees needed by applicatio
ns. The main security focus in the NIST PQC context has been IND-CCA secur
ity\, but other applications demand that PKE schemes provide *anonymity* (
Bellare et al.\, ASIACRYPT 2001)\, and *robustness* (Abdalla et al.\, TCC
2010). Examples of such applications include anonymous communication syste
ms\, cryptocurrencies\, anonymous credentials\, searchable encryption\, an
d auction protocols. Almost nothing is known about how to build post-quant
um PKE schemes offering these security properties. In particular\, the sta
tus of the NIST PQC candidates with respect to anonymity and robustness is
unknown. \n\nIn this work\, we initiate a systematic study of anonymity a
nd robustness for post-quantum PKE schemes. Firstly\, we identify implicit
rejection as a crucial design choice shared by most post-quantum KEMs\, s
how that implicit rejection renders prior results on anonymity and robustn
ess for KEM-DEM PKEs inapplicable\, and transfer prior results to the impl
icit-rejection setting where possible. Secondly\, since they are widely us
ed to build post-quantum PKEs\, we examine how the Fujisaki-Okamoto (FO) t
ransforms (Fujisaki and Okamoto\, Journal of Cryptology 2013) confer robus
tness and enhance weak anonymity of a base PKE. \n\nWe then leverage our t
heoretical results to study the anonymity and robustness of three NIST KEM
finalists---Saber\, Kyber\, and Classic McEliece---and one alternate\, Fr
odoKEM. Overall\, our findings for robustness are definitive: we provide p
ositive robustness results for Saber\, Kyber\, and FrodoKEM\, and a negati
ve result for Classic McEliece. Our negative result stems from a striking
property of KEM-DEM PKE schemes built with the Classic McEliece KEM: for a
ny message $m$\, we can construct a single hybrid ciphertext $c$ which dec
rypts to the chosen $m$ under *any* Classic McEliece private key.\n\nOur f
indings for anonymity are more mixed: we identify barriers to proving anon
ymity for Saber\, Kyber\, and Classic McEliece. We also found that in the
case of Saber and Kyber\, these barriers lead to issues with their IND-CCA
security claims. We have worked with the Saber and Kyber teams to fix the
se issues\, but they remain unresolved. On the positive side\, we were abl
e to prove anonymity for FrodoKEM and a variant of Saber introduced by D'A
nvers et al. (AFRICACRYPT 2018). Our analyses of these two schemes also id
entified technical gaps in their IND-CCA security claims\, but we were abl
e to fix them.\n\nThis is a joint work with Paul Grubbs (University of Mic
higan) and Kenneth G. Paterson (ETH Zurich). \n\n\nVarun Maram is a third-
year PhD student in the Applied Cryptography group at ETH Zurich\, supervi
sed by Prof. Kenny Paterson. His current research interests lie in the are
a of post-quantum cryptography\, both in the asymmetric and symmetric sett
ings. Varun is also one of the primary submitters of "Classic McEliece"\,
a finalist algorithm for PKE and key-establishment in the NIST PQC standar
dization process.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Non-Interactive Zero Knowledge from Sub-exponential DDH by Zhengzh
ong Jin
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220502T153000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220502T163000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202205021530@https://jcs.trusted-third-party/
DESCRIPTION:\n\nWe provide the first constructions of non-interactive zero
-knowledge and Zap arguments for NP based on the sub-exponential hardness
of Decisional Diffie-Hellman against polynomial time adversaries (without
use of groups with pairings).\n\nCentral to our results\, and of independe
nt interest\, is a new notion of interactive trapdoor hashing protocols.\n
\n\nI have a broad interest in Theoretical Computer Science. Currently\, I
am working on Cryptography and Coding Theory. I am a fifth year Ph.D. stu
dent at Johns Hopkins University\, fortunately co-advised by Abhishek Jain
and Xin Li. \n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Public-Key Encryption from Continuous LWE by Charlotte Hoffmann
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220404T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220404T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202204041300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThe continuous learning with errors (CLWE) problem was rec
ently introduced by Bruna et al. (STOC 2021). They showed that its hardnes
s implies infeasibility of learning Gaussian mixture models\, while its tr
actability implies efficient Discrete Gaussian Sampling and thus asymptoti
c improvements in worst-case lattice algorithms. No reduction between CLWE
and LWE is currently known\, in either direction. \n\nWe propose four pub
lic-key encryption schemes based on the hardness of CLWE\, with varying tr
adeoffs between decryption and security errors\, and different discretizat
ion techniques. Some of our schemes are based on hCLWE\, a homogeneous var
iant\, which is no easier than CLWE. Our schemes yield a polynomial-time a
lgorithm for solving hCLWE\, and hence also CLWE\, using a Statistical Zer
o-Knowledge oracle.\n\nThis is joint work with Andrej Bogdanov\, Miguel Cu
eto Noval and Alon Rosen. E-print: https://eprint.iacr.org/2022/093\n\n\nC
harlotte is a PhD student in the Cryptography group at IST Austria under t
he supervision of Krzysztof Pietrzak.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Classical vs Quantum Random Oracles by Takashi Yamakawa
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220307T103000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220307T113000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202203071030@https://jcs.trusted-third-party/
DESCRIPTION:\n\nIn this paper\, we study relationship between security of
cryptographic schemes in the random oracle model (ROM) and quantum random
oracle model (QROM). First\, we introduce a notion of a proof of quantum a
ccess to a random oracle (PoQRO)\, which is a protocol to prove the capabi
lity to quantumly access a random oracle to a classical verifier. We obser
ve that a proof of quantumness recently proposed by Brakerski et al. (TQC
'20) can be seen as a PoQRO. We also give a construction of a publicly ver
ifiable PoQRO relative to a classical oracle. Based on them\, we construct
digital signature and public key encryption schemes that are secure in th
e ROM but insecure in the QROM. In particular\, we obtain the first exampl
es of natural cryptographic schemes that separate the ROM and QROM under a
standard cryptographic assumption. \n\nOn the other hand\, we give liftin
g theorems from security in the ROM to that in the QROM for certain types
of cryptographic schemes and security notions. For example\, our lifting t
heorems are applicable to Fiat-Shamir non-interactive arguments\, Fiat-Sha
mir signatures\, and Full-Domain-Hash signatures etc. We also discuss appl
ications of our lifting theorems to quantum query complexity.\n\n\nTakashi
Yamakawa is a researcher at NTT in Japan. He earned his PhD in Science fr
om The University of Tokyo in 2017.His research focuses on post-quantum an
d quantum cryptography.
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the Lattice Isomorphism Problem\, Quadratic Forms\, Remarkable
Lattices\, and Cryptography by Wessel van Woerden
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220207T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220207T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202202071300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nA natural and recurring idea in the knapsack/lattice crypt
ography literature is to start from a lattice with remarkable decoding cap
ability as your private key\, and hide it somehow to make a public key. Th
is is also how the code-based encryption scheme of McEliece (1978) proceed
s.\n\nThis idea has never worked out very well for lattices: ad-hoc approa
ches have been proposed\, but they have been subject to ad-hoc attacks\, u
sing tricks beyond lattice reduction algorithms. On the other hand the fra
mework offered by the Short Integer Solution (SIS) and Learning With Error
s (LWE) problems\, while convenient and well founded\, remains frustrating
from a coding perspective: the underlying decoding algorithms are rather
trivial\, with poor decoding performance.\n\nIn this work\, we provide gen
eric realisations of this natural idea (independently of the chosen remark
able lattice) by basing cryptography on the lattice isomorphism problem (L
IP). More specifically\, we provide:\n\n- a worst-case to average-case red
uction for search-LIP and distinguish-LIP within an isomorphism class\, by
extending techniques of Haviv and Regev (SODA 2014). \n\n- a zero-knowled
ge proof of knowledge (ZKPoK) of an isomorphism. This implies an identific
ation scheme based on search-LIP. \n\n- a key encapsulation mechanism (KEM
) scheme and a hash-then-sign signature scheme\, both based on distinguish
-LIP.\n\nThe purpose of this approach is for remarkable lattices to improv
e the security and performance of lattice-based cryptography. For example\
, decoding within poly-logarithmic factor from Minkowski's bound in a rema
rkable lattice would lead to a KEM resisting lattice attacks down to a pol
y-logarithmic approximation factor\, provided that the dual lattice is als
o close to Minkowski's bound. Recent works have indeed reached such decode
rs for certain lattices (Chor-Rivest\, Barnes-Sloan)\, but these do not pe
rfectly fit our need as their duals have poor minimal distance.\n\nWessel
is a PhD student in the Cryptology Group at CWI in Amsterdam under the sup
ervision of Léo Ducas.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Log-S-unit lattices using Explicit Stickelberger Generators to sol
ve Approx Ideal-SVP by Olivier BERNARD
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220124T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220124T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202201241300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nIn 2020\, Bernard and Roux-Langlois introduced the Twisted
-PHS algorithm to solve Approx-SVP for ideal lattices on any number field\
, based on the PHS algorithm by Pellet-Mary\, Hanrot and Stehlé in 2019.
They performed experiments for prime conductors cyclotomic fields of degre
es at most 70\, reporting approximation factors reached in practice. The m
ain obstacle for these experiments is the computation of a log-$\\mathcal{
S}$-unit lattice\, which requires classical subexponential time.\n\nIn thi
s paper\, our main contribution is to extend these experiments to 210 cycl
otomic fields of any conductor $m$ and of degree up to 210. Building upon
new results from Bernard and Ku{\\v{c}}era on the Stickelberger ideal\, we
construct a maximal set of independent $\\mathcal{S}$-units lifted from t
he maximal real subfield using explicit Stickelberger generators obtained
via Jacobi sums. Hence\, we obtain full-rank log-$\\mathcal{S}$-unit subla
ttices fulfilling the role of approximating the full Tw-PHS lattice. Notab
ly\, our obtained approximation factors match those from Bernard and Roux-
Langlois using the original log-$\\mathcal{S}$-unit lattice in small dimen
sions.\n\nAs a side result\, we use the knowledge of these explicit Sticke
lberger elements to remove almost all quantum steps in the CDW algorithm\,
by Cramer\, Ducas and Wesolowski in 2021\, under the mild restriction tha
t the plus part of the class number verifies $h^{+}_{m}\\leq O(\\sqrt{m})$
.\n\nThe full paper is available on [ePrint:2021/1384](https://eprint.iacr
.org/2021/1384).\nThis is joint work with Andrea Lesavourey\, Tuong-Huy Ng
uyen and Adeline Roux-Langlois.\n\nOlivier BERNARD is a research engineer
at the cryptology laboratory of Thales\, Gennevilliers\, and is currently
in the third year of a part-time PhD under the supervision of Pierre-Alain
Fouque and Adeline Roux-Langlois. His research interests mainly focus on
number theoretic cryptanalyses and more generally on algorithmic number th
eory.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lattice sieving via quantum random walks by Johanna Loyer
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220110T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220110T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202201101300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nLattice-based cryptography is one of the leading proposals
for post-quantum cryptography. The Shortest Vector Problem (SVP) is argua
bly the most important problem for the cryptanalysis of latticebased crypt
ography\, and many lattice-based schemes have security claims based on its
hardness. The best quantum algorithm for the SVP is due to Laarhoven [Laa
16 PhD thesis] and runs in (heuristic) time $d^{0.2653d+o(d)}$. \nWe prese
nt an improvement over Laarhoven’s result and present an algorithm that
has a (heuristic) running time of $d^{0.2570d+o(d)}$ where $d$ is the latt
ice dimension. We also present time-memory trade-offs where we quantify th
e amount of quantum memory and quantum random access memory of our algorit
hm. \nThe core idea is to replace Grover’s algorithm used in [Laa16 PhD
thesis] in a key part of the sieving algorithm by a quantum random walk in
which we add a layer of local sensitive filtering.\n\n2nd year PhD studen
t at Inria Paris advised by André Chailloux.
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the (in)security of ROS by Michele Orrù
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20211213T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20211213T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202112131300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nWe present an algorithm solving the ROS (Random inh
omogeneities in a Overdetermined Solvable system of linear equatio
ns) problem in polynomial time for $\\ell > \\log p$ dimensions.
Our algorithm can be combined with Wagner’s attack\, and lead
s to a sub-exponential solution for any dimension $\\ell$ with b
est complexity known so far.\nWhen concurrent executions are allow
ed\, our algorithm leads to practical attacks against unforgeabili
ty of blind signature schemes such as Schnorr and Okamoto–Schn
orr blind signatures\, threshold signatures such as GJKR and the
original version of FROST\, multisignatures such as CoSI and t
he two-round version of MuSig\, partially blind signatures such a
s Abe–Okamoto\, and conditional blind signatures such as ZGP17.
\n\nThis is joint work with [Fabrice Benhamouda](https://www.normalesup.or
g/~fbenhamo/)\, [Tancrède Lepoint](https://tlepoint.github.io/)\, [Julian
Loss](https://www.julianloss.com/)\, [Mariana Raykova](https://marianapr.
github.io/).\n\n\nMichele is a postdoc at UC Berkeley under the supervisio
n of [Alessandro Chiesa](https://people.eecs.berkeley.edu/~alexch/). \n\nP
rior to that\, he was a PhD student at École Normale Supérieure\, under
the supervision of [Georg Fuchsbauer](https://www.di.ens.fr/~fuchsbau/). H
e is interested in the intersection between authentication and anonymity.\
n\nIn the past\, he contributed to Python\, Debian\, and Tor.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Does Fiat-Shamir Require a Cryptographic Hash Function by Willy Qu
ach
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20211129T143000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20211129T153000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202111291430@https://jcs.trusted-third-party/
DESCRIPTION:\n\nThe Fiat-Shamir transform is a general method for reducing
interaction in public-coin protocols by replacing the random verifier mes
sages with deterministic hashes of the protocol transcript. The soundness
of this transformation is usually heuristic and lacks a formal security pr
oof. Instead\, to argue security\, one can rely on the random oracle metho
dology\, which informally states that whenever a random oracle soundly ins
tantiates Fiat-Shamir\, a hash function that is ``sufficiently unstructure
d'' (such as fixed-length SHA-2) should suffice. Finally\, for some specia
l interactive protocols\, it is known how to (1) isolate a concrete securi
ty property of a hash function that suffices to instantiate Fiat-Shamir an
d (2) build a hash function satisfying this property under a cryptographic
assumption such as Learning with Errors.\n\nIn this work\, we abandon thi
s methodology and ask whether Fiat-Shamir truly requires a cryptographic h
ash function. Perhaps surprisingly\, we show that in two of its most commo
n applications --- building signature schemes as well as (general-purpose)
non-interactive zero-knowledge arguments --- there are sound Fiat-Shamir
instantiations using extremely simple and non-cryptographic hash functions
such as sum-mod-$p$ or bit decomposition. In some cases\, we make idealiz
ed assumptions (i.e.\, we invoke the generic group model)\, while in other
s\, we prove soundness in the plain model.\n\nOn the negative side\, we al
so identify important cases in which a cryptographic hash function is prov
ably necessary to instantiate Fiat-Shamir. We hope this work leads to an i
mproved understanding of the precise role of the hash function in the Fiat
-Shamir transformation.\n\nJoint work with Yilei Chen\, Alex Lombardi and
Fermi Ma.\nEprint: https://eprint.iacr.org/2020/915\n\nWilly Quach is a 5t
h year PhD student at Northeastern University advised by Daniel Wichs.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Compressed Σ-Protocol Theory by Thomas Attema
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20211115T120000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20211115T130000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202111151200@https://jcs.trusted-third-party/
DESCRIPTION:Note the changed time.\n\nΣ-Protocols provide a well-understo
od basis for secure algorithmics. Compressed Σ-protocol theory (CRYPTO 20
20) was introduced as a strengthening yielding protocols with low communic
ation complexity. It is built around basic Σ-protocols for proving that a
compactly committed (long) vector satisfies a linear constraint. The comm
unication complexity of these protocols is first compressed\, from linear
down to logarithmic\, using a recursive ``folding-technique'' adapted from
Bulletproofs (Bootle et al.\, EUROCRYPT 2016\, and Bünz et al.\, S&P 201
8)\, at the expense of logarithmic rounds. Proving in ZK that the secret v
ector satisfies a given constraint -- captured by a (non-linear) circuit -
- is then by (blackbox) reduction to the linear case\, via arithmetic secr
et-sharing techniques adapted from MPC.\n\nThis abstract modular theory ha
s been instantiated from a variety of cryptographic hardness assumptions\,
i.e.\, the discrete-logarithm\, strong-RSA\, knowledge-of-exponent assump
tion. In two separate works\, it has also been generalized to a bilinear c
ircuit model and instantiated from the ring-SIS assumption. Thus for all t
hese platforms compressed Σ-protocol theory yields circuit zero-knowledge
protocols with (poly)-logarithmic communication.\n\nAll in all\, our theo
ry should more generally be useful for modular (``plug-&-play'') design of
practical cryptographic protocols\; this is further evidenced by our sepa
rate work on proofs of partial knowledge.\n\nJoint work with: Ronald Crame
r\, Serge Fehr\, Lisa Kohl and Matthieu Rambaud\n\nThomas Attema is a rese
archer at the applied research institute TNO in The Netherlands\, where he
works on (applied) multi-party computation\, zero-knowledge proof systems
and post-quantum cryptography. Moreover\, he is pursuing a part-time PhD
in the Cryptology group of CWI under the supervision of Ronald Cramer.
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the Security of Homomorphic Encryption on Approximate Numbers b
y Baiyu Li
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20211004T150000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20211004T160000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202110041500@https://jcs.trusted-third-party/
DESCRIPTION:\n\nIn this talk\, we study the passive security model of appr
oximate\nhomomorphic encryption schemes. We present new passive security d
efinitions\nfor homomorphic encryption in the approximate computation sett
ing\, by naturally\nextending the traditional notion of IND-CPA security.\
nWe propose both indistinguishability-based and simulation-based variants\
,\nas well as restricted versions of the definitions that limit the order
and number\nof adversarial queries (as may be enforced by some application
s).\nWe prove implications and separations among different definitional va
riants\,\nshowing a hierarchy of approximate homomorphic encryption scheme
s.\nOur models provide a solid theoretical basis for the security evaluati
on of\napproximate homomorphic encryption schemes (against passive attacks
).\n\nAs the main application of our passive security models\, we present
passive attacks\nagainst CKKS\, the homomorphic encryption scheme for arit
hmetic on approximate numbers\npresented at Asiacrypt 2017. The attack is
both theoretically efficient (running in\nexpected polynomial time) and ve
ry practical\, leading to complete key recovery with\nhigh probability and
very modest running times. \nWe implemented and tested the attack against
major open source homomorphic encryption\nlibraries\, including HEAAN\, S
EAL\, HElib\, PALISADE and Lattigo\, and when computing\nseveral functions
that often arise in applications of the CKKS scheme to\nprivacy-preservin
g machine learning.\nOur attack shows that the traditional formulation of
IND-CPA security (or\nindistinguishability against chosen plaintext attack
s) achieved by CKKS does not\nadequately capture security against passive
adversaries when applied to approximate\nencryption schemes\, and that a d
ifferent\, stronger definition is required to evaluate\nthe security of su
ch schemes.\n\nWe further discuss possible modifications to CKKS that may
serve as countermeasures\nto our attacks\, and we also discuss open proble
ms of efficiently achieving provable\nsecurity under our new definitions.\
n\nThis talk is based on the joint work with Daniele Micciancio.\n\n\nBaiy
u Li graduated with a Ph.D. degree from UCSD in 2021\, advised by Daniele\
nMicciancio. His research interests include formal methods for secure comp
utation\nprotocol design and analysis\, as well as lattice-based cryptogra
phy.\nPreviously he received his Master's and Bachelor's degrees in CS and
Pure Math from\nthe University of Waterloo.
END:VEVENT
BEGIN:VEVENT
SUMMARY:Quantum Reduction of Finding Short Code Vectors to the Decoding Pr
oblem by Thomas Debris-Alazard
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20210920T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20210920T140000
DTSTAMP;VALUE=DATE-TIME:20241011T042904Z
UID:202109201300@https://jcs.trusted-third-party/
DESCRIPTION:The seminar will be at 13:00 UK time\, 14:00 FR time\n\nIn thi
s talk we will give a quantum reduction from finding short codewords in a
random linear code to decoding for the Hamming metric. This is the first t
ime such a reduction (classical or quantum) has been obtained. Our reducti
on adapts to linear codes Stehlé-Steinfield-Tanaka-Xagawa’ re-interpret
ation of Regev’s quantum reduction from finding short lattice vectors to
solving the Closest Vector Problem. The Hamming metric is a much coarser
metric than the Euclidean metric and this adaptation has needed several ne
w ingredients to make it work. For instance\, in order to have a meaningfu
l reduction it is necessary in the Hamming metric to choose a very large d
ecoding radius and this needs in many cases to go beyond the radius where
decoding is unique. Another crucial step for the analysis of the reduction
is the choice of the errors that are being fed to the decoding algorithm.
For lattices\, errors are usually sampled according to a Gaussian distrib
ution. However\, it turns out that the Bernoulli distribution (the analogu
e for codes of the Gaussian) is too much spread out and can not be used fo
r the reduction with codes. Instead we choose here the uniform distributio
n over errors of a fixed weight and bring in orthogonal polynomials tools
to perform the analysis and an additional amplitude amplification step to
obtain the aforementioned result.\n\n\n\nThomas Debris-Alazard is a resear
ch scientist (chargé de recherche) at Inria in the Grace project-team. He
was previously a postdoctoral research assistant in the Information Secur
ity Group under the supervision of Martin R. Albrecht. He received his PhD
from Inria under the supervision of Jean-Pierre Tillich.
END:VEVENT
END:VCALENDAR