BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//ENSL/CWI/RHUL Joint Online Cryptography Seminars//https://joint-
cryptography-seminars.isg.rhul.ac.uk//
BEGIN:VEVENT
SUMMARY:On Codes and Learning With Errors over Function Fields by Maxime B
ombar
DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220926T130000
DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220926T140000
DTSTAMP;VALUE=DATE-TIME:20220522T153750Z
UID:202209261300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202207111300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202206271300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202206131300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202205161300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202205021530@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202204041300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202203071030@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202202071300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202201241300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202201101300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202112131300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202111291430@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202111151200@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202110041500@https://joint-cryptography-seminars.isg.rhul.ac.uk
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:20220522T153750Z
UID:202109201300@https://joint-cryptography-seminars.isg.rhul.ac.uk
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