A delegateable signature scheme （DSS） which was first introduced by Barak is mainly based on the non-interactive zero-knowledge proof （NIZK） for preventing the signing verifier from telling which witness （i.e., r...A delegateable signature scheme （DSS） which was first introduced by Barak is mainly based on the non-interactive zero-knowledge proof （NIZK） for preventing the signing verifier from telling which witness （i.e., restricted subset） is being used. However, the scheme is not significantly efficient due to the difficulty of constructing NIZK. We first show that a non-interactive witness indistinguishable （NlWl） proof system and a non-interactive witness hiding （NIWH） proof system are easier and more efficient proof models than NIZK in some cases. Furthermore, the witnesses em- ployed in these two protocols （NlWl and NIWT） cannot also be distinguished by the verifiers. Combined with the E-protocol, we then construct NlWl and NIWH proofs for any NP statement under the existence of one-way functions and show that each proof is different from those under the existence of trapdoor permutations, Finally, based on our NlWl and NIWH proofs, we construct delegateable signature schemes under the existence of one-way functions, which are more efficient than Barak＇s scheme under the existence of trapdoor permutations.展开更多
In this work,we propose a stateless blockchain called CompactChain,which compacts the entire state of the UTXO(Unspent Transaction Output)based blockchain systems into two RSA accumulators.The first accumulator is cal...In this work,we propose a stateless blockchain called CompactChain,which compacts the entire state of the UTXO(Unspent Transaction Output)based blockchain systems into two RSA accumulators.The first accumulator is called Transaction Output(TXO)commitment which represents the TXO set.The second one is called Spent Transaction Output(STXO)commitment which represents the STXO set.In this work,we discuss three algorithms:(i)To update the TXO and STXO commitments by the miner.The miner also provides the proofs for the correctness of the updated commitments;(ii)To prove the transaction’s validity by providing a membership witness in TXO commitment and non-membership witness against STXO commitment for a coin being spent by a user;(iii)To update the witness for the coin that is not yet spent;The experimental results evaluate the performance of the CompactChain in terms of time taken by a miner to update the commitments and time taken by a validator to verify the commitments and validate the transactions.We compare the performance of CompactChain with the existing state-of-the-art works on stateless blockchains.CompactChain shows a reduction in commitments update complexity and transaction witness size which inturn reduces the mempool size and propagation latency without compromising the system throughput(Transactions per second(TPS)).展开更多
The famous zero-knowledge succinct non-interactive arguments of knowledge(zk-SNARK) was proposed by Groth in 2016.Typically, the construction is based on quadratic arithmetic programs which are highly efficient concer...The famous zero-knowledge succinct non-interactive arguments of knowledge(zk-SNARK) was proposed by Groth in 2016.Typically, the construction is based on quadratic arithmetic programs which are highly efficient concerning the proof length and the verification complexity. Since then, there has been much progress in designing zk-SNARKs, achieving stronger security,and simulated extractability, which is analogous to non-malleability and has broad applications. In this study, following Groth's pairing-based zk-SNARK, a simulation extractability zk-SNARK under the random oracle model is constructed. Our construction relies on a newly proposed property named target linearly collision-resistant, which is satisfied by random oracles under discrete logarithm assumptions. Compared to the original Groth16 zk-SNARK, in our construction, both parties are allowed to use such a random oracle, aiming to get the same random number. The resulting proof consists of 3 group elements and only 1 pairing equation needs to be verified. Compared to other related works, our construction is shorter in proof length and simpler in verification while preserving simulation extractability. The results also extend to achieve subversion zero-knowledge SNARKs.展开更多
An identity-based encryption(IBE) was studied with non-interactively opening property that the plain text of a ciphertext can be revealed without affecting the security of the encryption system.Two kinds of non-intera...An identity-based encryption(IBE) was studied with non-interactively opening property that the plain text of a ciphertext can be revealed without affecting the security of the encryption system.Two kinds of non-interactive opening properties for IBE schemes were defined along with a concrete scheme in each case.展开更多
Non-Interactive Zero-Knowledge(NIZK for short) proofs are fascinating and extremely useful in many security protocols. In this paper,a new group signature scheme,decisional linear assumption group signature(DLAGS for ...Non-Interactive Zero-Knowledge(NIZK for short) proofs are fascinating and extremely useful in many security protocols. In this paper,a new group signature scheme,decisional linear assumption group signature(DLAGS for short) with NIZK proofs is proposed which can prove and sign the multiple values rather than individual bits based on DLIN assumption. DLAGS does not need to interact between the verifier and issuer,which can decrease the communication times and storage cost compared with the existing interactive group signature schemes. We prove and sign the blocks of messages instead of limiting the proved message to only one bit(0 or 1) in the conventional non-interactive zero-knowledge proof system,and we also prove that our scheme satisfy the property of anonymity,unlinkability and traceability. Finally,our scheme is compared with the other scheme(Benoitt's scheme) which is also based on the NIZK proofs system and the DLIN assumption,and the results show that our scheme requires fewer members of groups and computational times.展开更多
Verifiable computation （VC） paradigm has got the captivation that in real term is highlighted by the concept of third party computation. In more explicate terms, VC allows resource constrained clients/organizations ...Verifiable computation （VC） paradigm has got the captivation that in real term is highlighted by the concept of third party computation. In more explicate terms, VC allows resource constrained clients/organizations to securely outsource expensive computations to untrusted service providers, while acquiring the publicly or privately verifiable results. Many mainstream solutions have been proposed to address the diverse problems within the VC domain. Some of them imposed assumptions over performed computations, while the others took advantage of interactivity /non-interactivity, zero knowledge proofs, and arguments. Further proposals utilized the powers of probabilistic checkable or computationally sound proofs. In this survey, we present a chronological study and classify the VC proposals based on their adopted domains. First, we provide a broader overview of the theoretical advancements while critically analyzing them. Subsequently, we present a comprehensive view of their utilization in the state of the art VC approaches. Moreover, a brief overview of recent proof based VC systems is also presented that lifted up the VC domain to the verge of practicality. We use the presented study and reviewed resuits to identify the similarities and alterations, modifications, and hybridization of different approaches, while comparing their advantages and reporting their overheads. Finally, we discuss implementation of such VC based systems, their applications, and the likely future directions.展开更多
Based on the analysis of the existing ranking terminology or subject relevancy of documents methods through an intermediary collection as a catalyst(designated as Group B collection) for the purpose of of non-interact...Based on the analysis of the existing ranking terminology or subject relevancy of documents methods through an intermediary collection as a catalyst(designated as Group B collection) for the purpose of of non-interactive literature-based discovery, this article proposes a bi-directional document occurrence frequency based ranking method according to the 'concurrence theory' and the degree and extent of the subject relevancy. This method explores and further refines the ranking method that is based on the occurrence frequency of the usage of certain terminologies and documents and injects a new insightful perspective of the concurrence of appropriate terminologies/documents in the 'low occurrence frequency component' of three non-interactive document collections. A preliminary experiment was conducted to analyze and to test the significance and viability of our newly designed operational method.展开更多
Recently,local differential privacy(LDP)has been used as the de facto standard for data sharing and analyzing with high-level privacy guarantees.Existing LDP-based mechanisms mainly focus on learning statistical infor...Recently,local differential privacy(LDP)has been used as the de facto standard for data sharing and analyzing with high-level privacy guarantees.Existing LDP-based mechanisms mainly focus on learning statistical information about the entire population from sensitive data.For the first time in the literature,we use LDP for distance estimation between distributed data to support more complicated data analysis.Specifically,we propose PrivBV—a locally differentially private bit vector mechanism with a distance-aware property in the anonymized space.We also present an optimization strategy for reducing privacy leakage in the high-dimensional space.The distance-aware property of PrivBV brings new insights into complicated data analysis in distributed environments.As study cases,we show the feasibility of applying PrivBV to privacy-preserving record linkage and non-interactive clustering.Theoretical analysis and experimental results demonstrate the effectiveness of the proposed scheme.展开更多
Commitment scheme is a basic component of many cryptographic protocols, such as coin-tossing, identification schemes, zero-knowledge and multi-party computation. In order to prevent man-in-middle attacks, non-malleabi...Commitment scheme is a basic component of many cryptographic protocols, such as coin-tossing, identification schemes, zero-knowledge and multi-party computation. In order to prevent man-in-middle attacks, non-malleability is taken into account. Many forming works focus on designing non-malleable commitments schemes based on number theory assumptions. In this paper we give a general framework to construct non- interactive and non-malleable commitment scheme with respect to opening based on more general assumptions called q-one way group homomorphisms (q-OWGH). Our scheme is more general since many existing commitment schemes can be deduced from our scheme.展开更多
Extracting the cell objects of red tide algae is the most important step in the construction of an automatic microscopic image recognition system for harmful algal blooms.This paper describes a set of composite method...Extracting the cell objects of red tide algae is the most important step in the construction of an automatic microscopic image recognition system for harmful algal blooms.This paper describes a set of composite methods for the automatic segmentation of cells of red tide algae from microscopic images.Depending on the existence of setae,we classify the common marine red tide algae into non-setae algae species and Chaetoceros,and design segmentation strategies for these two categories according to their morphological characteristics.In view of the varied forms and fuzzy edges of non-setae algae,we propose a new multi-scale detection algorithm for algal cell regions based on border-correlation,and further combine this with morphological operations and an improved GrabCut algorithm to segment single-cell and multicell objects.In this process,similarity detection is introduced to eliminate the pseudo cellular regions.For Chaetoceros,owing to the weak grayscale information of their setae and the low contrast between the setae and background,we propose a cell extraction method based on a gray surface orientation angle model.This method constructs a gray surface vector model,and executes the gray mapping of the orientation angles.The obtained gray values are then reconstructed and linearly stretched.Finally,appropriate morphological processing is conducted to preserve the orientation information and tiny features of the setae.Experimental results demonstrate that the proposed methods can effectively remove noise and accurately extract both categories of algae cell objects possessing a complete shape,regular contour,and clear edge.Compared with other advanced segmentation techniques,our methods are more robust when considering images with different appearances and achieve more satisfactory segmentation effects.展开更多
基金Supported partially by the National Natural Science Foundation of China(Grant Nos.90604034,10371127 and 10671114)
文摘A delegateable signature scheme （DSS） which was first introduced by Barak is mainly based on the non-interactive zero-knowledge proof （NIZK） for preventing the signing verifier from telling which witness （i.e., restricted subset） is being used. However, the scheme is not significantly efficient due to the difficulty of constructing NIZK. We first show that a non-interactive witness indistinguishable （NlWl） proof system and a non-interactive witness hiding （NIWH） proof system are easier and more efficient proof models than NIZK in some cases. Furthermore, the witnesses em- ployed in these two protocols （NlWl and NIWT） cannot also be distinguished by the verifiers. Combined with the E-protocol, we then construct NlWl and NIWH proofs for any NP statement under the existence of one-way functions and show that each proof is different from those under the existence of trapdoor permutations, Finally, based on our NlWl and NIWH proofs, we construct delegateable signature schemes under the existence of one-way functions, which are more efficient than Barak＇s scheme under the existence of trapdoor permutations.
文摘In this work,we propose a stateless blockchain called CompactChain,which compacts the entire state of the UTXO(Unspent Transaction Output)based blockchain systems into two RSA accumulators.The first accumulator is called Transaction Output(TXO)commitment which represents the TXO set.The second one is called Spent Transaction Output(STXO)commitment which represents the STXO set.In this work,we discuss three algorithms:(i)To update the TXO and STXO commitments by the miner.The miner also provides the proofs for the correctness of the updated commitments;(ii)To prove the transaction’s validity by providing a membership witness in TXO commitment and non-membership witness against STXO commitment for a coin being spent by a user;(iii)To update the witness for the coin that is not yet spent;The experimental results evaluate the performance of the CompactChain in terms of time taken by a miner to update the commitments and time taken by a validator to verify the commitments and validate the transactions.We compare the performance of CompactChain with the existing state-of-the-art works on stateless blockchains.CompactChain shows a reduction in commitments update complexity and transaction witness size which inturn reduces the mempool size and propagation latency without compromising the system throughput(Transactions per second(TPS)).
基金supported by the National Key R&D Program of China(Grant No.2019YFB2101703)the National Natural Science Foundation of China(Grant Nos.62272107 and U19A2066)+1 种基金the Innovation Action Plan of Shanghai Science and Technology(Grant No.21511102200)the Key R&D Program of Guangdong Province(Grant No.2020B0101090001)。
文摘The famous zero-knowledge succinct non-interactive arguments of knowledge(zk-SNARK) was proposed by Groth in 2016.Typically, the construction is based on quadratic arithmetic programs which are highly efficient concerning the proof length and the verification complexity. Since then, there has been much progress in designing zk-SNARKs, achieving stronger security,and simulated extractability, which is analogous to non-malleability and has broad applications. In this study, following Groth's pairing-based zk-SNARK, a simulation extractability zk-SNARK under the random oracle model is constructed. Our construction relies on a newly proposed property named target linearly collision-resistant, which is satisfied by random oracles under discrete logarithm assumptions. Compared to the original Groth16 zk-SNARK, in our construction, both parties are allowed to use such a random oracle, aiming to get the same random number. The resulting proof consists of 3 group elements and only 1 pairing equation needs to be verified. Compared to other related works, our construction is shorter in proof length and simpler in verification while preserving simulation extractability. The results also extend to achieve subversion zero-knowledge SNARKs.
文摘An identity-based encryption(IBE) was studied with non-interactively opening property that the plain text of a ciphertext can be revealed without affecting the security of the encryption system.Two kinds of non-interactive opening properties for IBE schemes were defined along with a concrete scheme in each case.
基金supported by the National High-Tech Research and Development Plan of China under Grant Nos.863-317-01- 04-99, 2009AA01Z122 (863)the Natural Science Foundation of Shenyang City of China under Grant No. F10-205-1-12
文摘Non-Interactive Zero-Knowledge(NIZK for short) proofs are fascinating and extremely useful in many security protocols. In this paper,a new group signature scheme,decisional linear assumption group signature(DLAGS for short) with NIZK proofs is proposed which can prove and sign the multiple values rather than individual bits based on DLIN assumption. DLAGS does not need to interact between the verifier and issuer,which can decrease the communication times and storage cost compared with the existing interactive group signature schemes. We prove and sign the blocks of messages instead of limiting the proved message to only one bit(0 or 1) in the conventional non-interactive zero-knowledge proof system,and we also prove that our scheme satisfy the property of anonymity,unlinkability and traceability. Finally,our scheme is compared with the other scheme(Benoitt's scheme) which is also based on the NIZK proofs system and the DLIN assumption,and the results show that our scheme requires fewer members of groups and computational times.
文摘Verifiable computation （VC） paradigm has got the captivation that in real term is highlighted by the concept of third party computation. In more explicate terms, VC allows resource constrained clients/organizations to securely outsource expensive computations to untrusted service providers, while acquiring the publicly or privately verifiable results. Many mainstream solutions have been proposed to address the diverse problems within the VC domain. Some of them imposed assumptions over performed computations, while the others took advantage of interactivity /non-interactivity, zero knowledge proofs, and arguments. Further proposals utilized the powers of probabilistic checkable or computationally sound proofs. In this survey, we present a chronological study and classify the VC proposals based on their adopted domains. First, we provide a broader overview of the theoretical advancements while critically analyzing them. Subsequently, we present a comprehensive view of their utilization in the state of the art VC approaches. Moreover, a brief overview of recent proof based VC systems is also presented that lifted up the VC domain to the verge of practicality. We use the presented study and reviewed resuits to identify the similarities and alterations, modifications, and hybridization of different approaches, while comparing their advantages and reporting their overheads. Finally, we discuss implementation of such VC based systems, their applications, and the likely future directions.
基金supported by Humanities and Social Science Foundation of Ministry of Education of China(Grant No.07JA870005)
文摘Based on the analysis of the existing ranking terminology or subject relevancy of documents methods through an intermediary collection as a catalyst(designated as Group B collection) for the purpose of of non-interactive literature-based discovery, this article proposes a bi-directional document occurrence frequency based ranking method according to the 'concurrence theory' and the degree and extent of the subject relevancy. This method explores and further refines the ranking method that is based on the occurrence frequency of the usage of certain terminologies and documents and injects a new insightful perspective of the concurrence of appropriate terminologies/documents in the 'low occurrence frequency component' of three non-interactive document collections. A preliminary experiment was conducted to analyze and to test the significance and viability of our newly designed operational method.
基金supported by National Key Research and Development Program of China(Nos.2019QY1402 and 2016YFB0800901)。
文摘Recently,local differential privacy(LDP)has been used as the de facto standard for data sharing and analyzing with high-level privacy guarantees.Existing LDP-based mechanisms mainly focus on learning statistical information about the entire population from sensitive data.For the first time in the literature,we use LDP for distance estimation between distributed data to support more complicated data analysis.Specifically,we propose PrivBV—a locally differentially private bit vector mechanism with a distance-aware property in the anonymized space.We also present an optimization strategy for reducing privacy leakage in the high-dimensional space.The distance-aware property of PrivBV brings new insights into complicated data analysis in distributed environments.As study cases,we show the feasibility of applying PrivBV to privacy-preserving record linkage and non-interactive clustering.Theoretical analysis and experimental results demonstrate the effectiveness of the proposed scheme.
基金the National Natural Science Foundations of China (Nos. 60673079 and 60572155)
文摘Commitment scheme is a basic component of many cryptographic protocols, such as coin-tossing, identification schemes, zero-knowledge and multi-party computation. In order to prevent man-in-middle attacks, non-malleability is taken into account. Many forming works focus on designing non-malleable commitments schemes based on number theory assumptions. In this paper we give a general framework to construct non- interactive and non-malleable commitment scheme with respect to opening based on more general assumptions called q-one way group homomorphisms (q-OWGH). Our scheme is more general since many existing commitment schemes can be deduced from our scheme.
基金Supported by the National Natural Science Foundation of China(Nos.61301240,61271406)
文摘Extracting the cell objects of red tide algae is the most important step in the construction of an automatic microscopic image recognition system for harmful algal blooms.This paper describes a set of composite methods for the automatic segmentation of cells of red tide algae from microscopic images.Depending on the existence of setae,we classify the common marine red tide algae into non-setae algae species and Chaetoceros,and design segmentation strategies for these two categories according to their morphological characteristics.In view of the varied forms and fuzzy edges of non-setae algae,we propose a new multi-scale detection algorithm for algal cell regions based on border-correlation,and further combine this with morphological operations and an improved GrabCut algorithm to segment single-cell and multicell objects.In this process,similarity detection is introduced to eliminate the pseudo cellular regions.For Chaetoceros,owing to the weak grayscale information of their setae and the low contrast between the setae and background,we propose a cell extraction method based on a gray surface orientation angle model.This method constructs a gray surface vector model,and executes the gray mapping of the orientation angles.The obtained gray values are then reconstructed and linearly stretched.Finally,appropriate morphological processing is conducted to preserve the orientation information and tiny features of the setae.Experimental results demonstrate that the proposed methods can effectively remove noise and accurately extract both categories of algae cell objects possessing a complete shape,regular contour,and clear edge.Compared with other advanced segmentation techniques,our methods are more robust when considering images with different appearances and achieve more satisfactory segmentation effects.
