多変数多項式求解問題(MQ問題)に基づく多変数多項式暗号は耐量子暗号の有力な候補のひとつである.SakumotoらはMQ問題の困難性に安全性が直接帰着可能なidentification scheme (IDS)を提案した.このIDSを変換することにより構成されるディジタル署名 (DSS)としてMQDSS,SOFIAなどが提案されている.さらにPetzoldtらはSakumotoらのIDSを基にDSSを高機能化した閾値リング署名 (threshold ring signature)を構成している.一方Beullensはhelperという第三者を加えたIDSを導入し,実際にMQ問題に基づくhelper付きIDSにより署名長の短い効率的なDSSを構成した.
本研究では,はじめにthreshold ring版のIDSにhelperを追加した方式 (helper付きthreshold ring IDS)を定義する.次にMQ問題に基づく具体的なhelper付きthreshold ring IDSを構成し,Beullensの変換手法を適用することで新たなthreshold ring signatureを提案する.この手法はPetzoldtらの手法と比較して,署名長を約48%,署名者グループ内の通信量を約17%削減している.
1A1-2
A MinRank attack against variants of UOV signature scheme
◎Hiroki Furue(The University of Tokyo)
、Yasuhiko Ikematsu(Kyushu University)
Multivariate public-key cryptography (MPKC) is considered as one of the main candidates for post-quantum cryptography (PQC).
In MPKC, the MinRank attacks, which try to solve the MinRank problem obtained from public key, are important since a lot of multivariate schemes are broken by these attacks.
Among them, the rectangular MinRank attack was recently proposed for the Rainbow scheme by Beullens, and it tries to solve a new MinRank problem obtained by transforming the public key of Rainbow.
Due to this attack, it is known that the security level of Rainbow is reduced.
Rainbow is a multi-layered variant of the UOV scheme, which has a resistance to all MinRank attacks since UOV does not have a structure of MinRank problem.
Recently, there have been proposed two new variants of UOV scheme having a small public key, MAYO and QR-UOV.
In this paper, we show that the rectangular MinRank attack can be applied for MAYO and QR-UOV.
Moreover, we estimate the complexity of the attack.
The multivariate-based unbalanced oil and vinegar signature scheme (UOV) is expected to be one of the candidates for post-quantum cryptography (PQC). UOV is a well-established signature scheme owing to its short signature and execution time. However, its public key is much larger than that of other PQC candidates. At ASIACRYPT 2021, Furue et al.\ proposed quotient ring UOV (QR-UOV) as a new variant of UOV, which reduces the public key size compared to the plain UOV. However, there has not been a formal security proof and detailed parameter analysis for QR-UOV. In this paper, one of our contributions is that we present the formal definitions of two assumptions and prove the EUF-CMA security of QR-UOV based on these assumptions. Furthermore, we propose various parameter sets of QR-UOV with different security levels, the orders of the finite field, and the purposes, and estimate the public key and signature size of these parameters. By comparing the public key and signature size of these parameter sets with those of other PQC candidates, we discuss the (dis)advantages of each parameter set.
1A1-5
Efficient Software Implementation of Signature Scheme QR-UOV
○Fumitaka Hoshino(University of Nagasaki)
、Hiroki Furue(The University of Tokyo)
、Yasuhiko Ikematsu(Kyushu University)
、Tsunekazu Saito(NTT Social Informatics Laboratories)
、Yutaro Kiyomura(NTT Social Informatics Laboratories)
、Tsuyoshi Takagi(The University of Tokyo)
In ASIACRYPT 2021, Furue et al. proposed a new post-quantum signature called QR-UOV, which is a variant of the multivariate signature schemes. In this work, we present an efficient software implementation of the QR-UOV on the x86 environments and evaluate its efficiency.
Threshold Signature Schemes based on Isogeny
○Wang Yusen(Osaka University)
、Miyaji Atsuko(Osaka University, Japan Advanced Institute of Science and Technology)
A threshold HHS(Hard Homogeneous Spaces) signature scheme has been proposed by Luca De Feo et al. . In their proposition, CSI-FiSh and its ancestors can be easily adapted into this model, and thus one can construct the threshold versions. However, a trusted dealer is necessary for the threshold HHS signature scheme to generate secret keys and distribute secret shares.
In this paper, we propose two dealer-less threshold signature schemes based on CSI-FiSh and CSI-SharK, respectively. In our proposals, all members communicate in broadcast channels and generate their own secret shares without a dealer. Thus, they are more suitable for scenarios where trusted third parties should not exist. We give the correctness and security analysis of both versions, and we compare their efficiencies theoretically.
Compact Broadcast Encryption from LWE
○Toi Tomita(Yokohama National University)
、Junji Shikata(Yokohama National University)
We propose the first compact lattice-based broadcast encryption (BE) scheme. More generally, we present the first lattice-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for the class of restricted degree 2 polynomials. Our CP-ABE scheme has the public key, ciphertext, and private key sizes of O(n), where n is the input length for the polynomial. From our CP-ABE scheme, we immediately derive a compact BE scheme for N parties with O(N^{1/2})-sized parameters. Our BE schemes achieve selective security and rely only on the learning with error assumption.
1A2-5
Revisiting Fiat-Shamir Signatures under Superposition Attacks
◎Quan Yuan(Graduate School of Information Science and Technology, The University of Tokyo)
、Tsuyoshi Takagi(Graduate School of Information Science and Technology, The University of Tokyo)
Fiat-Shamir transformation is widely used to construct signature schemes from secure identification protocols, such as Schnorr signature, CRYSTAL-Dilithium , and Picnic. The security of Fiat-Shamir signatures has been proven under chosen message attacks (CMAs) in the quantum random oracle model. However, CMAs do not cover superposition attacks, where the adversary can send signing queries in quantum states. Researchers recently proposed a security notion called blind-unforgeability considering superposition attacks. In this work, we revisit the security of Fiat-Shamir signatures in this model.
First, we show a separation result that a secure Fiat-Shamir signature under CMAs does not suffice to be blind-unforgeable (under superposition attacks). It implies that superposition attacks can be more threatening to Fiat-Shamir signatures than the classical attacks. Next, we attempt to show some positive results. We focus on a common variant called ``hedged'' Fiat-Shamir signatures, where the randomness of signing algorithm is replaced with a hash of the secret key, the message and a nonce. We prove that hedged Fiat-Shamir signatures are blind-unforgeable under superposition attacks in the quantum random oracle model if the underlying identification protocol is secure in the post-quantum settings.
On using``incomplete" primitives to construct new signature schemes.
○Sipasseuth Arnaud(KDDI Research, Inc.)
This short paper presents a simple construction to build signature schemes from ``incomplete" mathematical primitives.
Historically, cryptosystems have mostly been based from computational problems based on mathematical structures: number factoring, short vectors in lattices, error-decoding, roots of multivariate polynomials, and so on.
It has always been hard to conceive mathematical primitives to build cryptosystems:
while the academic literature is full of computationally hard problems in general (i.e, we can construct random instances which computational problems are hard to solve),
constructing hard instances with a trapdoor seem to be historically difficult. We focus here on a method to use primitives that by themselves fail to be standalone signature schemes, in the sense that it is unclear within the message space which messages we can sign and which we can not.
Currently, we are not aware of a primitive that we can use to make signatures that are competitive with most NIST submissions in terms of key and signature size, or even speed.
However, we believe this approach can be used to make use of primitives we could otherwise not use, and present some (currently bad) usage examples.
1A3-2
Secure Multi-key Homomorphic Signatures against Insider Corruption
◎Ye Xu(University of Tsukuba)
、Takashi Nishide(University of Tsukuba)
Homomorphic signature schemes (HS) enable an untrusted server to run some computation over the data signed under the same key and derive a short signature for authenticating the computation result. Recently, Fiore et al. (Asiacrypt '16) introduced multi-key homomorphic signatures (MKHS) to support the evaluation of signatures under different keys. Anyone can verify the signature by using corresponding public verification keys. However, even one leaked signing key enables the malicious server to forge a signature. To cope with the issue, we propose a new scheme building on the work of Fiore et al. (Asiacrypt '16) to achieve a stronger security guarantee. Moreover, our MKHS scheme is unforgeable even if an adversary holds all but one signing key.
1A3-3
再訪:否認不可署名 --- 応用と誤用 ---
○櫻井 幸一(九州大学)
ビットコインにはじまり、ブロックチェーン、さらにはNFTへとWeb 3.0が進化している。発表者は、池辺ら[本シンポジウムで発表]とのNFTに関する共同研究をきっかけに、Chaumの否認不可署名[CRYPTO’89]以降の一連の研究を調査した。Chaumの否認不可署名は、署名の一人歩き問題を解決したと評価されている。しかし、その後の追従研究の中には、プロトコル設計のミスやゼロ知識証明の誤用により、署名が一人歩きする危険性のある方式を、発表者は発見した。本研究では、その報告を行うものである。この研究は、発表者の30年前の論文[On the Discrepancy between Serial and Parallel of Zero-Knowledge Protocols, CRYPTO 1992]を再考するきっかけとなった。
多重署名方式は暗号通貨の発展に伴い注目を集め、様々な仮定から構成されている。特に離散対数ベースでは、鍵生成に無仮定なモデルでの安全性と鍵集約のサポートを達成した2ラウンド方式が複数提案された。これらの内、帰着ロスの大きい方式は128ビット安全性を達成可能な標準化楕円曲線を持たない。一方で帰着ロスのない方式は、標準化曲線P-256等で128ビット安全性を保証できるが、楕円曲線に理想的な計算モデルAlgebraic Group Model (AGM) を仮定する。AGMを用いない場合、どれ程帰着ロスの削減や効率性の向上が可能かは知られていない。本研究では、DDH仮定とランダムオラクルモデルから2ラウンド多重署名方式を構成した。帰着ロスが完全に排除できてはいないが、AGMを用いない既存方式と比べ削減でき、P-384の下で128ビット安全性を達成可能で、その場合の署名長は1152ビットであった。AGMを用いない方式の中で、唯一の128ビット安全性を達成可能な標準化曲線を持つ方式であり、最も短い署名長を達成している。署名生成や検証での必要計算時間の評価も行い、実用的な時間で動作することを確認した。
1A3-5
Two-round Tightly-Secure Multi-Signature with Key Aggregation
Jacob Schuldt(産業技術総合研究所)
、◎小嶋 陸大(富士通株式会社)
、花岡 悟一郎(産業技術総合研究所)
Multi-signatures have seen renewed interest due to their application to blockchains, e.g., BIP 340 (One of the Bitcoin improvement proposals), which has triggered the proposals of several new schemes with improved efficiency. However, many of these have a loose security reduction which makes the achieved level of security unclear when instantiated in groups typically used in practice or depending on strong idealized assumptions such as the AGM (Algebraic Group Model). When using a multi-signature with such loose security, it becomes unclear for the developers to understand how secure this scheme is if they choose any security parameters. Thus, it leads to whether we can construct a scheme with tight security based on standard assumptions.
In this paper, we show a simple two-round tightly-secure pairing-based multi-signature scheme based on the computation Diffie-Hellman problem in the random oracle model. In comparison, existing tightly-secure schemes that do not rely on the AGM are three-round schemes either do not support key aggregation (which our scheme does) or rely on a decisional hardness assumption. Compared to existing non-tight schemes instantiated in groups typically considered in practice but compensating for the scheme's security loss, our scheme provides shorter signatures and public keys for the same bits security level.
個人の交友関係や,市場における組織間の取引関係など,多種多様な社会的な関係が存在する.これらの関係により形成される社会的構造は社会的ネットワークと呼ばれ,数多くの分析や研究がなされている.中でも,社会的ネットワークにおけるノード(個人/組織)の評判や信頼性の指標は,ノード間の関係の形成や改善のための有用な情報である.さて,ネットワーク上の各ノードが関係のあるノードに対し主観的に点数で評価する状況を考える.このとき,ネットワークは Weighted Signed Network (WSN)と呼ばれる実数値の辺重み付き有向グラフにモデル化できる.これら主観的評価情報を用いることで,ネットワーク全体からみたノードの評判や信頼性の指標を計算するレーティング計算手法が研究されている.しかしながら,各ノードの主観的評価情報は,そのノードに対応する個人や組織にとっては機密な情報であり,他者に公開したくないことが多い.これまでに,我々は主観的評価情報及びその推定に結び付く情報を他者に知られないようにする秘匿レーティング計算手法を提案している.本稿では,提案する秘密計算プロトコルを計算機上でシミュレーション評価する.
文字列の接尾辞ソーティングは,接尾辞配列の構築やBurrows-Wheeler Transformation(BW変換)を行うために用いられ,これらは文字列圧縮や文字列検索等の処理を容易にする.接尾辞配列やBW変換を基にしたデータ解析手法は機械学習や生命情報などを含む様々な分野で応用されており,特に生命情報の分野において,大規模データを効率的に処理できる特性から,ゲノム解析など先進的な研究分野にて非常に重要な役割を担っている.一方でこれらの分野において,ゲノム情報など重要な個人情報を取り扱う必要があり,解析技術の進歩とともに個人情報漏洩のリスクも日に日に高まっている.この問題に対する対応策として,Secure Multi Party Computation(MPC)と呼ばれる,秘密情報を複数台の計算サーバーを使用して秘匿したまま特定の情報処理を行う手法に関する研究が現在活発に行われている.本稿では,文字列の接尾辞ソーティングをMPCを用いて秘匿化することを目指す.さらに本稿で提案する秘匿化手法の,DNA解析等で用いられているデータ解析手法の一つへの応用を試みる.
対象のデータの情報を秘匿したまま計算を行う秘密計算において,特にソーティングは多くのデータ処理において必要かつボトルネックであり,その高速化は重要な課題である.本論文では,3パーティの秘密分散によるsemi-honest安全な秘密計算基数ソートについて,入力を得た後の通信量(オンライン通信量)の削減による高速化を行う.
提案手法では,基数ソートのサブプロトコルである L ビット整数の計数ソートのオンライン通信量を改善する.既存手法では 2^L に比例するビット数のオンライン通信量を必要としていたが,各要素の単位ベクトルを生成する手法とShamirのシェアを用いた省通信化の手法を組み合わせることで,提案手法では L に比例する程度のオンライン通信量に抑える.これにより, L ビット計数ソートを用いて W ビット整数 N 個を安定ソートする秘密計算基数ソートにおいて,既存手法では事前計算の通信量とオンライン通信量共に O(2^LWN\log N/L)$であったのに対して,提案手法では同程度の事前計算でオンライン通信量 O(WN(1+log N/L)) を達成することを示す.そして, L が小さい場合も,提案手法は既存手法よりオンライン通信量及びラウンド数が改善していることを示す.
メッセージ認証コード(MAC)は,データの改竄を検知するための暗号技術である.従来,MAC は入力として単一のビット列形式のデータのみを対象としてきたが,ベクトル形式など,他の形式のデータにも適用したいという要求がある.
SCIS 2022 において,笠原らは,ベクトル形式のデータを対象とする MAC として,高安全性(使用する固定長暗号部品の入出力長 n に対して n-bit security)を保証する手法を提案したが,同手法は入力ベクトル長が固定であるという制約があった.
そこで,本提案では,可変長ベクトルを入力として取り,かつ高安全な MAC を提案する.
Non-Interactive Proof of Knowledge from Fiat-Shamir and Correlation Intractable Hash
◎Zehua Shang(Kyoto University)
、Miyako Ohkubo(Security Fundamentals Laboratory, CSR, NICT)
、Mehdi Tibouchi(NTT Social Informatics Laboratories)
、Masayuki Abe(NTT Social Informatics Laboratories)
Non-interactive zero-knowledge (NIZK) proofs are vital building blocks for a wide spread of non-interactive schemes such as public-key encryption and digital signature schemes. Constructions of Fiat-Shamir type NIZKs without random oracles have been a long time goal of the research community. The recent results such as Canetti et al. (STOC'19), Libert et al. (Asiacrypt'20) and Peikert and Shiehian (Crypto'19) only provide constructions of NIZKs with membership proofs. In this paper, we present a construction that achieves knowledge soundness with the Fiat-Shamir transform and correlation intractable hash families. Our construction requires several ingredients such as sigma-protocols, CPA-secure encryption schemes and correlation intractable hash functions. Our protocols avoid additional assumptions of trapdoor sigma-protocols or Omega-protocols.
本研究ではブロードキャストプロトコルに対するゲーム理論的安全性を考える.攻撃の検知を避ける臆病な攻撃者が合理的に振る舞う.Dolev-Strong (1983) により,決定性のプロトコルでは t 人の攻撃者がいる場合にラウンド数が t + 1 以上必要なことが示されている.本研究では,n人で実行するプロトコルとして,任意の t < n に対し,臆病な攻撃者が t 人いる場合にラウンド数が 5 の決定性のプロトコルを提案する.
After proposing Optimistic Signed Exchange to solve the transaction fee problems left by FairSwap, OptiSwap, and Zk-contingent payment, this protocol gives a satisfying result on transaction fees in the previous paper. Furthermore, the computation overhead is smaller than the ZK-knowledge contingent payment. And the comparison between it and previous protocols has been shown in the last paper. In this paper, we update several changes to our protocol considering the availability of building blocks and give the formal security proof based on the IND-CPA and hash security. The transaction fee between Optimistic Signed Exchange and previous protocols needs to be compared again.In addition, the transaction fee for exchanging larger files is estimated, and the final result shows that it is problematic in practice.
1C3-5
Composition of Zero-knowledge Proof Protocols from MPC-in-the-Head with Pre-processing
○Zhiyu Peng(Kyoto University)
、Miyako Ohkubo(National Institute of Information and Communications Technology)
、Mehdi Tibouchi(NTT Social Informatics Laboratories)
、Masayuki Abe(NTT Social Informatics Laboratories)
Katz, Kolesnikov, and Wang (KKW) built a powerful instantiation of the MPC-in-the-head paradigm. In particular, via a well-designed preprocessing phase, the KKW scheme greatly enlarges the space of applicable MPCs and corresponding relations, including various special relations that do not support logical formulas. However, applying logical formulas like composition is important in applications of the KKW scheme. Proof of partial knowledge proposed by Cramer, Damg?rd, and Schoenmakers (CDS) enables efficient composition of statements in zero-knowledge proof protocols by secret sharing the challenge into challenges for atomic protocols. Unfortunately, the CDS method works only when the atomic protocol is a special sound Σ-protocol, which deviates from the KKW protocol. Specifically, two challenge stages occur for the 5-round KKW protocol and may cause inconsistency in atomic protocols corresponding to transcripts at different stages, which hinders witness extraction. In this work, we apply a recent definition of special soundness for the multi-round protocol to the 5-round KKW protocol and extend the CDS protocol over it. In our method, the CDS style of secret sharing only happens at the first challenge stage to avoid potential inconsistency. Our result offers a statement-composable zero-knowledge proof system using the 5-round KKW protocol as the atomic protocol. Furthermore, it can be transformed into a NIZK using the Fiat-Shamir heuristic and be used to form practical signatures.
個人や組織の様々の活動がインターネット上で展開される時代へと移行する中,活動の過程で求められる個人や組織のアイデンティティ情報もネット経由の提供へ移行することが想定される.筆者らが提案している自己主権型アイデンティティ情報利活用基盤(SSIUF:Self-Sovereign Identity-information Utilization Framework)は,インターネット上での個人や組織間での安全なアイデンティティ情報の流通およびアイデンティティ情報の検証を可能とする情報流通基盤である.本稿では,SSIUF構想を発展させ,様々のアプリケーションの安心・安全なサービスの基盤となることを目指したブロックチェーンサービス基盤(BSI:Blockchain Service Infrastructure)構想を提案する.BSIは,各国の個人や組織の認証基盤(NAF:National Authentication Framework),自己主権型アイデンティティ基盤(SSIF:Self-Sovereign Identity Framework),多様なアプリケーションサービス(ASF:Application Service Framework)から構成され、個人や組織間での情報の送受信にはW3C(World Wide Web Consortium)で標準化が進められている分散型ID(DID:Decentralized Identifier)/検証可能属性証明(VC:Verifiable Credential)関連技術の活用を想定している。また,日本で早期の実現が期待されているNAFjp(NAF in Japan)を利用した日本におけるブロックチェーンサービス基盤BSIjp(BSI in Japan)の構成案を示す。
ユーザの持つ価値を交換できるプラットフォームは非同期的なデータのやり取りを可能とするクラウドストレージに支えられている.データ所有者がプラットフォーム上でデータが適切に存在していることの確認は,クラウドストレージ内のデータの完全性を検証可能とするProvable Data Possession(PDP)に基づいた監査システムを構築すれば可能となる.PDPでやりとりされるデータをブロックチェーンに記録することで,監査の透明性を保証する理論的な方式が提案されている.しかしながら,ブロックチェーンに記録されるデータをどのように取り扱うかの実装上の設計によってはその安全性が保証されない.本論文では,クラウドストレージを用いた透明性を持つ非同期なデータ交換にPDPを適用した監査システムにおける脅威について述べ,Ethereumのスマートコントラクトを実装する上での課題を整理し,具体的な実装手法を与え,監査システムの安全性について議論する.
BFL-Boost: Blockchain-based Federated Learning for Gradient Boosting to Enhance Security in Model Training
◎Septiviana Savitri Asrori(Kobe University)
、Lihua Wang(National Institute of Information and Communications Technology)
、Seiichi Ozawa(Kobe University)
Federated Learning (FL) is one of the techniques that allow collaborative machine learning in a privacy-preserving way. FL consists of several data owners and one central server, where each data owner shares only the model updates with a central server, then the central server will do the aggregation process to produce the global model. However, there are still challenges in FL implementation. First is the single-point-of-failure (SPOF) phenomenon, because the central server is the only party responsible for the model aggregation process. Second, there is still a chance when the data owner is dishonest and tries to poison the global model. Thus, we proposed BFL-Boost (Blockchain-based Federated Learning for Gradient Boosting), a framework run in a permissioned blockchain that ensures the security of the training process with a validation mechanism and secure aggregation mechanism. In addition, we provide the security measures on the proposed BFL-Boost based on three security aspects: Confidentiality, Integrity, and Availability (CIA).
2022年のSCISで,分散台帳をIoTデバイスとLPWA(Low Power Wide Area netowrok)を用いてポイント交換を行う方法を提案した.同方式はポイント交換を分散台帳に記録する時間が長いことが課題である.その一因には,パケットに含まれる署名がLPWAネットワークの通信帯域を圧迫していることが挙げられる.特に,分散台帳の管理に参加するノードがそれぞれ署名つきのデータをLPWAを用いたP2Pネットワーク上でブロードキャストするため,その影響が大きくなっている.そこで,本稿では他ノードのデータを中継する際,BLS署名を用いて複数の署名を,署名1つ分と同じ長さの署名データに集約することにより,ネットワーク全体に流れる署名の長さを短くする方式を提案する.提案方式により,どの程度通信のデータ量が改善されるのかを評価する.
現在, 世界各国でCentral Bank Digital Currency(CBDC)を発行する計画が進められており, EUでは2021年からCBDCの実証実験が行われている. 日本でも2021年からクラウド上の実験環境で様々な電子現金方式のCBDCの実証実験が行われている. その中で, トークン型電子現金方式のCBDCは, 災害時でもオフライン決済が可能で利便性が高いとして期待されている. 一方, 転々流通により通貨に付加された電子署名の個数が増加し,取引時の署名検証時間が増大するなどスケーラビリティの懸念がある. 本研究では,社会実験でしか本来得られない結果を元にCBDCに適した電子現金方式を策定するために,自律的なエージェントによる相互作用の結果が得られるMulti-Agent Simulationという手法でトークン型電子現金方式のシミュレーションを行った. その結果, 送金時に財布から通貨を選択するアルゴリズムをエージェント毎に設定することで,送金する通貨の署名の合計数の低減や通貨の還収頻度の上昇などの効果が観測された. これらのデータを元に, 主にスケーラビリティの観点からトークン型電子現金方式を評価した.
1D2-5
Cross-Ledger Communication in Layer 2
◎Maxim Jourenko(東京工業大学, IOG)
、Mario Larangeira(東京工業大学, IOG)
In this presentation we show our ongoing work on interconnecting distributed ledgers on Layer 2. With the ever greater adaptation of blockchain systems, smart contract based ecosystems have formed to provide financial services and other utility. This results in an ever increasing demand for transactions on blockchains. Layer-2 systems attempt to improve scalability by taking transactions off-chain, with building blocks that are two party channels which are concatenated to form networks. Interaction between two parties requires (1) routing such a network, (2) interaction with and collateral from all intermediaries on the routed path and (3) interactions are often more limited compared to what can be done on the ledger. In contrast to that design, recent constructions such as Hydra Heads (FC'21) are both multi-party and isomorphic, allowing interactions to have the same expressiveness as on the ledger making it akin to a ledger located on Layer-2. Our follow up Interhead Construction (MARBLE'22) further extends the protocol to connect Hydra Heads into networks by means of a virtual Hydra Head construction. In this presentation we show an even greater generalization of the Interhead Protocol, allowing for interaction across different Layer-2 ledgers with a multitude of improvements.
Statistical Model of Multiple Size Transistor SRAM PUF Mismatch Distribution after Hot Carrier Injection for Stability Enhancement
◎徐 舒帆(早稲田大学)
、劉 昆洋(早稲田大学)
、篠原 尋史(早稲田大学)
Physically Unclonable Function (PUF) is an emerging hardware fingerprint security technology, which is based on uncontrollable variations introduced in the chip manufacturing process. The generated PUF data can be used for authentication and cryptography. SRAM PUF utilizes the polarity of physical mismatches of transistors in the symmetrical inverters, and the random start-up states in SRAM bitcells are used as PUF data. Under normal circumstances, the mismatch of the bitcells obeys a Gaussian distribution. If the mismatch value of a bitcell is very small, the polarity is easily changed and some bit errors happen. To meet the strict bit error rate (BER) requirement for cryptographic use, hot carrier injection (HCI) is one of the methods to increase the stability of SRAM PUF. It selectively enlarges the threshold voltage (V_TH) of one of the pair transistors to increase the mismatch of the bitcell. Due to the inconsistency of the mismatch shift distribution, the mismatches of some bitcells are still within small values after HCI and needed longer burn-in time to eliminate. This ‘tail’ degrades the stability of SRAM PUF and causes bit errors. This work proposes multiple-size transistor SRAM PUF to reduce the ‘tail’. Statistical model for bitcell mismatch distribution on SRAM PUF after HCI burn-in is created to predict the effect of multiple-size transistor for HCI.
Distribution of mismatch shift by HCI was derived as a compound distribution of Poisson distribution (the number of injected hot electrons) and Gamma distribution (the mismatch shift caused by injected electrons). It is combined with the native mismatch of bitcells before HCI, which follows a Gaussian distribution. Mismatch distribution after HCI is established.
This mismatch shift distribution model suggests the ‘tail’ can be reduced by increasing average injected electrons λ, because μ/σ of Poisson distribution decreases in proportional to 1/√λ. And a hypothesis is proposed that if the width of a transistor is k times larger, the number of injected electrons becomes k times larger, and the effect of one injected electron is reduced to 1/k. This helps narrow the mismatch shift distribution shape and reduce the ‘tail’.
To predict the effect of multiple-size transistor on SRAM PUF stabilized by HCI, the statistical model for mismatch distribution after HCI is applied to normal-size transistor SRAM PUF and multiple-size transistor SRAM PUF. According to statistical model calculation, it is predicted that to achieve the low bit error rate (BER) requirement of within -20mV to 20mV mismatch range, the cumulative possibility is smaller than ?1E?^(-6), normal-size, double-size, and quadruple-size transistor PUF take 46-min, 25-min (0.54x) and 15-min (0.32x) burn-in time, respectively. By using quadruple-size transistor SRAM-PUF, HCI burn-in time is more than 3 times shorter than normal-size transistor.
1E1-2
A 5-Bit-Response Modeling Attack Resistant Strong Physically Unclonable Function
◎劉 昆洋(早稲田大学)
、篠原 尋史(早稲田大学)
A Strong PUF for lightweight IoT authentication was designed with a 5-bit response architecture to reduce the CRP consumption and related latency/energy for one authentication. Meanwhile, it realizes improved attack resistance with an obfuscated substitution-permutation network and several innovative techniques. This is proved with 40M CRP-trained modeling attacks, modeling attack stress tests, and close-to-ideal statistical performance.
Study on a Low-cost Privacy Conscious Surveillance System
○Yixuan He(Okayama University)
、Yuta Kodera(Okayama University)
、Takuya Kusaka(Okayama University)
、Yasuyuki Nogami(Okayama University)
With the rapid development of IoT technology in recent years, more and more weak terminal devices, like
surveillance cameras, have been able to acquire a large amount of private information. The problem of how to store those data securely and with great efficiency is becoming increasingly prominent. To tackle the issue, we devise a low-cost, secure surveillance system with a 4-layer model: device layer, data
storage layer, authentication layer, and user layer. The device layer is designed by Yolov5 and DeepSort to detect and track objects. By using identity-based encryption algorithms to solve the authentication problem at the authentication layer. The key features of this system are using AES and secret sharing scheme to realize security data storage at the data storage layer. More precisely, cameras get the detection results and transfer them to the data storage layer. According to the level of privacy they contain, those data are split into four parts and encrypted using four different keys. Utilizing multiple levels of secret sharing scheme to accomplish encryption key management and user access control. As a result of an experiment, the proposal significantly reduced the cost of storage.
In this paper and talk, we will provide an overview over the current research landscape on connected, automated & cooperative driving (CCAM) security and privacy. Starting from an overview over the past 20 years of research on automotive security, we will then discuss the challenges that CCAM provide and outline how subjective trust models can be used to model and analyze security in highly complex automotive CCAM systems-of-systems.
1E3-2
A Policy-driven Architecture for Security Incident Mitigation in Connected Vehicles
○Florian Fenzl(Fraunhofer SIT)
、Felix Gail(Fraunhofer SIT)
、Lukas Jäger(Fraunhofer SIT)
、Christian Plappert(Fraunhofer SIT)
、Roland Rieke(Fraunhofer SIT)
、Hussein Joumaa(Huawei)
、Ali Hariri(Huawei)
With vehicle networks increasing more and more in complexity to enable more advanced
features, such as autonomous driving, their cyberattack surface increases. In order to mitigate up-
coming cyberattacks, more sophisticated and adaptable security approaches are required. Especially
critical is the secure implementation of usage control systems within automotive networks since the in-
creased communication with external entities provides attackers with new ways to infiltrate the vehicle
network. Modern standard access management systems have difficulty dynamically adapting to new
situations or responding to potential attacks. To improve security and adaptability of usage control
systems, we propose means to integrate additional in-vehicle security measurement and verification
mechanisms, e.g., based on an Intrusion Detection System or Hardware Trust Anchors like Trusted
Platform Modules, with our policy driven usage control system. This allows us to incorporate runtime
and boot-time security incidents into our policy decisions. In addition, we discuss the described system
using some application scenarios for intrusions as an example.
1E3-3
Using TARA artefacts to generate and optimize test-suits
◎Anderson Ramon Ferraz de Lucena(DENSO automotive Deutschland gmbh)
、Markus Hoffmann(Freie Universitat Berlin)
、Florian Sommer(Karlsruhe University of Applied Sciences)
As interconnected systems are exposed to attacks by nature, the security of those systems plays a big role in their development process. To mitigate those threats controls are chosen to lessen the feasibility of an attacker to trigger a threat scenario. To ensure the controls work as intended the systems should be tested. Creating tests by hand is work intensive and prone to overlook the overall coverage of the system. Therefore, we propose an automated way of creating generic testcases and also a way of checking the overall coverage of the security requirements. This enables the possibility to ensure that a system is well-tested with less afford then when testcases are created manually.
Smart traffic lights systems (STLSs) are a promising approach to improve efficiency and safety at intersections. They rely on the information in the cooperative awareness messages (CAMs) sent by vehicles at the intersection which they are managing. Much work has been done on developing privacy mechanisms for STLSs given that they collect user data which allows for physical tracking of users. However, privacy mechanisms are also known to have an impact on the performance of STLSs. This paper analyzes the extent to which different privacy mechanisms affect the performance of two types STLS, phase-based and reservation-based STLS. It does this by first implementing the STLSs in SUMO and then running multiple simulations with various traffic scenarios. Time loss, waiting time, fuel consumption, and average velocity are the performance metrics that were analyzed. The analysis shows that the impact of privacy mechanisms on performance varies greatly depending on the STLS type. Finally, a hybrid STLS that is a combination of the two STLS types was proposed as potential solution for limiting the impact of privacy mechanisms.
Towards a Fine-grained Analysis of the Syndrome Decoding Problem: An implementation and comparison of modern ISD algorithms
○Mohamed Abdelmonem(KDDI Research Inc)
、Shintaro Narisada(KDDI Research Inc)
、Kazuhide Fukushima(KDDI Research Inc)
Code-based cryptography is one of the most promising candidates for public-key cryptosystems in the post-Quantum era. Originally, linear codes were used in signal processing, but as they are thought to be secure against a cryptanalytic attack by quantum computers, they have received a lot of attention recently and became one of the finalists of the NIST Post-Quantum Cryptography standardization process. The Syndrome Decoding problem (SDP) is proven to be NP-complete, and the best-known solvers are constructed from Information Set Decoding (ISD), which offer, with required parameters, a cryptographically hard problem. Many authors have studied the selection of these parameters on classical ISD algorithms and developed improved algorithms based on an estimation of their theoretical performance. We implemented these algorithms in Python to assess the practical hardness of these algorithms by solving several instances of the SDP and provide a comparison of our results with the theoretical results proposed by other authors.
Generating Falcon Trapdoors via Gibbs Sampler
◎Chao Sun(Kyoto University)
、Thomas Espitau(NTT Social Informatics Laboratories)
、Mehdi Tibouchi(NTT Social Informatics Laboratories, Kyoto University)
、Masayuki Abe(NTT Social Informatics Laboratories, Kyoto University)
Falcon is one of the NIST standardization candidates for post-quantum signature schemes. The trapdoor generation of Falcon, essentially amounts to the problem of generating two polynomials $f,g$ that satisfy certain conditions to reach a quality parameter $\alpha$ as small as possible, because when $\alpha$ is smaller, it becomes harder to do signature forgery (thus having higher security level) and the signature becomes shorter. The original approach to sample Falcon trapdoors, proposed by Ducas, Lyubashevsky and Prest (Asiacrypt 2014), is based on rejection sampling, i.e, generating $f, g$ with small coefficients and testing whether they satisfy the condition or not (if not, then repeat). In practice, $\alpha$ is chosen as 1.17, mainly because it is the smallest one to keep a mild number of repetitions.
In this paper, we propose a new approach to generate Falcon trapdoors using Gibbs sampler. From a high level point of view, the idea is that we start from a random point within the space that satisfies the desired quality and do random walks in that space. One interesting feature of this approach is that we can reach $\alpha$ arbitrarily close to 1 fairly efficiently. By comparison, reaching a quality parameter $\alpha = 1.1$ with rejection sampling requires millions of repetitions. As a result, by reaching smaller $\alpha$ and some other optimization techniques, we are able to increase a few bits of security for Falcon-512, reaching a standard NIST level one security. Besides, our approach removes the use of discrete Gaussian sampling, which is non-trivial to implement correctly. Actually, our approach only requires a uniform sampler over an interval.
Notes on the Strength of Finsler Encryption
○永野 哲也(長崎県立大学)
、穴田 啓晃(青森大学)
Finsler encryption scheme was proposed at CSS2019, SCIS2020 and SECITC2020, and has been studied with improvements (CSEC95 and SCIS2022). In this paper, the strength of Finsler encryption is presented in detail, the ideas of which was introduced at CRISMATH2022. One of the improvements is to increase the number of parameters of the public key. When a public key has $n+2$ parameters where the Finsler space is of dimension $n$, new $(n+1)k$ parameters are introduced, where $k(\geq n)$ is a natural number. This means that, in the simultaneous algebraic equations derived from a public key and a ciphertext, the number of unknown variables are larger than the number of equations.
The other point of our argument is that the number of elements of a secret key is increasing as depending on the dimension of Finsler space. The decryption uses simultaneous linear equations and energy equation as the norm of a vector from owing to special structure of Finsler space.
The simultaneous linear equations are derived from $n^2 + n+ 1$ parameters, and the energy equation has $n + {}_n C_2$ parameters. As a result, the length of a secret key depends on the number of dimension.
We revisit two security notions for public-key encryption (PKE): non-committing (NC) encryption and obliviously sampleability (OS). NC-PKE is the main tool to realize the secure message transmission functionality in adaptively secure multi-party computation. OS-PKE is a building block for various cryptographic primitives, including NC-PKE.
In this work, we propose a normal form of definitions for OS-PKE and NC-PKE, which focus on the randomness used in the algorithms. Then we observe that the normal form of NC and OS are in a dual relation; not only do they have similar security definitions but also there exists an interconversion that transforms OS to NC and NC to OS.
We also show that OS-PKE can be transformed into pseudorandom (PR) PKE, the simplest representative of OS-PKE. In summary, we previously knew that PR implies OS and OS implies NC, but actually, they are existentially equivalent under the normal form.
In July 2022, NIST announced to standardize three post-quantum digital signature algorithms: CRYSTALS?Dilithium, FALCON, and SPHINCS+. Blockchain security is especially threatened by quantum computing, and all chains will need to transition to post-quantum cryptographic (PQC) standards just as they initially embraced classical standards. Unfortunately, this opens up a new problem, namely, PQC algorithms tend to be much more expensive than their classical counterparts in terms of size. This is particularly problematic for blockchains where each full node keeps an entire record of all activities on the blockchain. If Bitcoin and Ethereum were to adopt the newly standardized PQC algorithms today, the size of both chains would explode. Even with the most space-efficient FALCON algorithm, public keys and digital signatures would consume 21.2x and 24.3x more space in Bitcoin and Ethereum, with the size of their respective ledgers increasing by 2.2x and 2.22x. These performance issues have widespread implications, affecting transaction speed, gas prices, and perhaps even the decentralization of the entire network. Upgrading blockchain security is not as simple as dropping in a PQC algorithm as a replacement for current algorithms. Here we present PQScale, a post-quantum signature aggregation algorithm that can combine multiple FALCON signatures and reduce the aggregated signature size by a factor of more than 20x when aggregating a few thousand signatures. It also has the potential to generalize and apply to other lattice-based digital signature algorithms.
2A4-2
Quantum Random Oracle Model上でのSequential OR SignatureのMulti-user Security
○福光 正幸(長崎県立大学)
、長谷川 真吾(東北大学)
Sequential OR Signatureは, Tight Reductionにより, MU-EUF-CMA (Multi-user Existential Unforgeability against Chosen-message Attack) with Corruptionを証明できることが知られている. PKC2022にてPan, Wagnerは, LatticeやIsogenyなどの耐量子計算機な方式にこの結果を拡張できることを示した. しかし, Pan, Wagnerの結果はClassical Random Oracle Model上での結果であり, Quantum Random Oracle Model上で同様の結果が成立するかどうかを未解決問題として残していた. そこで本稿では, Quantum Random Oracle Model上で, Sequential OR SignatureのMU-EUF-CMA with Corruptionを証明するTight Reductionを構成する.
2A4-3
Probabilistic Hash-and-sign with Retry in the Quantum Random Oracle Model
○小菅悠久(防衛省)
、草川恵太(NTT社会情報研究所)
A hash-and-sign signature based on preimage-sampleable function (PSF) (Gentry et al. [STOC 2008]) is secure in the Quantum Random Oracle Model (QROM) if the PSF is collision-resistant (Boneh et al [ASIACRYPT 2011]) or one-way (Zhandry [CRYPTO 2012]). However, trapdoor functions (TDFs) in code-based and multivariate-quadratic-based (MQ-based) signatures are not PSFs; for example, underlying TDFs of the Courtois-Finiasz-Sendrier (CFS), Unbalanced Oil and Vinegar (UOV), and Hidden Field Equations (HFE) signatures are not surjection. Thus, such signature schemes adopt probabilistic hash-and-sign with retry. This paradigm is secure in the (classical) Random Oracle Model (ROM), assuming that the underlying TDF is non-invertible; that is, it is hard to find a preimage of a given random value in the range (e.g., Sakumoto et al. [PQCRYPTO 2011] for the modified UOV/HFE signatures). Unfortunately, there is no known security proof for the probabilistic hash-and-sign with retry in the QROM.
We give the first security proof for the probabilistic hash-and-sign with retry in the QROM, assuming that the underlying non-PSF TDF is non-invertible. Our reduction from the non-invertibility is tighter than the existing ones that apply to only signature schemes based on PSFs. We apply the security proof to code-based and MQ-based signatures.
社会活動のデジタル化が進むに連れ、プラットフォームによるパーソナルデータの不透明な扱いや、事業者によるデータ管理コストの増大が社会課題となっている。現状の中央集権的なデータ管理手段を代替もしくは補完するものとして、近年、より分散的で個人中心型のアプローチが注目を集めている。アイデンティティ・ウォレットやDecentralized Web Node(DWN)と呼ばれる仕組みは、データ発行者による署名が付与されたVerifiable Credential(VC)を保存でき、データ利用サービスからの要求に応じて必要なVCだけを提示する機能を備えた、個人利用データストアの一種である。ここで、データストアに対する要求は独自言語で表現され、クエリ表現の多様性や柔軟性に劣る点が課題であった。本稿では、W3C標準であるクエリ言語SPARQLを用いた柔軟なクエリを可能とし、かつクエリ結果の検証と開示データの最小化が可能なデータストアの構成法を提案する。構成には、BBS+署名等のAnonymous Credential向け署名方式と、Bulletproofs等の汎用ゼロ知識証明を利用する。
近年,様々なものがインターネットに接続され,生活の中にIoT機器が増えている.IoT機器で取得した様々なデータを,IoTゲートウェイを通してそれぞれ複数アプリケーションに提供するシステムがある.この時アプリケーションごとに復号制御をしてデータの不正利用を防止することが望ましい.Pengら(ACM Trans. Internet Technol., 2021)はこの状況においてデータの安全性を保つための暗号化方式を提案した.Pengらの方式では登録されたアプリケーションに対して部分復号を行うエンティティを置くことで,アプリケーションごとにリアルタイムの復号制御を可能にしている.本研究ではIoTゲートウェイを用いたシステムにおける安全性をより状況に適した形で定義し,Pengらの方式の脆弱性を指摘し,新たな暗号化方式の提案を行う.
Efficient and Appropriate Key Generation Scheme in Different Internet of Tings Scenarios
◎Hong Zhao(University of Aizu)
、Chunhua Su(University of Aizu)
Most Internet of Things (IoT) devices have limited computing power and resources. Therefore lightweight encryption protocols are essential to secure communications between IoT devices. As a promising technique, physical layer key generation has been widely used in IoT applications to secure communication between devices. In this paper, we propose an Efficient and Appropriate Key Generation Scheme (EAKGS) for various IoT scenarios. According to the characteristics of the channel data, we design the pre-judgment stage to classify the values. Considering the key generation requirements and measured values characteristics in different scenarios, we propose efficient key generation schemes for static and dynamic scenarios. Furthermore, we conduct real-world experimental analysis and validation of our scheme. We analyze the feasibility of the scheme from key generation rate, key error rate and randomness. Experimental results show that our EAKGS is qualified in terms of adaptability and key performance.
2B4-2
Providing Accountability for Secure Zero Touch Provisioning
○Danu Dwi Sanjoyo(Kanazawa Univerity)
、Masahiro Mambo(Kanazawa Univerity)
Secure Zero Touch Provisioning (SZTP) is a provisioning technique for networking devices in a zero-touch fashion. SZTP provides the provisioning workflow from device enrollment between the Provider and Manufacturer until bootstrapping process. Unfortunately, implementing a single trust model of public key infrastructure scheme in zero-touch device provisioning is vulnerable to impersonation attacks using bogus certificates. This paper proposes a robust protocol for the bootstrapping process of edge devices by integrating the Attack Resilient Public Key Infrastructure (ARPKI) scheme with SZTP. ARPKI offers strong security as certificate management for SZTP. We adopt the security properties of ARPKI to construct an accountable bootstrapping scheme of a zero-touch provisioned edge device against threats, e.g., impersonation, incurred by insiders compromised by adversaries. We analyze our scheme's security properties by performing formal and informal analyses. We show that the combination of ARPKI and SZTP can detect malicious entities and mitigate misbehaving activities. Our provisioning scheme provides accountable bootstrapping for edge devices in a zero-touch fashion with integrity and confidentiality of bootstrapping data.
IoT分野における連合学習のオープンなプラットフォームの一つに,FedIoT(Federated Learning for Internet of Things)がある.本論文では,まず,FedIoTの評価で用いられていなかったデータセットを用いて実験した結果として,DDoS攻撃のトラフィックとは異なる統計的性質を持つ攻撃トラフィックでは検知性能が著しく低いことを指摘し,特徴量選択が有効であることを確認している.次に,選択した特徴量を単純にすべて使用する方法では検知性能は大きく向上することはないことを指摘し,攻撃の種類ごとにオートエンコーダを構築することが有効であることを確認している.すなわち,FedIoTのフレームワークにおいて,特徴量選択と特徴的な攻撃ごとに検知器を構築する手法を提案し,検知性能について議論している.本研究では,FedIoTに特徴量選択を適用しCICIDS2017の異常検知を行った結果,F1Scoreを7.21%から73.17%まで向上させることができた.
平常時と攻撃発生時の通信パケットの分布の差に着目したセキュリティ対策として,相対エントロピーを用いた攻撃検知手法が研究されている.平常時と攻撃時の確率分布の違いを相対エントロピーで評価できるため,DoS(Denial of Service)攻撃等の平常時とトラフィックが変化する攻撃は検知が容易である.一方,通常時のトラフィックを模倣する高度な偽装攻撃では相対エントロピーの値が小さくなり得るため,防御者は相対エントロピーを改善する通信方法や観測方法が必要である.そこで我々は制御システムで用いられるModbus TCP通信を対象に,相対エントロピーによる攻撃検知や攻撃時に小さくなった相対エントロピーの改善方法について検討する.本稿ではまず,相対エントロピーを用いた制御システムにおけるDoS攻撃の検知を行う.次に,リプレイ攻撃に対して相対エントロピーによる攻撃の検知を行う.この2つの結果から,尤度比検定により理論的に達成できる検知性能と実際の検知性能の関係を考察する.また,仕様が公開されているModbus TCPのペイロード部分にダミー信号の追加を検討する.ダミー信号を生成する確率分布を攻撃者から秘匿し,相対エントロピーの値を改善する方法について考察する.
近年,情報システムや制御システムを標的とするサイバー攻撃の脅威が増してきている.制御システムのように攻撃による被害が大きいシステムでは,存在するリスクの中で実際の攻撃につながりうるものを評価し,対策を講じることが求められる.リスク評価には攻撃のシナリオの検討・実証を行うペネトレーションテストが有効だが,専門家の高度なスキルが必要であり,セキュリティ技術者の育成や依頼費用の面で課題がある.このうち攻撃シナリオの検討を自動化する技術としてBreach and Attack Simulationが提案されているが,実機を用いて攻撃の成否を評価することが困難であり,実際には攻撃に失敗するような攻撃シナリオが提示される場合がある.そこで,システムに対する攻撃シナリオの生成および実証を自動化する技術を開発した.模擬制御システムを用いた実験を行い,攻撃シナリオが正しく生成されること,攻撃シナリオを自動で実行して攻撃の成否の評価が可能であることを確認した.これにより,専門家不在の組織でも容易に実際の攻撃や被害につながりうる攻撃シナリオを検討することができ,セキュリティリスクの把握が可能になる.
Combined Power Analysis and Lattice Attack on CRYSTALS-Kyber
◎Yen-Ting Kuo(University of Tokyo)
、Atsushi Takayasu(University of Tokyo)
CRYSTALS-Kyber is a key-encapsulation mechanism (KEM), whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. As in its specification, Kyber prescribes the usage of the Number Theoretic Transform (NTT) for efficient polynomial multiplication. Side-channel assisted attacks against Post-Quantum Cryptography (PQC) algorithms like Kyber remain a concern in the ongoing standardization process of quantum-computer-resistant cryptosystems. Among the attacks, correlation power analysis (CPA) is emerging as a popular option because it does not require detailed knowledge about the attacked device and can reveal the secret key even if the recorded power traces are extremely noisy. In this article, we present a methodology to utilize CPA to recover a portion of the secret key from the power consumption of these polynomial multiplications in the decryption process. Then, using the information, we are able to fully recover the secret key by constructing an LWE problem with a smaller lattice rank and solving it with lattice reduction algorithms. The CPA can be further parallelized and experiment on simulated traces shows that the whole process can be done within 20 minutes on a 16-core machine.
Probeheap: a fuzzing model accelerates test on linux heap allocator
◎Liu Peilin(東京大学)
、Miyamoto Daisuke(東京大学)
With the development of memory security mechanisms, the attackers focus more on the heap vulnerabilities. The Heap allocator is crucial in this aspect because it directly interacts with the potential malicious user. The security test on the heap allocator has therefore become a critical topic. Besides, the number of vulnerabilities has increased exponentially in recent years, which automatically explores potential vulnerabilities in a rising field. Automated exploit generation, shorted as AEG, helps security-related engineers find vulnerabilities in any kind of system much faster than ever. It was created from the idea of making a tool that could automatically find, assess and even generate exploit code for all potential exploits. This paper introduces a new algorithm, called bin penetration, to help accelerate fuzzing tests on Linux heap allocator. Our evaluation shows that less time is spent generating the same exploits compared to other works. We also assess the other metrics, including the overfitting problem and completeness of the system.
関数型暗号は、平文 x の暗号文を関数 f の秘密鍵で復号した時、関数値 f(x) が復号され、それ以外に x に関する情報が漏れないという特徴を持つ暗号方式である。関数型暗号において、 f がどのような関数クラスのものを扱えるかは、重要な研究対象であり、二次関数を扱う関数型暗号がペアリングから構成できることは知られている。しかし、これまでの二次関数型暗号は全てセットアップ時に平文長が固定されるという性質があった。本稿では、セットアップ時に平文長が制限されない二次関数型暗号をペアリングから構成する。
Considering that secure computing for multi-level users in enterprises, the notion of hierarchical identity-based inner product functional encryption scheme (HIB-IPFE) is proposed. This cryptosystem utilizes a hierarchical structure from the identity of the receiver while encrypting the vector x into ciphertext. A receiver can compute the inner product ?x, y? if they have the secret key for vector y. However, HIB-IPFE still lacks the flexibility of access control in cloud computing. In this paper, motivated by fine-grained revocation of decryption capacity, we propose a hierarchical identity- based puncturable scheme for inner product functional encryption (HIBP-IPFE). Our scheme allows users to puncture keys on tags, so that punctured keys with a specified key cannot be used to decrypt the ciphertext under those tags. For fine-grained access control, the high-level users can decide the decryption capacity for the low-level users. We formalize the formal definition and security models for HIBP-IPFE, and prove that the proposed scheme is secure under d-DBDHE assumption. In addition, we demonstrate that the theoretical analysis of our scheme satisfies desired features and is more practical in secure computing.
Receiver selective opening (RSO) security considers the security of encryption cryptosystems under the scenario of one sender and multiple receivers, where an adversary is allowed to adaptively corrupt some receivers' secret keys. In particular, RSO security has been proven that be more securer than standard securities (i.e., indistinguishability-based chosen-plaintext/ciphertext attacks). Much research has focused on RSO security in terms of public-key encryption and identity-based encryption (IBE); however, hierarchical IBE, which is a generalization of IBE, is still lacking in the study, and how to obtain such construction remains an open problem. To fulfilling this research gap, we initiate the study of RSO security on HIBE in this work. Precisely, we first formalize the definition of simulation-based RSO against chosen-plaintext/ciphertext attacks (SIM-RSO-CPA/CCA) for HIBE. We then introduce two generic SIM-RSO-CPA and SIM-RSO-CCA secure HIBE constructions. More specially, we show that (i) a SIM-RSO-CPA HIBE can be obtained from an IND-ID-CPA HIBE; (ii) a SIM-RSO-CCA HIBE can be obtained from an IND-ID-CPA secure HIBE as well as a NIZK that satisfies unbounded simulation soundness and multi-theorem zero-knowledge. Through our general construction, we can derive various concrete schemes based on different hard assumptions (e.g., pairing-based and lattice-based SIM-RSO-CPA/CCA HIBE) according to usage requirements.
How to compute multiplication in FHE encoding integer plaintexts into polynomials
○王中琦(筑波大学)
、梨本健斗(筑波大学)
、西出隆志(筑波大学)
Ring-LWE-based homomorphic encryption schemes such as BFV or BGV are popular because of their many good properties. Iliashenko et al. (PoPETs’22) proposed an efficient method to compute a BFV ciphertext of X^f (z) from a BFV ciphertext of X^z by encoding the input integer z as a polynomial X^z where f can be an arbitrary function. In this encoding, the homomorphic addition of a and b can be computed as X^(a+b) from the normal BFV homomorphic multiplication of X^a and X^b. A potential disadvantage of their scheme is that how to compute the homomorphic multiplication in that encoding (i.e., how to compute a BFV ciphertext of X^ab from BFV ciphertexts of X^a and X^b) is lacking, and in this work, we propose a method to compute the homomorphic multiplication.
同種写像に基づく暗号アルゴリズムの高性能ハードウェア実装
◎Hung Bui(The University of Tokyo)
、Makoto Ikeda(The University of Tokyo)
Post-quantum cryptography (PQC) is gaining steady traction as the next-generation of public-key cryptography due to its inherent resistance towards quantum and classical attacks. Of the various algorithmic approaches, supersingular isogeny-based algorithms such as SIKE offer many advantages over the others, primary of which are small-size public-keys and cipher-texts. However, its main deficiencies lie in its relative maturity and overall speed. Regarding the latter, these algorithms have execution times (1s-10s in software; 10ms-100ms in hardware) several magnitudes higher than the other types. To alleviate this issue, this research benchmarked the full potential of supersingular isogeny-based algorithms and provides 3 hardware implementations that have execution times up to 10 times faster (500us-7.50ms) than existing designs using SIKE as the case study. These implementations are developed using a seldom used top-down approach, which starts with a fully-parallelized implementation and creates further implementations by strategically placing clocks from top-to-bottom in the operation hierarchy.
PoDDL: A Provably Secure (Weight-Based) Blockchain Protocol via Proof-of-Useful-Work for Distributed Deep Learning
◎Xiangyu Su(Tokyo Institute of Technology)
、Mario Larangeira(Input Output HK, Tokyo Institute of Technology)
、Keisuke Tanaka(Tokyo Institute of Technology)
Proof-of-useful-work (PoUW), an alternative to the widely used proof-of-work (PoW), aims to re-purpose the network's computing power. Namely, users evaluate meaningful computational problems, e.g., solving optimization problems, instead of computing numerous hash function values as in PoW. A very recent approach is to utilize the training process of deep learning as the ``useful work''. However, these works lack security analysis when deploying them with blockchain-based protocols, let alone the informal and over-complicated system design. This work proposes a proof-of-distributed-deep-learning (PoDDL) scheme concerning PoUW's security requirements. With a novel hash-training-hash structure and model-referencing mechanism, our scheme is the first deep learning-based PoUW scheme that enables training models distributively. Next, we demonstrate a transformation from the PoDDL scheme to a generic PoDDL blockchain protocol and introduce two concrete protocol constructions by instantiating chain selection rules with the ``longest-chain rule'' and the ``weight-based blockchain'' framework (LatinCrypt' 21). Finally, we analyze the security of our concrete protocols in terms of the robust ledger properties, i.e., the chain growth, chain quality, and common prefix property.
Keelung: A domain-specific language for developing ZK applications
Ting-Gian Lua(BTQ AG)
、Tzu-Chi Lin(BTQ AG)
、Po-Chun Kuo(BTQ AG)
、○Chen-Mou Cheng(BTQ AG)
Zero-knowledge (ZK) proof techniques are revolutionizing the world of blockchains and Web3. However, developing ZK applications is still a labor-intensive task and an error-prone process, partly because the development tools are still far from mature. We present Keelung, a domain-specific language and development toolkit for ZK applications. By raising the abstraction level, Keelung makes it easy for the programmer to focus on the business logic rather than the low-level nuts and bolts of the underlying ZK proving system. Last but not least, embedding Keelung into Haskell allows its programmers to leverage Haskell's extensive libraries and rich ecosystem, making ZK application development no more painful than it needs to be.
A Spendable Cold Wallet from QR Code
Rafael Dowsley(Monash University)
、Mylene C.Q. Farias(University of Brasilia)
、◎Mario Larangeira(Tokyo Institute of Technology/IOG)
、Anderson Nascimento(University of Washington)
、Jot Virdee(University of Washington)
Hot/cold wallet refers to a widely used paradigm to enhance the security level of cryptocurrency applications that was proposed on Bitcoin Improvement Proposal 32. In a nutshell, after performing an initial setup in which the hot wallet receives partial information of the cold wallet in order to hierarchically generate (transaction receiving) addresses, the cold wallet stays offline, whereas the hot wallet is kept online. The initial transferred information enables the hot wallet to generate receiving addresses for both wallets, but it can only spend its own funds, i.e., it cannot spend the funds in the cold wallet. This design conveniently mimics money storage in daily life: pocket money is kept in a less safe location, e.g., a regular wallet, while life savings are kept in a more safe environment, e.g., banking account. Note that the funds that land in offline addresses cannot be spent if the cold wallet is kept permanently offline. We propose a protocol and a technical solution to spend funds from a cold wallet without physically connecting it to any network. We designed and implemented a prototype for a system based on Optical Camera Communication (OCC) in a screen to camera setting, which can receive messages from a computer screen at the rate of over 150kB per second. Our system consists of a sequence of QR codes -- a QR video. Our solution minimizes the possible attack vectors, including malware, by relying on optical communication yet providing a larger bandwidth than regular QR code based solutions.
記録の改さんが困難なブロックチェーン基盤の登場で、電子投票への応用も期待されている。発表者も、それまでは物理的仮定だった投票集計盤が、ブロックチェーンにより、常識的基盤になった効果を論じた[ブロックチェーンを利用した電子投票システムの安全性(SCIS2020)]。
しかし、果たして、電子投票システムはどこまでサイバー攻撃に耐えうるのか。米国ではMITのRivestらが否定的な限界を論じている[Going from Bad to Worse: From Internet Voting to Blockchain Voting (Draft/2020.Nov, Journal of Cybersecurity/2021.Feb.)]。その一方で、欧州は欧州研究集会e-Vote-IDが2007年以降、脈々と続いている。
本発表では、こうした欧米の電子投票システムの研究動向を報告する。[392文字]
Attention-Based Non-Profiled SCA on ASCAD Database
○Enhao Xu(Dept. of Informatics, The University of Electro- Communications, Tokyo, Japan)
、Takeshi Sugawara(Dept. of Informatics, The University of Electro- Communications, Tokyo, Japan)
、Kazuo Sakiyama(Dept. of Informatics, The University of Electro- Communications, Tokyo, Japan)
、Yuko Hara-Azumi(Dept. of Communications & C.E., Tokyo Institute of Technology, Tokyo, Japan)
、Yang Li(Dept. of Informatics, The University of Electro- Communications, Tokyo, Japan)
With the publication of attention in 2017, attention-based models occupy more than half of the top 10 in many fields’ major benchmarks, such as image classification and natural language processing (NLP). Therefore, compared with conventional DL-based techniques in non-profiled side-channel attacks (NP-SCA), such as convolutional neural network (CNN) based or multilayer perceptron (MLP) based, it is valuable to try using attention in the NP-SCA field. To our knowledge, only a few DL-based methods have been applied to NP-SCA. For example, the differential deep learning analysis (DDLA) based technique by Timon. Or the auto-encoder-based approach by Kwon et al.. In this paper, we first implemented NP-SCA on ASCAD fixed key database, a database consisting of one key byte’s leakage extracted by the proposer as a benchmark. The key byte was successfully recovered in 2000 traces, one-tenth of previous work. Furthermore, we tried to recover more key bytes using the raw ASCAD data. The result shows that our model has the generality to recover not only single key byte in the benchmark database but also multiple key bytes without adjusting the network's hyper-parameters.
近年,車載ネットワークにおいて,様々なサービス形態に柔軟に対応可能なサービス指向プロトコルであるSOME/IP(Scalable service-Oriented MiddlewarE over IP)の導入が注目されている.一方で車載ネットワークは外部からの攻撃による危険性が多数報告されており,使用するプロトコルのセキュリティ評価は重要である.現在,SOME/IPのセキュリティに関する研究は始まったばかりで,特にプロトコルスタックについては十分なセキュリティ評価がされていない.本研究では,SOME/IPプロトコルスタックに対してSOME/IP-SDメッセージを対象に複数の方式によるグレーボックスファジングを実施し,カバレッジ等のファジング性能の比較評価および検出したクラッシュについて考察を行った.結果より,SOME/IP-SDのフォーマットを考慮したファジングを実施することで,クラッシュが検出でき,ソースコードの安全性を向上することが確認できた.
Transferability of adversarial samples in machine learning based NIDS
○Mariama Mbow(Kyushu University)
、Hiroshi Koide(Kyushu University)
、Rodrigo Roman(University of Malaga)
、Kevin I-Kai Wang(University of Auckland)
、Kouichi Sakurai(Kyushu University)
In this paper we study the vulnerability of machine learning based network intrusion detection system (NIDS). In recent years, traditional machine learning and deep learning techniques have been adopted in NIDS to improve the attacks detection rate and with promising results. However, recent researches have shown that deep learning algorithms are prone to adversarial attacks. But not many works have investigated the vulnerability of traditional machine learning. This paper evaluates the robustness of traditional machine learning based NIDS. We first craft adversarial samples from a deep learning in white box setting and adopt the transferability methods to evade the machine learning detector.
Cryptanalysis of the randomized version of DRS scheme
◎Moeto Suzuki(Kyoto University)
、Mehdi Tibouchi(Kyoto University, NTT Social Informatics Laboratories)
、Masayuki Abe(Kyoto University, NTT Social Informatics Laboratories)
As one of the main approaches to postquantum cryptography, lattice-based cryptosystems have attracted a lot of attention, and have been the subject of active research in the past decade. DRS v1 was one of the signature candidates for the NIST postquantum round 1 competition and touts itself as simple and efficient. However, it was broken at least in principle by the Ducas-Yu statistical attack. In an attempt to mitigate the attack, the authors of DRS developed DRS v2, which is supposed to make the attack impractical, although it still lacks a clear proof of security.
In addition, a randomized version of DRS (both v1 and v2) was introduced to protect against certain classes of side-channel attacks. Li, Liu, Nitaj, and Pan presented an attack against DRS v1, which can successfully recover the absolute values of the coefficients of the secret key in a certain range of parameters. However, it fails to recover the signs (making it incomplete as a key recovery) and is also not analyzed against DRS v2.
In this work, we improve and extend the analysis of Li et al., and propose attacks on the randomized versions of both DRS v1 and v2. For DRS v1, we show that recovering the signs of coefficients reduces to an easily solved low-density knapsack. We also show how the attack should be modified to target DRS v2.
As a result, we are able to recover the entire secret key of randomized DRS v1 and v2. Moreover, our proposed method of recovering the signs of the coefficients also improves the Ducas-Yu attack, casting further doubt on the security of DRS.
Proposing a Trade-off SVP-solving Strategy by Improving pnj-BKZ Simulator
◎Leizhang Wang(Osaka University; Xidian University)
、Yuntao Wang(Osaka University)
、Baocang Wang(Xidian University)
Sieving is one of the best-known (approximate) SVP-solving algorithms in lattice theory. Sieving runs in a minimum exponential time complexity and exponential space cost with respect to the dimension of the lattice. It is critical to decreasing the memory cost of sieving when solving higher dimensional SVP. In 2018, Thijs Laarhoven et al. proposed a so-called progressive sieving whose running time and memory cost are primarily affected by the quality of the input lattice basis.
Currently, there are two main strategies for solving (approximate) SVP. One is the SVP solving strategy proposed in G6K, which has the least solving time cost but high memory cost requirements; another is to execute progressive BKZ (pBKZ) for preprocessing first, and then call the high-dimensional SVP-oracle to find the short vector on the original lattice. Due to the strong preprocessing on the lattice basis, the memory cost of the latter strategy is smaller than that of the former strategy, while the time cost of preprocessing in the latter strategy is relatively vast. In this paper, we revisit the pump-and-jump BKZ (pnj-BKZ) and optimize its simulator when the jump value is quite large. Then, based on the sharper pnj-BKZ simulator, we propose an SVP-solving strategy trade-off between G6K and pBKZ, which derives less time cost than pBKZ within less memory compared with G6K to solve higher-dimensional SVP instances.
Experimental results show that when solving the TU Darmstadt SVP challenge, our algorithm can save 50%-66% of memory compared with G6K's default SVP-solving strategy. Furthermore, our algorithm speeds up the preprocessing stage by 7-30 times, and it saves 4-6 times the time cost compared with pBKZ default SVP-solving strategy. Finally, using our proposed strategy, we solved the 170-dimensional TU Darmstadt SVP challenge and up to the 172-dimensional ideal lattice challenge.
International Mutual Recognition, A description of trusted services in US, UK, EU and Japan and the Testbed "Hakoniwa"
○Satoshi KAI(Keio university)
、Takao KONDO(Keio university)
、Konstantinos Mersinas(Royal Holloway, University of London)
、Naghmeh Karimi(University of Maryland, Baltimore County)
、Satoru TEZUKA(Keio university)
With the expected proliferation of digital transactions, trust is becoming increasingly important, as exemplified by Data Free Flow with Trust (DFFT). Digital signatures are often used to establish trust to prevent the spoofing or alteration of transmitted digital data. However, if the extent of trust guaranteed by the legally jurisdiction or technically trusted list or bridge Certificate Authority (CA ) is exceeded, the digital signature mechanism will not be able to prevent spoofing or tampering. For this reason, mutual recognition is known as mutual recognition, which means that trust recognized in one country must also be recognized in another country. Mutual recognition itself takes time to be established because of the laws, systems, and technologies involved. On the other hand, since electronic signatures consist of complex systems, early technical assistance can enhance mutual recognition. Therefore, the purpose of this study is to develop a testbed that can verify technical aspects of mutual recognition at hand. This paper describes the basic concept of the testbed “Hakoniwa”, the requirements for simulating trust services in EU, UK, US, and JP, and the planned mutual recognition experiments.
The Sleeve Framework: Hidden Secure Fallback for Cryptocurrency Wallets
David Chaum(XX Network)
、◎Mario Larangeira(Tokyo Institute of Technology/IOG)
、Mario Yaksetig(University of Porto/XX Network)
We introduce a new key generation mechanism where users can generate a “back up key”, securely nested inside the secret key of a signature scheme. Our main motivation is that in case of leakage of the secret key, established techniques based on zero-knowledge proofs of knowledge are void since the key becomes public. On the other hand, the “back up key”, which is secret, can be used to generate a “proof of ownership”, i.e., only the real owner of this secret key can generate such a proof. To the best of our knowledge, this extra level of security is novel, and could have already been used in practice, if available, in digital wallets for cryptocurrencies that suffered massive leakage of account private keys. In this work, we formalize the notion of “Proof of Ownership” and “Fallback” as new properties. Then, we introduce our construction, which is compatible with major designs for wallets based on ECDSA, and adds a W-OTS+ signing key as a “back up key”. Thus offering a quantum secure fallback. This design allows the hiding of any quantum secure signature key pair, and is not exclusive to W-OTS+. Finally, we briefly discuss the construction of multiple generations of proofs of ownership.
A Lattice-based Ring Signature Scheme Secure against Key Exposure
◎Yuntao Wang(Osaka University)
、Xiaoling Yu(Taiyuan University of Technology)
A ring signature scheme allows a group member to generate a signature on behalf of the whole group, while the verifier can not tell who computed this signature. However, most predecessors do not guarantee security from the secret key leakage of signers. In 2002, Anderson proposed the forward security mechanism to reduce the effect of such leakage.
In this paper, we construct the first lattice-based ring signature scheme with forward security. Our scheme combines the binary tree and lattice basis delegation technique to realize a key evolution mechanism, where secret keys are ephemeral and updated with generating nodes in the binary tree. Thus, the adversary cannot forge the past signature even if the users' present secret keys are revealed. Moreover, our scheme can offer unforgeability under standard models. Furthermore, our proposed scheme is expected to realize post-quantum security due to the underlying Short Integer Solution (SIS) problem in lattice-based cryptography.
Anonymous Reputation System (ARS) は,EC サイトにおいてユーザが購入した商品に対して匿名でレビューを付けられるシステムである.これは Blomer らによりグループ署名ベースのモデルで初めて定義され (FC’15),その後 El Kaafarani らにより安全性の強化が行われた (FC’18).本研究の貢献は以下の 3 つである.1 つめは,ARS の簡潔で自然なモデルの提案である.Blomer らのモデルは,管理者が2種類存在するモデルであったが,彼らのモデルではなりすましや偽造に対する安全性の考慮が不足していた.また,El Kaafarani らは1つの管理者のみを考えるモデルを提案したが,売買を管理者に委託するため信頼の一極化が生じ,また管理者はユーザの購入情報を見られるという問題が生じる.我々はこれらを防ぐ新たなモデルを提案する.2つめは,ARS の新たな安全性として Purchase Privacy を定義することである.これはグループ署名の安全性として Backes らにより提案されたものであり (CCS'19), ARS においては購入情報を秘匿するという重要な安全性を担う.また,既存の複雑な安全性定義が簡潔に定義できることを発見した.3つめは,効率的な一般的構成法を示すことである. 既存研究は全て特定の構成のみを提案しており,本稿は ARS の一般的構成法を示す初めての論文となる.
4B2-4
Collaborative but Controlled Tracing for Group Signatures
○Maharage Nisansala Sevwandi Perera(Advanced Telecommunications Research Institute International)
、Toru Nakamura(KDDI)
、Takashi Matsunaka(Advanced Telecommunications Research Institute International)
、Hiroyuki Yokoyama(Advanced Telecommunications Research Institute International)
、Kouichi Sakurai(Kyushu University)
We propopse a controlled tracing for group signatures. In our proposal, instead of a single centralized tracing authority there are multiple tracers possessing attribute sets. The signer id is encrypted in the signature with an attribute set. Thus attribute satisfying tracer can identify the signer. When there is no single tracer satisfying attributes, then based on the group manager agreement tracers can collaborate to identify the signer. Thus malicious users who try to be anonynous is prevented. On the other hand, group manager gets authority over tracers action.
2021年にYing Guoらによって提案された軽量ブロック暗号SHADOW-32に対してMILPを用いた差分パスの探索と鍵回復攻撃を行った。SHADOW-32はFeistel構造であり,フルラウンド16段,ブロック長32ビットの暗号である。SHADOW-32の提案者論文には、不能差分攻撃での定量的な安全性評価しかなされておらず、差分攻撃に関しては第三者評価もなされていない。本稿では、混合整数線形計画法(Mixed Integer Linear Programming:MILP)をもちいて差分特性を解析し、この差分特性用いて鍵回復を行った。
軽量ブロック暗号SHADOW-32の線形攻撃耐性評価を行った。Shadow-32は2021年にYing Guoらによって提案されたFeistel構造を持つブロック暗号である。ブロック長は32ビット、段数16段、鍵長は64ビットである。Shadow-32の提案者論文には、不能差分攻撃については定量的な安全性評価が記載されているが線形特性については評価が行われていない。そこで、本稿ではShadow-32に対する線形特性について混合整数線形計画法(Mixed Integer Linear Programming:MILP)を用いて調査を行い、発見した線形特性を利用することにより鍵回復を行った。
現在は様々な場面でメールが使用されており,機密な情報をメールを用いて送る際に,メールに,パスワードが必要な圧縮をした資料を添付し,別のメールでそのパスワードを送るPPAPが広く用いられている.しかしそれは安全性に欠けるうえに,使い勝手も悪いという問題がある.その代替案としてメール本文を暗号化し,認証する機能を持つS/MIMEがある.だが現在は,暗号化に使用する証明書の導入の困難性などから普及していない.本研究では,そのようなS/MIMEに対して利用しやすくする方法としてRPA(Robotic Process Automation)を用いて自動化の機能を実装し,評価実験を行ったのでその結果と残された課題について報告する.
User Perception of Value of Information in a Photo Privacy Tool
○Vanessa Bracamonte(KDDI Research, Inc.)
、Sebastian Pape(Goethe University Frankfurt)
、Sascha Loebner(Goethe University Frankfurt)
Privacy tools for photos could help protect users of social network sites, but previous research indicates that there can be a higher level of privacy concern towards those tools than towards non-privacy tools. Previous research has examined the possible reasons for this higher level of privacy concern, for example, that the privacy purpose of the tool can lead to higher awareness of the negative privacy-related consequences of providing data to the tool. In this study, we examine this effect of higher awareness in relation to the factor of perceived value of information. We conducted an online experiment to compare the perception and opinion of participants about a hypothetical privacy and non-privacy app for social media photos. The results show that in the privacy tool condition, participants had a higher perceived value of the information they provide the tool and the value of the information that the tool infers from them, compared to the non-privacy tool condition. In both conditions, we found a similar number of participants who indicated that they thought that their information had value to other entities, and this number was higher than the number of participants who thought their information had value only to themselves. However, only in the privacy tool condition we could identify responses that indicate that the perception of the value of information is increased due to the purpose of the tool. We discuss how the influence of the privacy purpose may be a challenge for providing this type of privacy-enhancing solutions.
適切なサイバーセキュリティ態勢を実現するためには、サイバー衛生(Cyber Hygiene)を実現することが重要な要素である。そのため、各社は様々なセキュリティプログラム、プロセス、ポリシーなどを準備し、セキュリティの運用を実現して行っている。しかし、その一方で、当該プロセスにおいて一つでも誤りやミスがあれば、その一つが単一障害点(Single Point of Failure)となり攻撃者の侵入を許してしまう可能性がある。そのため、セキュリティ態勢を能動的にチェックする手法が必要とあり、本論文ではCyber Hygiene Hunting(実効性確認)と呼ばれる手法を提案する。
Free-XOR in card-based garbled circuits
○Yoshifumi Manabe(Kogakuin University)
This paper shows a free-XOR technique in card-based garbled circuits.
Card-based cryptographic protocols were proposed as a secure multiparty computation using physical cards instead of computers. They can be used when users cannot trust software on computers.
Shinagawa and Nuida proposed card-based garbled circuits that calculate any logical functions using a single shuffle. Their construction uses one garbled table for each logic gate.
This paper introduces a free-XOR technique for standard garbled circuits to card-based garbled circuits.
It is unnecessary to prepare a garbled table for XOR gates. Thus, the number of cards can be reduced.
The card-based garbled circuits proposed by Shinagawa and Nuida have one restriction the output wires cannot be used for inputs to the other gates.
This paper considers eliminating the restriction with two different techniques.