eprint.iacr.org.rss.xml - sfeed_tests - sfeed tests and RSS and Atom files
(HTM) git clone git://git.codemadness.org/sfeed_tests
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
eprint.iacr.org.rss.xml (214812B)
---
1 <?xml version='1.0' encoding='UTF-8'?>
2 <rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:atom="http://www.w3.org/2005/Atom" xmlns:content="http://purl.org/rss/1.0/modules/content/" version="2.0">
3 <channel>
4 <title>Cryptology ePrint Archive</title>
5 <link>https://eprint.iacr.org/rss/rss.xml</link>
6 <description>The Cryptology ePrint Archive provides rapid access to recent
7 research in cryptology. Papers have been placed here by the
8 authors and did not undergo any refereeing process other than
9 verifying that the work seems to be within the scope of
10 cryptology and meets some minimal acceptance criteria and
11 publishing conditions.</description>
12 <atom:link href="https://eprint.iacr.org/rss/rss.xml" rel="self"/>
13 <category>Applications</category>
14 <category>Cryptographic protocols</category>
15 <category>Foundations</category>
16 <category>Implementation</category>
17 <category>Secret-key cryptography</category>
18 <category>Public-key cryptography</category>
19 <category>Attacks and cryptanalysis</category>
20 <copyright>Metadata is available under the CC0 license https://creativecommons.org/publicdomain/zero/1.0/. Each article has a PDF with different license specified for each one.</copyright>
21 <docs>https://validator.w3.org/feed/docs/rss2.html</docs>
22 <generator>None of your business</generator>
23 <image>
24 <url>https://iacr.org/img/logo/iacrlogo_small.png</url>
25 <title>Cryptology ePrint Archive</title>
26 <link>https://eprint.iacr.org/rss/rss.xml</link>
27 </image>
28 <language>en-US</language>
29 <lastBuildDate>Tue, 07 Mar 2023 18:03:34 +0000</lastBuildDate>
30 <ttl>1440</ttl>
31 <item>
32 <title>On the Security of Keyed Hashing Based on Public Permutations</title>
33 <link>https://eprint.iacr.org/2022/1172</link>
34 <description>Doubly-extendable cryptographic keyed functions (deck) generalize the concept of message authentication codes (MAC) and stream ciphers in that they support variable-length strings as input and return variable-length strings as output. A prominent example of building deck functions is Farfalle, which consists of a set of public permutations and rolling functions that are used in its compression and expansion layers. By generalizing the compression layer of Farfalle, we prove its universality in terms of the probability of differentials over the public permutation used in it. As the compression layer of Farfalle is inherently parallel, we compare it to a generalization of a serial compression function inspired by Pelican-MAC. The same public permutation may result in different universalities depending on whether the compression is done in parallel or serial. The parallel construction consistently performs better than the serial one, sometimes by a big factor. We demonstrate this effect using Xoodoo[3], which is a round-reduced variant of the public permutation used in the deck function Xoofff.</description>
35 <guid isPermaLink="true">https://eprint.iacr.org/2022/1172</guid>
36 <category>Secret-key cryptography</category>
37 <enclosure url="https://eprint.iacr.org/2022/1172.pdf" length="0" type="application/pdf"/>
38 <pubDate>Wed, 07 Sep 2022 16:20:02 +0000</pubDate>
39 <dc:creator>Jonathan Fuchs</dc:creator>
40 <dc:creator>Yann Rotella</dc:creator>
41 <dc:creator>Joan Daemen</dc:creator>
42 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
43 </item>
44 <item>
45 <title>Revisiting Related-Key Boomerang attacks on AES using computer-aided tool</title>
46 <link>https://eprint.iacr.org/2022/725</link>
47 <description>In recent years, several MILP models were introduced to search automatically for boomerang distinguishers and boomerang attacks on block ciphers. However, they can only be used when the key schedule is linear. Here, a new model is introduced to deal with nonlinear key schedules as it is the case for AES. This model is more complex and actually it is too slow for exhaustive search. However, when some hints are added to the solver, it found the current best related-key boomerang attack on AES-192 with $2^{124}$ time, $2^{124}$ data, and $2^{79.8}$ memory complexities, which is better than the one presented by Biryukov and Khovratovich at ASIACRYPT 2009 with complexities $2^{176}/2^{123}/2^{152}$ respectively. This represents a huge improvement for the time and memory complexity, illustrating the power of MILP in cryptanalysis.</description>
48 <guid isPermaLink="true">https://eprint.iacr.org/2022/725</guid>
49 <category>Attacks and cryptanalysis</category>
50 <enclosure url="https://eprint.iacr.org/2022/725.pdf" length="0" type="application/pdf"/>
51 <pubDate>Tue, 07 Jun 2022 14:40:31 +0000</pubDate>
52 <dc:creator>Patrick Derbez</dc:creator>
53 <dc:creator>Marie Euler</dc:creator>
54 <dc:creator>Pierre-Alain Fouque</dc:creator>
55 <dc:creator>Phuong Hoa Nguyen</dc:creator>
56 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
57 </item>
58 <item>
59 <title>Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head</title>
60 <link>https://eprint.iacr.org/2022/1407</link>
61 <description>The MPC-in-the-Head paradigm is a popular framework to build zero-knowledge proof systems using techniques from secure multi-party computation (MPC). While this paradigm is not restricted to a particular secret sharing scheme, all the efficient instantiations for small circuits proposed so far rely on additive secret sharing.
62
63 In this work, we show how applying a threshold linear secret sharing scheme (threshold LSSS) can be beneficial to the MPC-in-the-Head paradigm. For a general passively-secure MPC protocol model capturing most of the existing MPCitH schemes, we show that our approach improves the soundness of the underlying proof system from $1/N$ down to $1/\binom{N}{\ell}$, where $N$ is the number of parties and $\ell$ is the privacy threshold of the sharing scheme. While very general, our technique is limited to a number of parties $N \leq |\mathbb{F}|$, where $\mathbb{F}$ is the field underlying the statement, because of the MDS conjecture.
64
65 Applying our approach with a low-threshold LSSS also boosts the performance of the proof system by making the MPC emulation cost independent of $N$ for both the prover and the verifier. The gain is particularly significant for the verification time which becomes logarithmic in $N$ (while the prover still has to generate and commit the $N$ input shares). We further generalize and improve our framework: we show how homomorphic commitments can get rid of the linear complexity of the prover, we generalize our result to any quasi-threshold LSSS, and we describe an efficient batching technique relying on Shamir's secret sharing.
66
67 We finally apply our techniques to specific use-cases. We first propose a variant of the recent SDitH signature scheme achieving new interesting trade-offs. In particular, for a signature size of 10 KB, we obtain a verification time lower than $0.5$ ms, which is competitive with SPHINCS+, while achieving much faster signing. We further apply our batching technique to two different contexts: batched SDitH proofs and batched proofs for general arithmetic circuits based on the Limbo proof system. In both cases, we obtain an amortized proof size lower than $1/10$ of the baseline scheme when batching a few dozen statements, while the amortized performances are also significantly improved.</description>
68 <guid isPermaLink="true">https://eprint.iacr.org/2022/1407</guid>
69 <category>Cryptographic protocols</category>
70 <enclosure url="https://eprint.iacr.org/2022/1407.pdf" length="0" type="application/pdf"/>
71 <pubDate>Mon, 17 Oct 2022 11:41:11 +0000</pubDate>
72 <dc:creator>Thibauld Feneuil</dc:creator>
73 <dc:creator>Matthieu Rivain</dc:creator>
74 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
75 </item>
76 <item>
77 <title>Public Verification for Private Hash Matching</title>
78 <link>https://eprint.iacr.org/2023/029</link>
79 <description>End-to-end encryption (E2EE) prevents online services from accessing user content. This important security property is also an obstacle for content moderation methods that involve content analysis. The tension between E2EE and efforts to combat child sexual abuse material (CSAM) has become a global flashpoint in encryption policy, because the predominant method of detecting harmful content---server-side perceptual hash matching on plaintext images---is unavailable.
80
81 Recent applied cryptography advances enable private hash matching (PHM), where a service can match user content against a set of known CSAM images without revealing the hash set to users or nonmatching content to the service. These designs, especially a 2021 proposal for identifying CSAM in Apple's iCloud Photos service, have attracted widespread criticism for creating risks to security, privacy, and free expression.
82
83 In this work, we aim to advance scholarship and dialogue about PHM by contributing new cryptographic methods for system verification by the general public. We begin with motivation, describing the rationale for PHM to detect CSAM and the serious societal and technical issues with its deployment. Verification could partially address shortcomings of PHM, and we systematize critiques into two areas for auditing: trust in the hash set and trust in the implementation. We explain how, while these two issues cannot be fully resolved by technology alone, there are possible cryptographic trust improvements.
84
85 The central contributions of this paper are novel cryptographic protocols that enable three types of public verification for PHM systems: (1) certification that external groups approve the hash set, (2) proof that particular lawful content is not in the hash set, and (3) eventual notification to users of false positive matches. The protocols that we describe are practical, efficient, and compatible with existing PHM constructions.</description>
86 <guid isPermaLink="true">https://eprint.iacr.org/2023/029</guid>
87 <category>Cryptographic protocols</category>
88 <enclosure url="https://eprint.iacr.org/2023/029.pdf" length="0" type="application/pdf"/>
89 <pubDate>Mon, 09 Jan 2023 17:03:26 +0000</pubDate>
90 <dc:creator>Sarah Scheffler</dc:creator>
91 <dc:creator>Anunay Kulshrestha</dc:creator>
92 <dc:creator>Jonathan Mayer</dc:creator>
93 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
94 </item>
95 <item>
96 <title>Safely Doubling your Block Ciphers for a Post-Quantum World</title>
97 <link>https://eprint.iacr.org/2022/1342</link>
98 <description>In order to maintain a similar security level in a post-quantum setting, many symmetric primitives should have to double their keys and increase their state sizes. So far, no generic way for doing this is known that would provide convincing quantum security guarantees.
99 In this paper we propose a new generic construction that allows to double the key and the state size of a block cipher. For this we have modified the ECB-Mix-ECB (EME) construction, as we have been able to mount a new type of superposition attack on EME, and we provide several classical and quantum security arguments and analyses for our new construction QuEME. We propose a concrete instantiation of this construction with variants of AES-128.</description>
100 <guid isPermaLink="true">https://eprint.iacr.org/2022/1342</guid>
101 <category>Secret-key cryptography</category>
102 <enclosure url="https://eprint.iacr.org/2022/1342.pdf" length="0" type="application/pdf"/>
103 <pubDate>Fri, 07 Oct 2022 14:12:55 +0000</pubDate>
104 <dc:creator>Ritam Bhaumik</dc:creator>
105 <dc:creator>André Chailloux</dc:creator>
106 <dc:creator>Paul Frixons</dc:creator>
107 <dc:creator>María Naya-Plasencia</dc:creator>
108 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
109 </item>
110 <item>
111 <title>Half-Tree: Halving the Cost of Tree Expansion in COT and DPF</title>
112 <link>https://eprint.iacr.org/2022/1431</link>
113 <description>GGM tree is widely used in the design of correlated oblivious transfer (COT), subfield vector oblivious linear evaluation (sVOLE), distributed point function (DPF), and distributed comparison function (DCF). Often, the cost associated with GGM tree dominates the computation and communication of these protocols. In this paper, we propose a suite of optimizations that can reduce this cost by half.
114
115 • Halving the cost of COT and sVOLE. Our COT protocol introduces extra correlation to each level of a GGM tree used by the state-of-the-art COT protocol. As a result, it reduces both the number of AES calls and the communication by half. Extending this idea to sVOLE, we are able to achieve similar improvement with either halved computation or halved communication.
116
117 • Halving the cost of DPF and DCF. We propose improved two-party protocols for the distributed generation of DPF/DCF keys. Our tree structures behind these protocols lead to more efficient full-domain evaluation and halve the communication and the round complexity of the state-of-the-art DPF/DCF protocols.
118
119 All protocols are provably secure in the random-permutation model and can be accelerated based on fixed-key AES-NI. We also improve the state-of-the-art schemes of puncturable pseudorandom function (PPRF), DPF, and DCF, which are of independent interest in dealer-available scenarios.</description>
120 <guid isPermaLink="true">https://eprint.iacr.org/2022/1431</guid>
121 <category>Cryptographic protocols</category>
122 <enclosure url="https://eprint.iacr.org/2022/1431.pdf" length="0" type="application/pdf"/>
123 <pubDate>Fri, 21 Oct 2022 01:07:45 +0000</pubDate>
124 <dc:creator>Xiaojie Guo</dc:creator>
125 <dc:creator>Kang Yang</dc:creator>
126 <dc:creator>Xiao Wang</dc:creator>
127 <dc:creator>Wenhao Zhang</dc:creator>
128 <dc:creator>Xiang Xie</dc:creator>
129 <dc:creator>Jiang Zhang</dc:creator>
130 <dc:creator>Zheli Liu</dc:creator>
131 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
132 </item>
133 <item>
134 <title>Sorting Attacks Resilient Authentication Protocol for CMOS Image Sensor Based PUF</title>
135 <link>https://eprint.iacr.org/2022/1402</link>
136 <description>Physically Unclonable Functions (PUFs) have emerged as a viable and cost-effective method for device authentication and key generation. Recently, CMOS image sensors have been exploited as PUF for hardware fingerprinting in mobile devices. As CMOS image sensors are readily available in modern devices such as smartphones, laptops etc., it eliminates the need for additional hardware for implementing a PUF structure. In ISIC2014, an authentication protocol has been proposed to generate PUF signatures using a CMOS image sensor by leveraging the fixed pattern noise (FPN) of certain pixel values. This makes the PUF candidate an interesting target for adversarial attacks. In this work, we testify that a simple sorting attack and a win-rate (WR) based sorting attack can be launched in this architecture to predict the PUF response for given a challenge. We also propose a modified authentication protocol as a countermeasure to make it resilient against simple sorting and WR sorting attacks. The proposed work reduces the accuracy of prediction due to simple sorting attack and WR sorting attack by approximately 14% compared to the existing approach.</description>
137 <guid isPermaLink="true">https://eprint.iacr.org/2022/1402</guid>
138 <category>Applications</category>
139 <enclosure url="https://eprint.iacr.org/2022/1402.pdf" length="0" type="application/pdf"/>
140 <pubDate>Sun, 16 Oct 2022 07:19:44 +0000</pubDate>
141 <dc:creator>Chandan Kumar</dc:creator>
142 <dc:creator>Mahendra Rathor</dc:creator>
143 <dc:creator>Urbi Chatterjee</dc:creator>
144 <dc:rights>https://creativecommons.org/publicdomain/zero/1.0/</dc:rights>
145 </item>
146 <item>
147 <title>Lower-Bounds for Secret-Sharing Schemes for k-Hypergraphs</title>
148 <link>https://eprint.iacr.org/2023/289</link>
149 <description>A secret-sharing scheme enables a dealer, holding a secret string, to distribute shares to parties such that only pre-defined authorized subsets of parties can reconstruct the secret. The collection of authorized sets is called an access structure. There is a huge gap between the best known upper-bounds on the share size of a secret-sharing scheme realizing an arbitrary access structure and the best known lower-bounds on the size of these shares. For an arbitrary $n$-party access structure, the best known upper-bound on the share size is $2^{O(n)}$. On the other hand, the best known lower-bound on the total share size is much smaller, i.e., $\Omega(n^2/\log (n))$ [Csirmaz, \emph{Studia Sci. Math. Hungar.}]. This lower-bound was proved more than 25 years ago and no major progress was made since.
150
151
152 In this paper, we study secret-sharing schemes for k-hypergraphs, i.e., for access structure where all minimal authorized sets are of size exactly $k$ (however, unauthorized sets can be larger). We consider the case where $k$ is small, i.e., constant or at most $\log (n)$. The trivial upper-bound for these access structures is $O(k\cdot \binom{n}{k})$ and this can be slightly improved. If there were efficient secret-sharing schemes for such $k$-hypergraphs (e.g., $2$-hypergraphs or $3$-hypergraphs), then we would be able to construct secret-sharing schemes for arbitrary access structure that are better than the best known schemes. Thus, understanding the share size required for $k$-hypergraphs is important. Prior to our work, the best known lower-bound for these access structures was $\Omega(n \log (n))$, which holds already for graphs (i.e., $2$-hypergraphs).
153
154 We improve this lower-bound, proving a lower-bound of $\Omega(n^{1-1/(k-1)}/k)$ for some explicit $k$-hypergraphs, where $3 \leq k \leq \log (n)$. For example, for $3$-hypergraphs we prove a lower-bound of $\Omega(n^{3/2})$. For $\log (n)$-hypergraphs, we prove a lower-bound of $\Omega(n^{2}/\log (n))$, i.e., we show that the lower-bound of Csirmaz holds already when all minimal authorized sets are of size $\log (n)$. Our proof is simple and shows that the lower-bound of Csirmaz holds for a simple variant of the access structure considered by Csirmaz.</description>
155 <guid isPermaLink="true">https://eprint.iacr.org/2023/289</guid>
156 <category>Cryptographic protocols</category>
157 <enclosure url="https://eprint.iacr.org/2023/289.pdf" length="0" type="application/pdf"/>
158 <pubDate>Sun, 26 Feb 2023 17:26:27 +0000</pubDate>
159 <dc:creator>Amos Beimel</dc:creator>
160 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
161 </item>
162 <item>
163 <title>Succinct Vector, Polynomial, and Functional Commitments from Lattices</title>
164 <link>https://eprint.iacr.org/2022/1515</link>
165 <description>Vector commitment schemes allow a user to commit to a vector of values $\mathbf{x} \in \{0,1\}^\ell$ and later, open up the commitment to a specific set of positions. Both the size of the commitment and the size of the opening should be succinct (i.e., polylogarithmic in the length $\ell$ of the vector). Vector commitments and their generalizations to polynomial commitments and functional commitments are key building blocks for many cryptographic protocols.
166
167 We introduce a new framework for constructing non-interactive lattice-based vector commitments and their generalizations. A simple instantiation of our framework yields a new vector commitment scheme from the standard short integer solution (SIS) assumption that supports private openings and large messages. We then show how to use our framework to obtain the first succinct functional commitment scheme that supports openings with respect to arbitrary bounded-depth Boolean circuits. In this scheme, a user commits to a vector $\mathbf{x} \in \{0,1\}^\ell$, and later on, open the commitment to any function $f(\mathbf{x})$. Both the commitment and the opening are non-interactive and succinct: namely, they have size $\textsf{poly}(\lambda, d, \log \ell)$, where $\lambda$ is the security parameter and $d$ is the depth of the Boolean circuit computing $f$. Previous constructions of functional commitments could only support constant-degree polynomials, or require a trusted online authority, or rely on non-falsifiable assumptions. The security of our functional commitment scheme is based on a new falsifiable family of "basis-augmented" SIS assumptions (BASIS) we introduce in this work.
168
169 We also show how to use our vector commitment framework to obtain (1) a polynomial commitment scheme where the user can commit to a polynomial $f \in \mathbb{Z}_q[x]$ and subsequently open the commitment to an evaluation $f(x) \in \mathbb{Z}_q$; and (2) an aggregatable vector (resp., functional) commitment where a user can take a set of openings to multiple indices (resp., function evaluations) and aggregate them into a single short opening. Both of these extensions rely on the same BASIS assumption we use to obtain our succinct functional commitment scheme.</description>
170 <guid isPermaLink="true">https://eprint.iacr.org/2022/1515</guid>
171 <category>Public-key cryptography</category>
172 <enclosure url="https://eprint.iacr.org/2022/1515.pdf" length="0" type="application/pdf"/>
173 <pubDate>Wed, 02 Nov 2022 23:13:36 +0000</pubDate>
174 <dc:creator>Hoeteck Wee</dc:creator>
175 <dc:creator>David J. Wu</dc:creator>
176 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
177 </item>
178 <item>
179 <title>A Vulnerability in Implementations of SHA-3, SHAKE, EdDSA, and Other NIST-Approved Algorithm</title>
180 <link>https://eprint.iacr.org/2023/331</link>
181 <description>This paper describes a vulnerability in several implementations of the Secure Hash Algorithm 3 (SHA-3) that have been released by its designers. The vulnerability has been present since the final-round update of Keccak was submitted to the National Institute of Standards and Technology (NIST) SHA-3 hash function competition in January 2011, and is present in the eXtended Keccak Code Package (XKCP) of the Keccak team. It affects all software projects that have integrated this code, such as the scripting languages Python and PHP Hypertext Preprocessor (PHP). The vulnerability is a buffer overflow that allows attacker-controlled values to be eXclusive-ORed (XORed) into memory (without any restrictions on values to be XORed and even far beyond the location of the original buffer), thereby making many standard protection measures against buffer overflows (e.g., canary values) completely ineffective. First, we provide Python and PHP scripts that cause segmentation faults when vulnerable versions of the interpreters are used. Then, we show how this vulnerability can be used to construct second preimages and preimages for the implementation, and we provide a specially constructed file that, when hashed, allows the attacker to execute arbitrary code on the victim's device. The vulnerability applies to all hash value sizes, and all 64-bit Windows, Linux, and macOS operating systems, and may also impact cryptographic algorithms that require SHA-3 or its variants, such as the Edwards-curve Digital Signature Algorithm (EdDSA) when the Edwards448 curve is used. We introduce the Init-Update-Final Test (IUFT) to detect this vulnerability in implementations.</description>
182 <guid isPermaLink="true">https://eprint.iacr.org/2023/331</guid>
183 <category>Implementation</category>
184 <enclosure url="https://eprint.iacr.org/2023/331.pdf" length="0" type="application/pdf"/>
185 <pubDate>Mon, 06 Mar 2023 21:16:01 +0000</pubDate>
186 <dc:creator>Nicky Mouha</dc:creator>
187 <dc:creator>Christopher Celi</dc:creator>
188 <dc:rights>https://creativecommons.org/publicdomain/zero/1.0/</dc:rights>
189 </item>
190 <item>
191 <title>Extendable Threshold Ring Signatures with Enhanced Anonymity</title>
192 <link>https://eprint.iacr.org/2022/1568</link>
193 <description>Threshold ring signatures are digital signatures that allow $t$ parties to sign a message while hiding their identity in a larger set of $n$ users called ''ring''.
194 Recently, Aranha et al. [PKC 2022] introduced the notion of \emph{extendable} threshold ring signatures (ETRS).
195 ETRS allow one to update, in a non-interactive manner, a threshold ring signature on a certain message so that the updated signature has a greater threshold, and/or an augmented set of potential signers.
196 An application of this primitive is anonymous count me in.
197 A first signer creates a ring signature with a sufficiently large ring announcing a proposition in the signed message. After such cause becomes \emph{public}, other parties can anonymously decide to support that proposal by producing an updated signature. Crucially, such applications rely on partial signatures being posted on a \emph{publicly accessible} bulletin board since users may not know/trust each other.
198
199 In this paper, we first point out that even if anonymous count me in was suggested as an application of ETRS, the anonymity notion proposed in the previous work is insufficient in many application scenarios. Indeed, the existing notion guarantees anonymity only against adversaries who just see the last signature, and are not allowed to access the ''full evolution" of an ETRS. This is in stark contrast with applications where partial signatures are posted in a public bulletin board.
200 We therefore propose stronger anonymity definitions and construct a new ETRS that satisfies such definitions. Interestingly, while satisfying stronger anonymity properties, our ETRS asymptotically improves on the two ETRS presented in prior work [PKC 2022] in terms of both time complexity and signature size.
201 Our ETRS relies on extendable non-interactive witness-indistinguishable proof of knowledge (ENIWI PoK), a novel technical tool that we formalize and construct, and that may be of independent interest. We build our constructions from pairing groups under the SXDH assumption.</description>
202 <guid isPermaLink="true">https://eprint.iacr.org/2022/1568</guid>
203 <category>Cryptographic protocols</category>
204 <enclosure url="https://eprint.iacr.org/2022/1568.pdf" length="0" type="application/pdf"/>
205 <pubDate>Thu, 10 Nov 2022 17:39:00 +0000</pubDate>
206 <dc:creator>Gennaro Avitabile</dc:creator>
207 <dc:creator>Vincenzo Botta</dc:creator>
208 <dc:creator>Dario Fiore</dc:creator>
209 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
210 </item>
211 <item>
212 <title>Perfect MPC over Layered Graphs</title>
213 <link>https://eprint.iacr.org/2023/330</link>
214 <description>The classical "BGW protocol" (Ben-Or, Goldwasser and Wigderson, STOC 1988) shows that secure multiparty computation (MPC) among $n$ parties can be realized with perfect full security if $t < n/3$ parties are corrupted. This holds against malicious adversaries in the "standard" model for MPC, where a fixed set of $n$ parties is involved in the full execution of the protocol.
215 However, the picture is less clear in the mobile adversary setting of Ostrovsky and Yung (PODC 1991), where the adversary may periodically "move" by uncorrupting parties and corrupting a new set of $t$ parties. In this setting, it is unclear if full security can be achieved against an adversary that is maximally mobile, i.e., moves after every round. The question is further motivated by
216 the "You Only Speak Once" (YOSO) setting of Gentry et al. (Crypto 2021), where not only the adversary is mobile but also each round is executed by a disjoint set of parties. Previous positive results in this model do not achieve perfect security, and either assume probabilistic corruption and a nonstandard communication model, or only realize the weaker goal of security-with-abort. The question of matching the BGW result in these settings remained open.
217
218 In this work, we tackle the above two challenges simultaneously. We consider a layered MPC model, a simplified variant of the fluid MPC model of Choudhuri et al. (Crypto 2021). Layered MPC is an instance of standard MPC where the interaction pattern is defined by a layered graph of width $n$, allowing each party to send secret messages and broadcast messages only to parties in the next layer. We require perfect security against a malicious adversary who may corrupt at most $t$ parties in each layer.
219 Our main result is a perfect, fully secure layered MPC protocol with an optimal corruption threshold of $t < n/3$, thus extending the BGW feasibility result to the layered setting. This implies perfectly secure MPC protocols against a maximally mobile adversary.</description>
220 <guid isPermaLink="true">https://eprint.iacr.org/2023/330</guid>
221 <category>Cryptographic protocols</category>
222 <enclosure url="https://eprint.iacr.org/2023/330.pdf" length="0" type="application/pdf"/>
223 <pubDate>Mon, 06 Mar 2023 17:18:55 +0000</pubDate>
224 <dc:creator>Bernardo David</dc:creator>
225 <dc:creator>Anders Konring</dc:creator>
226 <dc:creator>Yuval Ishai</dc:creator>
227 <dc:creator>Eyal Kushilevitz</dc:creator>
228 <dc:creator>Varun Narayanan</dc:creator>
229 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
230 </item>
231 <item>
232 <title>Caveat Implementor! Key Recovery Attacks on MEGA</title>
233 <link>https://eprint.iacr.org/2023/329</link>
234 <description>MEGA is a large-scale cloud storage and communication platform that aims to provide end-to-end encryption for stored data. A recent analysis by Backendal, Haller and Paterson (IEEE S&P 2023) invalidated these security claims by presenting practical attacks against MEGA that could be mounted by the MEGA service provider. In response, the MEGA developers added lightweight sanity checks on the user RSA private keys used in MEGA, sufficient to prevent the previous attacks.
235
236 We analyse these new sanity checks and show how they themselves can be exploited to mount novel attacks on MEGA that recover a target user's RSA private key with only slightly higher attack complexity than the original attacks. We identify the presence of an ECB encryption oracle under a target user's master key in the MEGA system; this oracle provides our adversary with the ability to partially overwrite a target user's RSA private key with chosen data, a powerful capability that we use in our attacks. We then present two distinct types of attack, each type exploiting different error conditions arising in the sanity checks and in subsequent cryptographic processing during MEGA's user authentication procedure. The first type appears to be novel and exploits the manner in which the MEGA code handles modular inversion when recomputing $u = q^{-1} \bmod p$. The second can be viewed as a small subgroup attack (van Oorschot and Wiener, EUROCRYPT 1996, Lim and Lee, CRYPTO 1998). We prototype the attacks and show that they work in practice.
237
238 As a side contribution, we show how to improve the RSA key recovery attack of Backendal-Haller-Paterson against the unpatched version of MEGA to require only 2 logins instead of the original 512.
239
240 We conclude by discussing wider lessons about secure implementation of cryptography that our work surfaces.</description>
241 <guid isPermaLink="true">https://eprint.iacr.org/2023/329</guid>
242 <category>Attacks and cryptanalysis</category>
243 <enclosure url="https://eprint.iacr.org/2023/329.pdf" length="0" type="application/pdf"/>
244 <pubDate>Mon, 06 Mar 2023 17:00:03 +0000</pubDate>
245 <dc:creator>Martin R. Albrecht</dc:creator>
246 <dc:creator>Miro Haller</dc:creator>
247 <dc:creator>Lenka Mareková</dc:creator>
248 <dc:creator>Kenneth G. Paterson</dc:creator>
249 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
250 </item>
251 <item>
252 <title>Poseidon2: A Faster Version of the Poseidon Hash Function</title>
253 <link>https://eprint.iacr.org/2023/323</link>
254 <description>Zero-knowledge proof systems for computational integrity have seen a rise in popularity in the last couple of years. One of the results of this development is the ongoing effort in designing so-called arithmetization-friendly hash functions in order to make these proofs more efficient. One of these new hash functions, Poseidon, is extensively used in this context, also thanks to being one of the first constructions tailored towards this use case. Many of the design principles of Poseidon have proven to be efficient and were later used in other primitives, yet parts of the construction have shown to be expensive in real-word scenarios.
255
256 In this paper, we propose an optimized version of Poseidon, called Poseidon2. The two versions differ in two crucial points. First, Poseidon is a sponge hash function, while Poseidon2 can be either a sponge or a compression function depending on the use case. Secondly, Poseidon2 is instantiated by new and more efficient linear layers with respect to Poseidon. These changes allow to decrease the number of multiplications in the linear layer by up to 90% and the number of constraints in Plonk circuits by up to 70%. This makes Poseidon2 the currently fastest arithmetization-oriented hash function without lookups.
257
258 Besides that, we address a recently proposed algebraic attack and propose a simple modification that makes both Poseidon and Poseidon2 secure against this approach.</description>
259 <guid isPermaLink="true">https://eprint.iacr.org/2023/323</guid>
260 <category>Cryptographic protocols</category>
261 <enclosure url="https://eprint.iacr.org/2023/323.pdf" length="0" type="application/pdf"/>
262 <pubDate>Sat, 04 Mar 2023 13:00:41 +0000</pubDate>
263 <dc:creator>Lorenzo Grassi</dc:creator>
264 <dc:creator>Dmitry Khovratovich</dc:creator>
265 <dc:creator>Markus Schofnegger</dc:creator>
266 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
267 </item>
268 <item>
269 <title>The state diagram of $\chi$</title>
270 <link>https://eprint.iacr.org/2023/328</link>
271 <description>In symmetric cryptography, block ciphers, stream ciphers and permutations often make use of a round function and many round functions consist of a linear and a non-linear layer.
272 One that is often used is based on the cellular automaton that is denoted by $\chi$ as a Boolean map on bi-infinite sequences, $\mathbb{F}^{\mathbb{Z}}$.
273 It is defined by $\sigma \mapsto \nu$ where each $\nu_i = \sigma_i + (\sigma_{i+1}+1)\sigma_{i+2}$.
274 A map $\chi_n$ is a map that operatos on $n$-bit arrays with periodic boundary conditions.
275 This corresponds with $\chi$ restricted to periodic infinite sequences with period that divides $n$.
276 This map $\chi_n$ is used in various permutations, e.g., Keccak-f (the permutation in SHA-3), ASCON (the NIST standard for lightweight cryptography), Xoodoo, Rasta and Subterranean (2.0).
277
278 In this paper, we characterize the graph of $\chi$ on periodic sequences.
279 It turns out that $\chi$ is surjective on the set of \emph{all} periodic sequences.
280
281 We will show what sequences will give collisions after one application of $\chi$.
282 We prove that, for odd $n$, the order of $\chi_n$ (in the group of bijective maps on $\mathbb{F}^n$) is $2^{\lceil \operatorname{lg}(\frac{n+1}2)\rceil}$.
283
284 A given periodic sequence lies on a cycle in the graph of $\chi$, or it can be represented as a polynomial.
285 By regarding the divisors of such a polynomial one can see whether it lies in a cycle, or after how many iterations of $\chi$ it will.
286
287 Furthermore, we can see, for a given $\sigma$, the length of the cycle in its component in the state diagram.
288 Finally, we extend the surjectivity of $\chi$ to $\mathbb{F}^{\mathbb{Z}}$, thus to include non-periodic sequences.</description>
289 <guid isPermaLink="true">https://eprint.iacr.org/2023/328</guid>
290 <category>Secret-key cryptography</category>
291 <enclosure url="https://eprint.iacr.org/2023/328.pdf" length="0" type="application/pdf"/>
292 <pubDate>Mon, 06 Mar 2023 13:03:11 +0000</pubDate>
293 <dc:creator>Jan Schoone</dc:creator>
294 <dc:creator>Joan Daemen</dc:creator>
295 <dc:rights>https://creativecommons.org/licenses/by-sa/4.0/</dc:rights>
296 </item>
297 <item>
298 <title>New Quantum Search Model on Symmetric Ciphers and Its Applications</title>
299 <link>https://eprint.iacr.org/2023/327</link>
300 <description>It has been a long-standing viewpoint that doubling the length of key seeds in symmetric cipher can resist the quantum search attacks. This paper establishes a quantum key search model to deal with the post-quantum security of symmetric ciphers. The quantum search is performed in the punctured keystream/ciphertext space instead of the key space. On inputting the punctured keystreams/ciphertexts, we rule out the fake keys and find out the real key via the iterative use of the quantum singular value search algorithm.
301 We find out several parameters, such as the length and min-entropy of the punctured keystream, the iterations, and the error in the search algorithm, and all of them can influence the resulting complexity. When these parameters are chosen properly, a better complexity can be obtained than Grover algorithm. Our search model can apply to any typical symmetric cipher. To demonstrate the power, we apply our model to analyze block cipher AES family, stream ciphers Grain-128 and ZUC-128. The resulting complexity of AES-128 is $\tilde{\mathcal O}(2^{30.8})$, $\tilde{\mathcal O}(2^{32.0})$ of AES-192, $\tilde{\mathcal O}(2^{32.7})$ of AES-256, $\tilde{\mathcal O}(2^{27.5})$ of Grain-128, and $\tilde{\mathcal O}(2^{39.8})$ of ZUC-128.
302
303 Our results show that increasing the length of key seeds is not an effective way anymore to resist the quantum search attacks, and it is necessary to propose new measures to ensure the post-quantum security of symmetric ciphers.</description>
304 <guid isPermaLink="true">https://eprint.iacr.org/2023/327</guid>
305 <category>Attacks and cryptanalysis</category>
306 <enclosure url="https://eprint.iacr.org/2023/327.pdf" length="0" type="application/pdf"/>
307 <pubDate>Mon, 06 Mar 2023 12:44:07 +0000</pubDate>
308 <dc:creator>Yangru Zheng</dc:creator>
309 <dc:creator>Juntao Gao</dc:creator>
310 <dc:creator>Baocang Wang</dc:creator>
311 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
312 </item>
313 <item>
314 <title>Dory: Asynchronous BFT with Reduced Communication and Improved Efficiency</title>
315 <link>https://eprint.iacr.org/2022/1709</link>
316 <description>Asynchronous Byzantine fault-tolerant (BFT) protocols have received increasing attention, as they are particularly robust against timing and performance attacks. This paper designs and implements Dory, an asynchronous BFT protocol with reduced communication and improved efficiency compared to existing systems. In particular, Dory reduces communication both asymptotically and concretely and gains improved performance. To achieve this goal, we have devised a novel primitive called asynchronous vector data dissemination, and moreover, we have developed the technique of supplemental consensus originally working with reliable broadcast only, such that the technique can be compatible with the more efficient provable broadcast. We also built Dory-NG by separating data transmission from agreement, just as in Dumbo-NG.
317
318 We have implemented Dory, Dory-NG, Speeding Dumbo (sDumbo), and Dumbo-NG in a new Golang library. Via a deployment using up to 151 replicas on Amazon EC2, we have shown that Dory and Dory-NG consistently outperform sDumbo and Dumbo-NG, respectively---during both failure and failure-free scenarios. For instance, Dory has up to 5x the throughput of sDumbo, while lowering the communication cost for different batch sizes.</description>
319 <guid isPermaLink="true">https://eprint.iacr.org/2022/1709</guid>
320 <category>Cryptographic protocols</category>
321 <enclosure url="https://eprint.iacr.org/2022/1709.pdf" length="0" type="application/pdf"/>
322 <pubDate>Fri, 09 Dec 2022 13:42:50 +0000</pubDate>
323 <dc:creator>You Zhou</dc:creator>
324 <dc:creator>Zongyang Zhang</dc:creator>
325 <dc:creator>Haibin Zhang</dc:creator>
326 <dc:creator>Sisi Duan</dc:creator>
327 <dc:creator>Bin Hu</dc:creator>
328 <dc:creator>Licheng Wang</dc:creator>
329 <dc:creator>Jianwei Liu</dc:creator>
330 <dc:rights>https://creativecommons.org/licenses/by-nc/4.0/</dc:rights>
331 </item>
332 <item>
333 <title>A weakness in OCB3 used with short nonces allowing for a break of authenticity and confidentiality</title>
334 <link>https://eprint.iacr.org/2023/326</link>
335 <description>OCB3 is a mature and provably secure authenticated encryption mode of operation which allows for associated data (AEAD).
336 This note reports a small flaw in the security proof of OCB3 that may cause a loss of security in practice, even if OCB3 is correctly implemented in a trustworthy and nonce-respecting module.
337 The flaw is present when OCB3 is used with short nonces. It has security implications that are worse than nonce-repetition as confidentiality and authenticity are lost until the key is changed. The flaw is due to an implicit condition in the security proof and to the way OCB3 processes nonce. Different ways to fix the mode are presented.</description>
338 <guid isPermaLink="true">https://eprint.iacr.org/2023/326</guid>
339 <category>Attacks and cryptanalysis</category>
340 <enclosure url="https://eprint.iacr.org/2023/326.pdf" length="0" type="application/pdf"/>
341 <pubDate>Mon, 06 Mar 2023 09:42:33 +0000</pubDate>
342 <dc:creator>Jean Liénardy</dc:creator>
343 <dc:creator>Frédéric Lafitte</dc:creator>
344 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
345 </item>
346 <item>
347 <title>HOLMES: Efficient Distribution Testing for Secure Collaborative Learning</title>
348 <link>https://eprint.iacr.org/2021/1517</link>
349 <description>Using secure multiparty computation (MPC), organizations which own sensitive data (e.g., in healthcare, finance or law enforcement) can train machine learning models over their joint dataset without revealing their data to each other. At the same time, secure computation restricts operations on the joint dataset, which impedes computation to assess its quality. Without such an assessment, deploying a jointly trained model is potentially illegal. Regulations, such as the European Union's General Data Protection Regulation (GDPR), require organizations to be legally responsible for the errors, bias, or discrimination caused by their machine learning models. Hence, testing data quality emerges as an indispensable step in secure collaborative learning. However, performing distribution testing is prohibitively expensive using current techniques, as shown in our experiments.
350
351 We present HOLMES, a protocol for performing distribution testing efficiently. In our experiments, compared with three non-trivial baselines, HOLMES achieves a speedup of more than 10x for classical distribution tests and up to 10^4x for multidimensional tests. The core of HOLMES is a hybrid protocol that integrates MPC with zero-knowledge proofs and a new ZK-friendly and naturally oblivious sketching algorithm for multidimensional tests, both with significantly lower computational complexity and concrete execution costs.</description>
352 <guid isPermaLink="true">https://eprint.iacr.org/2021/1517</guid>
353 <category>Applications</category>
354 <enclosure url="https://eprint.iacr.org/2021/1517.pdf" length="0" type="application/pdf"/>
355 <pubDate>Sat, 20 Nov 2021 22:57:01 +0000</pubDate>
356 <dc:creator>Ian Chang</dc:creator>
357 <dc:creator>Katerina Sotiraki</dc:creator>
358 <dc:creator>Weikeng Chen</dc:creator>
359 <dc:creator>Murat Kantarcioglu</dc:creator>
360 <dc:creator>Raluca Ada Popa</dc:creator>
361 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
362 </item>
363 <item>
364 <title>Revocable Cryptography from Learning with Errors</title>
365 <link>https://eprint.iacr.org/2023/325</link>
366 <description>Quantum cryptography leverages many unique features of quantum information in order to construct cryptographic primitives that are oftentimes impossible classically. In this work, we build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
367
368 We define and construct several fundamental cryptographic primitives with key-revocation capabilities, namely pseudorandom functions, secret-key and public-key encryption, and even fully homomorphic encryption, assuming the quantum subexponential hardness of the learning with errors problem. Central to all our constructions is our approach for making the Dual-Regev encryption scheme (Gentry, Peikert and Vaikuntanathan, STOC 2008) revocable.</description>
369 <guid isPermaLink="true">https://eprint.iacr.org/2023/325</guid>
370 <category>Public-key cryptography</category>
371 <enclosure url="https://eprint.iacr.org/2023/325.pdf" length="0" type="application/pdf"/>
372 <pubDate>Mon, 06 Mar 2023 06:16:44 +0000</pubDate>
373 <dc:creator>Prabhanjan Ananth</dc:creator>
374 <dc:creator>Alexander Poremba</dc:creator>
375 <dc:creator>Vinod Vaikuntanathan</dc:creator>
376 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
377 </item>
378 <item>
379 <title>BlindHub: Bitcoin-Compatible Privacy-Preserving Payment Channel Hubs Supporting Variable Amounts</title>
380 <link>https://eprint.iacr.org/2022/1735</link>
381 <description>Payment Channel Hub (PCH) is a promising solution to the scalability issue of first-generation blockchains or cryptocurrencies such as Bitcoin. It supports off-chain payments between a sender and a receiver through an intermediary (called the tumbler). Relationship anonymity and value privacy are desirable features of privacy-preserving PCHs, which prevent the tumbler from identifying the sender and receiver pairs as well as the payment amounts. To our knowledge, all existing Bitcoin-compatible PCH constructions that guarantee relationship anonymity allow only a (predefined) fixed payment amount. Thus, to achieve payments with different amounts, they would require either multiple PCH systems or running one PCH system multiple times. Neither of these solutions would be deemed practical.
382
383 In this paper, we propose the first Bitcoin-compatible PCH that achieves relationship anonymity and supports variable amounts for payment. To achieve this, we have several layers of technical constructions, each of which could be of independent interest to the community. First, we propose $\textit{BlindChannel}$, a novel bi-directional payment channel protocol for privacy-preserving payments, where {one of the channel parties} is unable to see the channel balances. Then, we further propose $\textit{BlindHub}$, a three-party (sender, tumbler, receiver) protocol for private conditional payments, where the tumbler pays to the receiver only if the sender pays to the tumbler. The appealing additional feature of BlindHub is that the tumbler cannot link the sender and the receiver while supporting a variable payment amount. To construct BlindHub, we also introduce two new cryptographic primitives as building blocks, namely $\textit{Blind Adaptor Signature}$(BAS), and $\textit{Flexible Blind Conditional Signature}$. BAS is an adaptor signature protocol built on top of a blind signature scheme. Flexible Blind Conditional Signature is a new cryptographic notion enabling us to provide an atomic and privacy-preserving PCH. Lastly, we instantiate both BlindChannel and BlindHub protocols and present implementation results to show their practicality.</description>
384 <guid isPermaLink="true">https://eprint.iacr.org/2022/1735</guid>
385 <category>Applications</category>
386 <enclosure url="https://eprint.iacr.org/2022/1735.pdf" length="0" type="application/pdf"/>
387 <pubDate>Sat, 17 Dec 2022 01:52:24 +0000</pubDate>
388 <dc:creator>Xianrui Qin</dc:creator>
389 <dc:creator>Shimin Pan</dc:creator>
390 <dc:creator>Arash Mirzaei</dc:creator>
391 <dc:creator>Zhimei Sui</dc:creator>
392 <dc:creator>Oğuzhan Ersoy</dc:creator>
393 <dc:creator>Amin Sakzad</dc:creator>
394 <dc:creator>Muhammed F. Esgin</dc:creator>
395 <dc:creator>Joseph K. Liu</dc:creator>
396 <dc:creator>Jiangshan Yu</dc:creator>
397 <dc:creator>Tsz Hon Yuen</dc:creator>
398 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
399 </item>
400 <item>
401 <title>Mathematical Aspects of Division Property</title>
402 <link>https://eprint.iacr.org/2022/736</link>
403 <description>This work surveys mathematical aspects of division property, which is a state of the art technique in cryptanalysis of symmetric-key algorithms, such as authenticated encryption, block ciphers and stream ciphers. It aims to find integral distinguishers and cube attacks, which exploit weakness in the algebraic normal forms of the output coordinates of the involved vectorial Boolean functions. Division property can also be used to provide arguments for security of primitives against these attacks.
404
405 The focus of this work is a formal presentation of the theory behind the division property, including rigorous proofs, which were often omitted in the existing literature. This survey covers the two major variants of division property, namely conventional and perfect division property. In addition, we explore relationships of the technique with classic degree bounds.</description>
406 <guid isPermaLink="true">https://eprint.iacr.org/2022/736</guid>
407 <category>Secret-key cryptography</category>
408 <enclosure url="https://eprint.iacr.org/2022/736.pdf" length="0" type="application/pdf"/>
409 <pubDate>Thu, 09 Jun 2022 06:50:58 +0000</pubDate>
410 <dc:creator>Phil Hebborn</dc:creator>
411 <dc:creator>Gregor Leander</dc:creator>
412 <dc:creator>Aleksei Udovenko</dc:creator>
413 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
414 </item>
415 <item>
416 <title>Soteria: Preserving Privacy in Distributed Machine Learning</title>
417 <link>https://eprint.iacr.org/2021/966</link>
418 <description>We propose SOTERIA, a system for distributed privacy-preserving Machine Learning (ML) that leverages Trusted Execution Environments (e.g. Intel SGX) to run code in isolated containers (enclaves). Unlike previous work, where all ML-related computation is performed at trusted enclaves, we introduce a hybrid scheme, combining computation done inside and outside these enclaves. The conducted experimental evaluation validates that our approach reduces the runtime of ML algorithms by up to 41%, when compared to previous related work. Our protocol is accompanied by a security proof, as well as a discussion regarding resilience against a wide spectrum of ML attacks.</description>
419 <guid isPermaLink="true">https://eprint.iacr.org/2021/966</guid>
420 <enclosure url="https://eprint.iacr.org/2021/966.pdf" length="0" type="application/pdf"/>
421 <pubDate>Thu, 22 Jul 2021 09:14:36 +0000</pubDate>
422 <dc:creator>Cláudia Brito</dc:creator>
423 <dc:creator>Pedro Ferreira</dc:creator>
424 <dc:creator>Bernardo Portela</dc:creator>
425 <dc:creator>Rui Oliveira</dc:creator>
426 <dc:creator>João Paulo</dc:creator>
427 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
428 </item>
429 <item>
430 <title>LATKE: An identity-binding PAKE from lattice assumptions</title>
431 <link>https://eprint.iacr.org/2023/324</link>
432 <description>In a recent work, Cremers, Naor, Paz, and Ronen (CRYPTO '22) point out the problem of catastrophic impersonation in balanced password authenticated key exchange protocols (PAKEs). Namely, in a balanced PAKE, when a single party is compromised, the attacker learns the password and can subsequently impersonate anyone to anyone using the same password. The authors of the work present two solutions to this issue: CHIP, an identity-binding PAKE (iPAKE), and CRISP, a strong identity-binding PAKE (siPAKE). These constructions prevent the impersonation attack by generating a secret key on setup that is inextricably tied to the party's identity, and then deleting the password. Thus, upon compromise, all an attacker can immediately do is impersonate the victim. The strong variant goes further, preventing attackers from performing any precomputation before the compromise occurs.
433
434 In this work we present LATKE, an iPAKE from lattice assumptions in the random oracle model. In order to achieve security and correctness, we must make changes to CHIP's primitives, security models, and protocol structure.</description>
435 <guid isPermaLink="true">https://eprint.iacr.org/2023/324</guid>
436 <category>Cryptographic protocols</category>
437 <enclosure url="https://eprint.iacr.org/2023/324.pdf" length="0" type="application/pdf"/>
438 <pubDate>Sun, 05 Mar 2023 07:21:22 +0000</pubDate>
439 <dc:creator>Michael Rosenberg</dc:creator>
440 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
441 </item>
442 <item>
443 <title>Multilinear Schwartz-Zippel mod N with Applications to Succinct Arguments</title>
444 <link>https://eprint.iacr.org/2022/458</link>
445 <description>We show that for $\mathbf{x}\leftarrow [0,2^\lambda)^\mu$ and any integer $N$ the probability that $f(\mathbf{x})\equiv 0 \bmod N$ for any non-zero multilinear polynomial $f\in \mathbb{Z}[X_1, \dots,X_\mu]$, co-prime to $N$ is inversely proportional to $N$. As a corollary we show that if $\log_2 N\geq \log_2(2\mu)\lambda+8\mu^2 $ then the probability is bounded by $\frac{\mu+1}{2^\lambda}$. We also give tighter numerically derived bounds, showing that if $\log_2 N\geq {418}$, and $\mu\leq 20$ the probability is bounded by $\frac{\mu}{2^\lambda}+2^{-120}$.
446 We then apply this Multilinear Composite Schwartz-Zippel Lemma (LCSZ) to show that the classical Bulletproofs succinct argument of knowledge for a Pedersen commitment opening generalizes to commitment schemes binding only over short integer vectors, which includes commitments both from lattice hardness assumptions (SIS/R-SIS/M-SIS) and groups of unknown order (GUOs), in which case the verification time also becomes logarithmic.
447 Along the way we define the notion of Almost Special Soundness, a generalization of Special-Soundness which still implies knowledge soundness.
448 This unified treatment subsumes prior work in GUO-based SNARKs (DARK Eurocrypt 2020) and lattice-based Bulletproofs (Crypto 2020). Our analysis closes a critical gap in the original security proof of DARK. Prior analysis of lattice-based Bulletproofs showed knowledge soundness with polynomial-size challenge sets and thus had a non-negligible knowledge error that necessitated parallel repetition. Our analysis shows knowledge soundness for the original Bulletproofs protocol over an exponential-size challenge set and achieves a negligible soundness error without repetition. This circumvents a previous impossibility result.</description>
449 <guid isPermaLink="true">https://eprint.iacr.org/2022/458</guid>
450 <category>Cryptographic protocols</category>
451 <enclosure url="https://eprint.iacr.org/2022/458.pdf" length="0" type="application/pdf"/>
452 <pubDate>Tue, 12 Apr 2022 07:51:13 +0000</pubDate>
453 <dc:creator>Benedikt Bünz</dc:creator>
454 <dc:creator>Ben Fisch</dc:creator>
455 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
456 </item>
457 <item>
458 <title>Breaking RSA Generically is Equivalent to Factoring, with Preprocessing</title>
459 <link>https://eprint.iacr.org/2022/1261</link>
460 <description>We investigate the relationship between the classical RSA and factoring problems when preprocessing is considered. In such a model, adversaries can use an unbounded amount of precomputation to produce an “advice” string to then use during the online phase, when a problem instance becomes known. Previous work (e.g., [Bernstein, Lange ASI- ACRYPT ’13]) has shown that preprocessing attacks significantly im- prove the runtime of the best-known factoring algorithms. Due to these improvements, we ask whether the relationship between factoring and RSA fundamentally changes when preprocessing is allowed. Specifically, we investigate whether there is a superpolynomial gap between the run- time of the best attack on RSA with preprocessing and on factoring with preprocessing.
461
462 Our main result rules this out with respect to algorithms in a careful adaptation of the generic ring model [Aggarwal and Maurer, Eurocrypt 2009] to the preprocessing setting. In particular, in this setting we show the existence of a factoring algorithm with polynomially related parameters, for any setting of RSA parameters.</description>
463 <guid isPermaLink="true">https://eprint.iacr.org/2022/1261</guid>
464 <category>Foundations</category>
465 <enclosure url="https://eprint.iacr.org/2022/1261.pdf" length="0" type="application/pdf"/>
466 <pubDate>Fri, 23 Sep 2022 00:15:35 +0000</pubDate>
467 <dc:creator>Dana Dachman-Soled</dc:creator>
468 <dc:creator>Julian Loss</dc:creator>
469 <dc:creator>Adam O'Neill</dc:creator>
470 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
471 </item>
472 <item>
473 <title>Poseidon: A New Hash Function for Zero-Knowledge Proof Systems</title>
474 <link>https://eprint.iacr.org/2019/458</link>
475 <description>The area of practical computational integrity proof systems, like SNARKs, STARKs, Bulletproofs, is seeing a very dynamic development with several constructions having appeared recently with improved properties and relaxed setup requirements. Many use cases of such systems involve, often as their most expensive part, proving the knowledge of a preimage under a certain cryptographic hash function, which is expressed as a circuit over a large prime field. A notable example is a zero-knowledge proof of coin ownership in the Zcash cryptocurrency, where the inadequacy of the SHA-256 hash function for such a circuit caused a huge computational penalty.
476
477 In this paper, we present a modular framework and concrete instances of cryptographic hash functions which work natively with GF(p) objects. Our hash function Poseidon uses up to 8x fewer constraints per message bit than Pedersen Hash.
478
479 Our construction is not only expressed compactly as a circuit, but can also be tailored for various proof systems using specially crafted polynomials, thus bringing another boost in performance. We demonstrate this by implementing a 1-out-of-a-billion membership proof with Merkle trees in less than a second by using Bulletproofs.</description>
480 <guid isPermaLink="true">https://eprint.iacr.org/2019/458</guid>
481 <category>Cryptographic protocols</category>
482 <enclosure url="https://eprint.iacr.org/2019/458.pdf" length="0" type="application/pdf"/>
483 <pubDate>Fri, 10 May 2019 12:21:18 +0000</pubDate>
484 <dc:creator>Lorenzo Grassi</dc:creator>
485 <dc:creator>Dmitry Khovratovich</dc:creator>
486 <dc:creator>Christian Rechberger</dc:creator>
487 <dc:creator>Arnab Roy</dc:creator>
488 <dc:creator>Markus Schofnegger</dc:creator>
489 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
490 </item>
491 <item>
492 <title>SoK on Blockchain Evolution and a Taxonomy for Public Blockchain Generations</title>
493 <link>https://eprint.iacr.org/2023/315</link>
494 <description>Blockchain has been broadly recognized as a breakthrough technology of the world. Web3, recently, is emerging as a buzzword, indicating the next generation of Internet based on Blockchain, envisioning the Internet of Money to store and transfer value. However, when people want a comprehensive view throughout advancements in the Blockchain space, there is a missing in the academic domain and scientific publications regarding distributed ledger technology (DLT) classification and taxonomy for the evolution of public Blockchain generations. In this research, the author attempts to classify DLTs in terms of data structure (ledger type), governance and accessibility. Furthermore, based on the well-known problems and the most technical challenges in Blockchain space, the author studies breaking and significant inventions of various blockchain protocols to give a taxonomy for the evolution of four public Blockchain generations, blockchain layers (0, 1, 2, 3). The first and second generations are dominated by Bitcoin and Ethereum, respectively. The latest state-of-the-art blockchain protocols are developing and shaping the third and fourth generations, where several ``Ethereum-killer" candidates are trying to solve major problems, to offer fantastic functions and capacity, by their own outstanding innovations and distinguished architectural designs. This work helps readers quickly capture historical evolution and innovations of Blockchain, envisioning the next advancements of Web3 as well as the Internet of Value (Internet 2.0).</description>
495 <guid isPermaLink="true">https://eprint.iacr.org/2023/315</guid>
496 <category>Foundations</category>
497 <enclosure url="https://eprint.iacr.org/2023/315.pdf" length="0" type="application/pdf"/>
498 <pubDate>Fri, 03 Mar 2023 08:25:40 +0000</pubDate>
499 <dc:creator>Thuat Do</dc:creator>
500 <dc:rights>https://creativecommons.org/licenses/by-nc/4.0/</dc:rights>
501 </item>
502 <item>
503 <title>Differential Fault Attack on Rasta and $\text {FiLIP} _ {\text {DSM}}$</title>
504 <link>https://eprint.iacr.org/2023/322</link>
505 <description>In this paper we propose Differential Fault Attack (DFA) on two Fully Homomorphic Encryption (FHE) friendly stream ciphers Rasta and $\text {FiLIP} _ {\text {DSM}} $. Design criteria of Rasta rely on affine layers and nonlinear layers, whereas $\text {FiLIP} _ {\text {DSM}} $ relies on permutations and a nonlinear fil- ter function. Here we show that the secret key of these two ciphers can be recovered by injecting only 1 bit fault in the initial state. Our DFA on full round (# rounds = 6) Rasta with 219 block size requires only one block (i.e., 219 bits) of normal and faulty keystream bits. In the case of our DFA on FiLIP-430 (one instance of $\text {FiLIP} _ {\text {DSM}} $), we need 30000 normal and faulty keystream bits.</description>
506 <guid isPermaLink="true">https://eprint.iacr.org/2023/322</guid>
507 <category>Attacks and cryptanalysis</category>
508 <enclosure url="https://eprint.iacr.org/2023/322.pdf" length="0" type="application/pdf"/>
509 <pubDate>Sat, 04 Mar 2023 07:22:33 +0000</pubDate>
510 <dc:creator>R Radheshwar</dc:creator>
511 <dc:creator>Meenakshi Kansal</dc:creator>
512 <dc:creator>Pierrick Méaux</dc:creator>
513 <dc:creator>Dibyendu Roy</dc:creator>
514 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
515 </item>
516 <item>
517 <title>A Holistic Security Analysis of Monero Transactions</title>
518 <link>https://eprint.iacr.org/2023/321</link>
519 <description>Monero is a popular cryptocurrency with strong privacy guarantees for users' transactions. At the heart of Monero's privacy claims lies a complex transaction system called RingCT, which combines several building blocks such as linkable ring signatures, homomorphic commitments, and range proofs, in a unique fashion. In this work, we provide the first rigorous security analysis for RingCT (as given in Zero to Monero, v2.0.0, 2020) in its entirety. This is in contrast to prior works that provided security arguments for only parts of RingCT.
520
521 To this end, we provide the first holistic security model for Monero's RingCT. In our model, we then prove the security of RingCT. Our framework is modular in that it allows to view RingCT as a combination of various different sub-protocols. This has the benefit that these components can be easily updated in future versions of RingCT with only minor modifications to our analysis. At a technical level, we introduce several new techniques that we believe to be of independent interest. First, we need to make several subtle modifications to the syntax and security properties of existing building blocks (e.g., linkable ring signatures), which result from the unusual way in which they are combined within RingCT. Then, we show how these building blocks can be combined in order to argue security of the top level transaction scheme. As a technical highlight of our proof, we show that our security goals can be mapped to a suitable graph problem. This allows us to take advantage of ideas from the theory of network flows in our analysis.</description>
522 <guid isPermaLink="true">https://eprint.iacr.org/2023/321</guid>
523 <category>Cryptographic protocols</category>
524 <enclosure url="https://eprint.iacr.org/2023/321.pdf" length="0" type="application/pdf"/>
525 <pubDate>Sat, 04 Mar 2023 00:00:26 +0000</pubDate>
526 <dc:creator>Cas Cremers</dc:creator>
527 <dc:creator>Julian Loss</dc:creator>
528 <dc:creator>Benedikt Wagner</dc:creator>
529 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
530 </item>
531 <item>
532 <title>Anonymous Counting Tokens</title>
533 <link>https://eprint.iacr.org/2023/320</link>
534 <description>We introduce a new primitive called anonymous counting tokens (ACTs) which allows clients to obtain blind signatures or MACs (aka tokens) on messages of their choice, while at the same time enabling issuers to enforce rate limits on the number of tokens that a client can obtain for each message. Our constructions enforce that each client will be able to obtain only one token per message and we show a generic transformation to support other rate limiting as well. We achieve this new property while maintaining the unforgeability and unlinkability properties required for anonymous tokens schemes. We present four ACT constructions with various trade-offs for their efficiency and underlying security assumptions. One construction uses factorization-based primitives and a cyclic group. It is secure in the random oracle model under the q-DDHI assumption (in a cyclic group) and the DCR assumption. Our three other constructions use bilinear maps: one is secure in the standard model under q-DDHI and SXDH, one is secure in the random oracle model under SXDH, and the most efficient of the three is secure in the random oracle model and generic bilinear group model.</description>
535 <guid isPermaLink="true">https://eprint.iacr.org/2023/320</guid>
536 <category>Cryptographic protocols</category>
537 <enclosure url="https://eprint.iacr.org/2023/320.pdf" length="0" type="application/pdf"/>
538 <pubDate>Fri, 03 Mar 2023 22:38:15 +0000</pubDate>
539 <dc:creator>Fabrice Benhamouda</dc:creator>
540 <dc:creator>Mariana Raykova</dc:creator>
541 <dc:creator>Karn Seth</dc:creator>
542 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
543 </item>
544 <item>
545 <title>A Sharding-Based Approach for Enhancing Efficiency in ISSDOs for Sharing Scattered Values</title>
546 <link>https://eprint.iacr.org/2023/319</link>
547 <description>Data outsourcing is a solution aimed at addressing the security and reliability issues of data storage by ensuring professional handling of the data. The growing use of outsourcing is causing concern among users due to the lack of assurance regarding the security and reliability of data stored on servers. To address these issues, some attempts have been made to implement Secret Sharing-based Data Outsourcing (SSDO) schemes. The low efficiency of these schemes led researchers to use an index server (IS). However, IS are susceptible to frequency analysis. Bucket-Chain $B^+Tree$ ($BCB^+Tree$) was proposed to tackle the frequency analysis in the current Index Server Secret Sharing-based Data Outsourcing (ISSDO) schemes. Nevertheless, this scheme works very well when the data is discrete with a limited range. Otherwise, the scheme's efficiency declines significantly as it has to store one index in each bucket and the number of buckets rises significantly, rendering the use of an IS useless. In this paper, a new data structure is proposed to store the indexes in IS to mitigate this efficiency concern. Briefly, the domain of values is divided into several segments, and indexes of values in each segment are stored inside a $Shard$. Additionally, a data outsourcing scheme has been presented based on the proposed data structure. It can withstand collaboration from up to $k-1$ dishonest servers even if they have access to the IS.</description>
548 <guid isPermaLink="true">https://eprint.iacr.org/2023/319</guid>
549 <category>Applications</category>
550 <enclosure url="https://eprint.iacr.org/2023/319.pdf" length="0" type="application/pdf"/>
551 <pubDate>Fri, 03 Mar 2023 15:46:50 +0000</pubDate>
552 <dc:creator>Reza Ghasemi</dc:creator>
553 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
554 </item>
555 <item>
556 <title>Impossibility of Efficient Information-Theoretic Fuzzy Extraction</title>
557 <link>https://eprint.iacr.org/2023/172</link>
558 <description>Fuzzy extractors convert noisy signals from the physical world into reliable cryptographic keys. Fuzzy min-entropy is an important measure the ability of a fuzzy extractor to distill keys from a distribution: in particular, it bounds the length of the key that can be derived (Fuller, Reyzin, and Smith, IEEE Transactions on Information Theory 2020).
559 In general, fuzzy min-entropy that is superlogarithmic in the security parameter is required for a noisy distribution to be suitable for key derivation.
560
561 There is a wide gap between what is possible with respect to
562 computational and information-theoretic adversaries. Under the
563 assumption of general-purpose obfuscation, keys can be securely derived from all distributions with superlogarithmic entropy. Against information-theoretic adversaries, however, it is impossible to build a single fuzzy extractor that works for all distributions (Fuller, Reyzin, and Smith, IEEE Transactions on Information Theory 2020).
564
565 A weaker information-theoretic goal is to build a fuzzy extractor for each particular probability distribution. This is the approach taken by Woodage et al. (Crypto 2017). Prior approaches use the full description of the probability mass function and are inefficient. We show this is inherent: for a quarter of distributions with fuzzy min-entropy and $2^k$ points there is no secure fuzzy extractor that uses less $2^{\Theta(k)}$ bits of information about the distribution.} This result rules out the possibility of efficient, information-theoretic fuzzy extractors for many distributions with fuzzy min-entropy.
566
567 We show an analogous result with stronger parameters for information-theoretic secure sketches. Secure sketches are frequently used to construct fuzzy extractors.</description>
568 <guid isPermaLink="true">https://eprint.iacr.org/2023/172</guid>
569 <category>Foundations</category>
570 <enclosure url="https://eprint.iacr.org/2023/172.pdf" length="0" type="application/pdf"/>
571 <pubDate>Sat, 11 Feb 2023 18:09:12 +0000</pubDate>
572 <dc:creator>Luke Demarest</dc:creator>
573 <dc:creator>Benjamin Fuller</dc:creator>
574 <dc:creator>Alexander Russell</dc:creator>
575 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
576 </item>
577 <item>
578 <title>A Transformation for Lifting Discrete Logarithm Based Cryptography to Post-Quantum Cryptography</title>
579 <link>https://eprint.iacr.org/2023/318</link>
580 <description>We construct algebraic structures where rising to the non-associative power indices is no longer tied with the Discrete Logarithm Problem but with a problem that has been analysed in the last two decades and does not have a quantum polynomial algorithm that solves it. The problem is called Exponential Congruences Problem. By this, \emph{we disprove} the claims presented in the ePrint report 2021/583 titled "Entropoids: Groups in Disguise" by Lorenz Panny that \emph{"all instantiations of the entropoid framework should be breakable in polynomial time on a quantum computer."}
581
582 Additionally, we construct an Arithmetic for power indices and propose generic recipe guidelines that we call "Entropic-Lift" for transforming some of the existing classical cryptographic schemes that depend on the hardness of Discrete Logarithm Problem to post-quantum cryptographic schemes that will base their security on the hardness of the Exponential Congruences Problem.
583
584 As concrete examples, we show how to transform the classical Diffie-Hellman key exchange, DSA and Schnorr signature schemes.
585
586 We also post one open problem: From the perspective of provable security, specifically from the standpoint of security of post-quantum cryptographic schemes, to precisely formalize and analyze the potentials and limits of the Entropic-Lift transformation.</description>
587 <guid isPermaLink="true">https://eprint.iacr.org/2023/318</guid>
588 <category>Public-key cryptography</category>
589 <enclosure url="https://eprint.iacr.org/2023/318.pdf" length="0" type="application/pdf"/>
590 <pubDate>Fri, 03 Mar 2023 13:06:20 +0000</pubDate>
591 <dc:creator>Danilo Gligoroski</dc:creator>
592 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
593 </item>
594 <item>
595 <title>Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over $\mathbb F_p^n$</title>
596 <link>https://eprint.iacr.org/2021/1695</link>
597 <description>Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the number of multiplications over $\mathbb{F}_p$ for a large prime $p$ have been recently proposed in the literature. This goal is often achieved by instantiating the non-linear layer via power maps $x\mapsto x^d$.
598
599 In this paper, we start an analysis of new non-linear permutation functions over $\mathbb{F}_p^n$ that can be used as building blocks in such symmetric-key primitives. Given a local map $F:\mathbb{F}_p^m \rightarrow \mathbb{F}_p$, we limit ourselves to focus on S-Boxes over $\mathbb{F}_p^n$ for $n\ge m$ defined as $\mathcal{S}_F(x_0, x_1, \ldots, x_{n-1}) = y_0\| y_1\| \ldots \| y_{n-1}$ where $y_i := F(x_i, x_{i+1}, \ldots, x_{i+m-1} )$. As main results, we prove that
600 - given any quadratic function $F:\mathbb{F}_p^2 \rightarrow \mathbb{F}_p$, the corresponding S-Box $\mathcal{S}_F$ over $\mathbb{F}_p^n$ for $n\ge 3$ is never invertible;
601 - similarly, given any quadratic function $F:\mathbb{F}_p^3 \rightarrow \mathbb{F}_p$, the corresponding S-Box $\mathcal{S}_F$ over $\mathbb{F}_p^n$ for $n\ge 5$ is never invertible.
602 Moreover, for each $p\ge 3$, we present (1st) generalizations of the Lai-Massey construction over $\mathbb{F}_p^n$ defined as before via functions $F:\mathbb{F}_p^m \rightarrow \mathbb{F}_p$ for each $n=m\ge 2$ and (2nd) (non-trivial) quadratic functions $F:\mathbb{F}_p^3 \rightarrow \mathbb{F}_p$ such that $\mathcal{S}_F$ over $\mathbb{F}_p^n$ for $n\in \{3,4\}$ is invertible. As an open problem for future work, we conjecture that for each $m\ge 1$ there exists a \textit{finite} integer $n_{\text{max}}(m)$ such that $\mathcal{S}_F$ over $\mathbb{F}_p^n$ defined as before via a quadratic function $F:\mathbb{F}_p^m \rightarrow \mathbb{F}_p$ is \textit{not} invertible for each $n\ge n_{\text{max}}(m)$.
603
604 Finally, as a concrete application, we propose Neptune, a variant of the sponge hash function Poseidon, whose non-linear layer is designed by taking into account the results presented in this paper.
605 We show that this variant leads to a concrete multiplication reduction with respect to Poseidon.</description>
606 <guid isPermaLink="true">https://eprint.iacr.org/2021/1695</guid>
607 <category>Secret-key cryptography</category>
608 <enclosure url="https://eprint.iacr.org/2021/1695.pdf" length="0" type="application/pdf"/>
609 <pubDate>Thu, 30 Dec 2021 17:12:02 +0000</pubDate>
610 <dc:creator>Lorenzo Grassi</dc:creator>
611 <dc:creator>Silvia Onofri</dc:creator>
612 <dc:creator>Marco Pedicini</dc:creator>
613 <dc:creator>Luca Sozzi</dc:creator>
614 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
615 </item>
616 <item>
617 <title>The special case of cyclotomic fields in quantum algorithms for unit groups</title>
618 <link>https://eprint.iacr.org/2023/317</link>
619 <description>Unit group computations are a cryptographic primitive for which one has a fast quantum algorithm, but the required number of qubits is $\tilde{O}(m^5)$. In this work we propose a modification of the algorithm for which the number of qubits is $\tilde{O}(m^2)$ in the case of cyclotomic fields. Moreover, under a recent conjecture on the size of the class group of $\mathbb{Q}(\zeta_m+\zeta_m^{-1})$, the quantum algorithms is much simpler because it is a hidden subgroup problem (HSP) algorithm rather than its error estimation counterpart: continuous hidden subgroup problem (CHSP). We also discuss the (minor) speed-up obtained when exploiting Galois automorphisms thnaks to the Buchmann-Pohst algorithm over $\mathcal{O}_K$-lattices.</description>
620 <guid isPermaLink="true">https://eprint.iacr.org/2023/317</guid>
621 <category>Attacks and cryptanalysis</category>
622 <enclosure url="https://eprint.iacr.org/2023/317.pdf" length="0" type="application/pdf"/>
623 <pubDate>Fri, 03 Mar 2023 09:30:46 +0000</pubDate>
624 <dc:creator>Razvan Barbulescu</dc:creator>
625 <dc:creator>Adrien Poulalion</dc:creator>
626 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
627 </item>
628 <item>
629 <title>SCALLOP: scaling the CSI-FiSh</title>
630 <link>https://eprint.iacr.org/2023/058</link>
631 <description>We present SCALLOP: SCALable isogeny action based on
632 Oriented supersingular curves with Prime conductor, a new group action based on isogenies of supersingular curves. Similarly to CSIDH and
633 OSIDH, we use the group action of an imaginary quadratic order’s class
634 group on the set of oriented supersingular curves. Compared to CSIDH,
635 the main benefit of our construction is that it is easy to compute the
636 class-group structure; this data is required to uniquely represent— and
637 efficiently act by— arbitrary group elements, which is a requirement in,
638 e.g., the CSI-FiSh signature scheme by Beullens, Kleinjung and Vercauteren. The index-calculus algorithm used in CSI-FiSh to compute
639 the class-group structure has complexity L(1/2), ruling out class groups
640 much larger than CSIDH-512, a limitation that is particularly problematic in light of the ongoing debate regarding the quantum security of
641 cryptographic group actions.
642 Hoping to solve this issue, we consider the class group of a quadratic order of large prime conductor inside an imaginary quadratic field of small
643 discriminant. This family of quadratic orders lets us easily determine
644 the size of the class group, and, by carefully choosing the conductor,
645 even exercise significant control on it— in particular supporting highly
646 smooth choices. Although evaluating the resulting group action still has
647 subexponential asymptotic complexity, a careful choice of parameters
648 leads to a practical speedup that we demonstrate in practice for a security level equivalent to CSIDH-1024, a parameter currently firmly out of reach of index-calculus-based methods. However, our implementation
649 takes 35 seconds (resp. 12.5 minutes) for a single group-action evaluation at a CSIDH-512-equivalent (resp. CSIDH-1024-equivalent) security
650 level, showing that, while feasible, the SCALLOP group action does not
651 achieve realistically usable performance yet.</description>
652 <guid isPermaLink="true">https://eprint.iacr.org/2023/058</guid>
653 <category>Public-key cryptography</category>
654 <enclosure url="https://eprint.iacr.org/2023/058.pdf" length="0" type="application/pdf"/>
655 <pubDate>Wed, 18 Jan 2023 13:40:33 +0000</pubDate>
656 <dc:creator>Luca De Feo</dc:creator>
657 <dc:creator>Tako Boris Fouotsa</dc:creator>
658 <dc:creator>Péter Kutas</dc:creator>
659 <dc:creator>Antonin Leroux</dc:creator>
660 <dc:creator>Simon-Philipp Merz</dc:creator>
661 <dc:creator>Lorenz Panny</dc:creator>
662 <dc:creator>Benjamin Wesolowski</dc:creator>
663 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
664 </item>
665 <item>
666 <title>New Methods for Bounding the Length of Impossible Differentials of SPN Block Ciphers</title>
667 <link>https://eprint.iacr.org/2023/316</link>
668 <description>Impossible differential (ID) cryptanalysis is one of the most important cryptanalytic approaches for block ciphers. How to evaluate the security of Substitution-Permutation Network (SPN) block ciphers against ID is a valuable problem. In this paper, a series of methods for bounding the length of IDs of SPN block ciphers are proposed. From the perspective of overall structure, we propose a general framework and three implementation strategies. The three implementation strategies are compared and analyzed in terms of efficiency and accuracy. From the perspective of implementation technologies, we give the methods for determining representative set, partition table and ladder and integrating them into searching models. Moreover, the rotation-equivalence ID sets of ciphers are explored to reduce the number of models need to be considered. Thus, the ID bounds of SPN block ciphers can be effectively evaluated. As applications, we show that 9-round PRESENT, 8-round GIFT-64, 12-round GIFT-128, 5-round AES, 6-round Rijndael-160, 7-round Rijndael-192, 7-round Rijndael-224, 7-round Rijndael-256 and 10-round Midori64 do not have any ID under the sole assumption that the round keys are uniformly random. The results of PRESENT, GIFT-128, Rijndael-160, Rijndael-192, Rijndael-224, Rijndael-256 and Midori64 are obtained for the first time. Moreover, the ID bounds of AES, Rijndael-160, Rijndael-192, Rijndael-224 and Rijndael-256 are infimum.</description>
669 <guid isPermaLink="true">https://eprint.iacr.org/2023/316</guid>
670 <category>Secret-key cryptography</category>
671 <enclosure url="https://eprint.iacr.org/2023/316.pdf" length="0" type="application/pdf"/>
672 <pubDate>Fri, 03 Mar 2023 08:33:24 +0000</pubDate>
673 <dc:creator>Senpeng Wang</dc:creator>
674 <dc:creator>Dengguo Feng</dc:creator>
675 <dc:creator>Bin Hu</dc:creator>
676 <dc:creator>Jie Guan</dc:creator>
677 <dc:creator>Ting Cui</dc:creator>
678 <dc:creator>Tairong Shi</dc:creator>
679 <dc:creator>Kai Zhang</dc:creator>
680 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
681 </item>
682 <item>
683 <title>Memory-Tight Multi-Challenge Security of Public-Key Encryption</title>
684 <link>https://eprint.iacr.org/2023/314</link>
685 <description>We give the first examples of public-key encryption schemes which can be proven to achieve multi-challenge, multi-user CCA security via reductions that are tight in time, advantage, and memory. Our constructions are obtained by applying the KEM-DEM paradigm to variants of Hashed ElGamal and the Fujisaki-Okamoto transformation that are augmented by adding uniformly random strings to their ciphertexts and/or keys.
686
687 The reductions carefully combine recent proof techniques introduced by Bhattacharyya’20 and Ghoshal- Ghosal-Jaeger-Tessaro’22. Our proofs for the augmented ECIES version of Hashed-ElGamal make use of a new computational Diffie-Hellman assumption wherein the adversary is given access to a pairing to a random group, which we believe may be of independent interest.</description>
688 <guid isPermaLink="true">https://eprint.iacr.org/2023/314</guid>
689 <category>Public-key cryptography</category>
690 <enclosure url="https://eprint.iacr.org/2023/314.pdf" length="0" type="application/pdf"/>
691 <pubDate>Fri, 03 Mar 2023 04:39:50 +0000</pubDate>
692 <dc:creator>Joseph Jaeger</dc:creator>
693 <dc:creator>Akshaya Kumar</dc:creator>
694 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
695 </item>
696 <item>
697 <title>SoK: Metadata-Protecting Communication Systems</title>
698 <link>https://eprint.iacr.org/2023/313</link>
699 <description>Protecting metadata of communications has been an area of active research since the dining cryptographers problem was introduced by David Chaum in 1988. The Snowden revelations from 2013 resparked research in this direction. Consequently over the last decade we have witnessed a flurry of novel systems designed to protect metadata of users' communications online. However, these systems are often guided by the application they cater to, and leverage different assumptions and design choices to achieve their goal; resulting in a scattered view of the desirable properties, potential vulnerabilities, and limitations of existing metadata-protecting communication systems (MPCS).
700
701 In this work we survey 31 systems targeting metadata-protected communications, and present a unified view of the current state of affairs. We provide two different taxonomies for existing MPCS, first into three different categories by the precise type of metadata protections they offer, and next into six families based on the core techniques that underlie them. By contrasting these systems we identify potential vulnerabilities, as well as subtle privacy implications of design choices of existing MPCS. Furthermore, we identify promising avenues for future research for MPCS, and desirable properties that merit more attention.</description>
702 <guid isPermaLink="true">https://eprint.iacr.org/2023/313</guid>
703 <category>Applications</category>
704 <enclosure url="https://eprint.iacr.org/2023/313.pdf" length="0" type="application/pdf"/>
705 <pubDate>Thu, 02 Mar 2023 22:24:29 +0000</pubDate>
706 <dc:creator>Sajin Sasy</dc:creator>
707 <dc:creator>Ian Goldberg</dc:creator>
708 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
709 </item>
710 <item>
711 <title>BIP32-Compatible Threshold Wallets</title>
712 <link>https://eprint.iacr.org/2023/312</link>
713 <description>Cryptographic wallets have become an essential tool to secure users' secret keys and consequently their funds in Blockchain networks. The most prominent wallet standard that is widely adopted in practice is the BIP32 specification. This standard specifies so-called hierarchical deterministic wallets, which are organized in a tree-like structure such that each node in the tree represents a wallet instance and such that a parent node can derive a new child node in a deterministic fashion.
714 BIP32 considers two types of child nodes, namely non-hardened and hardened nodes, which differ in the security guarantees they provide. While the corruption of a hardened wallet does not affect the security of any other wallet instance in the tree, the corruption of a non-hardened node leads to a breach of the entire scheme.
715
716 In this work, we address this significant drawback of non-hardened nodes by laying out the design for the first hierarchical deterministic wallet scheme with thresholdized non-hardened nodes. We first provide a game-based notion of threshold signatures with rerandomizable keys and show an instantiation via the Gennaro and Goldfeder threshold ECDSA scheme (CCS'18). We further observe that the derivation of hardened child wallets according to the BIP32 specification does not translate easily to the threshold setting. Therefore, we devise a new and efficient derivation mechanism for hardened wallets in the threshold setting that satisfies the same properties as the original BIP32 derivation mechanism and therefore allows for efficient constructions of BIP32-compatible threshold wallets.</description>
717 <guid isPermaLink="true">https://eprint.iacr.org/2023/312</guid>
718 <category>Cryptographic protocols</category>
719 <enclosure url="https://eprint.iacr.org/2023/312.pdf" length="0" type="application/pdf"/>
720 <pubDate>Thu, 02 Mar 2023 19:16:39 +0000</pubDate>
721 <dc:creator>Poulami Das</dc:creator>
722 <dc:creator>Andreas Erwig</dc:creator>
723 <dc:creator>Sebastian Faust</dc:creator>
724 <dc:creator>Julian Loss</dc:creator>
725 <dc:creator>Siavash Riahi</dc:creator>
726 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
727 </item>
728 <item>
729 <title>Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States</title>
730 <link>https://eprint.iacr.org/2023/311</link>
731 <description>We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol, mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions…) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely to exist classically as Cryptomania is believed to be different from Minicrypt.
732
733 In particular, by instantiating our construction using Non-Interactive ZK (NIZK), we provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model, and round-optimal extensions to string and $k$-out-of-$n$ OT.
734
735 At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing (too much) information on it, even in a non-interactive way and/or with statistical guarantees when using an appropriate classical ZK protocol. We can notably prove that a state has been partially measured (with arbitrary constraints on the set of measured qubits), without revealing any additional information on this set. This notion can be seen as an analog of ZK to quantum states, and we expect it to be of independent interest as it extends complexity theory to quantum languages, as illustrated by the two new complexity classes we introduce, ZKstateQIP and ZKstateQMA.</description>
736 <guid isPermaLink="true">https://eprint.iacr.org/2023/311</guid>
737 <category>Cryptographic protocols</category>
738 <enclosure url="https://eprint.iacr.org/2023/311.pdf" length="0" type="application/pdf"/>
739 <pubDate>Thu, 02 Mar 2023 19:14:13 +0000</pubDate>
740 <dc:creator>Léo Colisson</dc:creator>
741 <dc:creator>Garazi Muguruza</dc:creator>
742 <dc:creator>Florian Speelman</dc:creator>
743 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
744 </item>
745 <item>
746 <title>DEEPAND: In-Depth Modeling of Correlated AND Gates for NLFSR-based Lightweight Block Ciphers</title>
747 <link>https://eprint.iacr.org/2022/1123</link>
748 <description>Automated cryptanalysis has taken center stage in the arena of cryptanalysis since the pioneering work by Mouha et al. which showcased the power of Mixed Integer Linear Programming (MILP) in solving cryptanalysis problems that otherwise, required significant effort. Since its inception, research in this area has moved in primarily two directions. One is to model more and more classical cryptanalysis tools as optimization problems to leverage the ease provided by state-of-the-art solvers. The other direction is to improve existing models to make them more efficient and/or accurate. The current work is an attempt to contribute to the latter. In this work, a general model referred to as DEEPAND has been devised to capture the correlation between AND gates in NLFSR-based lightweight block ciphers. DEEPAND builds upon and generalizes the idea of joint propagation of differences through AND gates captured using refined MILP modeling of TinyJAMBU by Saha et al. in FSE 2020. The proposed model has been applied to TinyJAMBU and KATAN and can detect correlations that were missed by earlier models. This leads to more accurate differential bounds for both ciphers.
749
750 In particular, a 384-round (full-round as per earlier specification) Type-IV trail is found for TinyJAMBU with 14 active AND gates using the new model, while the refined model reported this figure to be 19. This also reaffirms the decision of the designers to increase the number of rounds from 384 to 640. Moreover, the model succeeds in searching a full round Type-IV trail of TinyJAMBU keyed permutation $\mathcal{P}_{1024}$ with probability $2^{-108} (\gg 2^{-128})$. This reveals the non-random properties of $\mathcal{P}_{1024}$ thereby showing it to be non-ideal. Hence it cannot be expected to provide the same security levels as robust block ciphers. Further, the provable security of the TinyJAMBU AEAD scheme should be carefully revisited.
751
752 Similarly, for KATAN 32, DEEPAND modeling improves the 42-round trail with $2^{-11}$ probability to $2^{-7}$. Also, for KATAN 48 and KATAN 64, this model respectively improves the designer's claimed 43-round and 37-round trail probabilities. Moreover, in the related key setting, the DEEPAND model can make a better 140-round boomerang distinguisher (for both the data and time complexity) compared to the previous boomerang attack by Isobe et al. in ACISP 2013. In summary, DEEPAND seems to capture the underlying correlation better when multiple AND gates are at play and can be adapted to other classes of ciphers as well.</description>
753 <guid isPermaLink="true">https://eprint.iacr.org/2022/1123</guid>
754 <category>Attacks and cryptanalysis</category>
755 <enclosure url="https://eprint.iacr.org/2022/1123.pdf" length="0" type="application/pdf"/>
756 <pubDate>Mon, 29 Aug 2022 14:51:47 +0000</pubDate>
757 <dc:creator>Amit Jana</dc:creator>
758 <dc:creator>Mostafizar Rahman</dc:creator>
759 <dc:creator>Dhiman Saha</dc:creator>
760 <dc:rights>https://creativecommons.org/publicdomain/zero/1.0/</dc:rights>
761 </item>
762 <item>
763 <title>Ramen: Souper Fast Three-Party Computation for RAM Programs</title>
764 <link>https://eprint.iacr.org/2023/310</link>
765 <description>Secure RAM computation allows a number of parties to evaluate a function represented as a RAM program in a way that reveals nothing about the private inputs of the parties except from what is already revealed by the function output itself. In this work we present Ramen, which is a new protocol for computing RAM programs securely among three parties, tolerating up to one passive corruption. Ramen provides reasonable asymptotic guarantees and is concretely efficient at the same time. We have implemented our protocol and provide extensive benchmarks for various settings.
766
767 Asymptotically, our protocol requires a constant number of rounds and a amortized sublinear amount of communication and computation per memory access. In terms of concrete efficiency, our protocol outperforms previous solutions. For a memory of size $2^{26}$ our memory accesses are \(30\times\) faster in the LAN and \(8.7\times\) faster in the WAN setting, when compared to the previously fastest solution by Vadapalli, Henry, and Goldberg (ePrint 2022). Due to our superior asymptotic guarantees, the efficiency gap is only widening as the memory gets larger and for this reason Ramen provides the currently most scalable concretely efficient solution for securely computing RAM programs.</description>
768 <guid isPermaLink="true">https://eprint.iacr.org/2023/310</guid>
769 <category>Cryptographic protocols</category>
770 <enclosure url="https://eprint.iacr.org/2023/310.pdf" length="0" type="application/pdf"/>
771 <pubDate>Thu, 02 Mar 2023 15:17:36 +0000</pubDate>
772 <dc:creator>Lennart Braun</dc:creator>
773 <dc:creator>Mahak Pancholi</dc:creator>
774 <dc:creator>Rahul Rachuri</dc:creator>
775 <dc:creator>Mark Simkin</dc:creator>
776 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
777 </item>
778 <item>
779 <title>Practical Construction for Secure Trick-Taking Games Even With Cards Set Aside</title>
780 <link>https://eprint.iacr.org/2023/309</link>
781 <description>Trick-taking games are traditional card games played all over the world. There are many such games, and most of them can be played online through dedicated applications, either for fun or for betting money. However, these games have an intrinsic drawback: each player plays its cards according to several secret constraints (unknown to the other players), and if a player does not respect these constraints, the other players will not realize it until much later in the game.
782
783 In 2019, X. Bultel and P. Lafourcade proposed a cryptographic protocol for Spades in the random oracle model allowing peer-to-peer trick-taking games to be played securely without the possibility of cheating, even by playing a card that does not respect the secret constraints. However, to simulate card shuffling, this protocol requires a custom proof of shuffle with quadratic complexity in the number of cards, which makes the protocol inefficient in practice. In this paper, we improve their work in several ways. First, we extend their model to cover a broader range of games, such as those implying a set of cards set aside during the deal (for instance Triomphe or French Tarot). Then, we propose a new efficient construction for Spades in the standard model (without random oracles), where cards are represented by partially homomorphic ciphertexts. It can be instantiated by any standard generic proof of shuffle, which significantly improves the efficiency. We demonstrate the feasibility of our approach by giving an implementation of our protocol, and we compare the performances of the new shuffle protocol with the previous one. Finally, we give a similar protocol for French Tarot, with comparable efficiency.</description>
784 <guid isPermaLink="true">https://eprint.iacr.org/2023/309</guid>
785 <category>Cryptographic protocols</category>
786 <enclosure url="https://eprint.iacr.org/2023/309.pdf" length="0" type="application/pdf"/>
787 <pubDate>Thu, 02 Mar 2023 14:55:04 +0000</pubDate>
788 <dc:creator>Rohann Bella</dc:creator>
789 <dc:creator>Xavier Bultel</dc:creator>
790 <dc:creator>Céline Chevalier</dc:creator>
791 <dc:creator>Pascal Lafourcade</dc:creator>
792 <dc:creator>Charles Olivier-Anclin</dc:creator>
793 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
794 </item>
795 <item>
796 <title>Generic Attack on Duplex-Based AEAD Modes using Random Function Statistics</title>
797 <link>https://eprint.iacr.org/2023/262</link>
798 <description>Duplex-based authenticated encryption modes with a sufficiently large key length are proven to be secure up to the birthday bound 2^(c/2), where c is the capacity. However this bound is not known to be tight and the complexity of the best known generic attack, which is based on multicollisions, is much larger: it reaches (2^c)/α where α represents a small security loss factor. There is thus an uncertainty on the true extent of security beyond the bound 2^(c/2) provided by such constructions. In this paper, we describe a new generic attack against several duplex-based AEAD modes. Our attack leverages random functions statistics and produces a forgery in time complexity O(2^(3c/4)) using negligible memory and no encryption queries. Furthermore, for some duplex-based modes, our attack recovers the secret key with a negligible amount of additional computations. Most notably, our attack breaks a security claim made by the designers of the NIST lightweight competition candidate Xoodyak. This attack is a step further towards determining the exact security provided by duplex-based constructions.</description>
799 <guid isPermaLink="true">https://eprint.iacr.org/2023/262</guid>
800 <category>Secret-key cryptography</category>
801 <enclosure url="https://eprint.iacr.org/2023/262.pdf" length="0" type="application/pdf"/>
802 <pubDate>Wed, 22 Feb 2023 17:29:39 +0000</pubDate>
803 <dc:creator>Henri Gilbert</dc:creator>
804 <dc:creator>Rachelle Heim Boissier</dc:creator>
805 <dc:creator>Louiza Khati</dc:creator>
806 <dc:creator>Yann Rotella</dc:creator>
807 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
808 </item>
809 <item>
810 <title>Towards Secure Evaluation of Online Functionalities (Corrected and Extended Version)</title>
811 <link>https://eprint.iacr.org/2022/1755</link>
812 <description>To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private inputs of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols implementing online algorithms in a distributed fashion can be proven to be privacy-preserving. Online algorithms compute online functionalities that allow parties to arrive and leave over time, to provide multiple inputs and to obtain multiple outputs. In particular, the set of parties participating changes over time, i.e., at different points in time different sets of parties evaluate a function over their private inputs. To this end, we propose the notion of an online trusted third party that allows to prove the security of SMPC protocols implementing online functionalities or online algorithms, respectively. We show that any online functionality can be implemented perfectly secure in the presence of a semi-honest adversary, if strictly less than 1/2 of the parties participating are corrupted. We show that the same result holds in the presence of a malicious adversary if it corrupts strictly less than 1/3 of the parties and always allows the corrupted parties to arrive and provide input.
813 Note, this is the corrected and extended version of the work presented in [24].</description>
814 <guid isPermaLink="true">https://eprint.iacr.org/2022/1755</guid>
815 <category>Foundations</category>
816 <enclosure url="https://eprint.iacr.org/2022/1755.pdf" length="0" type="application/pdf"/>
817 <pubDate>Thu, 22 Dec 2022 07:05:35 +0000</pubDate>
818 <dc:creator>Andreas Klinger</dc:creator>
819 <dc:creator>Ulrike Meyer</dc:creator>
820 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
821 </item>
822 <item>
823 <title>Robust Channels: Handling Unreliable Networks in the Record Layers of QUIC and DTLS 1.3</title>
824 <link>https://eprint.iacr.org/2020/718</link>
825 <description>The common approach in secure communication channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example is the case with TLS or SSH. However, protocols like QUIC or DTLS which run over a non-reliable transport such as UDP, do not---and in fact cannot---close the connection if packets are lost or arrive in a different order. Those protocols instead have to carefully catch effects arising naturally in unreliable networks, usually by using a sliding-window technique where ciphertexts can be decrypted correctly as long as they are not misplaced too far.
826
827 In order to be able to capture QUIC and the newest DTLS version 1.3, we introduce a generalized notion of robustness of cryptographic channels. This property can capture unreliable network behavior and guarantees that adversarial tampering cannot hinder ciphertexts that can be decrypted correctly from being accepted. We show that robustness is orthogonal to the common notion of integrity for channels, but together with integrity and chosen-plaintext security it provides a robust analogue of chosen-ciphertext security of channels. In contrast to prior work, robustness allows us to study packet encryption in the record layer protocols of QUIC and of DTLS 1.3 and the novel sliding-window techniques both protocols employ. We show that both protocols achieve robust chosen-ciphertext security based on certain properties of their sliding-window techniques and the underlying AEAD schemes. Notably, the robustness needed in handling unreliable network messages requires both record layer protocols to tolerate repeated adversarial forgery attempts. This means we can only establish non-tight security bounds (in terms of AEAD integrity), a security degration that was missed in earlier protocol drafts. Our bounds led the responsible IETF working groups to introduce concrete forgery limits for both protocols and the IRTF CFRG to consider AEAD usage limits more broadly.</description>
828 <guid isPermaLink="true">https://eprint.iacr.org/2020/718</guid>
829 <category>Cryptographic protocols</category>
830 <enclosure url="https://eprint.iacr.org/2020/718.pdf" length="0" type="application/pdf"/>
831 <pubDate>Tue, 16 Jun 2020 06:57:14 +0000</pubDate>
832 <dc:creator>Marc Fischlin</dc:creator>
833 <dc:creator>Felix Günther</dc:creator>
834 <dc:creator>Christian Janson</dc:creator>
835 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
836 </item>
837 <item>
838 <title>Punctured Syndrome Decoding Problem Efficient Side-Channel Attacks Against Classic McEliece</title>
839 <link>https://eprint.iacr.org/2023/308</link>
840 <description>Among the fourth round finalists of the NIST post-quantum cryptography standardization process for public-key encryption algorithms and key encapsulation mechanisms, three rely on hard problems from coding theory. Key encapsulation mechanisms are frequently used in hybrid cryptographic systems: a public-key algorithm for key exchange and a secret key algorithm for communication. A major point is thus the initial key exchange that is performed thanks to a key encapsulation mechanism. In this paper, we analyze side-channel vulnerabilities of the key encapsulation mechanism implemented by the Classic McEliece cryptosystem, whose security is based on the syndrome decoding problem. We use side-channel leakages to reduce the complexity of the syndrome decoding problem by reducing the length of the code considered. The columns punctured from the original code reduce the complexity of a hard problem from coding theory. This approach leads to efficient profiled side-channel attacks that recover the session key with high success rates, even in noisy scenarios.</description>
841 <guid isPermaLink="true">https://eprint.iacr.org/2023/308</guid>
842 <category>Attacks and cryptanalysis</category>
843 <enclosure url="https://eprint.iacr.org/2023/308.pdf" length="0" type="application/pdf"/>
844 <pubDate>Thu, 02 Mar 2023 13:07:32 +0000</pubDate>
845 <dc:creator>Vincent Grosso</dc:creator>
846 <dc:creator>Pierre-Louis Cayrel</dc:creator>
847 <dc:creator>Brice Colombier</dc:creator>
848 <dc:creator>Vlad-Florin Dragoi</dc:creator>
849 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
850 </item>
851 <item>
852 <title>Vortex : Building a Lattice-based SNARK scheme with Transparent Setup</title>
853 <link>https://eprint.iacr.org/2022/1633</link>
854 <description>We present the first transparent and plausibly post-quantum SNARK relying on the Ring Short Integer Solution problem (Ring-SIS), a well-known assumption from lattice-based cryptography. At its core, our proof system relies on a new linear-commitment scheme named Vortex which is inspired from the work of Orion and Brakedown. Vortex uses a hash function based on Ring-SIS derived from “SWIFFT" (Lyubashevsky et al., FSE08). We take advantage of the linear structure of this particular hash function to craft an efficient self-recursion technique. Although Vortex proofs have $O(\sqrt{n})$ size in the witness size, we show how our self-recursion technique can be used to build a SNARK scheme based on Vortex. The resulting SNARK works over any field with reasonably large 2-adicity (also known as FFT-friendly fields). Moreover, we introduce Wizard-IOP, an extension of the concept of polynomial-IOP. Working with Wizard-IOP rather than separate polynomial-IOPs provides us with a strong tool for handling a wide class of queries, needed for proving the correct executions of the complex state machines (e.g., zk-EVM as our use-case) efficiently and conveniently.</description>
855 <guid isPermaLink="true">https://eprint.iacr.org/2022/1633</guid>
856 <category>Cryptographic protocols</category>
857 <enclosure url="https://eprint.iacr.org/2022/1633.pdf" length="0" type="application/pdf"/>
858 <pubDate>Thu, 24 Nov 2022 11:00:59 +0000</pubDate>
859 <dc:creator>Alexandre Belling</dc:creator>
860 <dc:creator>Azam Soleimanian</dc:creator>
861 <dc:rights>https://creativecommons.org/publicdomain/zero/1.0/</dc:rights>
862 </item>
863 <item>
864 <title>Mind Your Path: On (Key) Dependencies in Differential Characteristics</title>
865 <link>https://eprint.iacr.org/2022/1734</link>
866 <description>Cryptanalysts have been looking for differential characteristics in ciphers for
867 decades and it remains unclear how the subkey values and more generally the Markov
868 assumption impacts exactly their probability estimation. There were theoretical
869 efforts considering some simple linear relationships between differential characteristics
870 and subkey values, but the community has not yet explored many possible nonlinear
871 dependencies one can find in differential characteristics. Meanwhile, the overwhelming
872 majority of cryptanalysis works still assume complete independence between the cipher
873 rounds. We give here a practical framework and a corresponding tool to investigate
874 all such linear or nonlinear effects and we show that they can have an important
875 impact on the security analysis of many ciphers. Surprisingly, this invalidates many
876 differential characteristics that appeared in the literature in the past years: we have
877 checked differential characteristics from 8 articles (4 each for both SKINNY and GIFT)
878 and most of these published paths are impossible or working only for a very small
879 proportion of the key space. We applied our method to SKINNY and GIFT, but
880 we expect more impossibilities for other ciphers. To showcase our advances in the
881 dependencies analysis, in the case of SKINNY we are able to obtain a more accurate
882 probability distribution of a differential characteristic with respect to the keys (with
883 practical verification when it is computationally feasible). Our work indicates that
884 newly proposed differential characteristics should now come with an analysis of how
885 the key values and the Markov assumption might or might not affect/invalidate them.
886 In this direction, more constructively, we include a proof of concept of how one can
887 incorporate additional constraints into Constraint Programming so that the search
888 for differential characteristics can avoid (to a large extent) differential characteristics
889 that are actually impossible due to dependency issues our tool detected.</description>
890 <guid isPermaLink="true">https://eprint.iacr.org/2022/1734</guid>
891 <category>Attacks and cryptanalysis</category>
892 <enclosure url="https://eprint.iacr.org/2022/1734.pdf" length="0" type="application/pdf"/>
893 <pubDate>Fri, 16 Dec 2022 16:41:03 +0000</pubDate>
894 <dc:creator>Thomas Peyrin</dc:creator>
895 <dc:creator>Quan Quan Tan</dc:creator>
896 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
897 </item>
898 <item>
899 <title>The geometric interpretation of the Tate pairing and its applications</title>
900 <link>https://eprint.iacr.org/2023/177</link>
901 <description>While the Weil pairing is geometric, the Tate pairing is arithmetic: its value depends on the base field considered. Nevertheless, the étale topology allows to interpret the Galois action in a geometric manner. In this paper, we discuss this point of view for the Tate pairing: its natural geometric interpretation is that it gives étale $\mu_n$-torsors. While well known to experts, this interpretation is perhaps less known in the cryptographic community.
902
903 As an application, we explain how to use the Tate pairing to study the fibers of an isogeny, and we prove a conjecture by Castryck and Decru on multiradical isogenies.</description>
904 <guid isPermaLink="true">https://eprint.iacr.org/2023/177</guid>
905 <category>Foundations</category>
906 <enclosure url="https://eprint.iacr.org/2023/177.pdf" length="0" type="application/pdf"/>
907 <pubDate>Sun, 12 Feb 2023 22:15:36 +0000</pubDate>
908 <dc:creator>Damien Robert</dc:creator>
909 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
910 </item>
911 <item>
912 <title>SUPERPACK: Dishonest Majority MPC with Constant Online Communication</title>
913 <link>https://eprint.iacr.org/2023/307</link>
914 <description>In this work we present a novel actively secure dishonest majority MPC protocol, \textsc{SuperPack}, whose efficiency improves as the number of \emph{honest} parties increases. Concretely, let $0<\epsilon<1/2$ and consider an adversary that corrupts $t<n(1-\epsilon)$ out of $n$ parties.
915 \textsc{SuperPack} requires $6/\epsilon$ field elements of online communication per multiplication gate across all parties, assuming circuit-dependent preprocessing, and $10/\epsilon$ assuming circuit-independent preprocessing.
916 In contrast, most of the previous works such as SPDZ (Damg\aa rd \emph{et al}, ESORICS 2013) and its derivatives perform the same regardless of whether there is only one honest party or a constant (non-majority) fraction of honest parties.
917 A notable exception is due to Goyal \emph{et al} (CRYPTO 2022), which achieves $58/\epsilon + 96/\epsilon^2$ field elements assuming circuit-independent preprocessing.
918 Our work improves this result substantially by a factor of at least $25$ in the circuit-independent preprocessing model.
919
920 Practically, we also compare our work with the best concretely efficient online protocol Turbospeedz (Ben-Efraim \emph{et al}, ACNS 2019), which achieves $2(1-\epsilon)n$ field elements per multiplication gate among all parties. Our online protocol improves over Turbospeedz as $n$ grows, and as $\epsilon$ approaches $1/2$.
921 For example, if there are $90\%$ corruptions ($\epsilon=0.1$), with $n=50$ our online protocol is $1.5\times$ better than Turbospeedz and with $n=100$ this factor is $3\times$, but for $70\%$ corruptions ($\epsilon=0.3$) with $n=50$ our online protocol is $3.5\times$ better, and for $n=100$ this factor is $7\times$.
922
923 Our circuit-dependent preprocessing can be instantiated from OLE/VOLE. The amount of OLE/VOLE correlations required in our work is a factor of $\approx \epsilon n/2$ smaller than these required by Le Mans (Rachuri and Scholl, CRYPTO 2022) leveraged to instantiate the preprocessing of Turbospeedz.
924
925 Our dishonest majority protocol relies on packed secret-sharing and leverages ideas from the honest majority \textsc{TurboPack} (Escudero \emph{et al}, CCS 2022) protocol to achieve concrete efficiency for any circuit topology, not only SIMD.
926 We implement both \textsc{SuperPack} and Turbospeedz and verify with experimental results that our approach indeed leads to more competitive runtimes in distributed environments with a moderately large number of parties.</description>
927 <guid isPermaLink="true">https://eprint.iacr.org/2023/307</guid>
928 <category>Cryptographic protocols</category>
929 <enclosure url="https://eprint.iacr.org/2023/307.pdf" length="0" type="application/pdf"/>
930 <pubDate>Thu, 02 Mar 2023 02:26:04 +0000</pubDate>
931 <dc:creator>Daniel Escudero</dc:creator>
932 <dc:creator>Vipul Goyal</dc:creator>
933 <dc:creator>Antigoni Polychroniadou</dc:creator>
934 <dc:creator>Yifan Song</dc:creator>
935 <dc:creator>Chenkai Weng</dc:creator>
936 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
937 </item>
938 <item>
939 <title>A Simple Construction of Quantum Public-Key Encryption from Quantum-Secure One-Way Functions</title>
940 <link>https://eprint.iacr.org/2023/306</link>
941 <description>Quantum public-key encryption [Gottesman; Kawachi et al., Eurocrypt’05] generalizes public-key encryption (PKE) by allowing the public keys to be quantum states. Prior work indicated that quantum PKE can be constructed from assumptions that are potentially weaker than those needed to realize its classical counterpart. In this work, we show that quantum PKE can be constructed from any quantum-secure one-way function. In contrast, classical PKE is believed to require more structured assumptions. Our construction is simple, uses only classical ciphertexts, and satisfies the strong notion of CCA security.</description>
942 <guid isPermaLink="true">https://eprint.iacr.org/2023/306</guid>
943 <category>Foundations</category>
944 <enclosure url="https://eprint.iacr.org/2023/306.pdf" length="0" type="application/pdf"/>
945 <pubDate>Wed, 01 Mar 2023 23:23:42 +0000</pubDate>
946 <dc:creator>Khashayar Barooti</dc:creator>
947 <dc:creator>Giulio Malavolta</dc:creator>
948 <dc:creator>Michael Walter</dc:creator>
949 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
950 </item>
951 <item>
952 <title>A Novel Related Nonce Attack for ECDSA</title>
953 <link>https://eprint.iacr.org/2023/305</link>
954 <description>We describe a new related nonce attack able to extract the
955 original signing key from a small collection of ECDSA signatures generated with weak PRNGs. Under suitable conditions on the modulo order
956 of the PRNG, we are able to attack linear, quadratic, cubic as well as
957 arbitrary degree recurrence relations (with unknown coefficients) with
958 few signatures and in negligible time. We also show that for any collection of randomly generated ECDSA nonces, there is one more nonce that
959 can be added following the implicit recurrence relation, and that would
960 allow retrieval of the private key; we exploit this fact to present a novel
961 rogue nonce attack against ECDSA. Up to our knowledge, this is the
962 first known attack exploiting generic and unknown high-degree algebraic
963 relations between nonces that do not require assumptions on the value
964 of single bits or bit sequences (e.g. prefixes and suffixes).</description>
965 <guid isPermaLink="true">https://eprint.iacr.org/2023/305</guid>
966 <category>Attacks and cryptanalysis</category>
967 <enclosure url="https://eprint.iacr.org/2023/305.pdf" length="0" type="application/pdf"/>
968 <pubDate>Wed, 01 Mar 2023 20:35:22 +0000</pubDate>
969 <dc:creator>Marco Macchetti</dc:creator>
970 <dc:rights>https://creativecommons.org/licenses/by-nc-sa/4.0/</dc:rights>
971 </item>
972 <item>
973 <title>Fusion One-Time Non-Interactively-Aggregatable Digital Signatures From Lattices</title>
974 <link>https://eprint.iacr.org/2023/303</link>
975 <description>We present Fusion, a post-quantum one-time digital signature scheme with non-interactive aggregation with security resting on the short integer solution problem over ideal lattices. Fusion is structurally similar to CRYSTALS-Dilithium, but Fusion is based upon the aggregatable one-time lattice-based scheme by Boneh and Kim. Fusion parameters conservatively target at least $128$ bits of security against forgery, taking tightness gaps into account, and with tighter bounds than the BK scheme. Aggregate Fusion signatures are logarithmically sized in the number of keys, so aggregating enough signatures can be more efficient than stacking Dilithium or Falcon signatures.</description>
976 <guid isPermaLink="true">https://eprint.iacr.org/2023/303</guid>
977 <category>Cryptographic protocols</category>
978 <enclosure url="https://eprint.iacr.org/2023/303.pdf" length="0" type="application/pdf"/>
979 <pubDate>Wed, 01 Mar 2023 02:03:00 +0000</pubDate>
980 <dc:creator>Brandon Goodell</dc:creator>
981 <dc:creator>Aaron Feickert</dc:creator>
982 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
983 </item>
984 <item>
985 <title>Post-Quantum Signatures on RISC-V with Hardware Acceleration</title>
986 <link>https://eprint.iacr.org/2022/538</link>
987 <description>CRYSTALS-Dilithium and Falcon are digital signature algorithms based on cryptographic lattices, that are considered secure even if large-scale quantum computers will be able to break conventional public-key cryptography. Both schemes have been selected for standardization in the NIST post-quantum competition. In this work, we present a RISC-V HW/SW odesign that aims to combine the advantages of software- and hardware implementations, i.e. flexibility and performance. It shows the use of lexible hardware accelerators, which have been previously used for Public-Key Encryption (PKE) and Key-Encapsulation Mechanism (KEM), for post-quantum signatures. It is optimized for Dilithium as a generic signature cheme but also accelerates applications that require fast verification of Falcon’s compact signatures. We provide a comparison with previous works showing that for Dilithium and Falcon, cycle counts are significantly reduced, such that our design is faster than previous software implementations or other HW/SW codesigns. In addition to that, we present a compact Globalfoundries 22 nm ASIC design that runs at 800MHz. By using hardware acceleration, energy consumption for Dilithium is reduced by up to 92.2%, and up to 67.5% for Falcon’s signature verification.</description>
988 <guid isPermaLink="true">https://eprint.iacr.org/2022/538</guid>
989 <category>Implementation</category>
990 <enclosure url="https://eprint.iacr.org/2022/538.pdf" length="0" type="application/pdf"/>
991 <pubDate>Tue, 10 May 2022 08:06:48 +0000</pubDate>
992 <dc:creator>Patrick Karl</dc:creator>
993 <dc:creator>Jonas Schupp</dc:creator>
994 <dc:creator>Tim Fritzmann</dc:creator>
995 <dc:creator>Georg Sigl</dc:creator>
996 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
997 </item>
998 <item>
999 <title>TreeSync: Authenticated Group Management for Messaging Layer Security</title>
1000 <link>https://eprint.iacr.org/2022/1732</link>
1001 <description>Messaging Layer Security (MLS), currently undergoing standardization at the IETF, is an asynchronous group messaging protocol that aims to be efficient for large dynamic groups, while providing strong guarantees like forward secrecy (FS) and post-compromise security (PCS). While prior work on MLS has extensively studied its group key establishment component (called TreeKEM), many flaws in early designs of MLS have stemmed from its group integrity and authentication mechanisms that are not as well-understood. In this work, we identify and formalize TreeSync: a sub-protocol of MLS that specifies the shared group state, defines group management operations, and ensures consistency, integrity, and authentication for the group state across all members.
1002
1003 We present a precise, executable, machine-checked formal specification of TreeSync, and show how it can be composed with other components to implement the full MLS protocol. Our specification is written in F* and serves as a reference implementation of MLS; it passes the RFC test vectors and is interoperable with other MLS implementations. Using the DY* symbolic protocol analysis framework, we formalize and prove the integrity and authentication guarantees of TreeSync, under minimal security assumptions on the rest of MLS. Our analysis identifies a new attack and we propose several changes that have been incorporated in the latest MLS draft. Ours is the first testable, machine-checked, formal specification for MLS, and should be of interest to both developers and researchers interested in this upcoming standard.</description>
1004 <guid isPermaLink="true">https://eprint.iacr.org/2022/1732</guid>
1005 <category>Cryptographic protocols</category>
1006 <enclosure url="https://eprint.iacr.org/2022/1732.pdf" length="0" type="application/pdf"/>
1007 <pubDate>Fri, 16 Dec 2022 11:43:27 +0000</pubDate>
1008 <dc:creator>Théophile Wallez</dc:creator>
1009 <dc:creator>Jonathan Protzenko</dc:creator>
1010 <dc:creator>Benjamin Beurdouche</dc:creator>
1011 <dc:creator>Karthikeyan Bhargavan</dc:creator>
1012 <dc:rights>https://creativecommons.org/licenses/by-nc-nd/4.0/</dc:rights>
1013 </item>
1014 <item>
1015 <title>MixFlow: Assessing Mixnets Anonymity with Contrastive Architectures and Semantic Network Information</title>
1016 <link>https://eprint.iacr.org/2023/199</link>
1017 <description>Traffic correlation attacks have illustrated challenges with protecting communication meta-data, yet short flows as in messaging applications like Signal have been protected by practical Mixnets such as Loopix from prior traffic correlation attacks. This paper introduces a novel traffic correlation attack against short-flow applications like Signal that are tunneled through practical Mixnets like Loopix. We propose the MixFlow model, an approach for analyzing the unlinkability of communications through Mix networks. As a prominent example, we do our analysis on Loopix.
1018 The MixFlow is a contrastive model that looks for semantic relationships between entry and exit flows, even if the traffic is tunneled through Mixnets that protect meta-data like Loopix via Poisson mixing delay and cover traffic.
1019 We use the MixFlow model to evaluate the resistance of Loopix Mix networks against an adversary that observes only the inflow and outflow of Mixnet and tries to correlate communication flows. Our experiments indicate that the MixFlow model is exceptionally proficient in connecting end-to-end flows, even when the Poison delay and cover traffic are increased. These findings challenge the conventional notion that adding Poisson mixing delay and cover traffic can obscure the metadata patterns and relationships between communicating parties. Despite the implementation of Poisson mixing countermeasures in Mixnets, MixFlow is still capable of effectively linking end-to-end flows, enabling the extraction of meta-information and correlation between inflows and outflows. Our findings have important implications for existing Poisson-mixing techniques and open up new opportunities for analyzing the anonymity and unlinkability of communication protocols.</description>
1020 <guid isPermaLink="true">https://eprint.iacr.org/2023/199</guid>
1021 <category>Attacks and cryptanalysis</category>
1022 <enclosure url="https://eprint.iacr.org/2023/199.pdf" length="0" type="application/pdf"/>
1023 <pubDate>Wed, 15 Feb 2023 10:36:09 +0000</pubDate>
1024 <dc:creator>Reyhane Attarian</dc:creator>
1025 <dc:creator>Esfandiar Mohammadi</dc:creator>
1026 <dc:creator>Tao Wang</dc:creator>
1027 <dc:creator>Emad Heydari Beni</dc:creator>
1028 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1029 </item>
1030 <item>
1031 <title>On homomorphic encryption using abelian groups: Classical security analysis</title>
1032 <link>https://eprint.iacr.org/2023/304</link>
1033 <description>In [15], Leonardi and Ruiz-Lopez propose an additively homomorphic public key encryption scheme whose security is expected to depend on the hardness of the $\textit{learning homomorphism with noise problem}$ (LHN). Choosing parameters for their primitive requires choosing three groups $G$, $H$, and $K$. In their paper, Leonardi and Ruiz-Lopez claim that, when $G$, $H$, and $K$ are abelian, then their public-key cryptosystem is not quantum secure. In this paper, we study security for finite abelian groups $G$, $H$, and $K$ in the classical case. Moreover, we study quantum attacks on instantiations with solvable groups.</description>
1034 <guid isPermaLink="true">https://eprint.iacr.org/2023/304</guid>
1035 <category>Attacks and cryptanalysis</category>
1036 <enclosure url="https://eprint.iacr.org/2023/304.pdf" length="0" type="application/pdf"/>
1037 <pubDate>Wed, 01 Mar 2023 10:03:52 +0000</pubDate>
1038 <dc:creator>Eleni Agathocleous</dc:creator>
1039 <dc:creator>Vishnupriya Anupindi</dc:creator>
1040 <dc:creator>Annette Bachmayr</dc:creator>
1041 <dc:creator>Chloe Martindale</dc:creator>
1042 <dc:creator>Rahinatou Yuh Njah Nchiwo</dc:creator>
1043 <dc:creator>Mima Stanojkovski</dc:creator>
1044 <dc:rights>https://creativecommons.org/publicdomain/zero/1.0/</dc:rights>
1045 </item>
1046 <item>
1047 <title>Authenticated private information retrieval</title>
1048 <link>https://eprint.iacr.org/2023/297</link>
1049 <description>This paper introduces protocols for authenticated private information retrieval. These schemes enable a client to fetch a record from a remote database server such that (a) the server does not learn which record the client reads, and (b) the client either obtains the "authentic" record or detects server misbehavior and safely aborts. Both properties are crucial for many applications. Standard private-information-retrieval schemes either do not ensure this form of output authenticity, or they require multiple database replicas with an honest majority. In contrast, we offer multi-server schemes that protect security as long as at least one server is honest. Moreover, if the client can obtain a short digest of the database out of band, then our schemes require only a single server. Performing an authenticated private PGP-public-key lookup on an OpenPGP key server's database of 3.5 million keys (3 GiB), using two non-colluding servers, takes under 1.2 core-seconds of computation, essentially matching the time taken by unauthenticated private information retrieval. Our authenticated single-server schemes are 30-100$\times$ more costly than state-of-the-art unauthenticated single-server schemes, though they achieve incomparably stronger integrity properties.</description>
1050 <guid isPermaLink="true">https://eprint.iacr.org/2023/297</guid>
1051 <category>Cryptographic protocols</category>
1052 <enclosure url="https://eprint.iacr.org/2023/297.pdf" length="0" type="application/pdf"/>
1053 <pubDate>Mon, 27 Feb 2023 22:09:41 +0000</pubDate>
1054 <dc:creator>Simone Colombo</dc:creator>
1055 <dc:creator>Kirill Nikitin</dc:creator>
1056 <dc:creator>Henry Corrigan-Gibbs</dc:creator>
1057 <dc:creator>David J. Wu</dc:creator>
1058 <dc:creator>Bryan Ford</dc:creator>
1059 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1060 </item>
1061 <item>
1062 <title>KaLi: A Crystal for Post-Quantum Security using Kyber and Dilithium</title>
1063 <link>https://eprint.iacr.org/2022/1086</link>
1064 <description>Quantum computers pose a threat to the security of communications over the internet. This imminent risk has led to the standardization of cryptographic schemes for protection in a post-quantum scenario. We present a design methodology for future implementations of such algorithms. This is manifested using the NIST selected digital signature scheme CRYSTALS-Dilithium and key encapsulation scheme CRYSTALS-Kyber. A unified architecture, \crystal, is proposed that can perform key generation, encapsulation, decapsulation, signature generation, and signature verification for all the security levels of CRYSTALS-Dilithium, and CRYSTALS-Kyber. A unified yet flexible polynomial arithmetic unit is designed that can processes Kyber operations twice as fast as Dilithium operations. Efficient memory management is proposed to achieve optimal latency.
1065
1066 \crystal is explicitly tailored for ASIC platforms using multiple clock domains. On ASIC 28nm/65nm technology, it occupies 0.263/1.107 mm$^2$ and achieves a clock frequency of 2GHz/560MHz for the fast clock used for memory unit. On Xilinx Zynq Ultrascale+ZCU102 FPGA, the proposed architecture uses 23,277 LUTs, 9,758 DFFs, 4 DSPs, and 24 BRAMs, at 270 MHz clock frequency. \crystal performs better than the standalone implementations of either of the two schemes. This is the first work to provide a unified design in hardware for both schemes.</description>
1067 <guid isPermaLink="true">https://eprint.iacr.org/2022/1086</guid>
1068 <category>Implementation</category>
1069 <enclosure url="https://eprint.iacr.org/2022/1086.pdf" length="0" type="application/pdf"/>
1070 <pubDate>Sat, 20 Aug 2022 16:51:38 +0000</pubDate>
1071 <dc:creator>Aikata Aikata</dc:creator>
1072 <dc:creator>Ahmet Can Mert</dc:creator>
1073 <dc:creator>Malik Imran</dc:creator>
1074 <dc:creator>Samuel Pagliarini</dc:creator>
1075 <dc:creator>Sujoy Sinha Roy</dc:creator>
1076 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1077 </item>
1078 <item>
1079 <title>Algebraic Reductions of Knowledge</title>
1080 <link>https://eprint.iacr.org/2022/009</link>
1081 <description>We introduce reductions of knowledge, a generalization of arguments of knowledge, which reduce checking knowledge of a witness in one relation to checking knowledge of a witness in another (simpler) relation. Reductions of knowledge unify a growing class of modern techniques as well as provide a compositional framework to modularly reason about individual steps in complex arguments of knowledge. As a demonstration, we simplify and unify recursive arguments over linear algebraic statements by decomposing them as a sequence of reductions of knowledge. To do so, we develop the tensor reduction of knowledge, which generalizes the central reductive step common to most recursive arguments. Underlying the tensor reduction of knowledge is a new information-theoretic reduction, which, for any modules $U$, $U_1$, and $U_2$ such that $U \cong U_1 \otimes U_2$, reduces the task of evaluating a homomorphism in $U$ to evaluating a homomorphism in $U_1$ and evaluating a homomorphism in $U_2$.</description>
1082 <guid isPermaLink="true">https://eprint.iacr.org/2022/009</guid>
1083 <category>Foundations</category>
1084 <enclosure url="https://eprint.iacr.org/2022/009.pdf" length="0" type="application/pdf"/>
1085 <pubDate>Fri, 07 Jan 2022 16:53:39 +0000</pubDate>
1086 <dc:creator>Abhiram Kothapalli</dc:creator>
1087 <dc:creator>Bryan Parno</dc:creator>
1088 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1089 </item>
1090 <item>
1091 <title>New algorithms for the Deuring correspondence: toward practical and secure SQISign signatures</title>
1092 <link>https://eprint.iacr.org/2022/234</link>
1093 <description>The Deuring correspondence defines a bijection between isogenies of supersingular elliptic curves and ideals of maximal orders in a quaternion algebra.
1094 We present a new algorithm to translate ideals of prime-power norm to their corresponding isogenies ---
1095 a central task of the effective Deuring correspondence.
1096 The new method improves upon the algorithm introduced in 2021 by De Feo, Kohel, Leroux, Petit and Wesolowski as a building-block of the SQISign signature scheme. SQISign is the most compact post-quantum signature scheme currently known, but is several orders of magnitude slower than competitors, the main bottleneck of the computation being the ideal-to-isogeny translation. We implement the new algorithm and apply it to SQISign, achieving a more than two-fold speedup in key generation and signing with a new choice of parameter.
1097 Moreover, after adapting the state-of-the-art $\mathbb{F}_{p^2}$ multiplication algorithms by Longa to implement SQISign's underlying extension field arithmetic and adding various improvements, we push the total speedups to over three times for signing and four times for verification.
1098
1099 In a second part of the article, we advance cryptanalysis by showing a very simple distinguisher against one of the assumptions used in SQISign. We present a way to impede the distinguisher through a few changes to the generic KLPT algorithm. We formulate a new assumption capturing these changes, and provide an analysis together with experimental evidence for its validity.</description>
1100 <guid isPermaLink="true">https://eprint.iacr.org/2022/234</guid>
1101 <category>Public-key cryptography</category>
1102 <enclosure url="https://eprint.iacr.org/2022/234.pdf" length="0" type="application/pdf"/>
1103 <pubDate>Fri, 25 Feb 2022 08:08:34 +0000</pubDate>
1104 <dc:creator>Luca De Feo</dc:creator>
1105 <dc:creator>Antonin Leroux</dc:creator>
1106 <dc:creator>Patrick Longa</dc:creator>
1107 <dc:creator>Benjamin Wesolowski</dc:creator>
1108 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1109 </item>
1110 <item>
1111 <title>A Lower Bound on the Share Size in Evolving Secret Sharing</title>
1112 <link>https://eprint.iacr.org/2023/129</link>
1113 <description>Secret sharing schemes allow sharing a secret between a set of parties in a way that ensures that only authorized subsets of the parties learn the secret. Evolving secret sharing schemes (Komargodski, Naor, and Yogev [TCC ’16]) allow achieving this end in a scenario where the parties arrive in an online fashion, and there is no a-priory bound on the number of parties.
1114 An important complexity measure of a secret sharing scheme is the share size, which is the maximum number of bits that a party may receive as a share. While there has been a significant progress in recent years, the best constructions for both secret sharing and evolving secret sharing schemes have a share size that is exponential in the number of parties. On the other hand, the best lower bound, by Csirmaz [Eurocrypt ’95], is sub-linear.
1115 In this work, we give a tight lower bound on the share size of evolving secret sharing schemes. Specifically, we show that the sub-linear lower bound of Csirmaz implies an exponential lower bound on evolving secret sharing.</description>
1116 <guid isPermaLink="true">https://eprint.iacr.org/2023/129</guid>
1117 <category>Foundations</category>
1118 <enclosure url="https://eprint.iacr.org/2023/129.pdf" length="0" type="application/pdf"/>
1119 <pubDate>Fri, 03 Feb 2023 19:49:24 +0000</pubDate>
1120 <dc:creator>Noam Mazor</dc:creator>
1121 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1122 </item>
1123 <item>
1124 <title>Does the Dual-Sieve Attack on Learning with Errors even Work?</title>
1125 <link>https://eprint.iacr.org/2023/302</link>
1126 <description>Guo and Johansson (ASIACRYPT 2021), and MATZOV (tech.~report 2022) have independently claimed improved attacks against various NIST lattice candidate by adding a Fast Fourier Transform (FFT) trick on top of the so-called Dual-Sieve attack. Recently, there was more follow up work in this line adding new practical improvements.
1127
1128 However, from a theoretical perspective, all of these works are painfully specific to Learning with Errors, while the principle of the Dual-Sieve attack is more general (Laarhoven & Walter, CT-RSA 2021). More critically, all of these works are based on heuristics that have received very little theoretical and experimental attention.
1129
1130 This work attempts to rectify the above deficiencies of the literature.
1131 We first propose a generalization of the FFT trick by Guo and Johansson to arbitrary Bounded Distance Decoding instances. This generalization offers a new improvement to the attack.
1132
1133 We then theoretically explore the underlying heuristics and show that these are in contradiction with formal, unconditional theorems in some regimes, and with well-tested heuristics in other regimes. The specific instantiations of the recent literature fall into this second regime.
1134
1135 We confirm these contradictions with experiments, documenting several phenomena that are not predicted by the analysis, including a ``waterfall-floor'' phenomenon, reminiscent of Low-Density Parity-Check decoding failures.
1136
1137 We conclude that the success probability of the recent Dual-Sieve-FFT attacks are presumably significantly overestimated. We further discuss the adequate way forward towards fixing the attack and its analysis.</description>
1138 <guid isPermaLink="true">https://eprint.iacr.org/2023/302</guid>
1139 <enclosure url="https://eprint.iacr.org/2023/302.pdf" length="0" type="application/pdf"/>
1140 <pubDate>Tue, 28 Feb 2023 17:01:10 +0000</pubDate>
1141 <dc:creator>Léo Ducas</dc:creator>
1142 <dc:creator>Ludo Pulles</dc:creator>
1143 <dc:rights>https://creativecommons.org/publicdomain/zero/1.0/</dc:rights>
1144 </item>
1145 <item>
1146 <title>On Circuit Private, Multikey and Threshold Approximate Homomorphic Encryption</title>
1147 <link>https://eprint.iacr.org/2023/301</link>
1148 <description>Homomorphic encryption for approximate arithmetic allows one to encrypt discretized real/complex numbers and evaluate arithmetic circuits over them. The first scheme, called CKKS, was introduced by Cheon et al. (Asiacrypt 2017) and gained tremendous attention. The hype for CKKS-type encryption stems from its potential to be used in inference or multiparty computation tasks that do not require the exact output, for example, inference and training of machine learning models.
1149
1150 A desirable property for homomorphic encryption is circuit privacy, which requires that a ciphertext leaks no information on the computation performed to obtain it. Despite numerous improvements, directed toward improving efficiency, the question of circuit privacy for approximate homomorphic encryption remains open.
1151
1152 In this paper, we give the first formal study of circuit privacy for homomorphic encryption over approximate arithmetic. We introduce formal models that allow us to reason about circuit privacy. Then, we show that approximate homomorphic encryption can be made circuit private using tools from differential privacy with appropriately chosen parameters. In particular, we show that by applying an exponential (in the security parameter) Gaussian noise on the evaluated ciphertext, we remove useful information on the circuit from the ciphertext. Crucially, we show that the noise parameter is tight, and taking a lower one leads to an efficient adversary against such a system.
1153
1154 We expand our definitions and analysis to the case of multikey and threshold homomorphic encryption for approximate arithmetic. Such schemes allow users to evaluate a function on their combined inputs and learn the output without leaking anything on the inputs. A special case of multikey and threshold encryption schemes defines a so-called partial decryption algorithm where each user publishes a ``masked'' version of its secret key, allowing all users to decrypt a ciphertext. Similarly, in this case, we show that applying a proper differentially private mechanism gives us IND-CPA-style security where the adversary additionally gets as input the partial decryptions. This is the first security analysis of approximate homomorphic encryption schemes that consider the knowledge of partial decryptions. We show lower bounds on the differential privacy noise that needs to be applied to retain security. Analogously, in the case of circuit privacy, the noise must be exponential in the security parameter. We conclude by showing the impact of the noise on the precision of CKKS-type schemes.</description>
1155 <guid isPermaLink="true">https://eprint.iacr.org/2023/301</guid>
1156 <category>Public-key cryptography</category>
1157 <enclosure url="https://eprint.iacr.org/2023/301.pdf" length="0" type="application/pdf"/>
1158 <pubDate>Tue, 28 Feb 2023 16:33:04 +0000</pubDate>
1159 <dc:creator>Kamil Kluczniak</dc:creator>
1160 <dc:creator>Giacomo Santato</dc:creator>
1161 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1162 </item>
1163 <item>
1164 <title>CNF Characterization of Sets over $\mathbb{Z}_2^n$ and Its Applications in Cryptography</title>
1165 <link>https://eprint.iacr.org/2023/300</link>
1166 <description>In recent years, the automatic search has been widely used to search differential characteristics and linear approximations with high probability/correlation. Among these methods, the automatic search with the Boolean Satisfiability Problem (SAT, in short) gradually becomes a powerful cryptanalysis tool in symmetric ciphers. A key problem in the automatic search method is how to fully characterize a set $S \subseteq \{0,1\}^n$ with as few Conjunctive Normal Form (CNF, in short) clauses as possible, which is called a full CNF characterization (FCC, in short) problem. In this work, we establish a complete theory to solve a best solution of a FCC problem. Specifically, we start from plain sets, which can be characterized by exactly one clause. By exploring mergeable sets, we find a sufficient and necessary condition for characterizing a plain set. Based on the properties of plain sets, we further provide an algorithm for solving a FCC problem with $S$, which can generate all the minimal plain closures of $S$ and produce a best FCC theoretically. We also apply our algorithm to S-boxes used in block ciphers to characterize their differential distribution tables and linear approximation tables. All of our FCCs are the best-known results at present.</description>
1167 <guid isPermaLink="true">https://eprint.iacr.org/2023/300</guid>
1168 <category>Attacks and cryptanalysis</category>
1169 <enclosure url="https://eprint.iacr.org/2023/300.pdf" length="0" type="application/pdf"/>
1170 <pubDate>Tue, 28 Feb 2023 15:00:36 +0000</pubDate>
1171 <dc:creator>Hu Xiaobo</dc:creator>
1172 <dc:creator>Xu Shengyuan</dc:creator>
1173 <dc:creator>Tu Yinzi</dc:creator>
1174 <dc:creator>Feng Xiutao</dc:creator>
1175 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1176 </item>
1177 <item>
1178 <title>BalanceProofs: Maintainable Vector Commitments with Fast Aggregation</title>
1179 <link>https://eprint.iacr.org/2022/864</link>
1180 <description>We present BalanceProofs, the first vector commitment that is maintainable (i.e., supporting sublinear updates) while also enjoying fast proof aggregation and verification. The basic version of BalanceProofs has $O(\sqrt{n}\log n)$ update time and $O(\sqrt{n})$ query time and its constant-size aggregated proofs can be produced and verified in milliseconds. In particular, BalanceProofs improves the aggregation time and aggregation verification time of the only known maintainable and aggregatable vector commitment scheme, Hyperproofs (USENIX SECURITY 2022), by up to 1000$\times$ and up to 100$\times$ respectively. Fast verification of aggregated proofs is particularly useful for applications such as stateless cryptocurrencies (and was a major bottleneck for Hyperproofs), where an aggregated proof of balances is produced once but must be verified multiple times and by a large number of nodes. As a limitation, the updating time in BalanceProofs compared to Hyperproofs is roughly $6\times$ slower, but always stays in the range from 10 to 18 milliseconds. We finally study useful tradeoffs in BalanceProofs between (aggregate) proof size, update time and (aggregate) proof computation and verification, by introducing a bucketing technique, and present an extensive evaluation as well as a comparison to Hyperproofs.</description>
1181 <guid isPermaLink="true">https://eprint.iacr.org/2022/864</guid>
1182 <category>Cryptographic protocols</category>
1183 <enclosure url="https://eprint.iacr.org/2022/864.pdf" length="0" type="application/pdf"/>
1184 <pubDate>Fri, 01 Jul 2022 16:17:40 +0000</pubDate>
1185 <dc:creator>Weijie Wang</dc:creator>
1186 <dc:creator>Annie Ulichney</dc:creator>
1187 <dc:creator>Charalampos Papamanthou</dc:creator>
1188 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1189 </item>
1190 <item>
1191 <title>OpenPubkey: Augmenting OpenID Connect with User held Signing Keys</title>
1192 <link>https://eprint.iacr.org/2023/296</link>
1193 <description>OpenPubkey makes a client-side modification to OpenID Connect so that an ID Token issued by an OpenID Provider commits to a user held public key. This transforms an ID Token into a certificate that cryptographically binds an OpenID Connect identity to a public key. We call such an ID Token, a PK Token. The user can then sign messages with their signing key and these signatures can be authenticated and attributed to the user’s OpenID Connect identity. This allows OpenPubkey to upgrade OpenID Connect from Bearer Authentication to Proof-of-Possession, eliminating trust assumptions in OpenID Connect and defeating entire categories of attacks present in OpenID Connect. OpenPubkey was designed to satisfy a decade-long need for this functionality. Prior to OpenPubkey, OpenID Connect did not have a secure way for users to sign statements under their OpenID identities.
1194
1195 OpenPubkey is transparent to users and OpenID Providers. An OpenID Provider can not even determine that OpenPubkey is being used. This makes OpenPubkey fully compatible with existing OpenID Providers. In fact a variant of OpenPubkey is currently deployed and used to authenticate signed messages and identities for users with accounts on Google, Microsoft, Okta, and Onelogin. OpenPubkey does not add new trusted parties to OpenID Connect and reduces preexisting trust assumptions. If used in tandem with our MFA-cosigner, OpenPubkey can maintain security even against a malicious OpenID Provider (the most trusted party in OpenID Connect).</description>
1196 <guid isPermaLink="true">https://eprint.iacr.org/2023/296</guid>
1197 <category>Cryptographic protocols</category>
1198 <enclosure url="https://eprint.iacr.org/2023/296.pdf" length="0" type="application/pdf"/>
1199 <pubDate>Mon, 27 Feb 2023 21:31:37 +0000</pubDate>
1200 <dc:creator>Ethan Heilman</dc:creator>
1201 <dc:creator>Lucie Mugnier</dc:creator>
1202 <dc:creator>Athanasios Filippidis</dc:creator>
1203 <dc:creator>Sharon Goldberg</dc:creator>
1204 <dc:creator>Sebastien Lipman</dc:creator>
1205 <dc:creator>Yuval Marcus</dc:creator>
1206 <dc:creator>Mike Milano</dc:creator>
1207 <dc:creator>Sidhartha Premkumar</dc:creator>
1208 <dc:creator>Chad Unrein</dc:creator>
1209 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1210 </item>
1211 <item>
1212 <title>Approximate Modeling of Signed Difference and Digraph based Bit Condition Deduction: New Boomerang Attacks on BLAKE</title>
1213 <link>https://eprint.iacr.org/2023/299</link>
1214 <description>The signed difference is a powerful tool for analyzing the Addition, XOR, Rotation (ARX) cryptographic primitives. Currently, solving the accurate model for the signed difference propagation is infeasible.
1215 We propose an approximate MILP modeling method capturing the propagation rules of signed differences. Unlike the accurate signed difference model, the approximate model only focuses on active bits and ignores the possible bit conditions on inactive bits.
1216 To overcome the negative effect of a lower accuracy arising from ignoring bit conditions on inactive bits, we propose an additional tool for deducing all bit conditions automatically.
1217 Such a tool is based on a directed-graph capturing the whole computation process of ARX primitives by drawing links among intermediate words and operations.
1218 The digraph is also applicable in the MILP model construction process:
1219 it enables us to identify the parameters upper bounding the number of bit conditions so as to define the objective function; it is further used to connect the boomerang top and bottom signed differential paths by introducing proper constraints to avoid incompatible intersections.
1220 Benefiting from the approximate model and the directed-graph based tool, the solving time of the new MILP model is significantly reduced,
1221 enabling us to deduce signed differential paths efficiently and accurately.
1222
1223 To show the utility of our method, we propose boomerang attacks on the keyed permutations of three ARX hash functions of BLAKE.
1224 For the first time we mount an attack on the full 7 rounds of BLAKE3, with the complexity as low as $2^{180}$.
1225 Our best attack on BLAKE2s can improve the previously best result by 0.5 rounds but with lower complexity.
1226 The attacks on BLAKE-256 cover the same 8 rounds with the previous best result but with complexity $2^{16}$ times lower.
1227 All our results are verified practically with round-reduced boomerang quartets.</description>
1228 <guid isPermaLink="true">https://eprint.iacr.org/2023/299</guid>
1229 <category>Attacks and cryptanalysis</category>
1230 <enclosure url="https://eprint.iacr.org/2023/299.pdf" length="0" type="application/pdf"/>
1231 <pubDate>Tue, 28 Feb 2023 10:32:29 +0000</pubDate>
1232 <dc:creator>Yonglin Hao</dc:creator>
1233 <dc:creator>Qingju Wang</dc:creator>
1234 <dc:creator>Lin Jiao</dc:creator>
1235 <dc:creator>Xinxin Gong</dc:creator>
1236 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1237 </item>
1238 <item>
1239 <title>Functional Commitments for All Functions, with Transparent Setup and from SIS</title>
1240 <link>https://eprint.iacr.org/2022/1368</link>
1241 <description>A *functional commitment* scheme enables a user to concisely commit to a function from a specified family, then later concisely and verifiably reveal values of the function at desired inputs. Useful special cases, which have seen applications across cryptography, include vector commitments and polynomial commitments.
1242
1243 To date, functional commitments have been constructed (under falsifiable assumptions) only for functions that are essentially *linear*, with one recent exception that works for arbitrarily complex functions. However, that scheme operates in a strong and non-standard model, requiring an online, trusted authority to generate special keys for any opened function inputs.
1244
1245 In this work, we give the first functional commitment scheme for nonlinear functions---indeed, for *all functions* of any bounded complexity---under a standard setup and a falsifiable assumption. Specifically, the setup is ``transparent,'' requiring only public randomness (and not any trusted entity), and the assumption is the hardness of the standard Short Integer Solution (SIS) lattice problem. Our construction also has other attractive features, including: *stateless updates* via generic composability; excellent *asymptotic efficiency* for the verifier, and also for the committer in important special cases like vector and polynomial commitments, via preprocessing; and *post-quantum security*, since it is based on SIS.</description>
1246 <guid isPermaLink="true">https://eprint.iacr.org/2022/1368</guid>
1247 <category>Public-key cryptography</category>
1248 <enclosure url="https://eprint.iacr.org/2022/1368.pdf" length="0" type="application/pdf"/>
1249 <pubDate>Tue, 11 Oct 2022 18:59:59 +0000</pubDate>
1250 <dc:creator>Leo de Castro</dc:creator>
1251 <dc:creator>Chris Peikert</dc:creator>
1252 <dc:rights>https://creativecommons.org/licenses/by-nc-nd/4.0/</dc:rights>
1253 </item>
1254 <item>
1255 <title>Randomized Half-Ideal Cipher on Groups with applications to UC (a)PAKE</title>
1256 <link>https://eprint.iacr.org/2023/295</link>
1257 <description>An Ideal Cipher (IC) is a cipher where each key defines a random permutation on the domain. Ideal Cipher on a group has many attractive applications, e.g., the Encrypted Key Exchange (EKE) protocol for Password Authenticated Key Exchange (PAKE) [10], or
1258 asymmetric PAKE (aPAKE) [40, 36]. However, known constructions for IC on a group domain all have drawbacks, including key leakage from timing information [15], requiring 4 hash-onto-group operations if IC is an 8-round Feistel [27], and limiting the domain to half the group [12] or using variable-time encoding [56, 48] if IC is implemented via (quasi-) bijections from groups to bitstrings [40].
1259
1260 We propose an IC relaxation called a (Randomized) Half-Ideal Cipher (HIC), and we show that HIC on a group can be realized by a modified 2-round Feistel (m2F), at a cost of 1 hash-onto-group operation, which beats existing IC constructions in versatility and computational cost. HIC weakens IC properties by letting part of the ciphertext be non-random, but we exemplify that it can be used as a drop-in replacement for IC by showing that EKE [10] and aPAKE of [40] realize respectively UC PAKE and UC aPAKE even if they use HIC instead of IC. The m2F construction can also serve as IC domain extension, because m2F constructs HIC on domain D from an RO-indiferrentiable hash onto D and an IC on 2κ-bit strings, for κ a security parameter. One application of such extender is a modular lattice-based UC PAKE using EKE instantiated with HIC and anonymous lattice-based KEM.</description>
1261 <guid isPermaLink="true">https://eprint.iacr.org/2023/295</guid>
1262 <category>Cryptographic protocols</category>
1263 <enclosure url="https://eprint.iacr.org/2023/295.pdf" length="0" type="application/pdf"/>
1264 <pubDate>Mon, 27 Feb 2023 19:51:28 +0000</pubDate>
1265 <dc:creator>Bruno Freitas Dos Santos</dc:creator>
1266 <dc:creator>Yanqi Gu</dc:creator>
1267 <dc:creator>Stanislaw Jarecki</dc:creator>
1268 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1269 </item>
1270 <item>
1271 <title>New Records in Collision Attacks on RIPEMD-160 and SHA-256</title>
1272 <link>https://eprint.iacr.org/2023/285</link>
1273 <description>RIPEMD-160 and SHA-256 are two hash functions used to generate the bitcoin address. In particular, RIPEMD-160 is an ISO/IEC standard and SHA-256 has been widely used in the world. Due to their complex designs, the progress to find (semi-free-start) collisions for the two hash functions is slow. Recently at EUROCRYPT 2023, Liu et al. presented the first collision attack on 36 steps of RIPEMD-160 and the first MILP-based method to find collision-generating signed differential characteristics. We continue this line of research and implement the MILP-based method with a SAT/SMT-based method. Furthermore, we observe that the collision attack on RIPEMD-160 can be improved to 40 steps with different message differences. We have practically found a colliding message pair for 40-step RIPEMD-160 in 16 hours with 115 threads. Moreover, we also report the first semi-free-start (SFS) colliding message pair for 39-step SHA-256, which can be found in about 3 hours with 120 threads. These results update the best (SFS) collision attacks on RIPEMD-160 and SHA-256. Especially, we have made some progress on SHA-256 since the last update on (SFS) collision attacks on it at EUROCRYPT 2013, where the first practical SFS collision attack on 38-step SHA-256 was found.</description>
1274 <guid isPermaLink="true">https://eprint.iacr.org/2023/285</guid>
1275 <category>Attacks and cryptanalysis</category>
1276 <enclosure url="https://eprint.iacr.org/2023/285.pdf" length="0" type="application/pdf"/>
1277 <pubDate>Sat, 25 Feb 2023 13:25:23 +0000</pubDate>
1278 <dc:creator>Yingxin Li</dc:creator>
1279 <dc:creator>Fukang Liu</dc:creator>
1280 <dc:creator>Gaoli Wang</dc:creator>
1281 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1282 </item>
1283 <item>
1284 <title>Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions</title>
1285 <link>https://eprint.iacr.org/2022/431</link>
1286 <description>In this work we give the first non-adaptive construction of universal one-way hash functions (UOWHFs) from arbitrary one-way functions. Our construction uses $O(n^9)$ calls to the one-way function, has a key of length $O(n^{10})$, and can be implemented in NC1 assuming the underlying one-way function is in NC1.
1287
1288 Prior to this work, the best UOWHF construction used O(n13) adaptive calls and a key of size O(n5) (Haitner, Holenstein, Reingold, Vadhan and Wee [Eurocrypt ’10]). By the result of Applebaum, Ishai and Kushilevitz [FOCS ’04], the above implies the existence of UOWHFs in NC0, given the existence of one-way functions in NC1.
1289
1290 We also show that the PRG construction of Haitner, Reingold and Vadhan (HRV, [STOC ’10]), with small modifications, yields a relaxed notion of UOWHFs , which is a function family which can be (inefficiently) converted to UOWHF by changing the functions on a negligible fraction of the inputs. In order to analyze this construction, we introduce the notion of next-bit unreachable entropy, which replaces the next-bit pseudoentropy notion used by HRV.</description>
1291 <guid isPermaLink="true">https://eprint.iacr.org/2022/431</guid>
1292 <category>Foundations</category>
1293 <enclosure url="https://eprint.iacr.org/2022/431.pdf" length="0" type="application/pdf"/>
1294 <pubDate>Wed, 06 Apr 2022 13:07:22 +0000</pubDate>
1295 <dc:creator>Xinyu Mao</dc:creator>
1296 <dc:creator>Noam Mazor</dc:creator>
1297 <dc:creator>Jiapeng Zhang</dc:creator>
1298 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1299 </item>
1300 <item>
1301 <title>Hardening Signature Schemes via Derive-then-Derandomize: Stronger Security Proofs for EdDSA</title>
1302 <link>https://eprint.iacr.org/2023/298</link>
1303 <description>We consider a transform, called Derive-then-Derandomize, that hardens a given signature scheme against randomness failure and implementation error. We prove that it works. We then give a general lemma showing indifferentiability of Shrink-MD, a class of constructions that apply a shrinking output transform to an MD-style hash function. Armed with these tools, we give new proofs for the widely standardized and used EdDSA signature scheme, improving prior work in two ways: (1) we give proofs for the case that the hash function is an MD-style one, reflecting the use of SHA512 in the NIST standard, and (2) we improve the tightness of the reduction so that one has guarantees for group sizes in actual use.</description>
1304 <guid isPermaLink="true">https://eprint.iacr.org/2023/298</guid>
1305 <category>Public-key cryptography</category>
1306 <enclosure url="https://eprint.iacr.org/2023/298.pdf" length="0" type="application/pdf"/>
1307 <pubDate>Mon, 27 Feb 2023 23:29:34 +0000</pubDate>
1308 <dc:creator>Mihir Bellare</dc:creator>
1309 <dc:creator>Hannah Davis</dc:creator>
1310 <dc:creator>Zijing Di</dc:creator>
1311 <dc:rights>https://creativecommons.org/publicdomain/zero/1.0/</dc:rights>
1312 </item>
1313 <item>
1314 <title>Optimal Single-Server Private Information Retrieval</title>
1315 <link>https://eprint.iacr.org/2022/609</link>
1316 <description>We construct a single-server
1317 pre-processing Private Information Retrieval
1318 (PIR) scheme
1319 with optimal bandwidth
1320 and server computation (up to poly-logarithmic factors), assuming
1321 hardness of the Learning With Errors (LWE) problem.
1322 Our scheme achieves
1323 amortized
1324 $\widetilde{O}_{\lambda}(\sqrt{n})$
1325 server and client computation and $\widetilde{O}_\lambda(1)$
1326 bandwidth per query, completes in a single roundtrip, and requires
1327 $\widetilde{O}_\lambda(\sqrt{n})$
1328 client storage.
1329 In particular, we achieve a significant
1330 reduction in bandwidth over the
1331 state-of-the-art scheme by Corrigan-Gibbs,
1332 Henzinger, and Kogan (Eurocrypt'22):
1333 their scheme requires as much as
1334 $\widetilde{O}_{\lambda}(\sqrt{n})$
1335 bandwidth per query, with comparable
1336 computational and storage overhead as ours.</description>
1337 <guid isPermaLink="true">https://eprint.iacr.org/2022/609</guid>
1338 <category>Cryptographic protocols</category>
1339 <enclosure url="https://eprint.iacr.org/2022/609.pdf" length="0" type="application/pdf"/>
1340 <pubDate>Mon, 23 May 2022 08:20:59 +0000</pubDate>
1341 <dc:creator>Mingxun Zhou</dc:creator>
1342 <dc:creator>Wei-Kai Lin</dc:creator>
1343 <dc:creator>Yiannis Tselekounis</dc:creator>
1344 <dc:creator>Elaine Shi</dc:creator>
1345 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1346 </item>
1347 <item>
1348 <title>New Results on Machine Learning Based Distinguishers</title>
1349 <link>https://eprint.iacr.org/2023/235</link>
1350 <description>Machine Learning (ML) is almost ubiquitously used in multiple disciplines nowadays. Recently, we have seen its usage in the realm of differential distinguishers for symmetric key ciphers. In this work, we explore the possibility of a number of ciphers with respect to various ML-based distinguishers.
1351
1352 We show new distinguishers on the unkeyed and round reduced version of SPECK-32, SPECK-128, ASCON, SIMECK-32, SIMECK-64 and SKINNY-128. We explore multiple avenues in the process. In summary, we use neural network as well as support vector machine in various settings (such as varying the activation function), apart from experimenting with a number of input difference tuples. Among other results, we show a distinguisher of 8-round SPECK-32 that works with practical data complexity (most of the experiments take a few hours on a personal computer).</description>
1353 <guid isPermaLink="true">https://eprint.iacr.org/2023/235</guid>
1354 <category>Secret-key cryptography</category>
1355 <enclosure url="https://eprint.iacr.org/2023/235.pdf" length="0" type="application/pdf"/>
1356 <pubDate>Mon, 20 Feb 2023 20:18:35 +0000</pubDate>
1357 <dc:creator>Anubhab Baksi</dc:creator>
1358 <dc:creator>Jakub Breier</dc:creator>
1359 <dc:creator>Vishnu Asutosh Dasu</dc:creator>
1360 <dc:creator>Xiaolu Hou</dc:creator>
1361 <dc:creator>Hyunji Kim</dc:creator>
1362 <dc:creator>Hwajeong Seo</dc:creator>
1363 <dc:rights>https://creativecommons.org/licenses/by-nc-sa/4.0/</dc:rights>
1364 </item>
1365 <item>
1366 <title>Towards A Correct-by-Construction FHE Model</title>
1367 <link>https://eprint.iacr.org/2023/281</link>
1368 <description>This paper presents a correct-by-construction method of designing an FHE model based on the automated program verifier Dafny. We model FHE operations from the ground up, including fundamentals like GCD, coprimality, Montgomery multiplications, and polynomial operations, etc., and higher level optimizations such as Residue Number System (RNS) and Number Theoretic Transform (NTT). The fully formally verified FHE model serves as a reference design for both software stack development and hardware design, and verification efforts. Open-sourcing our FHE Dafny model with modular arithmetic libraries to GitHub is in progress.</description>
1369 <guid isPermaLink="true">https://eprint.iacr.org/2023/281</guid>
1370 <category>Implementation</category>
1371 <enclosure url="https://eprint.iacr.org/2023/281.pdf" length="0" type="application/pdf"/>
1372 <pubDate>Fri, 24 Feb 2023 18:12:45 +0000</pubDate>
1373 <dc:creator>Zhenkun Yang</dc:creator>
1374 <dc:creator>Wen Wang</dc:creator>
1375 <dc:creator>Jeremy Casas</dc:creator>
1376 <dc:creator>Pasquale Cocchini</dc:creator>
1377 <dc:creator>Jin Yang</dc:creator>
1378 <dc:rights>https://creativecommons.org/licenses/by-nc-nd/4.0/</dc:rights>
1379 </item>
1380 <item>
1381 <title>DIPSAUCE: Efficient Private Stream Aggregation Without Trusted Parties</title>
1382 <link>https://eprint.iacr.org/2023/214</link>
1383 <description>Private Stream Aggregation (PSA) schemes are efficient protocols for distributed data analytics. In a PSA scheme, a set of data producers can encrypt data for a central party so that it learns the sum of all (encrypted) values, but nothing about each individual value. Due to this ability to efficiently enable central data analytics without leaking individual user data, PSA schemes are often used for IoT data analytics scenarios where privacy is important, such as smart metering. However, all known PSA schemes require a trusted party for key generation, which is undesirable from a privacy standpoint. Further, even though the main benefit of PSA schemes over alternative technologies such as Functional Encryption is that they are efficient enough to run on IoT devices, there exists no evaluation of the efficiency of existing PSA schemes on realistic IoT devices.
1384
1385 In this paper, we address both these issues. We first evaluate the efficiency of the state of the art PSA schemes on realistic IoT devices. We then propose, implement and evaluate a DIstributed setup PSA scheme for Use in Constrained Environments (DIPSAUCE). DIPSAUCE is the first PSA scheme that does not rely on a trusted party. Our security and efficiency evaluation shows that it is indeed possible to construct an efficient PSA scheme without a trusted central party. Surprisingly, our results also show that, a side effect, our method for distributing the setup procedure also makes the encryption procedure more efficient than the state of the art PSA schemes which rely on trusted parties.</description>
1386 <guid isPermaLink="true">https://eprint.iacr.org/2023/214</guid>
1387 <category>Cryptographic protocols</category>
1388 <enclosure url="https://eprint.iacr.org/2023/214.pdf" length="0" type="application/pdf"/>
1389 <pubDate>Fri, 17 Feb 2023 10:45:48 +0000</pubDate>
1390 <dc:creator>Joakim Brorsson</dc:creator>
1391 <dc:creator>Martin Gunnarsson</dc:creator>
1392 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1393 </item>
1394 <item>
1395 <title>A Cryptographic Analysis of the TLS 1.3 Handshake Protocol</title>
1396 <link>https://eprint.iacr.org/2020/1044</link>
1397 <description>We analyze the handshake protocol of the Transport Layer Security (TLS) protocol, version 1.3. We address both the full TLS 1.3 handshake (the one round-trip time mode, with signatures for authentication and (elliptic curve) Diffie–Hellman ephemeral ((EC)DHE) key exchange), and the abbreviated resumption/"PSK" mode which uses a pre-shared key for authentication (with optional (EC)DHE key exchange and zero round-trip time key establishment). Our analysis in the reductionist security framework uses a multi-stage key exchange security model, where each of the many session keys derived in a single TLS 1.3 handshake is tagged with various properties (such as unauthenticated versus unilaterally authenticated versus mutually authenticated, whether it is intended to provide forward security, how it is used in the protocol, and whether the key is protected against replay attacks). We show that these TLS 1.3 handshake protocol modes establish session keys with their desired security properties under standard cryptographic assumptions.</description>
1398 <guid isPermaLink="true">https://eprint.iacr.org/2020/1044</guid>
1399 <category>Cryptographic protocols</category>
1400 <enclosure url="https://eprint.iacr.org/2020/1044.pdf" length="0" type="application/pdf"/>
1401 <pubDate>Fri, 28 Aug 2020 18:52:40 +0000</pubDate>
1402 <dc:creator>Benjamin Dowling</dc:creator>
1403 <dc:creator>Marc Fischlin</dc:creator>
1404 <dc:creator>Felix Günther</dc:creator>
1405 <dc:creator>Douglas Stebila</dc:creator>
1406 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1407 </item>
1408 <item>
1409 <title>DORCIS: Depth Optimized Quantum Implementation of Substitution Boxes</title>
1410 <link>https://eprint.iacr.org/2023/286</link>
1411 <description>In this paper, we present the ``DORCIS'' tool, which finds depth-optimized quantum circuit implementations for arbitrary 3- and 4-bit S-boxes. It follows up from the previous LIGHTER-R tool (which only works for 4-bit S-boxes) by extending it in multiple ways. LIGHTER-R only deals at the top level (i.e., Toffoli gates), whereas DORCIS takes quantum decomposition (i.e., Clifford + T gates) into account. Further, DORCIS optimizes for quantum depth and T depth. We match, if not surpass, other optimized quantum circuit implementations put forth in the other papers. Similar to LIGHTER-R, our tool is also easy to use, and we provide an extended interface to IBM's Qiskit.</description>
1412 <guid isPermaLink="true">https://eprint.iacr.org/2023/286</guid>
1413 <category>Secret-key cryptography</category>
1414 <enclosure url="https://eprint.iacr.org/2023/286.pdf" length="0" type="application/pdf"/>
1415 <pubDate>Sat, 25 Feb 2023 22:11:32 +0000</pubDate>
1416 <dc:creator>Matthew Chun</dc:creator>
1417 <dc:creator>Anubhab Baksi</dc:creator>
1418 <dc:creator>Anupam Chattopadhyay</dc:creator>
1419 <dc:rights>https://creativecommons.org/licenses/by-nc-nd/4.0/</dc:rights>
1420 </item>
1421 <item>
1422 <title>Lower Bound Framework for Differentially Private and Oblivious Data Structures</title>
1423 <link>https://eprint.iacr.org/2022/1553</link>
1424 <description>In recent years, there has been significant work in studying data structures that provide privacy for the operations that are executed. These primitives aim to guarantee that observable access patterns to physical memory do not reveal substantial information about the queries and updates executed on the data structure. Multiple recent works, including Larsen and Nielsen [Crypto'18], Persiano and Yeo [Eurocrypt'19], Hubáček et al. [TCC'19] and Komargodski and Lin [Crypto'21], have shown that logarithmic overhead is required to support even basic RAM (array) operations for various privacy notions including obliviousness and differential privacy as well as different choices of sizes for RAM blocks $b$ and memory cells $\omega$.
1425
1426 We continue along this line of work and present the first logarithmic lower bounds for differentially private RAMs (DPRAMs) that apply regardless of the sizes of blocks $b$ and cells $\omega$. This is the first logarithmic lower bounds for DPRAMs when blocks are significantly smaller than cells, that is $b \ll \omega$. Furthermore, we present new logarithmic lower bounds for differentially private variants of classical data structure problems including sets, predecessor (successor) and disjoint sets (union-find) for which sub-logarithmic plaintext constructions are known. All our lower bounds extend to the multiple non-colluding servers setting.
1427
1428 We also address an unfortunate issue with this rich line of work where the lower bound techniques are difficult to use and require customization for each new result. To make the techniques more accessible, we generalize our proofs into a framework that reduces proving logarithmic lower bounds to showing that a specific problem satisfies two simple, minimal conditions. We show our framework is easy-to-use as all the lower bounds in our paper utilize the framework and hope our framework will spur more usage of these lower bound techniques.</description>
1429 <guid isPermaLink="true">https://eprint.iacr.org/2022/1553</guid>
1430 <category>Cryptographic protocols</category>
1431 <enclosure url="https://eprint.iacr.org/2022/1553.pdf" length="0" type="application/pdf"/>
1432 <pubDate>Tue, 08 Nov 2022 14:48:09 +0000</pubDate>
1433 <dc:creator>Giuseppe Persiano</dc:creator>
1434 <dc:creator>Kevin Yeo</dc:creator>
1435 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1436 </item>
1437 <item>
1438 <title>The Return of the SDitH</title>
1439 <link>https://eprint.iacr.org/2022/1645</link>
1440 <description>This paper presents a code-based signature scheme based on the well-known syndrome decoding (SD) problem. The scheme builds upon a recent line of research which uses the Multi-Party-Computation-in-the-Head (MPCitH) approach to construct efficient zero-knowledge proofs, such as Syndrome Decoding in the Head (SDitH), and builds signature schemes from them using the Fiat-Shamir transform.
1441
1442 At the heart of our proposal is a new approach, Hypercube-MPCitH, to amplify the soundness of any MPC protocol that uses additive secret sharing. An MPCitH protocol with $N$ parties can be repeated $D$ times using parallel composition to reach the same soundness as a protocol run with $N^D$ parties. However, the former comes with $D$ times higher communication costs, often mainly contributed by the usage of $D$ `auxiliary' states (which in general have a significantly bigger impact on size than random states). Instead of that, we begin by generating $N^D$ shares, arranged into a $D$-dimensional hypercube of side $N$ containing only one `auxiliary' state. We derive from this hypercube $D$ sharings of size $N$ which are used to run $D$ instances of an $N$ party MPC protocol. Hypercube-MPCitH leads to a protocol with $1/N^D$ soundness error, requiring $N^D$ offline computation, but with only $N\cdot D$ online computation, and only $1$ `auxiliary'. As the (potentially offline) share generation phase is generally inexpensive, this leads to trade-offs that are superior to just using parallel composition.
1443
1444 Our novel method of share generation and aggregation not only improves certain MPCitH protocols in general but also shows in concrete improvements of signature schemes. Specifically, we apply it to the work of Feneuil, Joux, and Rivain (CRYPTO'22) on code-based signatures, and obtain a new signature scheme that achieves a 8.1x improvement in global runtime and a 30x improvement in online runtime for their shortest signatures size (8,481 Bytes). It is also possible to leverage the fact that most computations are offline to define parameter sets leading to smaller signatures: 6,784 Bytes for 26 ms offline and 5,689 Bytes for 320 ms offline. For NIST security level 1, online signature cost is around 3 million cycles ($<$1 ms on commodity processors), regardless of signature size.</description>
1445 <guid isPermaLink="true">https://eprint.iacr.org/2022/1645</guid>
1446 <category>Public-key cryptography</category>
1447 <enclosure url="https://eprint.iacr.org/2022/1645.pdf" length="0" type="application/pdf"/>
1448 <pubDate>Fri, 25 Nov 2022 18:09:02 +0000</pubDate>
1449 <dc:creator>Carlos Aguilar-Melchor</dc:creator>
1450 <dc:creator>Nicolas Gama</dc:creator>
1451 <dc:creator>James Howe</dc:creator>
1452 <dc:creator>Andreas Hülsing</dc:creator>
1453 <dc:creator>David Joseph</dc:creator>
1454 <dc:creator>Dongze Yue</dc:creator>
1455 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1456 </item>
1457 <item>
1458 <title>SCA-LDPC: A Code-Based Framework for Key-Recovery Side-Channel Attacks on Post-Quantum Encryption Schemes</title>
1459 <link>https://eprint.iacr.org/2023/294</link>
1460 <description>Whereas theoretical attacks on standardized crypto primitives rarely lead to actual practical attacks, the situation is different for side-channel attacks. Improvements in the performance of side-channel attacks are of utmost importance.
1461
1462 In this paper, we propose a framework to be used in key-recovery side-channel attacks on CCA-secure post-quantum encryption schemes. The basic idea is to construct chosen ciphertext queries to a plaintext checking oracle that collects information on a set of secret variables in a single query. Then a large number of such queries is considered, each related to a different set of secret variables, and they are modeled as a low-density parity-check code (LDPC code). Secret variables are finally determined through efficient iterative decoding methods, such as belief propagation, using soft information. The utilization of LDPC codes offers efficient decoding, source compression, and error correction benefits. It has been demonstrated that this approach provides significant improvements compared to previous work by reducing the required number of queries, such as the number of traces in a power attack.
1463
1464 The framework is demonstrated and implemented in two different cases. On one hand, we attack implementations of HQC in a timing attack, lowering the number of required traces considerably compared to attacks in previous work. On the other hand, we describe and implement a full attack on a masked implementation of Kyber using power analysis. Using the ChipWhisperer evaluation platform, our real-world attacks recover the long-term secret key of a first-order masked implementation of Kyber-768 with an average of only 12 power traces.</description>
1465 <guid isPermaLink="true">https://eprint.iacr.org/2023/294</guid>
1466 <category>Attacks and cryptanalysis</category>
1467 <enclosure url="https://eprint.iacr.org/2023/294.pdf" length="0" type="application/pdf"/>
1468 <pubDate>Mon, 27 Feb 2023 14:05:40 +0000</pubDate>
1469 <dc:creator>Qian Guo</dc:creator>
1470 <dc:creator>Denis Nabokov</dc:creator>
1471 <dc:creator>Alexander Nilsson</dc:creator>
1472 <dc:creator>Thomas Johansson</dc:creator>
1473 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1474 </item>
1475 <item>
1476 <title>Mitigating Decentralized Finance Liquidations with Reversible Call Options</title>
1477 <link>https://eprint.iacr.org/2023/254</link>
1478 <description>Liquidations in DeFi are both a blessing and a curse — whereas liquidations prevent lenders from capital loss, they simultaneously lead to liquidation spirals and system-wide failures. Since most lending and borrowing protocols assume liquidations are indispensable, there is an increased interest in alternative constructions that prevent immediate systemic-failure under uncertain circumstances.
1479
1480 In this work, we introduce reversible call options, a novel financial primitive that enables the seller of a call option to terminate it before maturity. We apply reversible call options to lending in DeFi and devise Miqado, a protocol for lending platforms to replace the liquidation mechanisms. To the best of our knowledge, Miqado is the first protocol that actively mitigates liquidations to reduce the risk of liquidation spirals. Instead of selling collateral, Miqado incentivizes external entities, so-called supporters, to top-up a borrowing position and grant the borrower additional time to rescue the debt. Our simulation shows that Miqado reduces the amount of liquidated collateral by 89.82% in a worst-case scenario.</description>
1481 <guid isPermaLink="true">https://eprint.iacr.org/2023/254</guid>
1482 <category>Applications</category>
1483 <enclosure url="https://eprint.iacr.org/2023/254.pdf" length="0" type="application/pdf"/>
1484 <pubDate>Wed, 22 Feb 2023 03:57:30 +0000</pubDate>
1485 <dc:creator>Kaihua Qin</dc:creator>
1486 <dc:creator>Jens Ernstberger</dc:creator>
1487 <dc:creator>Liyi Zhou</dc:creator>
1488 <dc:creator>Philipp Jovanovic</dc:creator>
1489 <dc:creator>Arthur Gervais</dc:creator>
1490 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1491 </item>
1492 <item>
1493 <title>Searching for Gemstones: Flawed Stegosystems May Hide Promissing Ideas</title>
1494 <link>https://eprint.iacr.org/2023/293</link>
1495 <description>The historical domain of information hiding is alternatively used nowadays for communication security. Maybe the oldest and certainly one of the most studied field that falls in this category is steganography. Within the current paper, we focus on image steganography techniques in the case of the JPEG format.
1496 We propose a corrected and optimized version of the J3 stegosystem which, to the best of our knowledge and as shown throughout the paper, may be considered a very good choice in terms of security and efficiency as compared to current solutions. We reconstruct the entire J3 algorithm (pre-processing, message insertion and extraction) and detail all the modifications. We also present implementation optimizations and cover all practical cases while still using the maximum image insertion capacity.</description>
1497 <guid isPermaLink="true">https://eprint.iacr.org/2023/293</guid>
1498 <category>Applications</category>
1499 <enclosure url="https://eprint.iacr.org/2023/293.pdf" length="0" type="application/pdf"/>
1500 <pubDate>Mon, 27 Feb 2023 12:25:07 +0000</pubDate>
1501 <dc:creator>Diana Maimut</dc:creator>
1502 <dc:creator>Evgnosia-Alexandra Kelesidis</dc:creator>
1503 <dc:creator>Ilona Teodora Ciocan</dc:creator>
1504 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1505 </item>
1506 <item>
1507 <title>Asymmetric Trapdoor Pseudorandom Generators: Definitions, Constructions, and Applications to Homomorphic Signatures with Shorter Public Keys</title>
1508 <link>https://eprint.iacr.org/2023/180</link>
1509 <description>We introduce a new primitive called the asymmetric trapdoor pseudorandom generator (ATPRG), which belongs to pseudorandom generators with two additional trapdoors (a public trapdoor and a secret trapdoor) or backdoor pseudorandom generators with an additional trapdoor (a secret trapdoor). Specifically, ATPRG can only generate public pseudorandom numbers $pr_1,\dots,pr_n $ for the users having no knowledge of the public trapdoor and the secret trapdoor; so that this function is the same as pseudorandom generators. However, the users having the public trapdoor can use any public pseudorandom number $pr_i$ to recover the whole $pr$ sequence; so that this function is the same as backdoor pseudorandom generators. Further, the users having the secret trapdoor can use $pr$ sequence to generate a sequence $sr_1,\dots,sr_n$ of the secret pseudorandom numbers.
1510 As for applications of ATPRG, we construct the first homomorphic signature scheme (in the standard model) whose public key size is only $O(T)$ independent of the dataset size. As a comparison, the shortest size of the existing public key is $O(\sqrt{N}+\sqrt{T})$, proposed by Catalano et al. (CRYPTO'15), where $N$ is the dataset size and $T$ is the dimension of the message. In other words, we provide the first homomorphic signature scheme with $O(1)$-sized public keys for the one-dimension messages.</description>
1511 <guid isPermaLink="true">https://eprint.iacr.org/2023/180</guid>
1512 <category>Public-key cryptography</category>
1513 <enclosure url="https://eprint.iacr.org/2023/180.pdf" length="0" type="application/pdf"/>
1514 <pubDate>Mon, 13 Feb 2023 09:58:25 +0000</pubDate>
1515 <dc:creator>Jinpeng Hou</dc:creator>
1516 <dc:creator>Yansong Gao</dc:creator>
1517 <dc:creator>Mang Su</dc:creator>
1518 <dc:creator>Willy Susilo</dc:creator>
1519 <dc:creator>Jie Chen</dc:creator>
1520 <dc:creator>Anmin Fu</dc:creator>
1521 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1522 </item>
1523 <item>
1524 <title>A Formal Treatment of Distributed Key Generation, and New Constructions</title>
1525 <link>https://eprint.iacr.org/2023/292</link>
1526 <description>In this work, we present a novel generic construction for a Distributed Key Generation (DKG) scheme. Our generic construction relies on three modular cryptographic building blocks. The first is an aggregatable Verifiable Secret Sharing (AgVSS) scheme, the second is a Non-Interactive Key Exchange (NIKE) scheme, and the third is a secure hash function. We give formal definitions for the AgVSS and NIKE schemes, as well as concrete constructions. The utility of this generic construction is flexibility; i.e., any aggregatable VSS and NIKE scheme can be employed, and the construction will remain secure.
1527
1528 To prove the security of our generic construction, we introduce formalized game based notions of security for DKGs, building upon existing notions in the literature. However, these prior security notions either were presented informally, omitted important requirements, or assumed certain algebraic structure of the underlying scheme. Our security notions make no such assumption of underlying algebraic structure, and explicitly consider details such as participant consistency, communication patterns, and key validity. Further, our security notions imply simulatability with respect to a target key generation scheme without rewinding. Hence, any construction that is proven secure using our security notions additionally imply UC security.
1529
1530 We then present STORM, a concrete instantiation of our generic construction that is secure in the discrete logarithm setting in the random oracle model. STORM is more efficient than related DKG schemes in the literature. Because of its simple design and composability, it is a practical choice for real world settings and standardization efforts.</description>
1531 <guid isPermaLink="true">https://eprint.iacr.org/2023/292</guid>
1532 <category>Public-key cryptography</category>
1533 <enclosure url="https://eprint.iacr.org/2023/292.pdf" length="0" type="application/pdf"/>
1534 <pubDate>Mon, 27 Feb 2023 01:04:17 +0000</pubDate>
1535 <dc:creator>Chelsea Komlo</dc:creator>
1536 <dc:creator>Ian Goldberg</dc:creator>
1537 <dc:creator>Douglas Stebila</dc:creator>
1538 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1539 </item>
1540 <item>
1541 <title>Actively Secure Half-Gates with Minimum Overhead under Duplex Networks</title>
1542 <link>https://eprint.iacr.org/2023/278</link>
1543 <description>Actively secure two-party computation (2PC) is one of the canonical building blocks
1544 in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols.
1545 In this paper, we propose a new actively secure constant-round 2PC protocol with one-way communication of $2\kappa+5$ bits per AND gate (for $\kappa$-bit computational
1546 security and any statistical security), essentially matching the one-way communication of semi-honest half-gates protocol. This is achieved by two new techniques:
1547
1548 1. The recent compression technique by Dittmer et al. (Crypto 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from $5\rho+1$ bits to $2$ bits per AND gate for $\rho$-bit statistical security.
1549
1550 2. Unfortunately, the above compressing technique is only compatible
1551 with a less compact authenticated garbled circuit of size $2\kappa+3\rho$ bits per AND gate.
1552 We designed a new authenticated garbling that does not use information
1553 theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit.
1554 This allows us to use a more compact half-gates based authenticated garbled circuit of size $2\kappa+1$ bits per AND gate, and meanwhile keep compatible
1555 with the compression technique. Our new technique can achieve one-way communication of $2\kappa+5$ bits per AND gate.
1556
1557 Our technique of yielding authenticated AND triples can also be used to optimize the two-way communication (i.e., the total communication) by combining it with the authenticated garbled circuits by Dittmer et al., which results in an actively secure 2PC protocol with two-way communication of $2\kappa+3\rho+4$ bits per AND gate.</description>
1558 <guid isPermaLink="true">https://eprint.iacr.org/2023/278</guid>
1559 <category>Cryptographic protocols</category>
1560 <enclosure url="https://eprint.iacr.org/2023/278.pdf" length="0" type="application/pdf"/>
1561 <pubDate>Fri, 24 Feb 2023 08:45:13 +0000</pubDate>
1562 <dc:creator>Hongrui Cui</dc:creator>
1563 <dc:creator>Xiao Wang</dc:creator>
1564 <dc:creator>Kang Yang</dc:creator>
1565 <dc:creator>Yu Yu</dc:creator>
1566 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1567 </item>
1568 <item>
1569 <title>Lower Bounds for (Batch) PIR with Private Preprocessing</title>
1570 <link>https://eprint.iacr.org/2022/828</link>
1571 <description>In this paper, we study (batch) private information retrieval with private preprocessing. Private information retrieval (PIR) is the problem where one or more servers hold a database of $n$ bits and a client wishes to retrieve the $i$-th bit in the database from the server(s). In PIR with private preprocessing (also known as offline-online PIR), the client is able to compute a private $r$-bit hint in an offline stage that may be leveraged to perform retrievals accessing at most $t$ entries. For privacy, the client wishes to hide index $i$ from an adversary that has compromised some of the servers. In the batch PIR setting, the client performs queries to retrieve the contents of multiple entries simultaneously.
1572
1573 We present a tight characterization for the trade-offs between hint size $r$ and number of accessed entries $t$ during queries. For any PIR scheme that enables clients to perform batch retrievals of $k$ entries, we prove a lower bound of $tr = \Omega(nk)$ when $r \ge k$. When $r < k$, we prove that $t = \Omega(n)$. Our lower bounds hold when the scheme errs with probability at most $1/15$ and against PPT adversaries that only compromise one out of $\ell$ servers for any $\ell = O(1)$. Our work also closes the multiplicative logarithmic gap for the single query setting $(k = 1)$ as our lower bound matches known constructions. Our lower bounds hold in the model where each database entry is stored without modification but each entry may be replicated arbitrarily.
1574
1575 Finally, we show connections between PIR and the online matrix-vector (OMV) conjecture from fine-grained complexity. We present barriers for proving lower bounds for two-server PIR schemes in general computational models as they would immediately imply the OMV conjecture.</description>
1576 <guid isPermaLink="true">https://eprint.iacr.org/2022/828</guid>
1577 <category>Cryptographic protocols</category>
1578 <enclosure url="https://eprint.iacr.org/2022/828.pdf" length="0" type="application/pdf"/>
1579 <pubDate>Thu, 23 Jun 2022 14:03:09 +0000</pubDate>
1580 <dc:creator>Kevin Yeo</dc:creator>
1581 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1582 </item>
1583 <item>
1584 <title>Function-Hiding Dynamic Decentralized Functional Encryption for Inner Products</title>
1585 <link>https://eprint.iacr.org/2022/1532</link>
1586 <description>Decentralized Multi-Client Functional Encryption (DMCFE) extends the basic functional encryption to multiple clients that do not trust each other. They can independently encrypt the multiple inputs to be given for evaluation to the function embedded in the functional decryption key. And they keep control on these functions as they all have to contribute to the generation of the functional decryption keys.
1587
1588 Dynamic Decentralized Functional Encryption (DDFE) is the ultimate extension where one can dynamically join the system and the keys and ciphertexts can be built by dynamic subsets of clients. As any encryption scheme, all the FE schemes provide privacy of the plaintexts. But the functions associated to the functional decryption keys might be sensitive too (e.g. a model in machine learning). The function-hiding property has thus been introduced to additionally protect the function evaluated during the decryption process.
1589
1590 In this paper, we provide new proof techniques, to analyse our new concrete constructions of function-hiding DMCFE and DDFE for inner products, with strong security guarantees: the adversary can adaptively query multiple challenge ciphertexts and multiple challenge keys. Previous constructions were proven secure in the selective setting only.</description>
1591 <guid isPermaLink="true">https://eprint.iacr.org/2022/1532</guid>
1592 <category>Public-key cryptography</category>
1593 <enclosure url="https://eprint.iacr.org/2022/1532.pdf" length="0" type="application/pdf"/>
1594 <pubDate>Sat, 05 Nov 2022 12:48:17 +0000</pubDate>
1595 <dc:creator>Ky Nguyen</dc:creator>
1596 <dc:creator>David Pointcheval</dc:creator>
1597 <dc:creator>Robert Schädlich</dc:creator>
1598 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1599 </item>
1600 <item>
1601 <title>PEO-Store: Practical and Economical Oblivious Store with Peer-to-Peer Delegation</title>
1602 <link>https://eprint.iacr.org/2023/291</link>
1603 <description>The growing popularity of cloud storage has brought attention to critical need for preventing information leakage from cloud access patterns. To this end, recent efforts have extended Oblivious RAM (ORAM) to the cloud environment in the form of Oblivious Store. However, its impracticality due to the use of probability encryption with fake accesses to obfuscate the access pattern, as well as the security requirements of conventional obliviousness designs, which hinder cloud interests in improving storage utilization by removing redundant data among cross-users, limit its effectiveness. Thus, we propose a practical Oblivious Store, PEO-Store, which integrates the obliviousness property into the cloud while removing redundancy without compromising security. Unlike conventional schemes, PEO-Store randomly selects a delegate for each client to communicate with the cloud, breaking the mapping link between a valid access pattern sequence and a specific client. Each client encrypts their data and shares it with selected delegates, who act as intermediaries with the cloud provider. This design leverages non-interactive zero-knowledge-based redundancy detection, discrete logarithm problem-based key sharing, and secure time-based delivery proof to protect access pattern privacy and accurately identify and remove redundancy in the cloud. The theoretical proof demonstrates that the probability of identifying the valid access pattern with a specific user is negligible in our design. Experimental results show that PEO-Store outperforms state-of-the-art methods, achieving an average throughput of up to 3 times faster and saving 74% of storage space.</description>
1604 <guid isPermaLink="true">https://eprint.iacr.org/2023/291</guid>
1605 <category>Applications</category>
1606 <enclosure url="https://eprint.iacr.org/2023/291.pdf" length="0" type="application/pdf"/>
1607 <pubDate>Sun, 26 Feb 2023 19:26:46 +0000</pubDate>
1608 <dc:creator>Wenlong Tian</dc:creator>
1609 <dc:creator>Jian Guo</dc:creator>
1610 <dc:creator>Zhiyong Xu</dc:creator>
1611 <dc:creator>Ruixuan Li</dc:creator>
1612 <dc:creator>Weijun Xiao</dc:creator>
1613 <dc:rights>https://creativecommons.org/licenses/by-nc/4.0/</dc:rights>
1614 </item>
1615 <item>
1616 <title>Improved Key Pair Generation for Falcon, BAT and Hawk</title>
1617 <link>https://eprint.iacr.org/2023/290</link>
1618 <description>In this short note, we describe a few implementation techniques that allow performing key pair generation for the Falcon and Hawk lattice-based signature schemes, and for the BAT key encapsulation scheme, in a fully constant-time way and without any use of floating-point operations. Our new code is faster than previously published implementations, especially when running on small embedded systems, and uses less RAM.</description>
1619 <guid isPermaLink="true">https://eprint.iacr.org/2023/290</guid>
1620 <category>Implementation</category>
1621 <enclosure url="https://eprint.iacr.org/2023/290.pdf" length="0" type="application/pdf"/>
1622 <pubDate>Sun, 26 Feb 2023 17:30:48 +0000</pubDate>
1623 <dc:creator>Thomas Pornin</dc:creator>
1624 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1625 </item>
1626 <item>
1627 <title>Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation</title>
1628 <link>https://eprint.iacr.org/2022/1747</link>
1629 <description>We design, analyze, and implement Duoram, a fast and bandwidth-efficient distributed ORAM protocol suitable for secure 2- and 3-party computation settings. Following Doerner and shelat's Floram construction (CCS 2017), Duoram leverages (2,2)-distributed point functions (DPFs) to represent PIR and PIR-writing queries compactly—but with a host of innovations that yield massive asymptotic reductions in communication cost and notable speedups in practice, even for modestly sized instances. Specifically, Duoram introduces a novel method for evaluating dot products of certain secret-shared vectors using communication that is only logarithmic in the vector length. As a result, for memories with $n$ addressable locations, Duoram can perform a sequence of $m$ arbitrarily interleaved reads and writes using just $O(m\lg n)$ words of communication, compared with Floram's $O(m \sqrt{n})$ words. Moreover, most of this work can occur during a data-independent preprocessing phase, leaving just $O(m)$ words of online communication cost for the sequence—i.e., a constant online communication cost per memory access.</description>
1630 <guid isPermaLink="true">https://eprint.iacr.org/2022/1747</guid>
1631 <category>Cryptographic protocols</category>
1632 <enclosure url="https://eprint.iacr.org/2022/1747.pdf" length="0" type="application/pdf"/>
1633 <pubDate>Mon, 19 Dec 2022 19:21:06 +0000</pubDate>
1634 <dc:creator>Adithya Vadapalli</dc:creator>
1635 <dc:creator>Ryan Henry</dc:creator>
1636 <dc:creator>Ian Goldberg</dc:creator>
1637 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1638 </item>
1639 <item>
1640 <title>CHVote Protocol Specification</title>
1641 <link>https://eprint.iacr.org/2017/325</link>
1642 <description>This document provides a self-contained, comprehensive, and fully-detailed specification of a new cryptographic voting protocol designed for political elections in Switzerland. The document describes every relevant aspect and every necessary technical detail of the computations and communications performed by the participants during the protocol execution. To support the general understanding of the cryptographic protocol, the document accommodates the necessary mathematical and cryptographic background information. By providing this information to the maximal possible extent, it serves as an ultimate companion document for the developers in charge of implementing this system. It may also serve as a manual for developers trying to implement an independent election verification software. The decision of making this document public even enables implementations by third parties, for example by students trying to develop a clone of the system for scientific evaluations or to implement protocol extensions to achieve additional security properties. In any case, the target audience of this document are system designers, software developers, and cryptographic experts.</description>
1643 <guid isPermaLink="true">https://eprint.iacr.org/2017/325</guid>
1644 <category>Cryptographic protocols</category>
1645 <enclosure url="https://eprint.iacr.org/2017/325.pdf" length="0" type="application/pdf"/>
1646 <pubDate>Mon, 17 Apr 2017 14:36:11 +0000</pubDate>
1647 <dc:creator>Rolf Haenni</dc:creator>
1648 <dc:creator>Reto E. Koenig</dc:creator>
1649 <dc:creator>Philipp Locher</dc:creator>
1650 <dc:creator>Eric Dubuis</dc:creator>
1651 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1652 </item>
1653 <item>
1654 <title>Efficient Detection of High Probability Statistical Properties of Cryptosystems via Surrogate Differentiation</title>
1655 <link>https://eprint.iacr.org/2023/288</link>
1656 <description>A central problem in cryptanalysis is to find all the significant deviations from randomness in a given $n$-bit cryptographic primitive. When $n$ is small (e.g., an $8$-bit S-box), this is easy to do, but for large $n$, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems which are designed to have hidden trapdoors.
1657
1658 In this paper we consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box, and reduce the complexity of the best known techniques for finding all its significant differential and linear properties by a large factor of $2^{n/2}$. Our main new tool is the idea of using {\it surrogate differentiation}. In the context of finding differential properties, it enables us to simultaneously find information about all the differentials of the form $f(x) \oplus f(x \oplus \alpha)$ in all possible directions $\alpha$ by differentiating $f$ in a single arbitrarily chosen direction $\gamma$ (which is unrelated to the $\alpha$'s). In the context of finding linear properties, surrogate differentiation can be combined in a highly effective way with the Fast Fourier Transform. For $64$-bit cryptographic primitives, this technique makes it possible to automatically find in about $2^{64}$ time all their differentials with probability $p \geq 2^{-32}$ and all their linear approximations with bias $|p| \geq 2^{-16}$; previous algorithms for these problems required at least $2^{96}$ time. Similar techniques can be used to significantly improve the best known time complexities of finding related key differentials, second-order differentials, and boomerangs. In addition, we show how to run variants of these algorithms which require no memory, and how to detect such statistical properties even in trapdoored cryptosystems whose designers specifically try to evade our techniques.</description>
1659 <guid isPermaLink="true">https://eprint.iacr.org/2023/288</guid>
1660 <category>Secret-key cryptography</category>
1661 <enclosure url="https://eprint.iacr.org/2023/288.pdf" length="0" type="application/pdf"/>
1662 <pubDate>Sun, 26 Feb 2023 10:04:00 +0000</pubDate>
1663 <dc:creator>Itai Dinur</dc:creator>
1664 <dc:creator>Orr Dunkelman</dc:creator>
1665 <dc:creator>Nathan Keller</dc:creator>
1666 <dc:creator>Eyal Ronen</dc:creator>
1667 <dc:creator>Adi Shamir</dc:creator>
1668 <dc:rights>https://creativecommons.org/licenses/by-nc-sa/4.0/</dc:rights>
1669 </item>
1670 <item>
1671 <title>Modelling Delay-based Physically Unclonable Functions through Particle Swarm Optimization</title>
1672 <link>https://eprint.iacr.org/2023/287</link>
1673 <description>Recent advancements in low-cost cryptography have converged upon the use of nanoscale level structural variances as sources of entropy that is unique to each device. Consequently, such delay-based Physically Unclonable Functions or (PUFs) have gained traction for several cryptographic applications. In light of recent machine learning (ML) attacks on delay-based PUFs, the common trend among PUF designers is to either introduce non-linearity using XORs or input transformations applied on the challenges in order to harden the security of delay-based PUFs. Such approaches make machine learning modelling attacks hard by destroying the linear relationship between challenge-response pairs of a PUF. However, we propose to perceive PUFs, which are fundamentally viewed as Boolean functional mapping, as a set of delay parameters drawn from normal distribution. Using this newfound perception, we propose an alternative attack strategy in this paper. We show that instead of trying to learn the exact functional relationship between challenge-response pairs from a PUF, one can search through the search space of all PUFs to find alternative PUF delay parameter set that exhibits similar behaviour as the target PUF. The core intuition behind this strategy is that one can consider a PUF as a set of stages wherein, depending on the corresponding input challenge bit, one of the several signals within a PUF's stage win a race condition. To utilize this idea, we develop a novel Particle Swarm Optimization based framework inspired by the biomimicry of amoebic reproduction. The proposed algorithm avoids the pitfalls of textbook Genetic Algorithms and demonstrates complete break of existing delay-based PUFs which are based on arbiter chains. More specifically, we are able to model higher-rder $k$-XOR PUF variants which are resistant to all-known ML modelling techniques, including $k=13, 15$ and $20$, without the knowledge of reliability values. In addition to that, we also model PUFs that incorporate input transformation, like variants of IPUF and LP-PUF. Furthermore, we take forward this idea across different search spaces in order to learn a higher order PUF using a lower order (and simpler) PUF architecture. This allows us to explore a novel class of attacks, including modelling a $k$-XOR PUF using a $(k-1)$-XOR PUF as well as bypassing input transformations based PUF designs.</description>
1674 <guid isPermaLink="true">https://eprint.iacr.org/2023/287</guid>
1675 <category>Attacks and cryptanalysis</category>
1676 <enclosure url="https://eprint.iacr.org/2023/287.pdf" length="0" type="application/pdf"/>
1677 <pubDate>Sun, 26 Feb 2023 05:09:41 +0000</pubDate>
1678 <dc:creator>Nimish Mishra</dc:creator>
1679 <dc:creator>Kuheli Pratihar</dc:creator>
1680 <dc:creator>Anirban Chakraborty</dc:creator>
1681 <dc:creator>Debdeep Mukhopadhyay</dc:creator>
1682 <dc:rights>https://creativecommons.org/licenses/by-nc-sa/4.0/</dc:rights>
1683 </item>
1684 <item>
1685 <title>MacORAMa: Optimal Oblivious RAM with Integrity</title>
1686 <link>https://eprint.iacr.org/2023/083</link>
1687 <description>Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM `96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size $N$, well-known lower bounds show that a multiplicative overhead of $\Omega(\log N)$ in the number of RAM queries is necessary assuming $O(1)$ client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO `21) with $O(\log N)$ worst-case overhead and $O(1)$ client storage. However, this optimal ORAM is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.
1688
1689 In this work, we construct the first maliciously secure ORAM with worst-case $O(\log N)$ overhead and $O(1)$ client storage assuming one-way functions, which are also necessary. By the $\Omega(\log N)$ lower bound, our construction is asymptotically optimal. To attain this overhead, we develop techniques to intricately interleave online and offline memory checking for malicious security. Furthermore, we complement our positive result by showing the impossibility of a generic overhead-preserving compiler from honest-but-curious to malicious security, barring a breakthrough in memory checking.</description>
1690 <guid isPermaLink="true">https://eprint.iacr.org/2023/083</guid>
1691 <category>Cryptographic protocols</category>
1692 <enclosure url="https://eprint.iacr.org/2023/083.pdf" length="0" type="application/pdf"/>
1693 <pubDate>Tue, 24 Jan 2023 05:07:03 +0000</pubDate>
1694 <dc:creator>Surya Mathialagan</dc:creator>
1695 <dc:creator>Neekon Vafa</dc:creator>
1696 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1697 </item>
1698 <item>
1699 <title>PROTEUS: A Tool to generate pipelined Number Theoretic Transform Architectures for FHE and ZKP applications</title>
1700 <link>https://eprint.iacr.org/2023/267</link>
1701 <description>Emerging cryptographic algorithms such as fully homomorphic encryption (FHE) and zero-knowledge proof (ZKP) perform arithmetic involving very large polynomials. One fundamental and time-consuming polynomial operation is the Number theoretic transform (NTT) which is a generalization of the fast Fourier transform. Hardware platforms such as FPGAs could be used to accelerate the NTTs in FHE and ZKP protocols. One major problem is that the FHE and ZKP protocols require different parameter sets, e.g., polynomial degree and coefficient size, depending on their applications. Therefore, a basic research question is: How to design scalable hardware architectures for accelerating NTTs in the FHE and ZKP protocols?
1702 In this paper, we present ‘PROTEUS’, an open-source and parametric tool that generates synthesizable bandwidth-efficient NTT architectures for user-specified parameter sets. The architectures can be tuned to utilize different memory bandwidths and parameters which is a very important design requirement in both FHE and ZKP protocols. The generated NTT architectures show a significant performance speedup compared to similar NTT architectures on FPGA. Further comparisons with state-of-the-art show a reduction of up to 23% and 35% in terms of DSP and BRAM utilization.</description>
1703 <guid isPermaLink="true">https://eprint.iacr.org/2023/267</guid>
1704 <category>Implementation</category>
1705 <enclosure url="https://eprint.iacr.org/2023/267.pdf" length="0" type="application/pdf"/>
1706 <pubDate>Thu, 23 Feb 2023 08:59:06 +0000</pubDate>
1707 <dc:creator>Florian Hirner</dc:creator>
1708 <dc:creator>Ahmet Can Mert</dc:creator>
1709 <dc:creator>Sujoy Sinha Roy</dc:creator>
1710 <dc:rights>https://creativecommons.org/licenses/by/4.0/</dc:rights>
1711 </item>
1712 </channel>
1713 </rss>