IACR News
If you have a news item you wish to distribute, they should be sent to the communications secretary. See also the events database for conference announcements.
Here you can see all recent updates to the IACR webpage. These updates are also available:
30 December 2021
Baofeng Wu
ePrint Report
In this note, we prove the conjecture posed by Keller and Rosemarin at Eurocrypt 2021 on the nullity of a matrix polynomial of a block matrix with Hadamard type blocks over commutative rings of characteristic 2. Therefore, it confirms the conjectural optimal bound on the dimension of invariant subspace of the Starkad cipher using the HADES design strategy. We also give characterizations of the algebraic structure formed by Hadamard matrices over commutative rings.
Eunsang Lee, Joon-Woo Lee, Junghyun Lee, Young-Sik Kim, Yongjune Kim, Jong-Seon No, Woosuk Choi
ePrint Report
Privacy-preserving machine learning on fully homomorphic encryption (FHE) is one of the most influential applications of the FHE scheme. Recently, Lee et al. [16] implemented the standard ResNet-20 model for the CIFAR-10 dataset with residue number system variant Cheon-Kim-Kim-Song (RNS-CKKS) scheme, one of the most promising FHE schemes, for the first time. However, its implementation should be improved because it requires large number of key-switching operations, which is the heaviest operation in the RNS-CKKS scheme. In order to reduce the number of key-switching operations, it should be studied to efficiently perform neural networks on the RNS-CKKS scheme utilizing full slots of RNS-CKKS ciphertext as much as possible. In particular, since the packing density is reduced to 1/4 whenever a convolution of stride two is performed, it is required to study convolution that maintains packing density of the data. On the other hand, when bootstrapping should be performed, it is desirable to use sparse slot bootstrapping that requires fewer key-switching operations instead of full slot bootstrapping. In this paper, we propose a new packing method that makes several tensors for multiple channels to be multiplexed into one tensor. Then, we propose new convolution method that outputs a multiplexed tensor for the input multiplexed tensor, which makes it possible to maintain a high packing density during the entire ResNet network with strided convolution. In addition, we propose a method that parallelly performs convolutions for multiple output channels using repeatedly packed input data, which reduces the running time of convolution. Further, we fine-tune the parameters to reach the standard 128-bit security level and to further reduce the number of the bootstrapping operations. As a result, the number of key-switching operations is reduced to 1/107 compared to Lee et al's implementation in the ResNet-20 model on the RNS-CKKS scheme. The proposed method takes about 37 minutes with only one thread for classification of one CIFAR-10 image compared to 3 hours with 64 threads of Lee et al.'s implementation. Furthermore, we even implement ResNet-32/44/56/110 models for the first time on RNS-CKKS scheme with the linear time of the number of layers, which is generally difficult to be expected in the leveled homomorphic encryption. Finally, we successfully classify the CIFAR-100 dataset on RNS-CKKS scheme for the first time using standard ResNet-32 model, and we obtain a running time of 3,942s and an accuracy of 69.4% close to the accuracy of backbone network 69.5%.
Nariyasu Heseri, Koji Nuida
ePrint Report
Due to the fact that classical computers cannot efficiently obtain random numbers, it is common practice to design cryptosystems in terms of real random numbers and then replace them with (cryptographically secure) pseudorandom ones for concrete implementations. However, as pointed out by [Nuida, PKC 2021], this technique may lead to compromise of security in secure multiparty computation (MPC) protocols. Although this work suggests using information-theoretically secure protocols and pseudorandom generators (PRGs) with high min-entropy to alleviate the problem, yet it is preferable to base the security on computational assumptions rather than the stronger information-theoretic ones. By observing that the contrived constructions in the aforementioned work use MPC protocols and PRGs that are closely related to each other, we notice that it may help to alleviate the problem by using protocols and PRGs that are "unrelated" to each other. In this paper, we propose a notion called "computational irrelevancy" to formalise the term "unrelated" and under this condition provide a security guarantee under computational assumptions.
Rawane Issa, Nicolas AlHaddad, Mayank Varia
ePrint Report
End-to-end encryption provides strong privacy protections to billions of people, but it also complicates efforts to moderate content that can seriously harm people. To address this concern, Tyagi et al. [CRYPTO 2019] introduced the concept of asymmetric message franking (AMF), which allows people to report abusive content to a moderator, while otherwise retaining end-to-end privacy by default and even compatibility with anonymous communication systems like Signal’s sealed sender.
In this work, we provide a new construction for asymmetric message franking called Hecate that is faster, more secure, and introduces additional functionality compared to Tyagi et al. First, our construction uses fewer invocations of standardized crypto primitives and operates in the plain model. Second, on top of AMF’s accountability and deniability requirements, we also add forward and backward secrecy. Third, we combine AMF with source tracing, another approach to content moderation that has previously been considered only in the setting of non-anonymous networks. Source tracing allows for messages to be forwarded, and a report only identifies the original source who created a message. To provide anonymity for senders and forwarders, we introduce a model of "AMF with preprocessing" whereby every client authenticates with the moderator out-of-band to receive a token that they later consume when sending a message anonymously.
In this work, we provide a new construction for asymmetric message franking called Hecate that is faster, more secure, and introduces additional functionality compared to Tyagi et al. First, our construction uses fewer invocations of standardized crypto primitives and operates in the plain model. Second, on top of AMF’s accountability and deniability requirements, we also add forward and backward secrecy. Third, we combine AMF with source tracing, another approach to content moderation that has previously been considered only in the setting of non-anonymous networks. Source tracing allows for messages to be forwarded, and a report only identifies the original source who created a message. To provide anonymity for senders and forwarders, we introduce a model of "AMF with preprocessing" whereby every client authenticates with the moderator out-of-band to receive a token that they later consume when sending a message anonymously.
Virtual event, Anywhere on Earth, 9 May - 11 May 2022
Event Calendar
Event date: 9 May to 11 May 2022
Submission deadline: 20 March 2022
Notification: 1 April 2022
Submission deadline: 20 March 2022
Notification: 1 April 2022
Villanova University, Department of ECE, Villanova, PA, USA
Job Posting
Ph.D. position opening (fully homomorphic encryption and related hardware implementation) at Dr. Jiafeng Harvest Xie's Security and Cryptography (SAC) Lab (https://www.ece.villanova.edu/~jxie02/lab/) in Department of Electrical and Computer Engineering, Villanova University, Villanova, PA USA.
Villanova University ranks #49 National Universities in the USA, is located in Villanova, Pennsylvania (west suburban of Philadelphia). Famous alumni include the current First Lady of the USA!
Requirements: Preferred to be in majors of EE/CE/CS, Applied Mathematics/Cryptography related majors are also warmly welcome!
Proficiency in English both speaking and writing abilities.
Skillful in programming Languages such as VHDL/Verilog, CC++, Python, and so on (FPGA-based experience is also desirable). Great enthusiasm for doing research-oriented tasks. Excellent teamwork member.
Degree: both BS and MS graduates or similar are warmly welcomed to apply.
Deadline: better to start in Summer/Fall 2022. It is always better to apply as early as possible. The position is open until it is filled.
Our lab atmosphere is peaceful and harmonious. Advisor and senior Ph.D. student will guide you to get started and work together on forthcoming challenges. You will not be fighting alone (emphasize this important thing three times!!!).
Email: jiafeng.xie@villanova.edu
This research focuses on the hardware-accelerated implementation of the combination of post-quantum cryptography and AI security (Fully Homomorphic Encryption). This direction is very new and looks promising for the next 5-n years, so a lot of research will be happening. At the same time, more opportunities are coming up, i.e., it is easier to find your development after exploring the combined research of post-quantum cryptography and AI. If you are interested, please email Dr. Xie.
Lastly, if you feel interested, please email: jiafeng.xie@villanova.edu and discuss your ideas.
Closing date for applications:
Contact: Dr. Jiafeng Harvest Xie
More information: https://www.ece.villanova.edu/~jxie02/lab/
27 December 2021
University of California, Santa Cruz (CSE Dept.)
Job Posting
The Computer Science and Engineering Department of the University of California, Santa Cruz invites applications for PhD students and Post-doctoral fellows in the topics of (applied) cryptography, security and privacy, secure databases and systems. Applicants should have a background/interest in cryptography, searchable encryption, databases and systems, oblivious RAM and oblivious computation, secure multi-party computation, hardware enclaves, computer & cloud security.
Closing Date for Application: January 10, 2022
Closing date for applications:
Contact: Assistant Prof. Ioannis Demertzis, idemertz (at) ucsc.edu
More information: http://idemertzis.com/UCSC_PHD_Postdoc_Openings.pdf
Spring Labs; Marina del Rey, Los Angeles, California
Job Posting
This role is responsible for design and specification of next-generation systems leveraging partial, somewhat, and fully homomorphic encryption. You will interact closely with Software Engineering and Product teams to ensure our newest products are effective, usable, performant and scalable.
Although Spring Labs has an in-office culture fostering a highly creative and collaborative environment, full-remote is acceptable for this role for the right candidate.
If you are motivated by solving real-world problems and want to work alongside veteran cryptographers and world-class engineers, we want to hear from you.
What you'll do- Design secure, novel, performant systems using cutting edge cryptography
- Author specifications, patents and papers detailing the systems and techniques that will underpin our next generation of products
- Communicate complex designs to engineers and support them in the implementation
- Educate technical and non-technical stakeholders on our tools and technologies
- Ph.D. – Cryptography, Math, Computer Science, Engineering or related discipline
- Strong background in design and evaluation of cryptographic primitives and protocols
- Preferably-extensive experience in homomorphic encryption schemes and underlying structures such as lattices, and their optimizations
- Robust interest in pursuing research/architecture of systems-level applications of cryptography pertaining to practical utilization of homomorphic encryption, oblivious transfer, secure multiparty computation, proxy re-encryption, privacy-preserving entity resolution, private information retrieval, private function evaluation, and functional encryption
- Genuine desire to maximize team output, e.g., exercise an established capability to cryptanalyze contributions of others
- Ability to implement prototypes and working knowledge of cryptographic libraries a plus
Closing date for applications:
Contact: David W. Kravitz, Director of Research, david@springlabs.com
Katie Thompson, Director of Human Resources, katiet@springlabs.com
More information: https://jobs.lever.co/springlabs/35c6327f-1ef9-47a8-b08c-3e79c45e2c23
23 December 2021
Washington, USA, 27 June - 30 June 2022
Event Calendar
Event date: 27 June to 30 June 2022
Submission deadline: 15 January 2022
Notification: 15 February 2022
Submission deadline: 15 January 2022
Notification: 15 February 2022
Aalto University & Helsinki University, Department of Computer Science, Espoo/Helsinki, Finland
Job Posting
We are hiring postdoctoral researchers working on the foundations of computing. We welcome applicants working in all areas of theoretical computer science, broadly interpreted, including e.g. algorithmics and algorithm engineering, computability and computational complexity, computational logic, optimization, cryptography, computational geometry, natural computation, and foundations of distributed, parallel, and quantum computing.
We offer the possibility to participate and take initiative in leading-edge research in a young and growing research environment with 10 professors and their teams working on foundational topics in the Helsinki area at Aalto University and the University of Helsinki (*). The postdoctoral researcher positions are full-time research positions for a duration of one year, with the possibility of extension to a second year by mutual consent. Travel funding is available for travel permitted by the pandemic situation. Participation in teaching of advanced courses and thesis instruction is possible and encouraged, with 5-10% allocation of the total working time.
(*) https://research.cs.aalto.fi/theory/
Supervisors:Chris Brzuska
Parinya Chalermsook
Petteri Kaski
Mikko Koivisto
Juha Kontinen
Sándor Kisfaludi-Bak
Pekka Orponen
Alexandru Paler
Jukka Suomela
Jara Uitto
General questions about HICT: Christina Sirviö, HICT team
General questions about recruitment process: Sanni Kirmanen, Aalto University HR
Questions about cryptography research at Aalto: Chris Brzuska
Firstname.lastname@aalto.fi
We offer the possibility to participate and take initiative in leading-edge research in a young and growing research environment with 10 professors and their teams working on foundational topics in the Helsinki area at Aalto University and the University of Helsinki (*). The postdoctoral researcher positions are full-time research positions for a duration of one year, with the possibility of extension to a second year by mutual consent. Travel funding is available for travel permitted by the pandemic situation. Participation in teaching of advanced courses and thesis instruction is possible and encouraged, with 5-10% allocation of the total working time.
(*) https://research.cs.aalto.fi/theory/
Supervisors:
Closing date for applications:
Contact:
More information: https://www.hiit.fi/open-calls/
22 December 2021
Debajyoti Das, Sebastian Meiser, Esfandiar Mohammadi, Aniket Kate
ePrint Report
While many anonymous communication (AC) protocols have been proposed to provide anonymity over the internet, scaling to a large number of users while remaining provably secure is challenging. We tackle this challenge by proposing a new scaling technique to improve the scalability/anonymity of AC protocols that distributes the computational load over many nodes without completely disconnecting the paths different messages take through the network.
We demonstrate that our scaling technique is useful and practical through a core sample AC protocol, Streams, that
offers provable security guarantees and scales for a million messages. The scaling technique ensures that each node in the system does the computation-heavy public key operation only for a tiny fraction of the total messages routed through the Streams network while maximizing the mixing/shuffling in every round.
We demonstrate Streams' performance through a prototype implementation. Our results show that Streams can scale well even if the system has a load of one million messages at any point in time. Streams maintains a latency of $16$ seconds while offering provable ``one-in-a-billion'' unlinkability, and can be leveraged for applications such as anonymous microblogging and network-level anonymity for blockchains. We also illustrate by examples that our scaling technique can be useful to many other AC protocols to improve their scalability and privacy, and can be interesting to protocol developers.
We demonstrate Streams' performance through a prototype implementation. Our results show that Streams can scale well even if the system has a load of one million messages at any point in time. Streams maintains a latency of $16$ seconds while offering provable ``one-in-a-billion'' unlinkability, and can be leveraged for applications such as anonymous microblogging and network-level anonymity for blockchains. We also illustrate by examples that our scaling technique can be useful to many other AC protocols to improve their scalability and privacy, and can be interesting to protocol developers.
Li Yao, Yilei Chen, Yu Yu
ePrint Report
At ITCS 2020, Bartusek et al. proposed a candidate indistinguishability obfuscator (iO) for affine determinant programs (ADPs). The candidate is special since it directly applies specific randomization techniques to the underlying ADP, without relying on the hardness of traditional cryptographic assumptions like discrete-log or learning with errors. It is relatively efficient compared to the rest of the iO candidates. However, the obfuscation scheme requires further cryptanalysis since it was not known to be based on any well-formed mathematical assumptions.
In this paper, we show cryptanalytic attacks on the iO candidate provided by Bartusek et al. Our attack exploits the weakness of one of the randomization steps in the candidate. The attack applies to a fairly general class of programs. At the end of the paper we discuss plausible countermeasures to defend against our attacks.
In this paper, we show cryptanalytic attacks on the iO candidate provided by Bartusek et al. Our attack exploits the weakness of one of the randomization steps in the candidate. The attack applies to a fairly general class of programs. At the end of the paper we discuss plausible countermeasures to defend against our attacks.
Valerie Fetzer, Marcel Keller, Sven Maier, Markus Raiber, Andy Rupp, Rebecca Schwerdt
ePrint Report
In this paper we propose Privacy-preserving User-data Bookkeeping & Analytics (PUBA), a building block destined to enable the implementation of business models (e.g., targeted advertising) and regulations (e.g., fraud detection) requiring user-data analysis in a privacy-preserving way.
In PUBA, users keep an unlinkable but authenticated cryptographic logbook containing their historic data on their device. This logbook can only be updated by the operator while its content is not revealed. Users can take part in a privacy-preserving analytics computation, where it is ensured that their logbook is up-to-date and authentic while the potentially secret analytics function is verified to be privacy-friendly. Taking constrained devices into account, users may also outsource analytic computations (to a potentially malicious proxy not colluding with the operator).
We model our novel building block in the Universal Composability framework and provide a practical protocol instantiation. To demonstrate the flexibility of PUBA, we sketch instantiations of privacy-preserving fraud detection and targeted advertising, although it could be used in many more scenarios, e.g. data analytics for multi-modal transportation systems. We implemented our bookkeeping protocols and an exemplary outsourced analytics computation based on logistic regression using the MP-SPDZ MPC framework. Performance evaluations using a smartphone as user device and more powerful hardware for operator and proxy suggest that PUBA for smaller logbooks can indeed be practical.
In PUBA, users keep an unlinkable but authenticated cryptographic logbook containing their historic data on their device. This logbook can only be updated by the operator while its content is not revealed. Users can take part in a privacy-preserving analytics computation, where it is ensured that their logbook is up-to-date and authentic while the potentially secret analytics function is verified to be privacy-friendly. Taking constrained devices into account, users may also outsource analytic computations (to a potentially malicious proxy not colluding with the operator).
We model our novel building block in the Universal Composability framework and provide a practical protocol instantiation. To demonstrate the flexibility of PUBA, we sketch instantiations of privacy-preserving fraud detection and targeted advertising, although it could be used in many more scenarios, e.g. data analytics for multi-modal transportation systems. We implemented our bookkeeping protocols and an exemplary outsourced analytics computation based on logistic regression using the MP-SPDZ MPC framework. Performance evaluations using a smartphone as user device and more powerful hardware for operator and proxy suggest that PUBA for smaller logbooks can indeed be practical.
Yi Liu, Qi Wang, Siu-Ming Yiu
ePrint Report
In the problem of two-party \emph{private function evaluation} (PFE), one party $P_A$ holds a \emph{private function} $f$ and (optionally) a private input $x_A$, while the other party $P_B$ possesses a private input $x_B$. Their goal is to evaluate $f$ on $x_A$ and $x_B$, and one or both parties may obtain the evaluation result $f(x_A, x_B)$ while no other information beyond $f(x_A, x_B)$ is revealed.
In this paper, we revisit the two-party PFE problem and provide several enhancements. We propose the \emph{first} constant-round actively secure PFE protocol with linear complexity. Based on this result, we further provide the \emph{first} constant-round publicly verifiable covertly (PVC) secure PFE protocol with linear complexity to gain better efficiency. For instance, when the deterrence factor is $\epsilon = 1/2$, compared to the passively secure protocol, its communication cost is very close and its computation cost is around $2.6\times$. In our constructions, as a by-product, we design a specific protocol for proving that a list of ElGamal ciphertexts is derived from an \emph{extended permutation} performed on a given list of elements. It should be noted that this protocol greatly improves the previous result and may be of independent interest. In addition, a reusability property is added to our two PFE protocols. Namely, if the same function $f$ is involved in multiple executions of the protocol between $P_A$ and $P_B$, then the protocol could be executed more efficiently from the second execution. Moreover, we further extend this property to be \emph{global}, such that it supports multiple executions for the same $f$ in a reusable fashion between $P_A$ and \emph{arbitrary} parties playing the role of $P_B$.
In this paper, we revisit the two-party PFE problem and provide several enhancements. We propose the \emph{first} constant-round actively secure PFE protocol with linear complexity. Based on this result, we further provide the \emph{first} constant-round publicly verifiable covertly (PVC) secure PFE protocol with linear complexity to gain better efficiency. For instance, when the deterrence factor is $\epsilon = 1/2$, compared to the passively secure protocol, its communication cost is very close and its computation cost is around $2.6\times$. In our constructions, as a by-product, we design a specific protocol for proving that a list of ElGamal ciphertexts is derived from an \emph{extended permutation} performed on a given list of elements. It should be noted that this protocol greatly improves the previous result and may be of independent interest. In addition, a reusability property is added to our two PFE protocols. Namely, if the same function $f$ is involved in multiple executions of the protocol between $P_A$ and $P_B$, then the protocol could be executed more efficiently from the second execution. Moreover, we further extend this property to be \emph{global}, such that it supports multiple executions for the same $f$ in a reusable fashion between $P_A$ and \emph{arbitrary} parties playing the role of $P_B$.
Pierrick Dartois, Luca De Feo
ePrint Report
The Oriented Supersingular Isogeny Diffie-Hellman is a post-quantum key exchange scheme recently introduced by Colò and Kohel. It is based on the group action of an ideal class group of a quadratic imaginary order on a subset of supersingular elliptic curves, and in this sense it can be viewed as a generalization of the popular isogeny based key exchange CSIDH. From an algorithmic standpoint, however, OSIDH is quite different from CSIDH. In a sense, OSIDH uses class groups which are more structured than in CSIDH, creating a potential weakness that was already recognized by Colò and Kohel. To circumvent the weakness, they proposed an ingenious way to realize a key exchange by exchanging partial information on how the class group acts in the neighborhood of the public curves, and conjectured that this additional information would not impact security.
In this work we revisit the security of OSIDH by presenting a new attack, building upon previous work of Onuki. Our attack has exponential complexity, but it practically breaks Colò and Kohel's parameters unlike Onuki's attack. We also discuss countermeasures to our attack, and analyze their impact on OSIDH, both from an efficiency and a functionality point of view.
In this work we revisit the security of OSIDH by presenting a new attack, building upon previous work of Onuki. Our attack has exponential complexity, but it practically breaks Colò and Kohel's parameters unlike Onuki's attack. We also discuss countermeasures to our attack, and analyze their impact on OSIDH, both from an efficiency and a functionality point of view.
Aisling Connolly, Pascal Lafourcade, Octavio Perez Kempner
ePrint Report
Anonymous attribute-based credentials (ABCs) are a powerful tool allowing users to authenticate while maintaining privacy. When instantiated from structure-preserving signatures on equivalence classes (SPS-EQ) we obtain a controlled form of malleability, and hence increased functionality and privacy for the user. Existing constructions consider equivalence classes on the message space, allowing the joint randomization of credentials and the corresponding signatures on them.
In this work, we additionally consider equivalence classes on the signing-key space. In this regard, we obtain a signer-hiding notion, where the issuing organization is not revealed when a user shows a credential. To achieve this, we instantiate the ABC framework of Fuchsbauer, Hanser, and Slamanig (FHS, Journal of Cryptology '19) with a recent SPS-EQ scheme (ASIACRYPT '19) modified to support a fully adaptive NIZK from the framework of Couteau and Hartmann (CRYPTO '20). We also show how to obtain Mercurial Signatures (CT-RSA, 2019), extending the application of our construction to anonymous delegatable credentials.
To further increase functionality and efficiency, we augment the set-commitment scheme of FHS19 to support openings on attribute sets disjoint from those possessed by the user, while integrating a proof of exponentiation to allow for a more efficient verifier. Instantiating in the CRS model, we obtain an efficient credential system, anonymous under malicious organization keys, with increased expressiveness and privacy, proven secure in the standard model.
In this work, we additionally consider equivalence classes on the signing-key space. In this regard, we obtain a signer-hiding notion, where the issuing organization is not revealed when a user shows a credential. To achieve this, we instantiate the ABC framework of Fuchsbauer, Hanser, and Slamanig (FHS, Journal of Cryptology '19) with a recent SPS-EQ scheme (ASIACRYPT '19) modified to support a fully adaptive NIZK from the framework of Couteau and Hartmann (CRYPTO '20). We also show how to obtain Mercurial Signatures (CT-RSA, 2019), extending the application of our construction to anonymous delegatable credentials.
To further increase functionality and efficiency, we augment the set-commitment scheme of FHS19 to support openings on attribute sets disjoint from those possessed by the user, while integrating a proof of exponentiation to allow for a more efficient verifier. Instantiating in the CRS model, we obtain an efficient credential system, anonymous under malicious organization keys, with increased expressiveness and privacy, proven secure in the standard model.
Jiaxin Guan, Daniel Wichs, Mark Zhandry
ePrint Report
Incompressible encryption allows us to make the ciphertext size flexibly large and ensures that an adversary learns nothing about the encrypted data, even if the decryption key later leaks, unless she stores essentially the entire ciphertext. Incompressible signatures can be made arbitrarily large and ensure that an adversary cannot produce a signature on any message, even one she has seen signed before, unless she stores one of the signatures essentially in its entirety.
In this work, we give simple constructions of both incompressible public-key encryption and signatures under minimal assumptions. Furthermore, large incompressible ciphertexts (resp. signatures) can be decrypted (resp. verified) in a streaming manner with low storage. In particular, these notions strengthen the related concepts of disappearing encryption and signatures, recently introduced by Guan and Zhandry (TCC 2021), whose previous constructions relied on sophisticated techniques and strong, non-standard assumptions. We extend our constructions to achieve an optimal ``rate'', meaning the large ciphertexts (resp. signatures) can contain almost equally large messages, at the cost of stronger assumptions.
In this work, we give simple constructions of both incompressible public-key encryption and signatures under minimal assumptions. Furthermore, large incompressible ciphertexts (resp. signatures) can be decrypted (resp. verified) in a streaming manner with low storage. In particular, these notions strengthen the related concepts of disappearing encryption and signatures, recently introduced by Guan and Zhandry (TCC 2021), whose previous constructions relied on sophisticated techniques and strong, non-standard assumptions. We extend our constructions to achieve an optimal ``rate'', meaning the large ciphertexts (resp. signatures) can contain almost equally large messages, at the cost of stronger assumptions.
21 December 2021
Budapest, Hungary, 1 August - 5 August 2022
School
Event date: 1 August to 5 August 2022
Zero-Knowledge for Homomorphic Key-Value Commitments with Applications to Privacy-Preserving Ledgers
Matteo Campanelli, Felix Engelmann, Claudio Orlandi
ePrint Report
Commitments to key-value maps (or, authenticated dictionaries) are an important building block in cryptographic applications, including cryptocurrencies and distributed file systems.
In this work we study short commitments to key-value maps with two additional properties: full-hiding (both keys and values should be hidden) and homomorphism (we should be able to combine two commitments to obtain one that is the ``sum'' of their key-value openings). Furthermore, we require these commitments to be short and to support efficient transparent zero-knowledge arguments (i.e., without a trusted setup).
As our main contribution, we show how to construct commitments with the properties above as well as efficient zero-knowledge arguments over them.
We additionally discuss a range of practical optimizations that can be carried out depending on the application domain.
Finally, we show a specific application of commitments to key-value maps to scalable anonymous ledgers. Our contribution there is to formalize multi-type anonimity ledgers and show how to extend QuisQuis (Fauzi et al., ASIACRYPT 2019). This results in an efficient, confidential multi-type system with a state whose size is independent of the number of transactions.
John Baena, Pierre Briaud, Daniel Cabarcas, Ray Perlner, Daniel Smith-Tone, Javier Verbel
ePrint Report
The Support-Minors (SM) method has opened new routes to attack multivariate schemes with rank properties that were previously impossible to exploit, as shown by the recent attacks of Tao at al. (CRYPTO 2021) and Beullens (EUROCRYPT 2021) on the NIST candidates GeMSS and Rainbow respectively. In this paper, we study this SM approach more in depth, which allows us first to propose a greatly improved attack on GeMSS, and also to define a more realistic cost model to evaluate the memory complexity of an XL strategy on the SM system using the Block-Wiedemann algorithm. Our new attack on GeMSS makes it completely unfeasible to repair the scheme by simply increasing the size of its parameters or even applying the projection technique from Øygarden et al. (PQCrypto 2021) as the signing time would be increased in a considerable way. Also, in our refined cost model, the rectangular MinRank attack from Beullens does indeed reduce the security of all Round 3 Rainbow parameter sets below their targeted security strengths.