IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
06 September 2021
Michael Scott
Shenghui Su, Jianhua Zheng, Shuwang Lv
Gianluca Brian, Antonio Faonio, Daniele Venturi
We also study the capacity (i.e., the maximum achievable asymptotic information rate) of continuously non-malleable secret sharing against joint continuous tampering attacks. In particular, we prove that whenever the attacker can tamper jointly with $k > t/2$ shares, the capacity is at most $t - k$. The rate of our construction matches this upper bound.
An important corollary of our results is the first non-malleable secret sharing scheme against independent tampering attacks breaking the rate-one barrier (under the same computational assumptions as above).
Bowen Liu, Qiang Tang, Jianying Zhou
Carlo Brunetta, Mario Larangeira, Bei Liang, Aikaterini Mitrokotsa, Keisuke Tanaka
Luise Mehner, Saskia Nuñez von Voigt, Florian Tschorsch
Priyanka Joshi, Bodhisatwa Mazumdar
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Elaine Shi
The previous best logarithmic overhead construction only guarantees it in an amortized sense, i.e., logarithmic overhead is achieved only for long enough access sequences, where some of the individual accesses incur $\Theta(N)$ overhead. The previously best ORAM in terms of worst-case overhead achieves $O(\log ^2 N/\log\log N)$ overhead.
Technically, we design a novel de-amortization framework for modern ORAM constructions that use the ``shuffled inputs'' assumption. Our framework significantly departs from all previous de-amortization frameworks, originating from Ostrovsky and Shoup (STOC '97), that seem to be fundamentally too weak to be applied on modern ORAM constructions.
03 September 2021
Marc Nemes, Rebecca Schwerdt, Dirk Achenbach, Bernhard Löwe, Jörn Müller-Quade
Lúcás Críostóir Meier, Simone Colombo, Marin Thiercelin, Bryan Ford
Minjoo Sim, Siwoo Eum, Hyeokdong Kwon, Kyungbae Jang, Hyunjun Kim, Hyunji Kim, Gyeongju Song, Wai-Kong Lee, Hwajeong Seo
Xiaoyang Dong, Zhiyu Zhang, Siwei Sun, Congming Wei, Xiaoyun Wang, Lei Hu
Pablo Rauzy, Ali Nehme
Hwajeong Seo, Hyeokdong Kwon, Siwoo Eum, Kyungbae Jang, Hyunjun Kim, Hyunji Kim, Minjoo Sim, Gyeongju Song, Wai-Kong Lee
Kelong Cong, Radames Cruz Moreno, Mariana Botelho da Gama, Wei Dai, Ilia Iliashenko, Kim Laine, Michael Rosenberg
We demonstrate that our protocol is significantly better than that of Chen et al. (CCS'18) for many practical parameters, especially in terms of online communication cost. For example, when intersecting $2^{28}$ and 2048 item sets, our protocol reduces the online computation time by more than 71% and communication by more than 63%. When intersecting $2^{24}$ and 4096 item sets, our protocol reduces the online computation time by 27% and communication by 63%. Our comparison to other state-of-the-art unbalanced PSI protocols shows that our protocol has the best total communication complexity when $\| X \| \geq 2^{24}$. For labeled PSI our protocol also outperforms Chen et al. (CCS'18). When intersecting $2^{20}$ and $256$ item sets, with the larger set having associated 288-byte labels, our protocol reduces the online computation time by more than 67% and communication by 34%.
Finally, we demonstrate a modification that results in nearly constant communication cost in the larger set size $\| X \|$, but impractically high computation complexity on today's CPUs. For example, to intersect a $210$-item set with sets of size $2^{22}$, $2^{24}$, or $2^{26}$, our proof-of-concept implementation requires only 0.76 MB of online communication, which is more than a 24-fold improvement over Chen et al. (CCS'18).
Chaoping Xing, Chen Yuan
In this work, we revisit evolving secret sharing schemes and present three constructions that take completely different approach. Most of the previous schemes mentioned above have more combinatorial flavor, while our schemes are more algebraic in nature. More precisely speaking, our evolving secret sharing schemes are obtained via either the Shamir secret sharing or arithmetic secret sharing from algebraic geometry codes alone. Our first scheme is an evolving $k$-threshold secret sharing scheme with share size $k^{1+\epsilon}\log t$ for any constant $\epsilon>0$. Thus, our scheme achieves almost the same share size as in \cite[TCC 2016]{KNY16}. Moreover, our scheme is obtained by a direct construction while the scheme in \cite[TCC 2016]{KNY16} that achieves the $(k-1)\log t$ share size is obtained by a recursive construction which makes their structure complicated. Our second scheme is an evolving $k_t$-threshold secret sharing scheme with any sequence $\{k_t\}_{t=1}^\infty$ of threshold values that has share size $t^4$. This scheme improves the share size by $\log t$ given in \cite{KC17} where a dynamic evolving $k_t$-threshold secret sharing scheme with the share size $O(t^4\log t)$ was proposed. In addition, we also show that if the threshold values $k_t$ grow in rate $\lfloor \beta t\rfloor$ for a real $\beta\in(0,1)$, then we have a dynamic evolving threshold secret sharing scheme with the share size $O(t^{4\beta})$. For $\beta<0.25$, this scheme has sub-linear share size which was not known before. Our last scheme is an evolving $(\Ga t,\Gb t)$-ramp secret sharing scheme with constant share size. One major feature of this ramp scheme is that it is multiplicative as the scheme is also an arithmetic secret sharing scheme. We note that the same technique in \cite{KC17} can also transform all of our schemes to a robust scheme as our scheme is linear.\footnote{We note that by replacing the building block scheme with an arithmetic secret sharing scheme, the evolving $(\Ga t,\Gb t)$-ramp secret sharing scheme in \cite{BO20} can also be multiplicative. However, their share size is much bigger than ours as each party hold multiple shares. }
Chris Monico
Elette Boyle, Justin Holmgren, Fermi Ma, Mor Weiss
In this note, we present an attack that provably breaks the BIPW TCC'17 toy conjecture. The attack identifies a natural embedding of permuted samples into a higher-dimensional linear space for which permuted polynomial samples will be rank deficient. We note, however, that our attack does not apply to the real assumption underlying the constructions, and thus the candidates still stand. We discuss extensions of the attack and present an alternative ``new toy conjecture'' for future study.
Similar results were independently obtained by (Blackwell and Wootters, ArXiv'21).
Daniel R. L. Brown
All non-interactive key agreement schemes, where each peer independently determines a single delivery to the other, reduce to this case, because the ability to agree implies the existence of an associative operation. By extending the associative operations domain, the key agreement scheme can be enveloped into a mathematical ring, such that all cryptographic values are ring elements, and all key agreement computations are ring multiplications. (A smaller envelope, a semigroup instead of a ring, is also possible.)
Security relies on the difficulty of division: here, meaning an operator $/$ such that $((ab)/b)b = ab$. Security also relies on the difficulty of the less familiar wedge operation $[ab, b, bc] \mapsto abc$.
When Rabi--Sherman key agreement is instantiated as Diffie--Hellman key agreement: its multiplication amounts to modular exponentiation; its division amounts to the discrete logarithm problem; the wedge operation amounts to the computational Diffie--Hellman problem.
Ring theory is well-developed and implies efficient division algorithms in some specific rings, such as matrix rings over fields. Semigroup theory, though less widely-known, also implies efficient division in specific semigroups, such as group-like semigroups.
The rarity of key agreement schemes with well-established security suggests that easy multiplication with difficult division (and wedges) is elusive.
Reduction of key agreement to ring or semigroup multiplication is not a panacea for cryptanalysis. Nonetheless, novel proposals for key agreement perhaps ought to run the gauntlet of a checklist for vulnerability to well-known division strategies that generalize across several forms of multiplication. Ambitiously applying this process of elimination to a plethora of diverse rings or semigroups might also, if only by a fluke, leave standing a few promising schemes, which might then deserve a more focused cryptanalysis.
02 September 2021
PQShield SAS
PQShield is a cybersecurity startup that specialises in post-quantum cryptography. Based in Paris, PQShield SAS concentrates the research activities of PQShield. Our mission is to come up with innovative algorithmic and/or protocol-level solutions to real-world cryptographic problems. Besides post-quantum cryptographic primitives, our research interests include advanced cryptosystems/protocols such as secure messaging, threshold schemes, and multiparty computation.
Who We Are Looking ForWe are looking for cryptographers with expertise in fields pertaining, but not limited, to post-quantum cryptography. Recruits will work with the team and provide new insights on research topics such as advanced cryptographic primitives, improvements to state-of-the-art practical cryptographic schemes, or constructions and proofs of security in models such as the QROM.
Skills we are interested in:- Deep knowledge of a relevant cryptographic field. We want future recruits to impulse new directions for our research and expand the spectrum of expertise of PQShield.
- Adaptability. You will be expected to work with a diverse team on projects that can cover various cryptographic fields.
- Dissemination of results. Working at PQShield entails publishing new research in top cryptographic conferences, and advertising our team’s work through invited talks, workshops, or blog articles.
- Competitive salaries. Yearly salaries start at 45,000 € for post-docs, and 65,000 € for full-fledged researchers.
- Stimulating environment. You will work with some of the best researchers in theoretical and practical aspects of post-quantum cryptography.
- Flexible work conditions. PQShield SAS has spacious and fully equipped offices in the heart of Paris. In addition, remote working and more specific arrangements (e.g. academic mobility programmes) are possible.
Please send your CV and cover letter to jobs (at) pqshield.com.
Closing date for applications:
Contact: jobs(at)pqshield.com
More information: https://www.linkedin.com/jobs/view/2704606293/