BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//ENSL/CWI/KCL Joint Online Cryptography Seminars//https://jcs.tru
sted-third-party///
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:20230926T144212Z
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: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:20230926T144212Z
UID:202310231300@https://jcs.trusted-third-party/
DESCRIPTION:\n\nLet G be a finite abelian group 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 distance decoding algorithm. Li\, Ling\, Xi
ng and Yeo (IEEE Transactions on Information Theory 2020) proposed using a
relation lattice for a version of the McEliece code-based post-quantum en
cryption scheme. I will survey these results and discuss some improvements
to the cryptosystem of Li\, Ling\, Xing and Yeo.\n\nProfessor Galbraith i
s a researcher in mathematics of public key cryptography at the University
of Auckland in New Zealand. He has held positions at Royal Holloway\, Bri
stol\, Institute of Experimental Mathematics (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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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:20230926T144212Z
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